Skip to content

From Noisy Traces to Root Causes: Structural Trajectory Analysis and Causal Extraction for Agent Optimization

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

Why this paper was selected

Causal extraction from noisy agent traces; directly improves long-horizon agent optimization

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

STRACE is an agent optimization framework that treats execution traces as causal graphs rather than linear text, enabling LLM-based optimizers to target root-cause modules rather than downstream symptom nodes. It combines batch-level failure pattern mining with intra-trace backward dependency slicing to construct high signal-to-noise optimization contexts. On VeruSAGE-Bench (formal verification), it improves success rate from 42.5% to 58.5%, a 1.4× gain over human-expert-designed agents.

Problem

Reflection-based agent optimization (LLM-as-optimizer over execution traces) fails at scale because: (1) large batches of heterogeneous failure traces cause redundancy and overfitting to low-value failures; and (2) individual trajectories contain many non-causal steps, but naive context reduction (truncation, sliding windows) severs long-range causal links between upstream root causes and downstream manifestation nodes. The result is optimizers that patch symptoms rather than origins.

Method

STRACE operates in four phases:

  1. Structural Modeling: An LLM reads the agent's source code and constructs a textual Execution Dependency Graph (EDG) \(G = (V, E)\), where \(V\) are atomic functional modules and \(E\) encode data dependencies (artifact production/consumption) and control dependencies (invocation control flow).

  2. Failure Pattern Mining and Trace Filtering: A dynamically generated Python parser extracts per-trace signals (global outcome \(y \in \{\text{Success}, \text{Failure}\}\) and local node status). Two diagnostic dimensions are computed — Statistical Severity (conditional failure probability \(P(\text{global failure} \mid \text{node error})\)) and Structural Path Patterns (recurring pathological invocation sequences, e.g., infinite self-loops). Traces are clustered on these dimensions and a minimal diverse exemplar set of size \(s\) is selected.

  3. Causal Localization: For each representative trace, STRACE identifies the Manifestation Node \(v_m\) (where the error surfaces) and extracts a Causal Slice \(C_{\text{slice}}\) via backward slicing over the EDG — retaining only steps reachable to \(v_m\) through the dependency closure \(\to^*\). A semantic reasoning pass then designates the Root Cause Node \(v_r\) (the upstream logical origin of the defect).

  4. Inductive Policy Optimization: Causal slices grouped by \(v_r\) are abstracted inductively into generalized natural-language heuristics, injected exclusively into the prompt policy of the root-cause module. No executable code is altered.

Key Contributions

  • End-to-end agent optimization framework that models execution logs as structured causal graphs, not monolithic text.
  • Diversity-based trace filtering using statistical severity and structural path pattern clustering to compress heterogeneous failure batches.
  • Backward dependency slicing for causal context distillation, enabling separation of manifestation node from root cause node across arbitrarily long trajectories.
  • Targeted, module-level prompt injection that avoids overfitting to instance-specific failures by synthesizing generalizable heuristics.

Results

  • VeruSAGE-Bench (formal Rust verification, 5 projects, avg. 947-line context): STRACE 58.5% SR vs. Base Agent 42.5% (+16.0 pp), vs. GEPA 47.2% (+11.3 pp). Sub-task highlights: Memory Allocator 88.9% vs. base 66.7%; Storage 61.5% vs. base 46.2%.
  • WebArena (web interaction, 4 domains): STRACE 23.7% overall EM vs. Base 10.8% (+12.9 pp), vs. TextGrad 17.3% (+6.5 pp), vs. GEPA 16.5% (+5.7 pp). Strongest gains on Reddit (36.4% vs. 4.5% base) and GitLab (17.1% vs. 7.3% base).
  • HotpotQA (multi-hop QA, EM): STRACE 68.5% vs. Base 37.0%, vs. GEPA 64.4%, vs. TextGrad 62.0%.
  • Scalability: At 453 training trajectories, STRACE achieves the best cost–performance curve; TextGrad costs escalate rapidly with scale, while STRACE's bottleneck filtering controls context growth.
  • Ablation (VeruSAGE SR): Full STRACE 56%; removing Structural Modeling drops to 48% (+cost); removing Trace Filtering drops to 46% (highest cost $8.45); removing Causal Localization (full trace) drops to 54% with $5.93 cost.

Limitations

  • EDG construction requires LLM access to agent source code; closed-source or black-box agents are not addressed.
  • The fallback trace filtering path (silent failures with no node-level error signals) relies only on global outcome and path patterns, potentially reducing clustering precision.
  • Ablation is reported on VeruSAGE only; ablation results on WebArena and HotpotQA are absent.
  • Evaluation uses a single optimizer backbone (Claude Sonnet 4.5); generalization across optimizer models is assessed only for EDG extraction quality (Appendix B.2), not for end-to-end optimization performance.
  • TextGrad is excluded from VeruSAGE-Bench due to context budget limits (>100k tokens), making the strongest gradient-based comparison unavailable on the hardest benchmark.

Relevance to Agentic AI / LLM Agents

STRACE directly advances the reflexive optimization paradigm — a core mechanism for self-improving LLM agents — by replacing coarse context-compression heuristics with dependency-guided causal analysis. The distinction between manifestation and root cause nodes is fundamental to modular multi-agent systems, where failures routinely propagate across component boundaries before surfacing; this work provides a concrete method for structural credit assignment without requiring differentiable reward signals. The framework's compatibility with existing prompt-optimization harnesses (DSPy, GEPA-style) means it can be adopted as a preprocessing layer, and its success on VeruSAGE-Bench — optimizing a 16-module hierarchical agent on formal verification — demonstrates applicability to state-of-the-art agentic architectures operating at the frontier of difficulty.