Skip to content

Adaptive Consistency Graph for Long-Horizon Agents

Sep 2026 · arXiv.org · Vol abs/2609.32754 · 0 citations · 30 references
Computer Science

TL;DR

The Adaptive Consistency Graph (ACG) is introduced, which 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.

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. Our code is available at https://github.com/yunsaijc/Adaptive-Consistency-Graph.

View source

Similar papers

Staying on Task: Testing the Foundations of Long-Horizon Agent Reliability

Long-horizon agentic workflows require models to sustain repeated state-dependent actions all while the context grows, sub-task complexity changes, and new data arrives. Each situation represents an independent axis along which an agent may fail. An agent reconciling a long ledger, for example, must repeatedly read its...

Jeffrey Willette, Krishna C. Puvvada, Boris Ginsburg · 0 citations

Learning from Failures: Heterogeneous Graph Memory for Small Language Model Tool-Using Agents

This paper proposes FRESH, a Failure-aware Retrieval framework over Experience-Structured Heterogeneous graphs, which transforms historical successes and failures into structured external experience for tool-using agents and consistently improves task success and tool-use reliability over no-memory agents and represent...

Jia-Xing Li, Lei Song, Rui Dong et al. · 0 citations
#artificial intelligence Preprint Oct 2026

Revision-Aware Independent Agent Graphs for Dynamic Reasoning

Conventional reasoning protocols present a fixed, preselected task, so they cannot test whether an agent propagates relevant updates, preserves unaffected work, or reconstructs a historical task binding. We therefore study \emph{dynamic task routing}, in which an event stream revises task bindings and a system must sel...

Yang-Hao Luo, Selim-Antoine Lali, Jeremy Moebel et al. · 0 citations
#artificial intelligence Preprint Sep 2026

DAGent: Evaluate-then-Grow Planning for Deep Research Agents

Deep research tasks require agents to navigate large knowledge spaces, synthesize evidence across many sources, and adapt their plans as findings emerge. Directed acyclic graph (DAG)-based multi-agent systems suit this setting because they support parallel execution and isolate each sub-task within a focused dependency...

Han-Wen Liu, Yuan-Fu Sun, Qiao-Yu Tan · 0 citations

Continuous Context Management

Results demonstrate that CCM is a viable inference paradigm for agents operating with substantially reduced retained context and that its performance can be improved through reinforcement learning with privileged full-history distillation.

William Hoy, Jing-Xuan Fan, Nurcin Celik et al. · 1 citation · ⚡1
#artificial intelligence Preprint Sep 2026

LazyAgent: Demand-Driven Materialization and Physical Optimization of Agentic Programs

LazyAgent is presented, a unified execution framework for agent-authored programs organized around a live, goal-derived demanded set that consistently outperforms the strongest goal-stopping eager baseline by refusing unrelated work before it starts and motivates benchmarks built from standing programs and sequences.

Xin Heng · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.