Adaptive Consistency Graph for Long-Horizon Agents

1 INTRODUCTION

• Useful execution context must connect historical evidence to the current decision, retain enough surrounding information to interpret it, and fit the available context budget.An observation may be insufficient when its meaning depends on the event that produced it or on related observations elsewhere in the trajectory.Source: §1 · p. 2
• ACG stores source-linked evidence and event relations, then builds a temporary requirement-centered view under the remaining context budget for each decision.The underlying memory remains available for later decisions; ACG does not replace the base planner or tool executor.Source: §1 · p. 2
• The empirical analyses do not establish inconsistent state as the cause of failure or attribute improvements in success and cost to an individual memory mechanism.The study covers constrained planning, corpus-based information retrieval, and repository-level code repair.Source: §1 · p. 2
• The study compares success, execution behavior, and inference cost across three benchmarks and two models against five baselines.Its contributions include persistent execution memory and adaptive decision views that select requirement-qualified evidence under a token budget.Source: §1 · p. 2

2.1 LONG-HORIZON PLANNING AND INTERACTIVE AGENTS

• Interactive planning methods improve action selection, feedback use, or search, while ACG addresses the complementary challenge of keeping requirements, prior evidence, and the latest state connected during execution.ACG leaves the base planner and action interface unchanged.Source: §2.1 · p. 2

2.2 MEMORY AND CONTEXT MANAGEMENT FOR LONG-HORIZON AGENTS

• Memory systems emphasize persistence, reflection, or reusable abstractions; ACG instead preserves event-level evidence and provenance in the execution record while creating a temporary decision view.The overview distinguishes the persistent source-grounded graph from the budgeted requirement-centered view shown to the agent at each decision.Source: §2.2 · p. 3, Figure 1 · p. 3
• More history does not ensure reliable use of relevant information, motivating bounded views that leave omitted evidence available in a source-addressable execution record.Lost in the Middle reports that information use can depend on its position within a long context.Source: §2.2 · p. 3

2.3 RELATIONAL RETRIEVAL AND GRAPH MEMORY

• Unlike graph memories for static knowledge collections, ACG represents evolving task execution, linking nodes to their source events and tool outputs without certifying truth or requirement satisfaction.Retrieval is conditioned on current requirements and state.Source: §2.3 · p. 3

3.1 PROBLEM FORMULATION

• At each step, the base policy selects an action using the task, recent history, and temporary view; after execution, the observation and action origin enter persistent memory for later retrieval.The base policy retains control of planning and tool use.Source: §3.1 · p. 4

3.2 SOURCE-GROUNDED EXECUTION MEMORY

• Memory units retain source references and observed occurrences, so reusing a content unit does not merge the distinct execution events that produced it.Source links do not certify truth or task completion, and temporal order alone does not make an observation false or obsolete.Source: §3.2 · p. 4

3.3 RELATIONAL ORGANIZATION AND CONTEXTUAL RETRIEVAL

• Task- and event-ranked lists are interleaved into unique seeds, then expanded through graph neighbors and local clusters; semantic and source links aid navigation without creating requirement attribution.Graph depth is fixed; adaptation concerns selected evidence and its level of detail at each decision.Source: §3.3 · p. 4

3.4 REQUIREMENT-GROUNDED DECISION VIEWS

• Requirement views use validated origin links to qualify candidates, rank up to eight historical units by requirement similarity, and retain qualified current-event units separately.Missing or ambiguous attribution remains unassigned rather than being supplied by semantic similarity.Source: §3.4 · pp. 4–5

3.5 BUDGET-AWARE CONTEXT CONSTRUCTION

• The renderer admits complete blocks only when the view stays within budget; tighter budgets prioritize current-event evidence and shorten associations, while omitted records remain in persistent memory.Evidence shared across requirements is expanded once and referenced elsewhere to reduce duplication.Source: §3.5 · p. 5

4.1 EXPERIMENTAL SETUP

• The fixed task sets contain 360 DeepPlanning tasks, 830 BrowseComp-Plus tasks, and 300 SWE-bench Lite tasks, evaluated with GPT-5.6-luna and DeepSeek-v4-flash under a nominal 100-action budget.LLM calls are counted separately from recorded external actions, and inference expenditure includes auxiliary calls and input plus output tokens.Source: §4.1 · p. 5

4.2 MAIN RESULTS

• 50.2% for GPT-5.6-luna ACG and 45.9% for DeepSeek-v4-flash ACG are the highest equal-weight average success rates across the three benchmarks.ACG ranks first in five of six model–benchmark settings and second in the remaining one; DeepPlanning remains difficult, with ACG success of 12.4% for Luna and 11.7% for DeepSeek.Source: §4.2 · p. 6, Table 1 · p. 6

4.3 TASK STRUCTURE AND BASELINE PERFORMANCE

• On SWE-bench Lite, ACG exceeds ReAct in all three displayed structural groups for both models, while DeepPlanning’s pooled profile reflects changing shopping and travel task composition.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 smaller three-hunk group has wider uncertainty. Equal DeepPlanning counts do not imply equal difficulty across shopping and travel.Source: §4.3 · pp. 6–7, Figure 2 · p. 7

4.4 EXECUTION LENGTH AND TASK OUTCOMES

• On DeepSeek BrowseComp-Plus, ReAct succeeds on 97.2% of tasks ending within 1–20 actions but 14.1% of those ending within 61–100 actions, so realized length must be read alongside outcome.These are conditional comparisons across different trajectory groups; observed length reflects both task difficulty and agent behavior and does not establish that changing the action limit improves success.Source: §4.4 · p. 7, Figure 3 · p. 8

4.5 MODEL-CALL OVERHEAD AND CONTEXT COST

• On Luna SWE-bench Lite, TDP* has a median of 86 calls versus ReAct’s 15, but success is 22.3% versus 60.3%; median token use is approximately 8.4 times as large.ACG’s call costs also vary by setting: Luna ACG uses 29 median calls versus ReAct’s 15 on SWE-bench Lite, while DeepSeek ACG uses 21 versus 30 on BrowseComp-Plus and has lower success there.Source: §4.5 · p. 8

4.6 EXECUTION AND DELIVERY DIAGNOSTICS

• On DeepSeek SWE-bench Lite failures, repeated execution occurs in 8.2% of assessable ACG failures versus 6.2% for ReAct, while missing deliverables account for 0.9% versus 26.2%.ACG and ReAct both resume accepted execution after 100.0% of assessed rejection episodes in this failed-task group, yet the tasks still fail; delivery progress is distinct from correctness, and the diagnostics do not isolate individual memory mechanisms.Source: §4.6 · pp. 8–9

5 CONCLUSION

• In matched comparisons, ACG improves success on selected benchmark–model pairs, but its performance pattern is uneven elsewhere.The conclusion frames structured access to execution history as a testable approach to studying task-success and inference-cost trade-offs.Source: §5 · p. 9
• The authors report that AI tools assisted code development, figure preparation, and language polishing, and that all assisted outputs were reviewed and verified.Source: AI USE STATEMENT · p. 10
• The paper directs readers to Section 4.1 and Appendices B–C for benchmark and comparison details, accounting, uncertainty, context selection, and execution diagnostics.Source: REPRODUCIBILITY STATEMENT · p. 10

A ALGORITHMIC DETAILS

• The online loop separates persistent evidence storage, temporary context construction, and base-agent execution.The base agent retains control of planning and tool use; the temporary view selects what it sees at a decision.Source: A ALGORITHMIC DETAILS · p. 13
• Ingest preserves event identity, source references, and available requirement origins, but does not infer missing attribution from semantic similarity.The renderer may shorten or omit records to meet the context budget while leaving omitted records in the persistent graph.Source: A ALGORITHMIC DETAILS · p. 13

B.1 ACG CONTEXT SELECTION

• ACG uses eight unique retrieval seeds and a fixed one-hop graph expansion to select context.Source: §B.1 · p. 13
• For each requirement, ranking retains up to eight historical candidates and also retains qualified evidence from the current event as a candidate.Source: §B.1 · p. 13
• The memory view has a 5,000-token cap, reduced when less context space is available, and rendering may omit or shorten retained candidates.Candidate retention does not guarantee full textual expansion.Source: §B.1 · p. 13

B.2 STRUCTURAL ORGANIZER

• Mutual-nearest-neighbor pairs receive unit semantic weight, while pairs sharing a source receive source-affinity weight 1/(n −1); the two weights are added.Identical source-member groups are counted once.Source: §B.2 · p. 13
• The organizer uses two-level structural entropy over graph-node partitions, with weighted degree, group volume, and crossing-edge weight defined in the accompanying account.Source: §B.2 · pp. 13–14
• The entropy criterion supplies local clusters for retrieval expansion; it is neither a learned ACG objective nor a guarantee of task success, action choice, or evidence validity.Source: §B.2 · p. 14

B.3 TASK ACCOUNTING AND UNCERTAINTY

• Comparisons use the same 360 DeepPlanning, 830 BrowseComp-Plus, and 300 SWE-bench Lite task identifiers within each model setting.Source: §B.3 · p. 14
• Step-based analyses count recorded external actions under a nominal 100-action budget, while LLM calls are separate and include auxiliary work.Total tokens are input plus output; cached input is already a subset of input.Source: §B.3 · p. 14
• Figure 3 success-rate curves use weighted Gaussian smoothing over five-action bins, with bandwidth seven actions and minimum segment requirements.Segments require three consecutive nonempty bins and at least 30 tasks; intervals are pointwise and uncorrected for smoothing bias.Source: §B.3 · p. 14
• Task-bootstrap standard deviations estimate task-sampling variation conditional on observed executions, not variation across repeated executions.All-failure resamples have zero standard deviation, which does not establish zero success probability on other tasks or executions.Source: §B.3 · p. 14

• Six overlapping categories describe execution obstacles and delivery outcomes, but do not form an exhaustive or causal taxonomy of task failure.Source: C OBSERVABLE EXECUTION AND DELIVERY… · p. 14
• Interface and precondition rejections require explicit tool responses; budget exhaustion requires a terminal budget reason, while repetition uses consecutive identical calls or repeated short patterns.Source: C OBSERVABLE EXECUTION AND DELIVERY… · p. 14
• Deliverable presence is task-specific and does not establish correctness; delivered-but-failed requires a present artifact and an official evaluation failure.Source: C OBSERVABLE EXECUTION AND DELIVERY… · p. 14
• Continuation after rejection is measured per episode, including resumption status and median attempt delay; accepted resumption does not imply repaired state or eventual success.Source: C OBSERVABLE EXECUTION AND DELIVERY… · p. 15, Table 3 · p. 16
• Table 2 reports category-specific assessable-task rates within outcome groups, so its overlapping percentages are not additive.Source: Table 2 · p. 15

• Provenance records evidence origins but does not establish that an observation is correct or that a task requirement is satisfied.Source: D LIMITATIONS · p. 18
• Missing or ambiguous action origins and finite context budgets can reduce requirement-specific coverage by excluding relevant evidence.Source: D LIMITATIONS · p. 18
• Graph construction and retrieval add computation, and generalization beyond the evaluated models, tools, and task sets remains unestablished.Source: D LIMITATIONS · p. 18