Adaptive Consistency Graph for Long-Horizon Agents

AI summary

Overview

Research area: AI agents and long-horizon planning — specifically memory organization and context construction for large language model (LLM) agents that execute long sequences of tool calls.

Technical level: Intermediate. The paper assumes familiarity with ReAct-style agents, retrieval-augmented generation, and agent memory systems, though the core idea is explained clearly enough for a motivated newcomer.

Scope in one sentence: The paper introduces the Adaptive Consistency Graph (ACG), a persistent, source-grounded execution memory that builds a temporary, requirement-centered context view for each decision under a token budget, and evaluates it on three benchmarks with two models against five baselines.

What This Paper Is About

LLM agents often make reasonable local decisions on short tasks, but their performance degrades when success requires long chains of dependent actions and tool calls. The authors argue that during execution, task requirements, historical evidence, and the current state gradually become disconnected, so later decisions drift from the original objective. ACG addresses this by organizing accumulated execution evidence into a persistent graph with provenance links, then assembling a fresh, bounded context view for each decision — without replacing the base agent's planner or tool executor.

Key Contributions

1. Persistent execution memory. ACG links evidence units to the source events that produced them and to related records, so details stay available for later retrieval rather than being replaced by a generated summary.

2. Adaptive decision views. Task-seeded and event-seeded retrieval selects evidence into requirement-qualified views under a token budget, without overwriting or destroying the underlying persistent memory.

3. Empirical evaluation. Across three benchmarks (DeepPlanning, BrowseComp-Plus, SWE-bench Lite) and two models (GPT-5.6-luna, DeepSeek-v4-flash), the paper compares success, execution behavior, and inference cost against five baselines (ReAct, COMPASS, TDP*, CUGA, ACON).

4. Execution and cost diagnostics. Beyond success rates, the paper reports trajectory structure, observed execution length, model-call counts, token expenditure, and six overlapping execution/delivery categories (interface rejection, operation-precondition rejection, budget exhaustion, repeated execution, missing deliverables, and delivered artifacts that fail evaluation).

Main Findings

• Average success gain on GPT-5.6-luna. ACG raises GPT-5.6-luna's equal-weight three-benchmark average from 44.5% with ReAct to 50.2%. The largest single gain is on BrowseComp-Plus: 73.5% versus 62.4%.

• Full benchmark table (GPT-5.6-luna). ACG scores 12.4% ± 1.75 on DeepPlanning, 73.5% ± 1.87 on BrowseComp-Plus, and 64.7% ± 2.76 on SWE-bench Lite. Comparable baselines: ReAct (10.8%, 62.4%, 60.3%; average 44.5%), COMPASS (6.4%, 48.1%, 12.7%; average 22.4%), TDP* (6.9%, 10.5%, 22.3%; average 13.3%), CUGA (0.0%, 10.96%, 3.67%; average 4.88%), ACON (7.8%, 10.2%, 50.0%; average 22.7%).

• Full benchmark table (DeepSeek-v4-flash). ACG scores 11.7% ± 1.70 on DeepPlanning, 62.7% ± 1.64 on BrowseComp-Plus, and 63.3% ± 2.76 on SWE-bench Lite, for an equal-weight average of 45.9%. ReAct scores 6.4%, 68.2% (highest in that column), and 56.7%, averaging 43.8%. COMPASS averages 7.74%, TDP* 10.5%, CUGA 4.07%, and ACON 27.6%.

• Ranking is not uniform. ACG ranks first in five of the six model–benchmark settings and second in the remaining one (DeepSeek on BrowseComp-Plus, where ReAct leads at 68.2%). ReAct is the strongest baseline in five settings; on DeepSeek DeepPlanning, COMPASS is the best baseline. The authors frame the result as a conditional claim: organizing execution evidence helps on some long-horizon task mixtures, but the effect is not uniform across models or benchmarks.

• Constrained planning stays hard. ACG's 12.4% and 11.7% DeepPlanning success rates show that constrained shopping and travel planning remains difficult despite ACG leading the compared methods there.

• Structural task difficulty (SWE-bench Lite). For DeepSeek, ACG succeeds on 71.6% of one-hunk tasks and 48.6% of three-hunk tasks, versus ReAct's 65.3% and 37.8%. The advantage extends beyond single-location repairs, though the smaller three-hunk group has wider uncertainty, so the point estimates do not establish a statistically significant interaction with patch size. Luna COMPASS stays near 12–14% across all three SWE groups.

• Longer executions contain many failures. For DeepSeek ReAct on BrowseComp-Plus, 279 of 287 tasks ending within 1–20 actions succeed (97.2%), compared with 24 of 170 ending within 61–100 actions (14.1%). On SWE-bench Lite the figures are 39/46 (84.8%) and 34/98 (34.7%). ACG shows the same pattern: on DeepSeek BrowseComp-Plus it falls from 88.7% (1–20 actions) to 6.9% (61–100 actions), but on SWE-bench Lite it retains 50.0% in the 61–100 action group versus ReAct's 34.7%.

• More model calls do not buy success. On SWE-bench Lite with GPT-5.6-luna, median call counts are 15 (ReAct), 60 (COMPASS), 86 (TDP*), and 30.5 (CUGA), with success rates of 60.3%, 12.7%, 22.3%, and 3.7%. TDP* uses roughly 5.7 times ReAct's median calls and roughly 8.4 times its median total tokens (1.075 million versus 0.128 million) without higher success.

• ACG's call cost varies by setting. On SWE-bench Lite, Luna ACG uses a median of 29 calls versus 15 for ReAct while success rises from 60.3% to 64.7%. With DeepSeek, medians are 47 and 44 calls with success of 63.3% and 56.7%. On BrowseComp-Plus, DeepSeek ACG uses fewer median calls (21 vs 30) but has lower success (62.7% vs 68.2%). ACG therefore does not offer a uniform reduction in inference effort.

• Repetition and delivery diagnostics. On SWE-bench Lite with DeepSeek, repeated execution occurs in 8.2% of assessable ACG failures, versus 27.9% (COMPASS), 96.4% (TDP*), 64.9% (CUGA), and 24.8% (ACON); ReAct is lower at 6.2%. With Luna, ACG and ReAct both show 0.0% repetition, against 4.6%, 84.2%, 12.8%, and 12.1% for the four baselines. Missing deliverables account for 0.9% of assessable DeepSeek ACG failures on SWE-bench Lite, versus 26.2% (ReAct), 94.1% (COMPASS), 78.4% (TDP*), 71.3% (CUGA), and 76.2% (ACON). Both ACG and ReAct resume accepted execution after 100.0% of assessed rejection episodes in the failed-task group, yet those tasks ultimately fail — showing that avoiding stalls is not the same as producing a correct solution.

• Stated limits on causal claims. The authors explicitly note that baseline analyses motivate the evaluation of ACG but do not identify inconsistent state as the cause of failure, and that the diagnostics do not isolate the individual contributions of graph retrieval, provenance qualification, or rendering.

Methodology in Plain English

ACG keeps two things separate: a permanent archive (the execution graph) and a temporary view (the context handed to the agent at each step).

Storage. Every observation or explicit state record is broken into memory units. Each unit holds its content, type, source references, the events in which it was observed, and structured fields such as object identifiers. Repeated content shares one unit but keeps every occurrence separately, along with the originating event and tool call. The graph connects units that are mutual nearest neighbors in embedding space, and adds extra weight between units that share an original source (weighted as 1/(n−1) for a source with n units). A structural-entropy organizer groups this weighted graph into local clusters.

Retrieval per decision. Two ranked lists are built — one from the original task instruction and one from the latest interaction. The two lists are interleaved round-robin to pick unique seeds, up to a limit K. Candidates are then gathered by expanding the graph to depth d and adding local clusters. In the reported configuration, ACG uses eight unique retrieval seeds with a fixed one-hop expansion.

Requirement grounding. Requirements are represented as exact instruction spans. Attribution is tracked at the level of individual action or tool-call occurrences via structured origin declarations whose identifiers must resolve to existing requirements. Observations can inherit anchors through an unambiguous parent action. Missing or ambiguous attribution stays unassigned rather than being filled in by semantic similarity — so a qualification validates provenance, not truth or task completion. Qualified candidates are ranked by embedding similarity to the requirement text; up to eight historical units are kept per requirement, and qualified evidence from the current event is retained as well. Ties break by latest associated event, then memory identifier. These incidences are a temporary projection and are never written back to the persistent graph.

Rendering under budget. The renderer admits ordered blocks (membership, current-event, evidence, cross-reference) only when the complete rendered view still fits the remaining budget. The memory view has a 5,000-token cap, further reduced when less space is available. Under tighter budgets, ACG shortens requirement–evidence associations and prioritizes current-event evidence; evidence shared by multiple requirements is expanded once and referenced elsewhere. Omitted records stay in persistent memory for later.

Evaluation setup. Three benchmarks with fixed task sets: DeepPlanning (360 tasks), BrowseComp-Plus (830 tasks), and SWE-bench Lite (300 tasks), using each benchmark's native success criterion. Two models, GPT-5.6-luna and DeepSeek-v4-flash, with a nominal budget of 100 external actions per task and an executor output limit of 4,096 tokens per call. Five baselines: ReAct, COMPASS, TDP*, CUGA, and ACON. Uncertainty is reported as standard deviations from 5,000 task-bootstrap resamples with fixed seeds derived from the combination identity and seed 20260923; these measure task-sampling variation only.

Why This Matters

Impact on research. Most agent-memory work emphasizes persistence, reflection, or reusable abstractions; long-context work emphasizes capacity. ACG targets a narrower question: during ongoing execution, how should information from different events and requirements be brought together to build the context for the next decision? The paper's framing — a permanent, source-addressable archive plus a throwaway, budgeted view — is a testable alternative to replacing history with generated summaries, and its honest reporting of uneven gains provides a calibrated baseline for follow-up work.

Real-world applications (as represented by the evaluated domains):

• Constrained planning assistants — shopping and travel planning under hard constraints, the setting of DeepPlanning.
• Research and evidence retrieval over a fixed corpus — the setting of BrowseComp-Plus, where provenance and source links matter.
• Automated repository-level code repair — the setting of SWE-bench Lite, where fixes touch multiple hunks.
• Enterprise agent platforms — deployments where long tool-use trajectories must stay traceable and cost-bounded; the third author's affiliation is QI-ANXIN GROUP.

Industry relevance. Two of the paper's practical messages carry directly into production agent systems: more model calls and more tokens do not reliably buy higher task success (TDP* used roughly 5.7x the median calls and roughly 8.4x the median tokens of ReAct on SWE-bench Lite for far lower success), and cost savings are not automatic (ACG's call counts rise on some settings and fall on others). Additionally, the graph is inspected and rendered, not trained, and it does not replace the planner or tool executor — it can be layered onto an existing agent stack.

Future Directions

• Ablate the components. The authors state that the diagnostics locate behavioral differences "without isolating the contribution of graph retrieval, provenance qualification, or rendering individually." Separating these mechanisms is the clearest open experiment.
• Improve constrained planning. DeepPlanning remains the weakest benchmark for every method, including ACG (12.4% and 11.7%). Understanding why requirement-centered views do not help there is unresolved.
• Test whether context structure generalizes beyond the evaluated settings. Results are reported for two models and three fixed task sets, with ACG ranking first in five of six model–benchmark cells and second in one. Additional models, task mixtures, and repeated runs are not reported.
• Reconcile the execution-length finding. The paper shows that longer observed executions contain substantial unsuccessful effort, and notes that observed length reflects both difficulty and agent behavior — it states these associations do not establish that changing the action limit would improve success. Whether budget policy and context design should be tuned jointly is left open.

Target Audience

This paper is most useful to agent researchers and engineers building or evaluating long-horizon LLM systems — particularly those working on agent memory, context management, and tool-use cost. It also suits benchmark and evaluation researchers interested in execution-trace diagnostics (repetition, budget exhaustion, missing deliverables, resumption behavior) rather than success rates alone. Readers need comfort with terms like retrieval, provenance, token budget, and bootstrap resampling, but no specialized mathematics: the structural-entropy organizer is presented as an adopted criterion, not a learned objective.

Authors’ abstract

Large language model agents can often make reasonable local decisions on short tasks, yet their performance degrades when success requires long sequences of dependent actions and tool calls. During execution, task requirements, historical evidence, and the current execution state may gradually become disconnected, so later decisions can drift from the original objective. We study this problem by introducing the Adaptive Consistency Graph (ACG) for long-horizon execution. ACG incrementally organizes execution evidence and its provenance in a persistent graph, then constructs a temporary requirement-centered view for each decision under a bounded context budget. Rather than replacing the base agent's planner or tool executor, ACG provides a structured and traceable context view for each decision. In the matched evaluation, ACG improves GPT-5.6-luna's average success from 44.5\% with ReAct to 50.2\%, with the largest gain on BrowseComp-Plus (73.5\% versus 62.4\%). We further analyze trajectory structure and inference cost to characterize this improvement.