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

Source: arXiv:2607.07702 · Published 2026-07-08 · By Ying Chang, Jiahang Xu, Xuan Feng, Chenyuan Yang, Peng Cheng, Yuqing Yang

TL;DR

This paper addresses the challenge of optimizing long-horizon agents through reflection-based mechanisms where large language models (LLMs) optimize agent policies based on execution traces. Real-world agent execution traces are large, heterogeneous, and noisy, resulting in inefficient optimization and overfitting to low-value failures. Prior context reduction methods such as truncation discard causal information and introduce misleading signals. The authors propose STRACE, a novel framework that treats execution logs as structural dependency graphs instead of linear text, enabling improved trace filtering, causal localization, and focused policy optimization. STRACE first mines failure patterns to select a diverse representative subset of failure traces and then extracts minimal causal slices from these traces to isolate root causes rather than mere symptoms. Finally, STRACE applies inductive abstraction to synthesize module-level heuristics for policy improvement. Empirical results on benchmarks HotpotQA, WebArena, and VeruSAGE-Bench show STRACE significantly outperforms prior baselines across diverse reasoning and long-horizon agent tasks. In particular, on the challenging formal verification VeruSAGE-Bench, success rate increased from 42.5% to 58.5%, a 1.4× relative gain over the base agent and 11.3% over the best baseline. Ablations confirm the necessity of structural modeling, trace filtering, and causal localization for both effectiveness and cost savings. This work effectively bridges the gap between raw execution trace analysis and targeted agent policy repair by leveraging dependency-guided causal reasoning and trace pattern mining.

Key findings

• STRACE improves success rate on VeruSAGE-Bench from 42.5% (base) to 58.5%, a +16.0% absolute gain and +11.3% over strongest baseline GEPA (47.2%).
• On HotpotQA, STRACE achieves 68.5% Exact Match, outperforming baseline agents by up to +12.9% absolute.
• STRACE reduces optimization cost compared to full-trace methods like TextGrad while maintaining higher success rates, showing a favorable cost-performance tradeoff across up to 453 trajectories (Fig 3).
• Removing structural modeling or trace filtering reduces success rates by 8-10%, increases optimization cost by up to 3×, and decreases efficiency (Table 2).
• STRACE’s causal localization phase remaps 48% of failure traces from manifestation nodes to correct root cause nodes, improving optimization targeting and breaking error propagation loops (Figure 4).
• STRACE’s trace filtering clusters heterogeneous failures based on statistical severity and structural call-path patterns to select diverse, representative exemplars for optimization, reducing redundant data volume.
• STRACE supports fallback to global outcome plus structural patterns when node-level error signals are absent, maintaining representative trace selection.
• STRACE’s inductive policy optimization synthesizes generalized heuristics applied as prompt updates to specific root-cause modules instead of ad hoc trace-level patches.

Threat model

STRACE assumes the optimizer has full or partial white-box access to the agent's source code, modular structure, configuration, and execution logs. The adversary considered is not malicious but rather environmental complexity and noise, producing heterogeneous and redundant failure traces. The system does not consider actively adversarial agents that hide causal structure or deliberately obfuscate failures. The framework assumes truthful, sufficiently rich observational data to enable causal dependency extraction.

Methodology — deep read

The paper addresses the problem of inefficient and noisy optimization of long-horizon agent policies based on complex execution traces, where large trace collections contain redundant, heterogeneous failure data and within-trace noise obscures root causes.

1. Threat Model & Assumptions: The adversary notion is implicit: the system assumes availability of agent code and execution traces with sufficient visibility into modules and control flow. The optimizer cannot operate purely as a black box; it needs to access module-level artifacts, logs, and dependencies. Adversarial tampering or obfuscation of logs is not considered.

2. Data: The authors evaluate on three public benchmarks with execution traces derived from deployed agents: HotpotQA multi-hop question answering (150/300 train/test split), WebArena web tasks covering various domains, and VeruSAGE-Bench formal verification workflows over five real-world Rust projects. VeruSAGE-Bench has extremely long context lengths (~947 lines on average). Each benchmark contains thousands of execution traces labeled success/failure and node-level error signals when available.

3. Architecture and Components: STRACE operates in four integrated phases: • Structural Modeling: An LLM parses the agent's codebase to construct an execution dependency graph (EDG) representing modules as nodes and data/control dependencies as edges. • Failure Pattern Mining & Trace Filtering: A Python parser extracts structured signals from raw traces (global outcomes, node errors). Statistical severity metrics and call-path pattern mining identify dominant failure types. Traces are clustered by severity and structural patterns, then a compact diverse set of exemplars is selected. • Causal Localization: For each representative failure trace, backward slicing on the EDG is performed from the manifestation node to identify a minimal causal slice containing only steps causally contributing to failure. The root cause module is isolated by tracing initial logic deviations upstream. • Inductive Policy Optimization: Aggregated causal slices grouped by root cause modules are abstracted into persistent heuristics, formulated as natural language prompt instructions, and injected into the relevant module's policy.

4. Training & Optimization: The optimization is iterative with up to 20 repair attempts or 20 minutes per task. Batch sizes and exemplar counts are controlled (bottleneck threshold k=5, exemplar count s=5). Optimization uses Claude Sonnet 4.5 as the reflection-based meta-controller with temperature 1.0.

5. Evaluation Protocol: Metrics include Exact Match for HotpotQA and Success Rate for WebArena and VeruSAGE-Bench. Baselines include static heuristic methods, retrieval approaches, full-trace gradient-based (TextGrad), and evolutionary optimization (GEPA). Ablations remove individual STRACE components to assess their contribution. Cost is evaluated in USD estimated from token usage at fixed API pricing.

6. Reproducibility: Code and instructions are publicly released (github.com/moomight/STRACE). Benchmarks are standard public datasets. Certain core models like Claude Sonnet 4.5 used for optimization are proprietary but publicly accessible via API. Dataset splits and preprocessing are documented in detail. Dependency graph construction and diagnosis parsing benefit from deterministic scripts.

Example end-to-end: Starting with thousands of heterogeneous agent execution traces, STRACE first constructs a module dependency graph from code. Then, it parses logs to extract node-level errors and global success/failure signals, mining severity and recurring call paths. It clusters traces by these failure signatures and selects a minimal representative subset. For each selected trace, a backward slice is extracted over the dependency graph to isolate only causal steps leading to the manifestation of failure. The root cause module responsible for the logical deviation is identified. Aggregated causal slices for this root cause are condensed into general heuristics, which are injected as text prompt updates to optimize agent behavior. This process yields targeted, effective optimization at manageable cost.

Technical innovations

• Formulating execution trace filtering and optimization context construction as a structured causal graph extraction problem rather than linear text processing.
• Combining statistical failure severity with structural call path pattern mining to select diverse, representative trace exemplars for optimization.
• Performing causal localization by backward slicing on a textual execution dependency graph to extract minimal causal slices that isolate root-cause modules rather than failure symptoms.
• Inductive synthesis of generalized natural language heuristic policies applied at the root-cause module level, enabling targeted and persistent agent policy improvement.

Datasets

• HotpotQA — 150/300 train/test split — public multi-hop QA benchmark
• WebArena — multiple web task domains (Shopping, CMS, Reddit, GitLab) — public
• VeruSAGE-Bench — 5 Rust projects (IronKV, Memory Allocator, Node Replication, NRKernel, Storage) with 80%/20% train/test splits — public formal verification benchmark

Baselines vs proposed

• Base Agent (VeruSAGE-Bench): Success Rate = 42.5%
• GEPA (evolutionary baseline): Success Rate = 47.2% vs STRACE = 58.5%
• TextGrad (full-trace gradient baseline, omited on VeruSAGE-Bench due to cost): Success Rate not available
• Naive Few-shot (static prompt baseline): Success Rate = 39.6% vs STRACE = 58.5%
• Summary-based Selection: Success Rate = 45.3% vs STRACE = 58.5%
• Retrieval-based Selection: Success Rate = 41.5% vs STRACE = 58.5%
• STRACE outperforms all baselines across HotpotQA, WebArena, and VeruSAGE-Bench with absolute gains up to +16.0% and relative gains up to +1.4×

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.07702.

Fig 1: Comparison of context construction strate-

Fig 2: Illustration of the STRACE framework. The system optimizes long-horizon agents via four phases: (1)

Fig 3: Success rate on 50 independent tasks and

Fig 4: Distinguishing Symptoms from Root

Fig 5: Visualization of a Failure Summarization Map generated during the optimization of the IronKV project.

Fig 6: Instruction for Phase 1–Structural Modeling.

Fig 7: Instruction for Phase 2 – Failure Pattern Mining and Trace Filtering.

Fig 8: Instruction for Phase 3 – Causal Localization.

Limitations

• STRACE requires access to the agent's codebase and/or execution harness to construct dependency priors; it cannot directly optimize black-box agents lacking internal visibility.
• The method assumes availability of structured execution logs with node-level error signals; fully silent or opaque failures may degrade performance.
• The dependency graph construction relies on heuristics and LLM parsing of code, which may be brittle or incomplete for very complex or dynamically evolving agents.
• No direct adversarial evaluation was conducted; robustness to noisy, adversarial, or corrupted logs is unclear.
• The approach focuses on optimization within the context window constraints of current LLMs, limiting scalability to extremely large trace corpora without further compression.
• Generalization was tested on a subset of formal verification and reasoning benchmarks; applicability to other agent domains remains to be explored.

Open questions / follow-ons

• How can STRACE be extended to work with fully black-box agents or agents with limited internal visibility, relying only on end-to-end traces?
• Can the causal localization approach be adapted to handle noisy or adversarial execution logs where error manifestations are obscured or misleading?
• How to scale STRACE to even larger trace collections and more complex agent workflows with thousands of components and longer time horizons?
• What are the theoretical guarantees on causal root cause identification accuracy and how do errors in dependency graph extraction propagate to optimization outcomes?

Why it matters for bot defense

For bot-defense and CAPTCHA application engineers, STRACE offers a compelling approach to diagnosing and optimizing complex multi-step agentic workflows. Execution traces from chatbot or agent interactions often contain noisy, redundant data and subtle causal dependencies between user inputs, multi-stage interactions, and failure modes. STRACE’s methodology of constructing explicit structural dependency graphs, mining representative failures, and performing causal localization can help developers pinpoint root causes of problematic behaviors (e.g., erroneous challenge generation, false positives/negatives) rather than reactive symptom fixes. This causal understanding can enable more precise and data-efficient policy optimization when tuning LLM-based CAPTCHAs or bot detectors. Moreover, STRACE’s principled trace filtering reduces computational overhead and risk of overfitting to spurious failure signals common in bot logs. The inductive policy synthesis phase also aligns with ongoing efforts to learn interpretable heuristic rules that improve CAPTCHA reliability while minimizing user friction. However, adaptation to bot-defense settings may require extending STRACE’s visibility assumptions, as many deployed bot-detection systems treat agents as black boxes with limited access to internal decision pathways. Overall, the paper highlights the importance of structured execution log analysis and causal attribution for improving agentic systems in any multi-component, multi-step environment — including CAPTCHAs or related bot-defense LLM workflows.

Cite

@article{arxiv2607_07702,
  title={ From Noisy Traces to Root Causes: Structural Trajectory Analysis and Causal Extraction for Agent Optimization },
  author={ Ying Chang and Jiahang Xu and Xuan Feng and Chenyuan Yang and Peng Cheng and Yuqing Yang },
  journal={arXiv preprint arXiv:2607.07702},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.07702}
}

Read the full paper

• arXiv:2607.07702 (abstract)
• arXiv:2607.07702 (PDF)