🤖 AI

TraceGraph: Shared Decision Landscapes for Diagnosing and Improving Agent Trajectories

TraceGraph introduces a graph-based framework that transforms multi-model agent trajectories into shared decision landscapes to reveal hidden navigation differences and failure patterns, which in turn enables a trap-aware recovery pipeline that significantly improves resolution rates on the SWE-bench.

Original authors: Junjie Nian, Kang Chen, Ge Zhang, Yixin Cao, Yugang Jiang

Published 2026-06-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Junjie Nian, Kang Chen, Ge Zhang, Yixin Cao, Yugang Jiang

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 watching a group of five different explorers trying to solve a complex maze. In the past, if you wanted to know who was the best explorer, you would just look at the final score: "Did they reach the exit? Yes or No?"

The paper TraceGraph argues that this "Yes or No" score hides too much. It's like judging a chef only by whether the cake was eaten, without noticing if one chef burned the kitchen down to get there, while another took a scenic route through the garden.

Here is how TraceGraph works, explained simply:

1. The Shared Map (The Decision Landscape)

Instead of looking at each explorer's path in isolation, TraceGraph takes all their steps and merges them onto one giant, shared map.

The Steps: Every time an AI agent (the explorer) takes an action (like "read a file" or "run a test") and sees a result, it leaves a "footprint."
The Clustering: TraceGraph looks at these footprints. If two steps look very similar (e.g., both are trying to fix a specific error in the same file), it draws a line connecting them.
The Result: This creates a web or a "landscape" of the task. Some areas are safe and lead to success; others are dead ends.

2. The Three Key Events

Once the map is built, TraceGraph watches how each AI moves across it. It doesn't care about the final score yet; it cares about three specific moments:

Access: Did the AI find the "productive core"? (The safe, high-value area where good work happens).
Trap Exposure: Did the AI wander into a "trap"? (A confusing area where many others have failed or gotten stuck).
Repair: If the AI fell into a trap, did it manage to climb out and get back to the productive core?

3. What the Map Revealed

When the researchers looked at this shared map, they found things that simple scores missed:

Different Styles: Some models (like DeepSeek-V3.2) were brave explorers. They often found the productive core, sometimes fell into traps, but were very good at climbing out (Repair). Others (like Qwen3-Next) were very cautious. They rarely fell into traps, but they also rarely found the productive core because they were too afraid to explore.
Different Rules for Different Mazes: The researchers tested this on five different types of tasks (like fixing software bugs, searching the web, or using tools). They found that some mazes reward avoiding traps (don't make a mistake!), while others (like fixing software bugs) reward recovering from mistakes. A model that is great at avoiding traps might actually fail at a task where you need to be able to recover from a mistake.

4. The "Trap Detector" Experiment

The most exciting part is how they used this map to help the AI in real-time.

The Idea: Since they knew exactly what a "trap" looked like on the map (a specific pattern of actions and errors), they built a detector.
The Trigger: When an AI was solving a new problem and stepped into a pattern that matched a known "trap," the detector would sound an alarm.
The Rescue: When the alarm went off, the system didn't just let the AI keep failing. It paused and tried two simple fixes:
1. The "Hot" Fix: It told the AI to try again with a bit more randomness (like shaking the dice) to see if a different path worked.
2. The "Note" Fix: It gave the AI a gentle reminder note based on the error: "Hey, you seem stuck here. Re-read the error, focus on this specific file, and try one small change."

The Result: On a software repair task (SWE-bench), using this trap detector helped the AI fix about 3 to 4% more problems than it could on its own. It proved that knowing where the traps are allows you to build a safety net that catches the AI before it fails.

Summary

TraceGraph is a tool that stops us from just looking at the final score of an AI. Instead, it builds a shared map of how AI agents move through tasks. It shows us:

Which models are brave explorers vs. cautious walkers.
Which tasks require avoiding mistakes vs. recovering from them.
How to build a simple "safety net" that detects when an AI is about to fall into a known trap and gives it a second chance to fix it.

It turns the black box of "AI failed" into a clear story: "The AI walked into a trap, but with a little help, it could have climbed out."

Technical Summary: TraceGraph – Shared Decision Landscapes for Diagnosing and Improving Agent Trajectories

1. Problem Statement

Current agent benchmarks increasingly record rich, interleaved interaction trajectories (thoughts, tool calls, environment feedback). However, evaluation practices typically collapse these complex processes into a single scalar metric (e.g., pass/fail rate or reward score). While such scores rank systems, they obscure the underlying process dynamics: they fail to reveal how models navigate task spaces, where they diverge in strategy, or whether they avoid failure regions or recover from them.

The core challenge is the lack of a shared coordinate system for comparing trajectories across different models. Agent states are long, branching, and benchmark-specific, mixing tool choices, file cues, and partial evidence. Without alignment, it is difficult to determine if Model A reached an analogous state to Model B, avoided the same failure region, or recovered via a different route. Existing methods often inspect individual trajectories in isolation or rely on aggregate scores that hide process diversity.

2. Methodology: The TraceGraph Framework

TraceGraph is a graph-based framework that transforms pooled agent rollouts into a shared decision landscape. It operates in three stages, constructing a model-agnostic map of the task space before analyzing specific model behaviors.

Stage 1: Building the Shared Landscape

The framework ingests action–observation steps from multiple models and tasks.

Encoding: Each step $i$ is encoded as a sparse set of observable keys $K_i$ , including tool/action types, command classes, observation patterns (e.g., error traces), file cues, and temporal phases. For search tasks, specific keys for URL domains and query novelty are added.
Similarity & Graph Construction: Pairwise similarity is calculated using an IDF-weighted Jaccard overlap over key sets. Rare, informative keys (e.g., specific traceback patterns) weigh more heavily than generic ones.
Topology: A mutual- $k$ $k$ NN graph is built over all pooled steps. This graph is decomposed into Biconnected Components (BCCs) and articulation points (gates).
- BCCs group steps with dense mutual similarity, representing coarse shared agent states.
- Articulation points mark strategy or phase transitions where a rollout can branch into qualitatively different continuations.
Model Agnosticism: Model identity is excluded from the signature and graph construction. The landscape is defined solely by the observable state space.

Stage 2: Outcome-Informed Overlays

Once the graph structure is fixed, the framework overlays outcome data to identify "productive cores" and "trap regions."

Reward Diffusion: For each BCC block, a Laplace-smoothed reward is assigned based on the terminal outcomes of rollouts visiting that block. This reward is then diffused across the block quotient graph to smooth local noise.
Region Definition:
- Productive Core ( $C_t$ ): High-positive quantiles of the diffused reward field.
- Trap Regions ( $B_t$ ): Low-negative quantiles of the diffused reward field.
These overlays are descriptive, locating where high- and low-outcome traffic concentrates, rather than predicting outcomes for unseen runs.

Stage 3: Rollout Event Summarization

Each model's trajectory is summarized by three discrete events defined on the core/trap overlays:

Access ( $A_r$ ): Did the rollout intersect the productive core?
Trap Exposure ( $E_r$ ): Did the rollout intersect a trap region?
Repair ( $R_r$ ): Did the rollout visit a trap and subsequently reach a core?

Analysis: Supply and Demand Profiles

TraceGraph generates two descriptive profiles:

Model Supply: The task-centered mean of a model's events relative to the average model. This reveals a model's "navigation style" (e.g., high-access/high-repair vs. conservative/shallow).
Benchmark Demand: The reward-weighted contrast between high- and low-outcome traffic. This reveals what a specific benchmark rewards (e.g., trap avoidance vs. recovery).

3. Key Contributions

TraceGraph Framework: A method to construct model-agnostic task graphs from pooled rollouts and overlay outcome-informed regions to create a shared decision landscape.
Compact Process Profiles: A demonstration that across five benchmark splits (7,329 records, 427 tasks, 5 models), the events of Access, Trap exposure, and Repair separate model navigation styles and benchmark demands that aggregate scores collapse.
TraceGraph-Guided Recovery Pipeline: A practical application on SWE-bench where graph-derived trap regions serve as runtime triggers. When a live agent enters a historical trap region, a lightweight recovery policy is activated.

4. Experimental Results

Diagnostic Insights

Model Diversity: Aggregate scores often hide process differences. For instance, on a shared landscape, DeepSeek-V3.2 exhibits a "high-access, high-repair" style, while Qwen3-Next shows "low-access, low-repair" (conservative, shallow navigation).
Benchmark Heterogeneity: Benchmarks impose different process demands:
- $\tau^2$ -bench, MCPBench, TerminalBench: Strongly trap-averse (high outcomes correlate with avoiding low-outcome regions).
- SWE-bench: Strongly repair-demanding (high outcomes correlate with recovering from trap-like states after initial failure).
- Search: Rewards productive evidence access with occasional recovery.

Recovery Experiment (SWE-bench)

The authors instantiated a trap-aware prefix-fork pipeline on SWE-bench Verified instances (500 total).

Mechanism: A detector fires when a live rollout matches a canonicalized trap signature. Upon firing, the agent continues from the same state under three policies:
1. Baseline: Standard continuation ( $T=0.6$ ).
2. Hot: Increased sampling diversity ( $T=0.9$ ).
3. Note: A conservative, evidence-grounded diagnosis note appended to the context (no gold patches).
Results:
- On the per-provider fired subset ( $n=616$ ), the best pooled policy (Hot) raised the resolved rate from 40.4% to 43.5% (+3.1 pp, $p=0.016$ ).
- On the common-fired subset ( $n=288$ ), the Hot policy raised the rate from 41.0% to 44.8% (+3.8 pp, $p=0.045$ ).
- Provider Specificity: The active recovery component varied by provider. Qwen3.6-35B-A3B benefited most from the diagnosis note, while GLM-5.1 and DeepSeek-V4-Pro benefited most from the temperature bump.

5. Significance and Claims

The paper positions TraceGraph not as a new scalar score or a blind success predictor, but as a process vocabulary for agent evaluation.

Descriptive Power: It reveals what a benchmark tests (e.g., avoidance vs. recovery) and where models diverge on a shared landscape.
Actionable Guidance: It demonstrates that graph-derived traps can guide downstream interventions. By identifying historical failure regions, the framework enables targeted recovery policies that improve task resolution rates without requiring oracle information or full re-training.
Modesty: The authors emphasize that the recovery pipeline is a local intervention on a specific subset of SWE-bench and is not claimed as a universal agent-repair mechanism. The framework is an analytical instrument for explaining traffic concentration, not a controller for all agent behaviors.

In summary, TraceGraph shifts the focus from "how many tasks did the agent solve?" to "how did the agent navigate the task landscape, and where did it get stuck or recover?" providing a structural basis for understanding and improving agent trajectories.