🤖 AI

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

This paper introduces Graph-Regularized Agentic Context Evolution (GRACE), a method that structures persistent system instructions as typed semantic graphs to enable local verification of updates, thereby significantly improving the long-horizon reliability of LLM agents under distribution shift compared to flat-text baselines.

Original authors: Dan C. Hsu, Luke Lu

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dan C. Hsu, Luke Lu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are training a super-smart robot assistant to handle customer calls for a phone company. You can't reprogram the robot's brain every day, and you can't change the tools it uses. The only thing you can tweak is its "rulebook"—a long list of instructions telling it how to behave, what to say, and what to avoid.

This paper, GRACE, asks a simple but tricky question: How do you keep updating that rulebook over a long time without it turning into a messy, contradictory disaster?

The Problem: The "Flat Text" Trap

Most people try to update the rulebook by just rewriting the whole thing or adding new paragraphs to the bottom of a long text document. The authors call this "flat-text maintenance."

Think of this like a group chat where everyone just keeps typing new rules at the bottom. At first, it works great. But after a few weeks, the chat is 500 pages long. You have a rule on page 10 that says "Always be polite," and a new rule on page 499 that says "Be blunt when angry." The chat doesn't know these contradict each other. The robot gets confused, starts making mistakes, and eventually, the whole system breaks down. The paper shows that when you just keep adding text, the robot's reliability actually drops back down after a while.

The Solution: The "Smart Map" (GRACE)

The authors propose a new way called GRACE (Graph-Regularized Agentic Context Evolution). Instead of a long list of text, they turn the rulebook into a structured map (a graph).

Imagine the rules aren't just lines of text, but nodes (dots) on a map, connected by lines that show how they relate.

One dot is a "Rule" (e.g., "Be polite").
Another dot is a "Fact" (e.g., "Customers are tired").
A line connects them saying, "This fact supports this rule."

When the robot makes a mistake, the system doesn't just write a new paragraph. It looks at the map. It finds the specific dot (the rule) that caused the trouble and checks its immediate neighbors.

Does this new idea clash with the rules right next to it? (Contradiction check)
Is this new idea just a repeat of an old one? (Redundancy check)

If the new idea fits the local neighborhood of the map, it gets added. If it breaks the map's logic, it gets rejected or fixed immediately. Finally, the system translates the updated map back into the text the robot actually reads.

The Experiment: A Tug-of-War

The researchers tested this in a simulated telecom environment (a fake phone company) using a specific robot model (Gemini 2.5 Flash). They ran the simulation five times to be sure the results weren't just luck. They changed the types of customer calls the robot faced every few rounds to see if the rulebook could adapt without falling apart.

Here is what happened:

The Starting Point: Before any updates, the robot was terrible at being reliable. It only passed the strictest test (getting the job right three times in a row) 0.091 of the time (about 9% of the time).
The "Flat Text" Team (HCE): They tried the old way of just adding text. The robot got a little better at first, reaching 0.215, but then it started to slip. By the end, it was back down to 0.191. The rulebook got too messy, and the robot forgot how to be consistent.
The "Map Without Checks" Team: They used the map but didn't check for contradictions or redundancy. They got a decent boost to 0.458, but then they crashed hard, ending at 0.248. The map helped organize things, but without the "neighborhood check," the rules still piled up into a mess.
The GRACE Team: This team used the map and the strict neighborhood checks. They started at 0.091 and climbed steadily. By the final checkpoint, they were passing the strict test 0.673 of the time (about 67%).

The Big Comparison: Even a brand-new, much smarter robot model (Gemini 3.1 Pro) starting from scratch without any updates only managed 0.242. The GRACE team, using an older robot model but a smarter update system, beat the new robot by a huge margin.

What This Means (and What It Doesn't)

The paper suggests that for a robot to keep learning over a long time without breaking, you can't just keep piling on text. You need a structure (like a map) that lets you check if new ideas fit with the old ones locally, right where they connect.

However, the authors are careful to say this isn't a magic bullet for everything.

They only tested this in a telecom customer service simulation. They don't know yet if it works for coding, medical advice, or driving cars.
They only tested it with one specific robot model and one specific set of tools.
The results are based on simulations (computer tests), not real-world phone calls with real humans.

But the lesson is clear: If you want a robot to evolve its personality and rules over months or years, you need to stop treating its instructions like a diary and start treating them like a well-organized map. If you don't check the neighborhood before adding a new house, the whole city eventually collapses.

Technical Summary: Scoped Verification for Reliable Long-Horizon Agentic Context Evolution (GRACE)

1. Problem Formulation

The paper addresses the challenge of long-horizon agentic context evolution under a fixed operational harness. In deployed Large Language Model (LLM) agent systems, the "agent context" is assembled from task inputs, tool observations, and a persistent system-level instruction that defines the agent's role, constraints, and domain assumptions.

When task distributions shift over time, this persistent instruction must be revised based on operational experience to remain effective. However, maintaining this instruction as flat text leads to significant failure modes as the artifact grows:

Context Collapse: Inconsistencies accumulate, undermining previous improvements.
Verification Difficulty: As the document grows, verifying relationships between rules, constraints, and procedures becomes increasingly dependent on long-context processing, making it difficult to detect contradictions or redundancy.
Unbounded Growth: Without structural management, instruction content can grow unmanageably, leading to guideline conflicts and degraded reliability.

The core problem is isolating the representation substrate used for evolution. The paper asks whether a structural representation can sustain verification effectiveness and consolidation over extended evolution horizons compared to flat-text maintenance, while keeping the model, tools, and harness fixed.

2. Methodology: GRACE

The authors propose Graph-Regularized Agentic Context Evolution (GRACE), a framework that maintains the persistent instruction as a typed semantic graph rather than flat text. The deployed artifact remains textual, but the evolution process operates on the graph substrate.

2.1 Graph-Regularized Substrate

GRACE represents the instruction as a directed typed graph $G_t = (V_t, E_t)$ :

Nodes ( $V$ ): Encode atomic instruction units, categorized into three object types:
- identity: Agent standing (mandate and subject).
- norm: Conduct rules (standards to satisfy or breach).
- knowledge: Domain premises (reasoning foundations).
Edges ( $E$ ): Encode structural relations, categorized into:
- supports: Grounding or justification.
- refines: Specialization (adding conditions/exceptions).
- sequence: Procedural ordering.
Schema Constraints: A network schema $\mathcal{T}_G$ defines admissible source-target type pairs for relations, ensuring all updates are schema-conformant.

2.2 Evolution Pipeline

The evolution operator $F_{Evolve}$ transforms the previous state $(G_{t-1}, \ell_{t-1}, o_t)$ into the next state $(G_t, \ell_t)$ through three stages:

Operation Planning:
- An LLM-mediated planner converts a diagnostic observation (derived from failed agent interactions) into a set of typed graph edits $\Delta^{edit}_t$ (e.g., AddNode, ModifyNode, AddEdge).
- These edits are deterministically applied to create an intermediate graph $\hat{G}_t$ .
- A relation-maintenance module reviews relations incident to edited nodes and proposes additional relation-level edits $\Delta^{rel}_t$ .
Structural Validation (Scoped Verification):
- Instead of re-reading the entire text, validation focuses on local typed neighborhoods.
- A validation radius $k$ defines a neighborhood $N_k$ around the "touched" nodes (those modified in the planning stage).
- Structural Analysis (SA) inspects this local subgraph for two semantic issues:
  - Contradiction: Detects joint unsatisfiability where overlapping instruction units cannot be simultaneously satisfied.
  - Redundancy: Detects lack of marginal semantic contribution where one unit subsumes another without structural differentiation (e.g., distinct support neighborhoods).
- Detected issues are repaired using schema-conformant operations.
Delta Reconstruction:
- The validated graph $G_t$ is converted back into the textual instruction checkpoint $\ell_t$ .
- This is done via incremental edits aligned with the graph-level changes, preserving unaffected content and formatting.

3. Experimental Setup

Domain: Telecom customer service, derived from $\tau^2$ -bench.
Protocol: A controlled distribution-shift protocol over 10 evolution batches. The experience batches alternate between two intent-mixture phases (Phase A and Phase B) to test retention and adaptation.
Conditions:
1. GRACE: Full method (Graph substrate + Structural Analysis).
2. GRACE w/o SA: Graph substrate without Structural Analysis (ablation).
3. HCE (Holistic Context Evolution): Flat-text baseline with a built-in consistency guard.
Metrics:
- pass@k: Capability (best-of-k).
- pass^k: Strict reliability (all-k trials must succeed).
- Backward Transfer (BWT): Retention of performance on specific intents after the distribution shifts away from them.
Model: Agent model is fixed at Gemini 2.5 Flash. Diagnosis and evaluation use fixed procedures.

4. Key Results

Across five independent replications, GRACE demonstrated superior reliability and retention compared to baselines:

Sustained Improvement: GRACE improved strict reliability (pass^3) from a zero-shot baseline of 0.091 to 0.673 ± 0.136 at the final checkpoint ( $\ell_{10}$ ).
Comparison to Baselines:
- HCE (Flat Text): Improved initially but degraded over time, finishing at 0.191 ± 0.051. It suffered from "context collapse" as the instruction grew.
- GRACE w/o SA: Improved initially (0.458 at $\ell_6$ ) but failed to consolidate gains, dropping to 0.248 ± 0.144 at $\ell_{10}$ .
Reference Performance: The final GRACE checkpoint (0.673) exceeded a Gemini 3.1 Pro zero-shot reference of 0.242 on the same held-out set.
Failure Mode Analysis:
- HCE accumulated high contradiction counts (avg 3.35) and large instruction sizes (82,592 chars), leading to coherence loss.
- GRACE w/o SA maintained low contradiction counts but failed to consolidate, resulting in higher redundancy (avg 4.85) and uncontrolled growth.
- GRACE maintained low contradiction (1.75–1.90) and lower redundancy (4.15), effectively consolidating the instruction substrate.
Retention: GRACE showed positive or zero backward transfer in most cycles, whereas HCE exhibited persistent negative backward transfer, indicating a loss of capability when distributions shifted.

5. Contributions and Significance

The paper makes three primary contributions:

Graph-Regularized Substrate: Introduces a typed semantic graph as an intermediate representation for evolving persistent agent instructions, enabling scoped structural validation that focuses on local neighborhoods rather than global text re-reading.
Evaluation Protocol: Proposes a controlled distribution-shift protocol that tests both within-phase improvement and cross-phase retention, isolating the effects of representation and verification mechanisms.
Mechanism Insight: Through ablation, the paper identifies two distinct requirements for reliable long-horizon evolution:
- Structural Substrate: Necessary to make verification local and prevent gross contradictions.
- Consolidation Mechanism: Necessary (via Structural Analysis) to merge overlapping content and resolve subtle tensions, preventing unbounded growth and redundancy.

Significance:
The paper argues that for reliable long-horizon context evolution, the representation of the evolving artifact is critical. Flat-text maintenance becomes increasingly difficult to verify as the artifact grows. GRACE demonstrates that maintaining instructions as a typed graph with local structural validation allows agents to sustain reliability and adapt to distribution shifts more effectively than flat-text approaches or graph approaches lacking consolidation. The work suggests that "relationships among accumulated instruction units" must be explicit and local enough to inspect to ensure durability.

Limitations:
The authors note that the evidence is currently limited to the telecom domain of $\tau^2$ -bench with a fixed agent model and harness. Future work is required to evaluate GRACE across additional domains and against full prior context-evolution systems under matched implementation budgets.