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

# Scoped Verification for Reliable Long-Horizon Agentic Context Evolution under Distribution Shift
Source: [https://arxiv.org/html/2607.09175](https://arxiv.org/html/2607.09175)
\\jmlryear

2026\\jmlrproceedingsPreprintPreprint\\jmlrworkshop

San FranciscoCAUSA \\addrNational Taiwan UniversityTaipeiTaiwan\\NameLuke Lu\\Emailluke@redmindresearch\.org \\addrRedMind ResearchSan FranciscoCAUSA

###### Abstract

Deployed LLM agents rely on agentic context, the model\-external textual control content assembled by an operational harness\. In this work, the mutable component of that context is a persistent system\-level instruction that is updated from operational experience while the model, tools, and harness remain fixed\. Over long evolution horizons, flat\-text maintenance makes verification increasingly difficult as accumulated instructions grow and interact\. We propose Graph\-Regularized Agentic Context Evolution \(GRACE\), which maintains the persistent instruction component as a typed semantic graph and validates proposed updates within the local typed neighborhoods of modified nodes\. Accepted graph updates are reconstructed as incremental edits to the textual instruction checkpoint used at deployment\. We evaluate GRACE within a fixed telecom agent harness derived fromτ2\\tau^\{2\}\-bench under a controlled distribution\-shift protocol\. Across five independent replications, GRACE improves strict reliability, measured by pass^3, from the Gemini 2\.5 Flash zero\-shot value of 0\.091 to 0\.673±\\pm0\.136 at the final checkpoint\. This exceeds a Gemini 3\.1 Pro zero\-shot reference of 0\.242 on the same held\-out set, while the flat\-text HCE baseline finishes at 0\.191±\\pm0\.051\. These results identify two requirements for reliable long\-horizon context evolution, a structural substrate that makes verification local and a consolidation mechanism that keeps accumulated instruction content usable\.

###### keywords:

agentic context, context evolution, persistent instruction, structural validation, reliability, distribution shift

## 1Introduction

As large language models have become better at following natural\-language instructions, model\-external text has become a primary control surface for deployed agents\(khattab2024dspy;zhang2026ace\)\. In operational agent systems, this text is assembled with task inputs, tool observations, and harness\-provided information before each model call\(yao2024taubench;yao2025tau2bench\)\. We refer to the resulting inference\-time input as the agent context\. In the setting studied here, the mutable component of this context is a persistent system\-level instruction that specifies the agent’s role, behavioral constraints, procedural guidance, and domain assumptions\(qin2025sysbench;lee2024align\)\. When task distributions shift, this persistent instruction can encode stale or incomplete assumptions about the environment it is meant to govern\. We study context evolution as the process of revising this persistent context component from operational experience while the model, tools, and harness remain fixed\. The evolving artifact may be a playbook\(zhang2026ace\), an adaptive memory\(suzgun2026dc\), a set of strategic principles\(wu2025evolver\), or a set of structured guidelines\(pei2025scope\)\. Across these forms, prior work has shown that iterative updates can improve agent behavior\(zhang2026ace;shinn2023reflexion\)\.

However, over extended evolution horizons, previously accumulated improvements can be undermined by inconsistencies introduced in subsequent steps\. Because the persistent instruction is included in the agent context throughout deployment, degradation in this artifact can compromise operational reliability as well as update efficiency\. Context collapse during full\-document rewriting has been documented as one failure mode in agentic context engineering\(zhang2026ace\), alongside unbounded memory growth in adaptive memory\(suzgun2026dc\)and guideline conflict accumulation in prompt evolution\(pei2025scope\)\. These failures point to a shared structural limitation\. Flat\-text maintenance leaves relationships among rules, constraints, and procedures implicit in the document’s linear order, which makes verification increasingly dependent on long\-context processing as the artifact grows\(liu2024lost\)\. Prior work has shown that model\-external guidance can be iteratively improved, but it has not directly isolated whether verification remains effective when the persistent instruction grows over long evolution horizons\.

We propose Graph\-Regularized Agentic Context Evolution \(GRACE\), which maintains a typed semantic graph as the intermediate substrate for evolving the persistent instruction component of agent context\. GRACE represents atomic instruction units as graph nodes, encodes structural relationships among them as typed directed edges, and uses graph locality to validate each proposed update near the affected nodes\. Accepted graph updates are reconstructed as incremental text edits to the deployed instruction checkpoint\. This paper studies the representation substrate within a fixed deployment interface\. The agent model, tools, harness, diagnosis procedure, and evaluation set are held fixed, while the representation and verification mechanism vary\. We evaluate GRACE in the telecom customer\-service domain derived fromτ2\\tau^\{2\}\-bench\(yao2025tau2bench\), using its operational harness with fixed tool interfaces and evaluation criteria\. Under a controlled shift protocol across 10 evolution batches, the main comparison uses three conditions with the same diagnosis procedure but different representation and verification mechanisms: GRACE, GRACE without structural analysis, and HCE\. Across replicated runs, GRACE remains ahead at the later checkpoints, indicating that structure\-enabled verification and consolidation both matter for sustained context evolution\.

In summary, the paper makes three contributions\. First, GRACE introduces a graph\-regularized substrate for evolving the persistent instruction component of agent context and performs scoped structural validation at each evolution step\. Second, the evaluation protocol introduces alternating distribution shift, so the same trajectory tests both within\-phase improvement and cross\-phase retention\. Third, replicated experiments in the telecom domain show that GRACE outperforms a flat\-text context\-evolution baseline and a graph\-based ablation without structural analysis\. The ablation separates two failure modes\. Contradiction avoidance helps, but sustained improvement also requires consolidation of the growing instruction substrate\.

## 2Related Work

#### Context evolution and persistent control artifacts\.

Optimizing the textual artifacts that steer LLM behavior has progressed from prompt\-level refinement to long\-horizon context evolution\. Prompt optimization and self\-refinement methods such as OPRO\(yang2024opro\), TextGrad\(yuksekgonul2024textgrad\), DSPy\(khattab2024dspy\), Reflexion\(shinn2023reflexion\), and Self\-Refine\(madaan2023selfrefine\)demonstrate effective short\-horizon improvement, but they do not maintain a persistent context component through repeated batch\-level updates and address a different optimization setting\. More recent work treats model\-external guidance as a persistent artifact that accumulates knowledge across episodes\. ACE\(zhang2026ace\)introduces incremental delta updates to prevent context collapse, SCOPE\(pei2025scope\)applies conflict resolution and subsumption pruning on dual\-stream memory, and Dynamic Cheatsheet\(suzgun2026dc\)and ExpeL\(zhao2024expel\)accumulate reusable guidance and experiential insights over time\. These systems are closest in spirit because they manage growing model\-external guidance, but they differ in artifact interface, update contract, and evaluation protocol\. We focus on a narrower question inside one fixed harness, namely whether the representation substrate used by the evolution operator can sustain verification as the persistent instruction component grows\.

Broader agent\-evolution frameworks address tool, workflow, or environment adaptation\(xi2024agentgym;wang2025gem\)\. A\-Evolve\(lin2026aevolve\)frames cross\-episode updates over a persistent artifact state\. Our work shares this cross\-episode perspective, but focuses specifically on the persistent system\-level instruction inside agent context and on controlled instantiations of the same evolution interface\. ProEvolve\(hsu2025proevolve\)likewise applies typed\-graph transformations, but to evolve benchmark environments, whereas GRACE applies graph\-structured editing to the persistent instruction itself\. Complementarily, Meta\-Harness\(lee2026metaharness\)optimizes the harness code surrounding the model, whereas we hold the harness fixed and evolve only the instruction component it assembles\. Across the context\-evolution methods above, the evolving artifact is typically maintained as flat text, and the question of whether an alternative representation substrate can sustain verification effectiveness over extended horizons remains underexplored\.

#### Structured knowledge representation for LLMs\.

Graph structures have been widely adopted in LLM systems for knowledge organization, memory, and retrieval\. GraphRAG\(edge2024graphrag\)constructs entity\-relation graphs to support query\-focused summarization over large corpora, HippoRAG\(gutierrez2024hipporag\)builds knowledge graphs as long\-term memory for associative retrieval, and broader surveys map the expanding landscape of knowledge\-graph and LLM integration\(pan2024kgllm\)\. These applications demonstrate that graphs can organize knowledge that LLMs operate over, but their use as an evolving substrate for persistent instruction content remains underexplored\. GRACE addresses this gap by using a typed semantic graph as the intermediate representation on which context evolution and structural validation operate\.

## 3Problem Formulation

We study long\-horizon agentic context evolution under a fixed operational harness\. Letπθ​\(a∣c\)\\pi\_\{\\theta\}\(a\\mid c\)denote the frozen action\-selection policy induced by the LLM, tools, and harness when supplied with agent contextcc\. The model parameters, tool interfaces, harness logic, and context\-assembly procedure are held fixed throughout the evolution trajectory\.

In this work, the mutable component of the agent context is a persistent system\-level instruction, denoted byℓt\\ell\_\{t\}after thett\-th batch\-level update\. This instruction is included in the context supplied to the agent, but it is not itself the action\-selection policy\. At inference time, the harness assembles a task\-specific context

ct​\(h,x\)=Assemble⁡\(ℓt,h,x\),c\_\{t\}\(h,x\)=\\operatorname\{Assemble\}\(\\ell\_\{t\},h,x\),\(1\)wherehhdenotes harness\-provided information andxxdenotes the task or user input\. The full task\-specific context changes across episodes throughhhandxx, while onlyℓt\\ell\_\{t\}is updated across evolution batches\.

We model context evolution as a closed\-loop cross\-episode update process, following the persistent artifact update perspective oflin2026aevolve\. We use*substrate*to denote the mutable representation used during offline evolution\. The substrate is the internal form in which the persistent instruction is maintained, edited, and validated before the next instruction checkpoint is reconstructed\. Letsts\_\{t\}denote this substrate at update steptt\. The initial instructionℓ0\\ell\_\{0\}is shared across all conditions, and the initial substrates0s\_\{0\}is initialized fromℓ0\\ell\_\{0\}\. For text\-maintained methods,sts\_\{t\}is the instruction text itself\. For GRACE,st=Gts\_\{t\}=G\_\{t\}is a graph\-regularized substrate from whichℓt\\ell\_\{t\}is reconstructed\.

For each update stept∈\{1,…,T\}t\\in\\\{1,\\ldots,T\\\}, the agent is executed on tasks drawn from the batch distribution𝒟t\\mathcal\{D\}\_\{t\}\. Execution uses the frozen action\-selection policyπθ\\pi\_\{\\theta\}under contexts assembled from the previous instruction checkpointℓt−1\\ell\_\{t\-1\}\. The resulting interaction traces are

ℰt=FExperience​\(πθ,Assemble⁡\(ℓt−1,⋅,⋅\),𝒟t\)\.\\mathcal\{E\}\_\{t\}=F\_\{\\mathrm\{Experience\}\}\\left\(\\pi\_\{\\theta\},\\operatorname\{Assemble\}\(\\ell\_\{t\-1\},\\cdot,\\cdot\),\\mathcal\{D\}\_\{t\}\\right\)\.\(2\)The diagnostic observation is then computed as

ot=FDiagnose​\(ℰt\)\.o\_\{t\}=F\_\{\\mathrm\{Diagnose\}\}\(\\mathcal\{E\}\_\{t\}\)\.\(3\)
The evolution function uses the diagnostic observation to update the substrate and produce the next instruction checkpoint:

\(st,ℓt\)←FEvolve​\(st−1,ℓt−1,ot\)\.\(s\_\{t\},\\ell\_\{t\}\)\\leftarrow F\_\{\\mathrm\{Evolve\}\}\(s\_\{t\-1\},\\ell\_\{t\-1\},o\_\{t\}\)\.\(4\)For a text\-maintained context\-evolution baseline,

ℓt←FEvolvetext​\(ℓt−1,ot\)\.\\ell\_\{t\}\\leftarrow F\_\{\\mathrm\{Evolve\}\}^\{\\mathrm\{text\}\}\(\\ell\_\{t\-1\},o\_\{t\}\)\.\(5\)For GRACE,

\(Gt,ℓt\)←FEvolvegraph​\(Gt−1,ℓt−1,ot\)\.\(G\_\{t\},\\ell\_\{t\}\)\\leftarrow F\_\{\\mathrm\{Evolve\}\}^\{\\mathrm\{graph\}\}\(G\_\{t\-1\},\\ell\_\{t\-1\},o\_\{t\}\)\.\(6\)The graphGtG\_\{t\}is used only during offline editing and validation\. Deployment uses the reconstructed textual instructionℓt\\ell\_\{t\}, which is assembled withhhandxxto form the agent context supplied toπθ\\pi\_\{\\theta\}\.

We holdFExperienceF\_\{\\mathrm\{Experience\}\}andFDiagnoseF\_\{\\mathrm\{Diagnose\}\}fixed across all conditions\. The comparison therefore isolates how each method maintains, validates, and reconstructs the evolving instruction component throughFEvolveF\_\{\\mathrm\{Evolve\}\}\. In this work, GRACE is the proposed graph\-regularized realization of this operator, introduced in §[4](https://arxiv.org/html/2607.09175#S4)\. The empirical protocol in §[5\.1](https://arxiv.org/html/2607.09175#S5.SS1)specifies the controlled shift schedule, checkpoint evaluation procedure, and reliability metrics used to evaluate the resulting deployed context checkpoints\. Throughout the paper, context evolution refers to the batch\-level process that updates the persistent instruction component of the agent context\. The term policy is reserved for the frozen action\-selection policyπθ​\(a∣c\)\\pi\_\{\\theta\}\(a\\mid c\), except when discussing terminology used in prior work\.

![Refer to caption](https://arxiv.org/html/2607.09175v1/figs/fig1.jpg)Figure 1:Overview of the GRACE evolution pipeline\.Given a diagnosis report and the current graphGt−1G\_\{t\-1\}, the pipeline produces an updated graphGtG\_\{t\}and corresponding instruction checkpointℓt\\ell\_\{t\}through three stages: Operation Planning, Structural Validation, and Delta Reconstruction\. Sequence planning is performed as a substep within Operation Planning, while Structural Validation combines deterministic schema checks with iterative structural analysis \(SA\)\.
## 4Method: Graph\-Regularized Agentic Context Evolution

In the notation of §[3](https://arxiv.org/html/2607.09175#S3), GRACE instantiates the evolution substratests\_\{t\}as a typed graphGtG\_\{t\}\. Nodes encode atomic instruction units extracted from the persistent system\-level instructionℓt\\ell\_\{t\}, and edges encode structural relations among those units\. The deployed artifact remains textual\. After schema\-constrained editing and local structural validation, GRACE reconstructs the next instruction checkpointℓt\\ell\_\{t\}, which is assembled into the agent context at inference time\.

### 4\.1Graph\-Regularized Substrate

Following the formulation of heterogeneous information networks\(sun2011pathsim\), GRACE maintains the substrate as a directed typed graphGt=\(Vt,Et\)G\_\{t\}=\(V\_\{t\},E\_\{t\}\)at update steptt, where nodes encode atomic instruction units and edges encode directed structural relations\. The graph is equipped with an object\-type mapping functionφ:V→𝒜\\varphi:V\\rightarrow\\mathcal\{A\}and a relation\-type mapping functionψ:E→ℛ\\psi:E\\rightarrow\\mathcal\{R\}\. GRACE instantiates the object and relation type sets as

𝒜=\{𝗂𝖽𝖾𝗇𝗍𝗂𝗍𝗒,𝗇𝗈𝗋𝗆,𝗄𝗇𝗈𝗐𝗅𝖾𝖽𝗀𝖾\},ℛ=\{𝗌𝗎𝗉𝗉𝗈𝗋𝗍𝗌,𝗋𝖾𝖿𝗂𝗇𝖾𝗌,𝗌𝖾𝗊𝗎𝖾𝗇𝖼𝖾\}\.\\mathcal\{A\}=\\\{\\mathsf\{identity\},\\mathsf\{norm\},\\mathsf\{knowledge\}\\\},\\qquad\\mathcal\{R\}=\\\{\\mathsf\{supports\},\\mathsf\{refines\},\\mathsf\{sequence\}\\\}\.\(7\)Following the ontology\-specification convention ofgruber1993translation, we specify each object and relation type by an identifier, a natural\-language description of its intended meaning, and constraints that determine admissible instances\. These definitions induce the network schema

TG=\(𝒜,ℛ,\{σr\}r∈ℛ\),T\_\{G\}=\(\\mathcal\{A\},\\mathcal\{R\},\\\{\\sigma\_\{r\}\\\}\_\{r\\in\\mathcal\{R\}\}\),\(8\)where eachσr⊆𝒜×𝒜\\sigma\_\{r\}\\subseteq\\mathcal\{A\}\\times\\mathcal\{A\}specifies the admissible source and target object types for relation typerr\. For every edgee=\(u,v\)e=\(u,v\)withψ​\(e\)=r\\psi\(e\)=r, GRACE requires\(φ​\(u\),φ​\(v\)\)∈σr\(\\varphi\(u\),\\varphi\(v\)\)\\in\\sigma\_\{r\}, ensuring schema\-conformant updates\. For GRACE, the initial substrates0s\_\{0\}is the graphG0G\_\{0\}, obtained by a semantics\-preserving decomposition of the shared initial instructionℓ0\\ell\_\{0\}into schema\-conformant objects and relations\. Figure[2](https://arxiv.org/html/2607.09175#S4.F2)visualizes the schema used in our implementation\.

The object types correspond to classes in the Ontolingua convention, treated as unary relations whose instance variable ranges over admissible graph nodes\. Relation\-type definitions constrain source and target arguments and therefore determine the endpoint signatures inσr\\sigma\_\{r\}\. Table[1](https://arxiv.org/html/2607.09175#S4.T1)summarizes the object and relation type definitions used by GRACE, and Table[2](https://arxiv.org/html/2607.09175#S4.T2)gives the induced type\-signature matrix\.

Table 1:Object and relation type definitions in the GRACE network schema\.Each row gives the natural\-language rendering of the corresponding:defcondition\.identitynormknowledgesupportssupportsrefinessupportsrefinessequencesupportsrefinesFigure 2:GRACE network schemaTG=\(𝒜,ℛ,\{σr\}r∈ℛ\)T\_\{G\}=\(\\mathcal\{A\},\\mathcal\{R\},\\\{\\sigma\_\{r\}\\\}\_\{r\\in\\mathcal\{R\}\}\)\.Nodes denote object types in𝒜\\mathcal\{A\}, and directed labeled edges denote admissible relation types:supports,refines, andsequence\.Table 2:Type\-signature matrix for the GRACE network schema\.Each cell lists relation types allowed from the source object type to the target object type\.
### 4\.2Evolution Pipeline

At each update step, GRACE instantiates the evolution operator in Eq\.[4](https://arxiv.org/html/2607.09175#S3.E4)as a mapping from the previous graph substrate, previous instruction checkpoint, and diagnostic observation to the next graph substrate and instruction checkpoint,\(Gt−1,ℓt−1,ot\)↦\(Gt,ℓt\)\(G\_\{t\-1\},\\ell\_\{t\-1\},o\_\{t\}\)\\mapsto\(G\_\{t\},\\ell\_\{t\}\)\. The pipeline obtains these outputs through operation planning, structural validation, and delta reconstruction\.

#### Operation planning\.

The first stage converts the diagnosis into schema\-constrained graph updates\. Let each graph state be represented as\(V,E,φ,ψ,m\)\(V,E,\\varphi,\\psi,m\), wherem:V→𝒯m:V\\rightarrow\\mathcal\{T\}maps each node to its natural\-language instruction content\. GRACE defines a finite editing algebra overTGT\_\{G\}:

𝒪TG=\{AddNode,AddEdge,ModifyNode,RemoveNode,RemoveEdge,Merge\}\.\\mathcal\{O\}\_\{T\_\{G\}\}=\\\{\\mathrm\{AddNode\},\\mathrm\{AddEdge\},\\mathrm\{ModifyNode\},\\mathrm\{RemoveNode\},\\mathrm\{RemoveEdge\},\\mathrm\{Merge\}\\\}\.\(9\)An operation belongs to𝒪TG\\mathcal\{O\}\_\{T\_\{G\}\}only when applying it preserves schema conformance underTGT\_\{G\}\. Table[3](https://arxiv.org/html/2607.09175#S4.T3)summarizes the six operators\. An LLM\-mediated edit planner with a fixed prompt interface proposes a finite set of typed graph edits over this algebra:

Δtedit=Fedit​\(Gt−1,ot\),Δtedit⊆𝒪TG\.\\Delta\_\{t\}^\{\\mathrm\{edit\}\}=F\_\{\\mathrm\{edit\}\}\(G\_\{t\-1\},o\_\{t\}\),\\qquad\\Delta\_\{t\}^\{\\mathrm\{edit\}\}\\subseteq\\mathcal\{O\}\_\{T\_\{G\}\}\.\(10\)
Table 3:Graph editing operators in𝒪TG\\mathcal\{O\}\_\{T\_\{G\}\}\.Each edit inΔtedit\\Delta\_\{t\}^\{\\mathrm\{edit\}\}is traceable to a diagnosis finding and must conform toTGT\_\{G\}\. For every proposed relation edgee=\(u,v\)e=\(u,v\)withψ​\(e\)=r\\psi\(e\)=r, the source and target object types must satisfy\(φ​\(u\),φ​\(v\)\)∈σr\(\\varphi\(u\),\\varphi\(v\)\)\\in\\sigma\_\{r\}\. The planned editsΔtedit\\Delta\_\{t\}^\{\\mathrm\{edit\}\}are deterministically applied toGt−1G\_\{t\-1\}, yielding an intermediate graphG^t\\widehat\{G\}\_\{t\}together with the edit\-touched node setUteditU\_\{t\}^\{\\mathrm\{edit\}\}\. The intermediate graph is then passed to a relation\-maintenance module before structural validation\. This LLM\-mediated pass reviews the typed relation layer ofG^t\\widehat\{G\}\_\{t\}, focusing on the relations incident to the edit\-touched setUteditU\_\{t\}^\{\\mathrm\{edit\}\}, and proposes relation\-level edits:

Δtrel=Frelation​\(G^t,Utedit\),Δtrel⊆𝒪TG\.\\Delta\_\{t\}^\{\\mathrm\{rel\}\}=F\_\{\\mathrm\{relation\}\}\(\\widehat\{G\}\_\{t\},U\_\{t\}^\{\\mathrm\{edit\}\}\),\\qquad\\Delta\_\{t\}^\{\\mathrm\{rel\}\}\\subseteq\\mathcal\{O\}\_\{T\_\{G\}\}\.\(11\)Relation\-level edits must also conform toTGT\_\{G\}\. The accepted relation editsΔtrel\\Delta\_\{t\}^\{\\mathrm\{rel\}\}are deterministically incorporated intoG^t\\widehat\{G\}\_\{t\}, yielding the candidate graphGtcandG\_\{t\}^\{\\mathrm\{cand\}\}together with the relation\-touched setUtrelU\_\{t\}^\{\\mathrm\{rel\}\}\.

#### Structural validation\.

The candidate graphGtcandG\_\{t\}^\{\\mathrm\{cand\}\}is first checked for conformance to the network schema\. Structural analysis \(SA\) then examines the affected typed neighborhoods for local semantic issues, and flagged issues are repaired through schema\-conformant operations\. Following the PathSim framework ofsun2011pathsim, where meta\-paths define semantically meaningful comparison contexts for objects in heterogeneous information networks, structural analysis adapts the same typed\-neighborhood principle to LLM\-mediated instruction validation over local typed graph neighborhoods\. Given a symmetric meta\-path𝒫\\mathcal\{P\}, PathSim between same\-type objectsxxandyyis

sP​\(x,y\)=2×\|\{px↝y:px↝y∈𝒫\}\|\|\{px↝x:px↝x∈𝒫\}\|\+\|\{py↝y:py↝y∈𝒫\}\|\.s\_\{P\}\(x,y\)=\\frac\{2\\times\\left\|\\\{p\_\{x\\rightsquigarrow y\}:p\_\{x\\rightsquigarrow y\}\\in\\mathcal\{P\}\\\}\\right\|\}\{\\left\|\\\{p\_\{x\\rightsquigarrow x\}:p\_\{x\\rightsquigarrow x\}\\in\\mathcal\{P\}\\\}\\right\|\+\\left\|\\\{p\_\{y\\rightsquigarrow y\}:p\_\{y\\rightsquigarrow y\}\\in\\mathcal\{P\}\\\}\\right\|\}\.\(12\)Herepx↝yp\_\{x\\rightsquigarrow y\}denotes a path instance betweenxxandyyfollowing𝒫\\mathcal\{P\}\. GRACE adopts PathSim’s typed comparison principle while changing the objective from similarity ranking to scoped validation\. A typed local neighborhood defines which instruction units are compared and which structural evidence can distinguish, merge, or repair them\.

LetUt=Utedit∪UtrelU\_\{t\}=U\_\{t\}^\{\\mathrm\{edit\}\}\\cup U\_\{t\}^\{\\mathrm\{rel\}\}denote the update\-touched node set, and letdGd\_\{G\}denote shortest\-path distance in graphGG\. For any validation radiuskk, we define thekk\-hop typed neighborhood as

Nk​\(Ut,Gtcand\)=\{v∈Vtcand:minu∈Ut⁡dGtcand​\(u,v\)≤k\}\.N\_\{k\}\(U\_\{t\},G\_\{t\}^\{\\mathrm\{cand\}\}\)=\\left\\\{v\\in V\_\{t\}^\{\\mathrm\{cand\}\}:\\min\_\{u\\in U\_\{t\}\}d\_\{G\_\{t\}^\{\\mathrm\{cand\}\}\}\(u,v\)\\leq k\\right\\\}\.\(13\)Here,kk\-hop refers to all nodes reachable fromUtU\_\{t\}within at mostkkgraph hops\. In implementation, structural analysis uses a deterministic progressive schedule that starts fromk=3k=3and increases the radius by 3 across a fixed number of local expansion rounds\. Letk⋆k^\{\\star\}denote the final radius reached by this schedule\. The validation neighborhoodHtH\_\{t\}is the local typed subgraph induced byNk⋆​\(Ut,Gtcand\)N\_\{k^\{\\star\}\}\(U\_\{t\},G\_\{t\}^\{\\mathrm\{cand\}\}\)insideGtcandG\_\{t\}^\{\\mathrm\{cand\}\}, containing the selected neighborhood nodes, all candidate\-graph edges among them, and the inherited type mappings\. Structural analysis is performed onHtH\_\{t\}, and repairs are applied back toGtcandG\_\{t\}^\{\\mathrm\{cand\}\}to obtainGtG\_\{t\}\.

Structural analysis detects two semantic issue families\. First, contradiction captures joint unsatisfiability under overlapping applicability scope\. For nodesu,v∈V​\(Ht\)u,v\\in V\(H\_\{t\}\), letOverlapHt⁡\(u,v\)\\operatorname\{Overlap\}\_\{H\_\{t\}\}\(u,v\)indicate that the two units apply under overlapping graph\-local scope, and letModHt⁡\(x\)\\operatorname\{Mod\}\_\{H\_\{t\}\}\(x\)denote the set of coherent instruction interpretations satisfying contentxxin the validation neighborhoodHtH\_\{t\}\. We define

ContrHt⁡\(u,v\)⇔OverlapHt⁡\(u,v\)∧ModHt⁡\(m​\(u\)∧m​\(v\)\)=∅\.\\operatorname\{Contr\}\_\{H\_\{t\}\}\(u,v\)\\iff\\operatorname\{Overlap\}\_\{H\_\{t\}\}\(u,v\)\\land\\operatorname\{Mod\}\_\{H\_\{t\}\}\\big\(m\(u\)\\land m\(v\)\\big\)=\\emptyset\.\(14\)This follows the standard view that contradictory contents cannot be jointly satisfied, adapted to natural\-language instruction units whose applicability is determined by the validation neighborhood\(demarneffe2008finding\)\.

Second, redundancy captures lack of marginal semantic contribution within the same object type\. We first define a redundancy candidate:

RedCandHt⁡\(u,v\)⇔\\displaystyle\\operatorname\{RedCand\}\_\{H\_\{t\}\}\(u,v\)\\iffφ​\(u\)=φ​\(v\)∧OverlapHt⁡\(u,v\)\\displaystyle\\varphi\(u\)=\\varphi\(v\)\\land\\operatorname\{Overlap\}\_\{H\_\{t\}\}\(u,v\)\(15\)∧\(EntailsHt,φ​\(u\)⁡\(u,v\)∨EntailsHt,φ​\(u\)⁡\(v,u\)\)\.\\displaystyle\\land\\left\(\\operatorname\{Entails\}\_\{H\_\{t\},\\varphi\(u\)\}\(u,v\)\\lor\\operatorname\{Entails\}\_\{H\_\{t\},\\varphi\(u\)\}\(v,u\)\\right\)\.The predicateEntailsHt,a⁡\(u,v\)\\operatorname\{Entails\}\_\{H\_\{t\},a\}\(u,v\)denotes type\-conditioned semantic subsumption for object typea∈𝒜a\\in\\mathcal\{A\}: under the validation neighborhoodHtH\_\{t\}, the content ofvvcan be inferred from the content ofuu\. This follows textual\-entailment theory\(dagan2009recognizing;androutsopoulos2010survey\)and operationalizes redundancy as informational equivalence or subsumption between texts\(zanzotto2011linguistic\)\. The same\-type restriction prevents identity, norm, and knowledge nodes from being collapsed merely because their natural\-language contents are related\. A candidate becomes an actionable redundancy issue only when the graph provides no structural reason to keep the two units distinct:

RedHt⁡\(u,v\)⇔RedCandHt⁡\(u,v\)∧¬DiffHt⁡\(u,v\)\.\\operatorname\{Red\}\_\{H\_\{t\}\}\(u,v\)\\iff\\operatorname\{RedCand\}\_\{H\_\{t\}\}\(u,v\)\\land\\neg\\operatorname\{Diff\}\_\{H\_\{t\}\}\(u,v\)\.\(16\)Here,DiffHt⁡\(u,v\)\\operatorname\{Diff\}\_\{H\_\{t\}\}\(u,v\)indicates that the validation neighborhood structurally differentiates the two units\. Differentiating evidence can include specialization, grounding, procedural ordering, or distinct typed support neighborhoods, preventing semantically related but functionally distinct instruction units from collapsing\. Structural analysis flags pairs that satisfy either contradiction or actionable redundancy:

ℐt=\{\(u,v\)∈V​\(Ht\)×V​\(Ht\):ContrHt⁡\(u,v\)∨RedHt⁡\(u,v\)\}\.\\mathcal\{I\}\_\{t\}=\\left\\\{\(u,v\)\\in V\(H\_\{t\}\)\\times V\(H\_\{t\}\):\\operatorname\{Contr\}\_\{H\_\{t\}\}\(u,v\)\\lor\\operatorname\{Red\}\_\{H\_\{t\}\}\(u,v\)\\right\\\}\.\(17\)Detected issues inℐt\\mathcal\{I\}\_\{t\}are repaired through schema\-conformant operations in𝒪TG\\mathcal\{O\}\_\{T\_\{G\}\}, resulting in the validated graphGtG\_\{t\}\.

#### Delta reconstruction

After validation, delta reconstruction converts the graph\-level change logℒtG=Gt​△​Gt−1\\mathcal\{L\}\_\{t\}^\{G\}=G\_\{t\}\\triangle G\_\{t\-1\}into the deployed instruction checkpoint, where△\\triangledenotes the component\-wise symmetric difference over the typed graph state, interpreted fromGt−1G\_\{t\-1\}toGtG\_\{t\}\. The instruction checkpoint is produced asℓt=Frecon​\(ℓt−1,ℒtG\)\\ell\_\{t\}=F\_\{\\mathrm\{recon\}\}\(\\ell\_\{t\-1\},\\mathcal\{L\}\_\{t\}^\{G\}\), editing only text regions aligned with validated graph\-level changes while preserving unaffected content, formatting, and section structure\. At deployment,ℓt\\ell\_\{t\}is assembled with harness\-provided information and task input to form the agent context supplied toπθ\\pi\_\{\\theta\}\.

## 5Experiments

### 5\.1Experimental Setup

#### Benchmark, harness, and comparison scope\.

We evaluate on the telecom domain ofτ2\\tau^\{2\}\-bench\(yao2025tau2bench\), which comprises 2,285 composable tasks constructed from 15 atomic subtask groups across three intent categories\. Within this harness, the evolving component is the persistent system\-level instruction included in the agent context\. All conditions share the same initial instruction, experience batches, diagnosis procedure, held\-out evaluation set, agent model, and user simulator\. They differ only in howFEvolveF\_\{\\mathrm\{Evolve\}\}maintains, validates, and reconstructs this persistent context component\.

#### Controlled shift protocol and task allocation\.

To evaluate whether the evolved instruction component preserves reliable behavior when the experience distribution changes, we construct a controlled shift protocol over user intents\. The protocol preserves subpopulation support across phases while changing relative intent frequencies, matching the subpopulation\-shift setting ofkoh2021wilds\. We partition 486 tasks into a held\-out evaluation set of 66 tasks and 10 experience batches of 42 tasks each, disjoint at the task level but sharing underlying atomic subtask groups\. The experience batches alternate between two intent\-mixture configurations across the 10\-batch trajectory, as detailed in Table[4](https://arxiv.org/html/2607.09175#S5.T4)\. The supplementary material quantifies the induced shift over intents and atomic subtask groups\.

Table 4:Controlled shift protocol and task allocation\.The held\-out evaluation set is shared across all checkpoints and never used for evolution\. Experience batches alternate between two intent\-mixture phases, both containing all three intents\. MMS and Mobile Data are reweighted in opposite directions, while Service is held constant\. Numbers in parentheses denote Easy/Hard/None customer persona splits\. No two batches share any task\.
#### Evaluation metrics\.

At each reported evaluation checkpoint, the agent is evaluated using the deployed context assembled from instruction checkpointℓt\\ell\_\{t\}on the same 66\-task held\-out set with three independent trials per task, yielding 198 episodes per checkpoint\. The replicated evaluation reports the shared initial instructionℓ0\\ell\_\{0\}and later checkpointsℓ6,ℓ8,ℓ10\\ell\_\{6\},\\ell\_\{8\},\\ell\_\{10\}\. Followingτ\\tau\-bench\(yao2024taubench\), pass@kkmeasures task\-level capability under a best\-of\-kkcriterion, while pass^kkmeasures trial\-level reliability under an all\-kkcriterion\. To measure retention under phase changes, we report intent\-level backward transfer followinglopezpaz2017gem\. For a phase transition fromXXtoYYand an intentddnot emphasized in PhaseYY,BWTd​\(X→Y\)=pass^​kd​\(πYend\)−pass^​kd​\(πXend\)\\text\{BWT\}\_\{d\}\(X\\to Y\)=\\text\{pass\\textasciicircum\{\}\}k\_\{d\}\(\\pi\_\{Y\_\{\\text\{end\}\}\}\)\-\\text\{pass\\textasciicircum\{\}\}k\_\{d\}\(\\pi\_\{X\_\{\\text\{end\}\}\}\)\. Positive BWT indicates retained or improved performance on that intent after the experience distribution shifts away from it\. In all reported BWT results,k=3k=3\. The post\-hoc consistency audit used for diagnostic analysis is described in the supplementary material\.

#### Evolution conditions and shared diagnosis\.

We compare three primary instantiations ofFEvolveF\_\{\\mathrm\{Evolve\}\}\.Holistic Context Evolution\(HCE\) applies a single\-pass text\-maintained update to the persistent instruction with a built\-in consistency guard\.GRACE without SAablates structural analysis from the graph\-regularized instruction substrate, whileGRACEdenotes the full method\. These are controlled instantiations of the same evolution interface, designed to isolate the effects of representation and structural validation, not to reimplement full prior systems with different artifacts and protocols\. All conditions use Gemini 2\.5 Flash as the agent model and GPT\-4\.1 as the user simulator\. They share the same two\-stage diagnosis procedure, which reflects on failed conversations and synthesizes the resulting findings into prioritized update themes\. The procedure is fixed across conditions, but diagnosis content may differ after the first update\. The comparison matches the initial instruction, experience batches, diagnosis procedure, held\-out evaluation set, and one batch\-level evolution opportunity per update, but not internal LLM\-call budgets\. Zero\-shot Gemini 2\.5 Flash and Gemini 3\.1 Pro references are included only as fixed held\-out references\. The evolution comparison itself is between the three Gemini 2\.5 Flash conditions above\.

#### Replication and audit scope\.

Each primary condition is run for five independent evolution trajectories\. At every reported checkpoint, each trajectory is evaluated on the same 66 held\-out tasks with three trials per task\. Each method\-checkpoint mean therefore aggregates five 198\-episode evaluations\. HCE receives the same diagnosis signal and update schedule as GRACE and maintains the deployed instruction directly as text with an explicit consistency guard, so it is not a zero\-shot prompt baseline\. The post\-hoc LLM\-as\-Judge audit\(zheng2023judging\)is applied only toℓ0,ℓ6,ℓ8,ℓ10\\ell\_\{0\},\\ell\_\{6\},\\ell\_\{8\},\\ell\_\{10\}and is used only for mechanism analysis\. It is not used to select checkpoints, modify instruction checkpoints, or compute pass^3, pass@3, or pass@1\. The supplementary material gives the controlled\-shift quantification and audit protocol\.

### 5\.2Main Results

Table[5](https://arxiv.org/html/2607.09175#S5.T5)summarizes the checkpoint results, and Figure[3](https://arxiv.org/html/2607.09175#S5.F3)shows the replicated pass^3 trajectories\. The conditions share the agent model, simulator, experience batches, diagnosis procedure, held\-out set, and update schedule\. The comparison therefore turns on how each instantiation ofFEvolveF\_\{\\mathrm\{Evolve\}\}maintains, verifies, and reconstructs the evolving instruction component\.

![Refer to caption](https://arxiv.org/html/2607.09175v1/x1.png)Figure 3:Replicated pass^3 checkpoint trajectories for the three primary conditions\.Points report mean pass^3 over five independent replications\. Standard deviations are reported in Table[5](https://arxiv.org/html/2607.09175#S5.T5)\. Dashed horizontal lines mark the zero\-shot pass^3 references for Gemini 3\.1 Pro and Gemini 2\.5 Flash on the same held\-out set\.#### GRACE sustains cumulative improvement\.

Across five independent replications, GRACE is the only primary condition that shows sustained improvement through the later checkpoints of the controlled shift protocol \(Figure[3](https://arxiv.org/html/2607.09175#S5.F3)\)\. Starting from the shared initial instruction with pass^3 of 0\.091, it reaches 0\.530±\\pm0\.086 atℓ6\\ell\_\{6\}, 0\.594±\\pm0\.135 atℓ8\\ell\_\{8\}, and 0\.673±\\pm0\.136 atℓ10\\ell\_\{10\}\. Its pass@3 remains near ceiling over the same checkpoints, reaching 0\.979±\\pm0\.025 atℓ10\\ell\_\{10\}\(Table[5](https://arxiv.org/html/2607.09175#S5.T5)\)\. The remaining gap between pass@3 and pass^3 indicates that capability is easier to recover than strict reliability, which requires all three independent trials to succeed\.

#### Flat\-text instruction maintenance exhibits distinct failure patterns\.

HCE improves over the shared initial instruction but does not sustain the gain\. It reaches 0\.215±\\pm0\.066 atℓ6\\ell\_\{6\}and 0\.236±\\pm0\.109 atℓ8\\ell\_\{8\}, then finishes at 0\.191±\\pm0\.051\. The same pattern is visible in pass@3\. HCE reaches 0\.618±\\pm0\.218 atℓ6\\ell\_\{6\}but drops to 0\.479±\\pm0\.244 atℓ10\\ell\_\{10\}\. This trajectory illustrates that flat\-text context evolution can exploit diagnostic signal but remains vulnerable to later degradation as the maintained instruction grows\.

#### Graph structure alone is not sufficient for sustained improvement\.

GRACE without SA improves to 0\.458±\\pm0\.177 atℓ6\\ell\_\{6\}, but the gain is not consolidated\. Its pass^3 drops to 0\.303±\\pm0\.165 atℓ8\\ell\_\{8\}and 0\.248±\\pm0\.144 atℓ10\\ell\_\{10\}, while pass@3 falls from 0\.845±\\pm0\.189 to 0\.685±\\pm0\.254\. The graph substrate makes the instruction artifact more verifiable, but the ablation shows that structure alone does not protect accumulated gains over time\.

Table 5:Replicated checkpoint summary\.Values are mean \(std\) over five runs\. The shared initial instruction has pass^3 = \.091, pass@3 = \.333, and pass@1 = \.202\.

### 5\.3Analysis

The three trajectories differ not only in final score but also in failure mode\. We next examine the mechanisms behind those differences\.

#### Contradiction accumulation distinguishes HCE from the other failure modes\.

We use the post\-hoc LLM\-as\-Judge audit described in §[5\.1](https://arxiv.org/html/2607.09175#S5.SS1)to examine whether evolved instruction artifacts accumulate internal contradictions\. The audit uses a single contradiction category\. Two instruction statements are counted as contradictory when they prescribe incompatible behavior under overlapping conditions and the graph or text provides no structural relation that resolves the tension\. Across the audited checkpointsℓ0,ℓ6,ℓ8,ℓ10\\ell\_\{0\},\\ell\_\{6\},\\ell\_\{8\},\\ell\_\{10\}, HCE has the highest contradiction count at 3\.35 on average, while GRACE and GRACE without SA remain in a narrower range from 1\.75 to 1\.90\. This evidence is correlational, but it matches the observed performance collapse\. As HCE’s flat text grows, its built\-in consistency guard has increasing difficulty keeping incompatible rules apart\.

GRACE without SA keeps contradiction counts low but still fails to sustain improvement\. Avoiding contradictions is therefore not enough\. The remaining failure mode is lack of consolidation over the growing graph substrate\.

#### Graph structure suppresses contradictions but does not consolidate\.

GRACE and GRACE without SA maintain similarly low contradiction counts, indicating that typed graph representation and incremental delta reconstruction already help avoid gross contradictions\. The difference appears in growth and consolidation\. By the final checkpoint, the graph\-only ablation reaches 421 nodes, compared to 370 nodes for GRACE\. The deployed instruction\-size measurements in Table[6](https://arxiv.org/html/2607.09175#S5.T6)show the same pattern at the text layer on the reported checkpoints\. HCE grows substantially more than either graph\-based condition, while GRACE remains slightly smaller than the graph\-only ablation atℓ10\\ell\_\{10\}\. The LLM\-as\-Judge redundancy audit points in the same direction\. Acrossℓ0,ℓ6,ℓ8,ℓ10\\ell\_\{0\},\\ell\_\{6\},\\ell\_\{8\},\\ell\_\{10\}, GRACE without SA has a higher redundancy count than GRACE on average, 4\.85 compared to 4\.15, and reaches 6\.5 atℓ10\\ell\_\{10\}\. This expansion matches the stochastic trajectory in §[5\.2](https://arxiv.org/html/2607.09175#S5.SS2)\. Individual checkpoints can improve, but the gains are not consolidated into a durable instruction component\. The graph and SA play different roles\. The graph makes relationships among accumulated instruction units explicit and helps prevent gross contradictions\. SA consolidates the growing substrate by merging overlapping content and resolving subtle tensions\.

Table 6:Mean deployed instruction size in characters\.Values average over five runs and measure the persistent system\-level instruction assembled into the deployed agent context, not the internal graph substrate\.
#### Retention under distribution shift reflects these mechanism differences\.

The controlled shift protocol tests whether these mechanism differences translate into retention under changing experience distributions\. GRACE shows positive or zero backward transfer in all cycles except Mobile Data in Cycle 1, where a temporary drop of 0\.233 is later recovered\. HCE exhibits persistent negative backward transfer, with Mobile Data BWT reaching−0\.500\-0\.500in Cycle 1 and never recovering\. The mechanism analysis explains the split\. HCE’s contradiction\-laden instruction artifact loses coherence when the experience distribution shifts, while GRACE’s consolidated instruction component is more resilient to the shift\.

## 6Conclusion

This paper studied long\-horizon agentic context evolution through the lens of verification\. In the setting considered here, the evolving object is the persistent system\-level instruction assembled into the agent context, while the model, tools, and harness remain fixed\. GRACE maintains this instruction component as a typed semantic graph, enabling structural validation to focus on affected typed neighborhoods without rereading the entire flat\-text artifact at each update\. Under a controlled shift protocol across 10 evolution batches, replicated evaluation shows that GRACE sustains later\-checkpoint improvement more reliably than both HCE and GRACE without SA\. The ablation clarifies the mechanism\. Contradiction avoidance helps, but durable improvement also requires active consolidation of the growing instruction substrate\.

The evidence is still limited to the telecom domain ofτ2\\tau^\{2\}\-bench with a fixed agent model and harness\. Future work should evaluate GRACE across additional domains and against full prior context\-evolution systems under matched implementation budgets\. Within the controlled substrate\-level setting studied here, the main lesson is direct\. Long\-horizon context evolution is easier to verify when relationships among accumulated instruction units are explicit and local enough to inspect\.

## References