Adaptive Consistency Graph for Long-Horizon Agents

Jiecong Wang; Hao Peng; Zhanyi Wang

cs.AISep 26, 2026

Adaptive Consistency Graph for Long-Horizon Agents

Authors: Jiecong Wang, Hao Peng, Zhanyi Wang

Organizations: Beihang University · QI-ANXIN GROUP

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.

Figures & tables

Figure 1: Overview of Adaptive Consistency Graph. ACG retains a source-grounded execution graph and produces a budgeted, requirement-centered view for the base agent at each decision. The view is temporary; the underlying event record remains available for subsequent steps.

Model	Method	Dataset			Avg.
Model	Method	DeepPlanning	BrowseComp-Plus	SWE-bench Lite	Avg.
GPT-5.6- luna	ReAct	$10.8\,\mathbin{\pm}_{\scriptscriptstyle 1.64}$	$62.4\,\mathbin{\pm}_{\scriptscriptstyle 1.71}$	$60.3\,\mathbin{\pm}_{\scriptscriptstyle 2.84}$	44.5
	COMPASS	$6.4\,\mathbin{\pm}_{\scriptscriptstyle 1.28}$	$48.1\,\mathbin{\pm}_{\scriptscriptstyle 1.72}$	$12.7\,\mathbin{\pm}_{\scriptscriptstyle 1.93}$	22.4
	TDP*	$6.9\,\mathbin{\pm}_{\scriptscriptstyle 1.36}$	$10.5\,\mathbin{\pm}_{\scriptscriptstyle 1.05}$	$22.3\,\mathbin{\pm}_{\scriptscriptstyle 2.39}$	13.3
	CUGA	$0.0\,\mathbin{\pm}_{\scriptscriptstyle 0.00}$	$10.96\,\mathbin{\pm}_{\scriptscriptstyle 1.08}$	$3.67\,\mathbin{\pm}_{\scriptscriptstyle 1.08}$	4.88
	ACON	$7.8\,\mathbin{\pm}_{\scriptscriptstyle 1.42}$	$10.2\,\mathbin{\pm}_{\scriptscriptstyle 1.04}$	$50.0\,\mathbin{\pm}_{\scriptscriptstyle 2.89}$	22.7

Table 1: Task success rates (%). All methods use the same task set within each benchmark. Avg. is the equal-weight arithmetic mean of the three benchmark rates; it is not pooled over tasks. Subscripts after

\pm

in the benchmark columns are bootstrap standard deviations.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$x$	task instruction
$a_{t}$ , $o_{t}$	action and resulting observation at step $t$
$h_{t}^{\mathrm{recent}}$	recent action–observation history
$G_{t}$	persistent source-grounded execution memory
$m$	memory unit; $\mathcal{O}_{t}(m)$ stores its occurrences
$L_{t}^{x}$ , $L_{t}^{e}$	task-seeded and event-seeded ranked lists

Appendix

Table 1: Notation used in the ACG formulation.

Method	Outcome	Interface	Condition	Budget	Repeat	No output	Eval. fail
BrowseComp-Plus / GPT-5.6-luna
ReAct	F	2.6%	0.0%	1.4%	0.0%	7.7%	92.3%
	S	0.8%	0.0%	0.0%	0.0%	0.0%	0.0%
COMPASS	F	87.5%	0.0%	47.0%	67.5%	75.4%	24.6%
	S	55.4%	0.0%	0.0%	15.3%	0.0%	0.0%
TDP*	F	96.8%	0.0%	0.0%	43.9%	72.8%	26.6%

Appendix

Table 2: Task-level execution and delivery observations, reported as percentages; F/S denotes final failure/success. Each category cell is positive / assessable

\times 100

within its outcome group, using that category’s assessable-task denominator. Categories overlap and are not mutually exclusive, so percentages are not additive; a dash denotes no denominator.

Method	Outcome	Resumed	Reject-only	No further attempt	Delay
BrowseComp-Plus / GPT-5.6-luna
ReAct	F	100.0%	0.0%	0.0%	1
	S	100.0%	0.0%	0.0%	1
COMPASS	F	95.8%	0.4%	3.8%	1
	S	100.0%	0.0%	0.0%	1
TDP*	F	98.1%	0.8%	1.1%	1

Appendix

Table 3: Continuation after an interface or operation-precondition rejection, reported as percentages; F/S denotes final failure/success. Resumed, Reject-only, and No further attempt use their total observed episodes as the denominator; Delay is the median subsequent interface-attempt count until resumption. These are event-level observations, and continuation does not imply task success; a dash denotes no denominator or unavailable metric.

Explore similar work

LongHorizon-Harness: Advancing Long-Horizon Agents for Real-World Tasks
Aug 3, 2026Ziyu Ma, Hailang Huang, Shun Zou +5Long-Horizon Agents Long-Horizon Task Planning
DreamX Team, Alibaba Group
PRO-LONG: Programmatic Memory Enables Long-Horizon Reasoning
Jul 22, 2026Alexis Fox, Junlin Wang, Paul Rosu +1Long-Horizon Agents Long-Term Agent Memory
Duke University
LemonHarness Technical Report
Jun 23, 2026Kailong Ren, Fubo Sun, Jiachen Liu +18Long-Horizon Agents Tool Invocation

Aug 3, 2026, cs.CVJ/K move · Enter open · S save

LongHorizon-Harness: Advancing Long-Horizon Agents for Real-World Tasks

Ziyu Ma, Hailang Huang, Shun Zou, Yong Wang+4

DreamX Team, Alibaba Group

Long-Horizon Agents Long-Horizon Task Planning Agent Harness Real-World Tasks Model Auditing

Open paper AskPDF arXiv

Large language model (LLM) agents increasingly undertake long-horizon tasks that require sustained reasoning, tool use, and revision across many interdependent steps. However, existing agent harnesses maintain task execution, task state, and completion assessment within a growing context, making the state difficult to track and allowing incorrect self-assessments to propagate into later decisions. We reformulate long-horizon execution as a task-state management problem and propose LongHorizon-Harness, which maintains the task state explicitly outside execution and updates it only with facts independently verified from the environment. Its Manage-Execute-Audit(MEA) loop uses a manager to maintain the task state and determine the next subtask, a fresh-context executor to perform it, and a read-only auditor to verify the resulting environment state before the next round. A lightweight AgentAdapter supports interchangeable model and harness backends without modifying their native agent loops. LongHorizon-Harness improves Qwen~~3.7-Plus from 51.8% to 80.7% on WeaveBench, from 69.7% to 77.2% on Terminal-Bench~~2.1, and from 2.8% to 8.3% on OSWorld~~2.0. It also raises Claude Opus~~4.7 from 20.0% to 34.3% on an OSWorld2.0 subset, demonstrating consistent gains across models, harnesses, and interaction domains.

Abstract

Explore similar work

LongHorizon-Harness: Advancing Long-Horizon Agents for Real-World Tasks

PRO-LONG: Programmatic Memory Enables Long-Horizon Reasoning

LemonHarness Technical Report