PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ying Chang, Jiahang Xu, Xuan Feng, Chenyuan Yang, Peng Cheng, Yuqing Yang

arXiv:2607.07702v1cs.CL

TL;DR

Long-horizon agent optimization struggles to extract useful causal evidence from noisy, redundant execution traces. STRACE filters representative failures and localizes root causes, outperforming baselines and improving VeruSAGE-Bench success rates from 42.5% to 58.5%.

  • Problem

    Optimizing agents from execution trajectories remains difficult because traces are noisy, redundant, and may obscure upstream root causes.

  • Method

    STRACE treats execution logs as causal graphs, mining failure patterns to filter representative traces and localizing causal steps for targeted policy optimization.

  • Results

    Absolute success rates on VeruSAGE-Bench increased 16.0%, from 42.5% to 58.5%, while STRACE significantly outperformed state-of-the-art baselines across three benchmarks.

  • Takeaways & Limitations

    STRACE provides a flexible framework for cost-efficient, high-performing optimization of complex long-horizon agents and can guide updates to editable harness components.

  • Takeaways & Limitations

    STRACE requires sufficient system-level visibility into the agent implementation or harness and is not directly applicable to fully black-box agents.

Abstract

from arXiv · show

The optimization of long-horizon agents increasingly relies on reflection-based mechanisms, where a large language model (LLM) acts as an optimizer to diagnose agent failures and improve agent policies. However, real execution traces are difficult to use directly for optimization: large trace collections are often redundant and heterogeneous, making optimization inefficient and prone to overfitting to low-value failures; meanwhile, each individual trajectory also contains many irrelevant steps, while naive context reduction methods such as truncation or sliding windows can discard causally important evidence and produce misleading optimization signals. To resolve this dilemma, we introduce STRACE (Structural TRajectory Analysis and Causal Extraction), a framework that constructs high signal-noise optimization contexts for more precise and effective optimization. At the batch level, STRACE mines failure patterns to filter redundant traces and retain representative failures; within each selected trace, it performs causal localization over a textual dependency graph to remove non-causal steps and identify the true root-cause module for optimization. Empirical results demonstrate that STRACE significantly outperforms standard context-filtering baselines. Notably, on a challenging formal verification task (VeruSAGE-Bench), it successfully optimizes human-expert designed agents, delivering $1.4\times$ success-rate improvement (42.5% to 58.5%). The code is available at https://github.com/moomight/STRACE .

1 Introduction

STRACE addresses noisy, heterogeneous execution traces by filtering representative failures across batches and extracting compact causal slices within traces to identify root causes. Across HotpotQA, WebArena, and VeruSAGE-Bench, it significantly outperforms baselines, improving VeruSAGE success rates from 42.5% to 58.5%.

  • Motivation: Reflexive optimization struggles with large, heterogeneous trajectory batches, making direct use of execution data inefficient for diagnosing agent failures.The problem arises in complex long-horizon tasks, where generated data is voluminous and difficult to process.
  • Motivation: Full trajectories can overwhelm optimizers with irrelevant steps, causing low-signal contexts, spurious correlations, and hallucinated prompt patches.STRACE contrasts this with causal context distillation, which extracts a compact causal slice for higher-signal optimization.
  • Motivation: Because downstream error manifestations may originate upstream, optimizers need dependency-aware localization to repair root causes rather than symptoms.A Code Interpreter crash at Step 50 may result from an incorrect Planner parameter generated at Step 5.
  • STRACE: STRACE models execution logs as causal graphs, filters redundant or low-value failures, and traces dependencies backward to extract compact causal slices and root-cause modules.Its pipeline combines structural modeling, failure pattern mining and trace filtering, causal localization, and inductive policy optimization.
  • Results: 16.0% absolute improvement raised VeruSAGE-Bench success from 42.5% to 58.5% across evaluations on HotpotQA, WebArena, and VeruSAGE-Bench.The paper reports significant gains over state-of-the-art, full-trajectory, truncation, and prompt-optimization baselines.

2 Related Work

Related work spans automated prompt optimization, reflexive and self-evolving agents, and credit-assignment methods for attributing outcomes to decisions. However, explicit causal attribution in long-horizon trajectories remains an open challenge.

  • Automated Prompt Optimization: Automated prompt optimization uses LLMs to iteratively search for better instructions, extending from score-based natural-language search to feedback, textual gradients, and evolutionary strategies.These methods target complex, multi-stage workflows through reflexive feedback or modular textual gradients.
  • Reflexive and Self-Evolving Agents: Reflexive and self-evolving agents improve behavior through feedback-driven revision spanning inference-time refinement, verifier-based reinforcement, and code- or architecture-level evolution.Recent harness-level systems additionally use optimizers for agent self-evolution.
  • Credit Assignment: The Credit Assignment Problem concerns attributing outcomes to specific decisions, while reinforcement learning traditionally addresses it through temporal reward redistribution.In modular agents, Structural Credit Assignment instead uses bottleneck penalties or generative critiques to refine reasoning chains.
  • Credit Assignment: Despite advances in temporal redistribution and structural credit assignment, explicit causal attribution in long-horizon trajectories remains an open challenge.This gap motivates methods that identify which trajectory decisions causally produced outcomes.

3 The STRACE Framework

STRACE improves long-horizon agent optimization by increasing context signal-to-noise through structural modeling, representative failure selection, causal localization, and root-cause-targeted policy updates. It constructs an execution dependency graph, preserves diverse failure modes while removing redundant traces, and converts causal slices into reusable heuristics.

  • Structural Modeling: STRACE uses an LLM to construct a textual Execution Dependency Graph whose vertices are functional modules and whose edges encode artifact and execution-path dependencies.The graph captures both data dependencies and control dependencies among modules.
  • Failure Pattern Mining and Trace Filtering: Failure Pattern Mining and Trace Filtering compresses heterogeneous trace batches into minimal exemplar sets that preserve diverse, major failure modes without redundancy.It clusters traces using statistical error severity and structural path patterns, then selects a predefined number of exemplars from each cluster.
  • Failure Pattern Mining and Trace Filtering: STRACE dynamically infers logging schemas from a pilot trace and parses global outcomes alongside local node statuses to support failure diagnosis.The generated parser identifies structural delimiters and records whether specific modules encounter runtime exceptions.
  • Causal Localization: Causal Localization backtracks through the execution structure to remove non-causal steps, producing a high-signal slice that captures the corrupted information flow.Divergent, data-independent exploration branches are bypassed because errors on one branch lack causal links to the others.
  • Inductive Policy Optimization: Inductive Policy Optimization groups purified causal slices by verified root-cause modules and injects generalized, reusable heuristics into those modules’ textual prompt policies.This abstraction targets recurring structural errors rather than instance-specific failure records that risk overfitting.

4 Experiments

STRACE is evaluated on HotpotQA, WebArena, and VeruSAGE-Bench using task-appropriate metrics, and achieves the strongest overall performance across these settings. Analyses show that its gains come from representative-trace selection and causal localization, which improve the cost–performance trade-off and target upstream failure causes.

  • Overall Results: STRACE achieves the strongest overall performance across HotpotQA, WebArena, and VeruSAGE-Bench compared with the unoptimized agent and optimization baselines.The benchmarks cover general multi-hop reasoning, general-purpose web interaction, and domain-intensive formal verification.
  • WebArena Analysis: On WebArena, STRACE remains competitive when workflow guidance matters and achieves clearer improvements when domains require failure-aware rules.Shopping and CMS require more procedural context, whereas Reddit and GitLab benefit more from failure-aware rules.
  • Cost–Performance Scaling: As training data scales, STRACE maintains the most favorable cost–performance trend relative to TextGrad full-trace optimization and GEPA local-node slicing.Its Statistical Bottleneck Diagnosis module selects a small set of representative, high-value exemplars for optimization.
  • Causal Localization: 12 of 25 traces are re-mapped to upstream root-cause actions, expanding optimization targets to 6 distinct nodes.The redistribution includes an additional upstream assertion_reasoning_pipeline module and shows that crash locations can identify the wrong target.
  • Ablation Study: Removing structure modeling lowers effectiveness and raises cost, while removing trace filtering further degrades both performance and efficiency.The ablation uses the same optimization protocol and training traces across variants.

5 Conclusions

STRACE addresses the context-noise trade-off in long-horizon agent optimization by combining failure pattern mining with causal localization for targeted policy optimization. Results across three benchmarks show gains in success rate and efficiency, while localized diagnoses support harness engineering and updates to tunable agent components.

  • Conclusions: STRACE combines failure pattern mining with causal localization to enable targeted, cost-efficient, and high-performing policy optimization.The method is designed for long-horizon agent optimization under the context-noise trade-off.
  • Conclusions: STRACE consistently improves success rate and efficiency on HotpotQA, WebArena, and VeruSAGE-Bench, outperforming all baselines.Ablation studies and further analysis validate the method’s effectiveness.
  • Conclusions: STRACE transfers to harness engineering by using localized diagnoses to guide updates to skills, tool-use policies, and other editable harness components.This transferability makes STRACE applicable to improving complex long-horizon agents.

Limitations

STRACE’s main limitation is its reliance on sufficient visibility into the target agent system, making it most applicable when implementation or harness artifacts are inspectable.

  • STRACE relies on codebase- or harness-level artifacts, limiting direct applicability to agents whose components and control flow are hidden.The dependency prior uses agent definitions, tool interfaces, configuration files, prompts, skills, and execution logs.

Ethical considerations · Appendix

The study uses publicly available resources under their licenses for academic research and benchmarking, without collecting new human-subject data. Results are reported in aggregate, while the authors acknowledge potential implications of stronger agent optimization.

  • Ethical considerations: All datasets, models, and software artifacts used are publicly available.The study follows the respective licenses or terms of use for these resources.
  • Ethical considerations: The study follows the licenses or terms of use governing its research resources.Resource use is described as compliant with the applicable conditions.
  • Ethical considerations: Resource use is strictly confined to academic research and benchmarking purposes.The stated restriction applies to all datasets, models, and software artifacts used in the experiments.
  • Ethical considerations: The study does not collect new human-subject data.This limits the work’s direct involvement with newly gathered human-subject information.
  • Ethical considerations: All reported results are presented in aggregate form.The paper describes aggregate reporting as part of its ethical considerations.
  • Appendix: STRACE is designed to improve the efficiency and reliability of long-horizon agent optimization.The authors frame this design objective within their ethical discussion.

A Agent Implementation Details … B.1 Architecture and Context Management

The paper specifies the architectures and optimization targets for HotpotQA, WebArena, and VeruSAGE-Bench, then describes STRACE as a four-phase workflow with shared context for Phases 1–3 and localized context for Phase 4. These designs range from simultaneous optimization of four HotpotQA module prompts to optimization of a single WebArena instruction prompt and VeruSAGE’s specialized repair components.

  • A Agent Implementation Details: The implementation section details the base agents’ architectural workflows and identifies the sub-agents or prompts targeted for optimization.This provides the setup for the HotpotQA, WebArena, and VeruSAGE-Bench agents.
  • A.1 HotpotQA Agent Workflow: HotpotQA uses four sequential sub-agents for multi-hop reasoning, and STRACE optimizes all four module system prompts simultaneously.The workflow includes first-hop summarization, second-hop query generation, and second-hop evidence integration.
  • A.2 WebArena Agent Workflow: WebArena is a single prompt-based navigation agent that reasons over an accessibility tree, URL, user instruction, and previous action to predict browser actions.Its loop observes the page, reasons and acts, then executes the predicted action in the browser environment.
  • A.2 WebArena Agent Workflow: During WebArena optimization, STRACE targets the agent’s instruction prompt because the baseline has no explicit sub-agents, planners, or external memory modules.The prompt defines the action space, reasoning style, and few-shot behavior examples.
  • A.3 VeruSAGE Agent Workflow: VeruSAGE-Bench uses an iterative multi-agent repair architecture in which verification failures are analyzed, routed among 35 actions, and handled by selected executor sub-agents.The process ends after successful verification or when the budget of 20 attempts or 20 minutes is exhausted.
  • A.3 VeruSAGE Agent Workflow: VeruSAGE comprises 15 specialized sub-agents spanning tasks such as invariant repair, proof-strategy application, prover-mode activation, syntax correction, and standard-lemma guidance.These specialized roles cover distinct formal-verification failure modes.
  • B.1 Architecture and Context Management: STRACE runs on Claude-Agent-SDK as four sequential phases, sharing one context window across Phases 1–3 and separating Phase 4 to focus revision on the root-cause node.The separation reduces unnecessary context overhead and keeps the final revision step focused and modular.

B.2 Textual Dependency Graph Construction … C More Experiments Results

STRACE constructs framework-agnostic textual dependency graphs from repository artifacts, and its optimization remains effective under moderate graph noise while collapsing without the structural prior. Its failure-pattern mining further summarizes heterogeneous traces using statistical severity and recurring structural paths, with reproducible phase instructions provided separately.

  • B.2 Textual Dependency Graph Construction: STRACE’s optimizer inspects repository artifacts, identifies active and passive modules, and constructs a textual dependency graph for Phase 1.The implementation uses the Claude Agent SDK and a dedicated graph-construction instruction.
  • B.2 Textual Dependency Graph Construction: The graph-construction process is framework-agnostic and recovers dependency priors from code, configuration, and agent definitions without framework-specific APIs.
  • B.2 Textual Dependency Graph Construction: All evaluated optimizer models recover the core dependencies, while stronger models produce cleaner graphs and weaker models add roughly 10% noisy edges.The expert-reviewed comparison finds differences mainly in granularity and extra infrastructure-level detail.
  • B.2 Textual Dependency Graph Construction: Removing the dependency graph entirely reduces performance to the base-agent level of 48%, showing that the structural prior is essential for effective optimization.
  • B.2 Textual Dependency Graph Construction: 56% to 54%: removing 25% of graph edges slightly lowers success rate, whereas adding 25% preserves 56%; 10% perturbations preserve or improve performance.STRACE benefits substantially from a dependency prior but does not require it to be perfectly specified.
  • B.3 Visualization of Failure Pattern Mining: Failure-pattern mining converts heterogeneous logs into structured records and aggregates them into dataset-level failure patterns before trace filtering.Figure 5 illustrates the resulting diagnostic summary rather than raw-trace optimization.
  • B.3 Visualization of Failure Pattern Mining: Statistical severity estimates P(Task Fail | vi Fail), prioritizing local failures strongly associated with global failure over low-impact or stochastic errors.Here, vi denotes a local node error extracted from a structured trace record.
  • B.3 Visualization of Failure Pattern Mining: Structural path patterns track module invocation sequences across traces to reveal recurring pathological trajectories for complementary trace filtering.

C.1 Stage-wise Cost Breakdown for the Ablation Study · C.2 Average Turns of VeruSAGE (STRACE-enhanced) Compared to the Base Agent

STRACE’s cost is dominated by downstream inductive policy optimization, while removing structural modeling, trace filtering, or causal slicing substantially increases cost or degrades performance. STRACE-enhanced VeruSAGE also requires fewer repair turns than the base agent across all five VeruSAGE-Bench categories, indicating faster convergence.

  • C.1 Stage-wise Cost Breakdown for the Ablation Study: Phase 1 is Structural Modeling, Phase 2 is Failure Pattern Mining and Trace Filtering, Phase 3 is Causal Localization, and Phase 4 is Inductive Policy Optimization.Stage-wise costs track optimizer-side LLM input and output tokens priced using Claude Sonnet 4.5 API rates.
  • C.1 Stage-wise Cost Breakdown for the Ablation Study: Removing Structural Modeling reduces success rate from 56% to 48% despite eliminating only 0.1135, or 3.8% of STRACE’s total cost.The passage attributes this degradation to less accurate and less efficient subsequent localization and repair.
  • C.1 Stage-wise Cost Breakdown for the Ablation Study: Removing Trace Filtering raises overall cost to 8.4489, with Phase 4 reaching 7.602 (90.0% of the total).Phase 1 and Phase 3 remain comparatively small at 0.1667 (2.0%) and 0.6802 (8.1%).
  • C.1 Stage-wise Cost Breakdown for the Ablation Study: Removing current-node slicing yields cost 2.8762, while removing slicing and using the full trace yields 5.9276, driven mainly by Phase 4.Phase 4 is 2.0486 (71.2%) with current-node removal and 5.3179 (89.7%) with full-trace input.
  • C.1 Stage-wise Cost Breakdown for the Ablation Study: Across variants, cost variation concentrates in Phase 4 because trace filtering localizes failures and causal slicing supplies compact, dependency-preserving context.Full-trace inputs instead cause token and turn expansion during downstream prompt optimization.
  • C.2 Average Turns of VeruSAGE (STRACE-enhanced) Compared to the Base Agent: A VeruSAGE turn is one atomic repair attempt in the outer interaction loop, counted until success or termination under the stopping criteria.For assertion failures, the assertion_reasoning_pipeline and its selected downstream sub-agent together form the relevant repair process.
  • C.2 Average Turns of VeruSAGE (STRACE-enhanced) Compared to the Base Agent: STRACE-enhanced VeruSAGE consistently requires fewer turns than the base agent across all five VeruSAGE-Bench categories, with the largest reductions on IronKV and NRKernel.Fewer turns indicate faster outer-loop convergence, fewer LLM calls, lower latency, and reduced interaction overhead under identical stopping criteria.

C.3 STRACE Performance on VeruSAGE-Bench Compared with Hands-off Agents

On VeruSAGE-Bench, STRACE is competitive with hands-off agents, outperforming hands-off GPT-5 in overall success rate and approaching Claude Sonnet 4 at 58.5% versus 59.4% despite using o4-mini. Its gains are strongest on several categories, while remaining gaps indicate limits on some failure modes.

  • Comparison setup: STRACE is evaluated on the same VeruSAGE-Bench split and protocol as hands-off GPT-5 and Claude Sonnet 4 reference results.The hands-off agents use generic coding agents with lightweight anti-cheating prompts and direct access to Verus, a cheat checker, and vstd.
  • Overall performance: STRACE outperforms hands-off GPT-5 in overall success rate and reaches a comparable level to Claude Sonnet 4.The comparison is 58.5% vs 59.4%, despite STRACE using the substantially smaller o4-mini model.
  • Category-level results: STRACE shows its largest gains on Memory Allocator, Node Replication, and Storage.These category-level improvements indicate that learned, task-specific guidance can improve repair reliability in several benchmark categories.
  • Remaining limitations: STRACE remains behind on IronKV and NRKernel, where stronger general reasoning and long-horizon robustness may still help.These gaps suggest that some failure modes are not fully addressed by the learned task-specific guidance.

D Evolution Examples in VeruSAGE Task

STRACE converts trace-specific observations from VeruSAGE into transferable heuristics for the assertion_reasoning_pipeline module. The revised prompt emphasizes failure-aware action selection and concrete, proof-state-specific guidance.

  • Generalized Rules: STRACE de-contextualizes specific trace observations into reusable heuristics across varying proof states.These generalized rules are synthesized from the VeruSAGE benchmark for assertion_reasoning_pipeline.
  • Failure-Aware Action Selection: After 2–3 consistent rejections, stop retrying the same action in the current proof context and switch to another candidate action.This especially applies when failures arise from syntax errors or failure to fix the target assertion.
  • Proof-State-Specific Guidance: Guidance must be specific and actionable, using concrete anchors from the visible code and current goal structure.Generic suggestions are discouraged.
  • Action-Specific Guidance: USELEMMA should identify relevant helper lemmas and their established results, while CASE_ANALYSIS should specify the split expression and each branch’s goal.USELEMMA is avoided when no relevant lemmas exist, with direct proof actions preferred instead.
Loading 2607.07702v1…