Skip to content

Scoped Verification for Reliable Long-Horizon Agentic Context Evolution under Distribution Shift

🕒 Published (v1): 2026-07-10 08:10 UTC · Source: Arxiv · link

Why this paper was selected

Directly theorizes harness-managed agentic context evolution and scoped verification under distribution shift

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

GRACE (Graph-Regularized Agentic Context Evolution) replaces flat-text maintenance of a persistent system-level instruction with a typed semantic graph substrate, enabling scoped local validation at each evolution step. Over 10 evolution batches in a telecom agent harness, it raises strict reliability (\(\widehat{\text{pass}}@3\)) from 0.091 to 0.673±0.136, substantially outperforming flat-text and graph-without-validation baselines.

Problem

Deployed agents rely on a persistent system-level instruction assembled by an operational harness; as this instruction evolves from operational experience over many batches, flat-text maintenance leaves relationships among rules implicit, making verification increasingly dependent on long-context processing. Known failure modes include context collapse during full rewrites, unbounded memory growth, and guideline-conflict accumulation. Prior work shows iterative updates can improve behavior but does not isolate whether verification remains effective as the artifact grows—GRACE addresses this specific structural gap.

Method

GRACE maintains the evolving instruction as a directed typed heterogeneous information network \(G_t = (V_t, E_t)\) with object types \(\mathcal{A} = \{\texttt{identity}, \texttt{norm}, \texttt{knowledge}\}\) and relation types \(\mathcal{R} = \{\texttt{supports}, \texttt{refines}, \texttt{sequence}\}\), governed by a schema \(\mathcal{T}_G\) that enforces admissible source–target type pairs per relation. Each evolution step runs three stages:

  1. Operation Planning: An LLM edit planner proposes schema-conformant graph edits from a finite algebra \(\mathcal{O}_{\mathcal{T}_G} = \{\texttt{AddNode, AddEdge, ModifyNode, RemoveNode, RemoveEdge, Merge}\}\); a relation-maintenance pass then repairs incident typed edges.
  2. Structural Validation: Scoped to the \(k\)-hop typed neighborhood \(N_k(U_t, G_t^{\text{cand}})\) around update-touched nodes \(U_t\), with a progressive radius schedule starting at \(k=3\). Structural analysis (SA) detects contradictions (joint unsatisfiability under overlapping scope: \(\text{ModHt}(m(u)) \cap \text{ModHt}(m(v)) = \emptyset\)) and actionable redundancies (type-conditioned semantic subsumption without structural differentiation).
  3. Delta Reconstruction: The change log \(L_t^G = G_t \triangle G_{t-1}\) is converted to incremental text edits on \(\ell_{t-1}\), preserving unaffected formatting and sections. The deployed artifact remains plain text \(\ell_t\).

The harness, model, tools, and diagnosis procedure are held fixed across all conditions; only the evolution substrate and verification mechanism vary.

Key Contributions

  • GRACE substrate: typed semantic graph as the intermediate representation for persistent instruction evolution, enabling schema-constrained editing and scoped structural validation.
  • Controlled shift protocol: 10 alternating-phase experience batches that test both within-phase improvement and cross-phase retention, using backward transfer (\(\text{BWT}_d\)) as a retention metric.
  • Ablation isolating two failure modes: GRACE-without-SA shows contradiction avoidance alone is insufficient; sustained improvement also requires consolidation via structural analysis.

Results

  • GRACE \(\widehat{\text{pass}}@3\) at final checkpoint: 0.673±0.136 (5 replications)
  • Gemini 2.5 Flash zero-shot baseline: 0.091
  • Flat-text HCE baseline: 0.191±0.051
  • Gemini 3.1 Pro zero-shot reference (stronger model, same held-out set): 0.242 — GRACE exceeds this with the weaker Gemini 2.5 Flash agent
  • GRACE-without-SA finishes between HCE and GRACE, confirming that the graph substrate helps but structural analysis is additionally necessary
  • Evaluated on 66-task held-out set (198 episodes/checkpoint), τ²-bench telecom domain

Limitations

  • Single domain (telecom, τ²-bench); generalization to other task domains is untested.
  • Evaluation uses only Gemini 2.5 Flash as the agent model; results may not transfer across LLMs.
  • The graph schema (\(|\mathcal{A}|=3\), \(|\mathcal{R}|=3\)) is hand-designed for instruction structure; schema design is not automated or domain-adaptive.
  • Internal LLM-call budgets are not matched across conditions, complicating direct cost comparisons.
  • Structural analysis relies on LLM-mediated detection of contradictions and redundancies within neighborhoods—its own reliability is not separately characterized.
  • Paper text is truncated; replication details and supplementary BWT numbers are not fully available.

Relevance to Harnesses / Meta-Harnesses

GRACE explicitly positions itself relative to harness-level work: while MetaHarness (Lee et al., 2026) optimizes the harness code surrounding the model, GRACE holds the harness fixed and evolves only the persistent instruction component the harness assembles—a complementary axis of control. This makes GRACE directly relevant to researchers tracking how harnesses manage their mutable context payloads over time, and it provides a formalized substrate (typed graph + scoped validation) that could be integrated into meta-harness designs that need to evolve prompt artifacts reliably at scale. The paper's framing of the harness as a fixed interface through which context evolution operates also clarifies what "harness-level" vs. "instruction-level" optimization means in practice.