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

# From Noisy Traces to Root Causes: Structural Trajectory Analysis and Causal Extraction for Agent Optimization
Source: [https://arxiv.org/html/2607.07702](https://arxiv.org/html/2607.07702)
Ying Chang1 2 †,Jiahang Xu2 \*,Xuan Feng2, Chenyuan Yang2,Peng Cheng2,Yuqing Yang2 1University of Chinese Academy of Sciences, Beijing, China, 2Microsoft Research\. Correspondence:[jiahangxu@microsoft\.com](https://arxiv.org/html/2607.07702v1/mailto:[email protected])

###### Abstract

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 introduceSTRACE\(StructuralTrajectoryAnalysis andCausalExtraction\), 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×\\timessuccess\-rate improvement \(42\.5% to 58\.5%\)\. The code is available at[https://github\.com/moomight/STRACE](https://github.com/moomight/STRACE)\.

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

Ying Chang1 2 †, Jiahang Xu2 \*, Xuan Feng2,Chenyuan Yang2,Peng Cheng2,Yuqing Yang21University of Chinese Academy of Sciences, Beijing, China,2Microsoft Research\.Correspondence:[jiahangxu@microsoft\.com](https://arxiv.org/html/2607.07702v1/mailto:[email protected])

††footnotetext:Ying Chang did the work during an internship at Microsoft Research\.\*\*footnotetext:Corresponding author\.## 1Introduction

![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/teaser2.jpg)Figure 1:Comparison of context construction strategies\. Existing methods struggle with thecontext\-noise trade\-off:\(a\) Full Trajectoryintroduces noise leading to spurious correlations, while\(b\) Short Truncationfails to capture long\-range causal dependencies \(e\.g\., linking Step 1 to Step 48\)\. In contrast,\(c\) STRACEperforms causal context distillation to extract a compact causal slice, providing a high\-SNR context for precise optimization\.The field of Artificial Intelligence is undergoing a paradigm shift from single\-turn interactions to Compound Agent SystemsZahariaet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib39)\)\. Powered by reasoning\-intensive models capable ofComputer UseAnthropic \([2024a](https://arxiv.org/html/2607.07702#bib.bib44),[b](https://arxiv.org/html/2607.07702#bib.bib43)\)and autonomous software engineeringJimenezet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib46)\); Chenet al\.\([2021](https://arxiv.org/html/2607.07702#bib.bib47)\); OpenAI \([2024b](https://arxiv.org/html/2607.07702#bib.bib51)\), these systems are no longer mere chatbots but sophisticated operational units\. They orchestrate complex tool usage, manage dynamic memory, and execute multi\-step control flows to solve intricate long\-horizon tasksWanget al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib15)\); Xiet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib16)\); Schicket al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib18)\)\. Meanwhile, the artifacts generated by these systems have evolved from simple conversational logs into complex execution trajectories with reasoning chains, code execution environments and state transitions\. How to effectively use such trajectory information to further enhance agent systems has become a critical question\.

A predominant paradigm for optimizing such agent systems isreflexive optimizationPryzantet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib33)\); Shinnet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib24)\); Yanget al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib23)\), which uses an LLM to diagnose agent\-system failures and evolve agent policies based on historical feedback derived from agent trajectories\. However, when deployed on complex long\-horizon tasks, these frameworks struggle to process the sheer volume and complexity of generated data\. In realistic settings, batched execution trajectories contain heterogeneous failures with different frequencies, severities, and causesCemriet al\.\([2026](https://arxiv.org/html/2607.07702#bib.bib6)\); Barkeet al\.\([2026](https://arxiv.org/html/2607.07702#bib.bib8)\)\. Attempting to optimize the agent from every failed trace is computationally intractable and often leads to brittle, overfitted updates\. Consequently, a mechanism is needed to aggregate these heterogeneous logs, isolate the most frequent and consequential failure patterns, and distill them into generalized improvements\.

Even after representative failures are selected, optimization within an individual trace remains challenging due to thecontext\-noise trade\-offLiuet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib56)\)\. Existing methods often force a choice between two imperfect extremes \(illustrated in Figure[1](https://arxiv.org/html/2607.07702#S1.F1)\)\. Feeding thefull trajectory\(a\) overwhelms the optimizer with irrelevant successful steps and low\-SNR context, inviting spurious correlations and hallucinated prompt patchesYuksekgonulet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib38)\); Shiet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib57)\)\. Conversely, relying onshort truncation\(b\) treats local proximity as a signal of causal relevanceAgrawalet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib5)\); Kanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib9)\); it risks discarding distant but causally essential history, severing the link between a symptom and its origin\.

This dilemma exposes a fundamental reality of agentic workflows: the node where an error manifests \(the downstream symptom\) is often not the node where it originates \(the upstream root cause\)Zhanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib7)\)\. For instance, a Code Interpreter crash at Step 50 may be the delayed consequence of an incorrect parameter generated by a Planner at Step 5\. Without a mechanism to bridge this temporal gap while filtering noise, optimizers tend to repair symptoms rather than root causes\.

To address these challenges, we introduceSTRACE\(StructuralTrajectoryAnalysis andCausalExtraction\), an optimization framework that treats execution logs not as monolithic linear text, but as causal graphs \(Figure[1](https://arxiv.org/html/2607.07702#S1.F1)\(c\)\)\. STRACE systematically resolves these dual challenges through a decoupled pipeline\.

First,Structural Modelinginfers a compact textual dependency graph that records data and control relations among agent components as dependency priors\. Building on this topology,Failure Pattern Mining and Trace Filteringtackles large\-scale trace heterogeneity by summarizing each batch into statistical and structural diagnoses, then filtering redundant or low\-value failures using recurrence and severity signals to retain a compact trace set\. Within these representative traces,Causal Localizationidentifies the true root cause as the optimization target and provides the causal context needed for optimization: it traces dependencies backward to discard irrelevant steps, extract a compact causal slice, and locate the failure’s logical origin rather than its manifestation node\. Finally, duringInductive Policy Optimization, STRACE uses localized failure episodes to synthesize generalized, natural language heuristics\. These preventative guidelines are injected exclusively into the instructions of the identified root\-cause modules, enabling continuous, safe, and cost\-effective improvement without altering the underlying executable code\.

We validate this capability onHotpotQAYanget al\.\([2018](https://arxiv.org/html/2607.07702#bib.bib36)\),WebArenaZhouet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib79)\), andVeruSAGE\-BenchYanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib35)\)benchmarks, where STRACE significantly outperforms state\-of\-the\-art baselines, notably boosting success rates on the rigorous VeruSAGE benchmark by an absolute16\.0%\(42\.5%→\\to58\.5%\)\. In summary, our contributions are:

- •We propose STRACE, an end\-to\-end agent optimization framework that treats execution logs as structured causal evidence rather than monolithic linear text\.
- •We introduce a trace filtering and causal localization mechanism that selects representative failures, extracts compact causal slices, and identifies root\-cause modules as optimization targets\.
- •We evaluate STRACE on comprehensive benchmarks covering diverse reasoning and long\-horizon agent settings, showing consistent gains over full\-trajectory, truncation, and prompt\-optimization baselines\.

## 2Related Work

### 2\.1Automated Prompt Optimization

Automated Prompt Optimization \(APO\) employs LLMs to iteratively search for superior instructions\. Pioneering works formulate this as a natural language search problem based on performance scoresZhouet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib32)\); Yanget al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib23)\)\. To handle complex workflows, recent frameworks leverage reflexive feedbackShinnet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib24)\)or modular textual gradientsPryzantet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib33)\); Khattabet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib1)\)to optimize multi\-stage pipelines\. Furthermore, evolutionary strategies have been adopted to enhance exploration through population\-based mutation and environmental feedback, such as EvoPromptGuoet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib58)\), GEPAAgrawalet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib5)\), and SCOPEPeiet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib67)\)\. However, a critical limitation remains incontext management\. Existing methods typically rely on scalar rewards or truncated summaries to fit context windows\. In long\-horizon agentic tasks, this compression obscures deep structural dependencies, hindering the diagnosis of complex, multi\-step failures\.

### 2\.2Reflexive Agents and Harness Evolution

Distinct from APO, reflexive and self\-evolving agents improve agent behavior through feedback\-driven revision, ranging from inference\-time refinementMadaanet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib68)\); Sunet al\.\([2023](https://arxiv.org/html/2607.07702#bib.bib69)\)and verifier\-based reinforcementJianget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib70)\); Zhouet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib71)\)to code\- and architecture\-level evolutionNovikovet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib72)\); Sharma \([2025](https://arxiv.org/html/2607.07702#bib.bib75)\); Huet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib73)\); Zhaiet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib74)\)\. Recent harness\-level systems, such as Hermes Agent Self\-EvolutionNous Research \([2026](https://arxiv.org/html/2607.07702#bib.bib13)\), further use optimizers like GEPA to evolve editable agent components\. However, these methods still largely rely on unstructured feedback or trajectory\-level reflection to decide what to modify\. Without structured failure localization, they may repair downstream symptoms or update the wrong component\. In contrast, STRACE performs dependency\-guided diagnosis before optimization, producing localized repair signals that can transfer to skills and other tunable harness components\.

### 2\.3Agent Diagnostics and Credit Assignment

The Credit Assignment Problem \(CAP\) fundamentally challenges the attribution of outcomes to specific decisionsPignatelliet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib42)\)\. In Reinforcement Learning, this is traditionally addressed by mitigating reward sparsity via temporal redistribution mechanismsHarutyunyanet al\.\([2019](https://arxiv.org/html/2607.07702#bib.bib62)\); Arjona\-Medinaet al\.\([2019](https://arxiv.org/html/2607.07702#bib.bib63)\)\. In modular agent systems, the focus shifts to Structural Credit Assignment \(SCA\), where recent frameworks utilize min\-form bottleneck penaltiesChenget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib65)\)or generative critiquesXieet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib64)\)to refine reasoning chains\. Despite these advancements, establishing explicit, causal\-based attribution in long\-horizon trajectories remains an open challenge\.

![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/workflow6.jpg)Figure 2:Illustration of theSTRACEframework\. The system optimizes long\-horizon agents via four phases: \(1\)Structural Modeling, which constructs execution topology; \(2\)Failure Pattern Mining and Trace Filtering, which compresses failures into representative traces; \(3\)Causal Localization, which performs causal context distillation and root cause isolation; and \(4\)Inductive Policy Optimization, which injects heuristics into identified root cause modules\.

## 3The STRACE Framework

### 3\.1System Overview

STRACE is an advanced optimization framework designed to maximize the context signal\-to\-noise ratio \(SNR\) in the optimization of long\-horizon agents\. Directly placing massive traces into the agent optimizer’s context window introduces substantial noise, diluting the LLM’s reasoning signal and often trapping optimization in local optima\. STRACE resolves this context\-noise trade\-off through a two\-pronged approach: first, it performs trace filtering to retain only highly diverse, representative traces; second, it executes rigorous causal localization to explicitly strip away non\-causal noise\. By condensing large execution batches into high\-quality diagnostic evidence, STRACE enables precise and stable optimization within finite context limits\.

As illustrated in Figure[2](https://arxiv.org/html/2607.07702#S2.F2), the STRACE process operates through four integrated phases\. First,Structural Modelingconstructs a textual Execution Dependency Graph \(EDG\) to serve as the topological foundation for subsequent trace filtering\. Second,Failure Pattern Mining and Trace Filteringcompresses massive, heterogeneous trace batches into a compact, diverse set of representative exemplars\. Third,Causal Localizationdistills the minimal causal context via backward slicing and isolates the true root cause node\. Finally,Inductive Policy Optimizationconverts this localized evidence into generalized, persistent prompt updates for the defective modules\.

### 3\.2Phase 1: Structural Modeling

To enable structural analysis, STRACE leverages an LLM to read the agent’s source implementation and construct atextual Execution Dependency Graph \(EDG\)𝒢=\(𝒱,E\)\\mathcal\{G\}=\(\\mathcal\{V\},E\), which serves as the structural prior for the subsequent phases\. Specifically, STRACE parses the agent’s codebase to identify the atomic functional modules \(the vertex set𝒱\\mathcal\{V\}\)\. Simultaneously, it infers the textual edgesEEby analyzing the artifacts these modules produce, consume, or utilize to dictate downstream execution paths\.

This construction yields a faithful, lightweight dependency map that captures two dependency types among modules:data dependencies, where moduleBBconsumes artifacts produced by moduleAA\(e\.g\., intermediate plans, retrieved evidence, or execution outputs\), andcontrol dependencies, where moduleAAgoverns the downstream execution path by deciding whether moduleBBis invoked or which tool/sub\-agent is selected\. We provide the graph extraction procedure and detailed assessments in Appendix[B\.2](https://arxiv.org/html/2607.07702#A2.SS2)and Tables[3](https://arxiv.org/html/2607.07702#A2.T3)–[4](https://arxiv.org/html/2607.07702#A2.T4), showing that the extracted graph is effective and remains useful for STRACE across different optimizer models\.

### 3\.3Phase 2: Failure Pattern Mining and Trace Filtering

Long\-horizon agents often generate massive, heterogeneous failure traces during rollouts, making direct optimization inefficient and unstable\. In this phase, STRACE compresses the raw trace set into a manageable size while rigorously preserving the diversity of failure modes\. The pipeline operates in two steps: global diagnosis summarization followed by representative trace selection\.

Diagnosis Summarization\.Instead of feeding raw traces directly to the LLM, STRACE generates a deterministic Python parser to extract key execution signals\. To seamlessly adapt to varying agent logging formats, the system dynamically infers a trace schema from a single pilot trace, identifies structural delimiters \(e\.g\.,“Action:”,“Observation:”\), and compiles a tailored parsing script on\-the\-fly\. This parser then traverses the full trace set to record both the Global Outcome \(y∈\{S​u​c​c​e​s​s,F​a​i​l​u​r​e\}y\\in\\\{Success,Failure\\\}\) and the Local Node Status \(e\.g\., whether a specific module threw a runtime exception\)\.

Upon processing the entire trace corpus, the system evaluates the aggregated dataset across two analytical dimensions: \(1\)Statistical Severity, which computes the conditional probability of a global task failure given a specific local node error, thereby identifying the most lethal bottlenecks; and \(2\)Structural Path Patterns, which tracks module invocation sequences to capture recurring pathological topologies\. Specifically, this structural tracking detects anomalous behaviors such as infinite self\-loops \(e\.g\., a module repeatedly invoking the same tool without state progression\) and dead\-end trajectories \(e\.g\., specific calling sequences that consistently lead to an abrupt timeout\)\. The output is a comprehensive diagnostic summary mapping these dominant failure patterns across the entire dataset, serving as the quantitative basis for trace selection \(see Appendix[B\.3](https://arxiv.org/html/2607.07702#A2.SS3)for an example\)\.

Representative Trace Selection\.Because agent failures are heavily repetitive, STRACE applies diversity\-based sampling to reduce trace volume\. Based on the diagnostic summary, the framework clusters the trace data using both thestatistical severityof the errors and theirstructural path patterns\. It then selects a minimal exemplar set from each distinct cluster with a predefined size\. This guarantees that the optimizer reviews a compact dataset covering all major failure modes with a controllable size, without being overwhelmed by redundancy\.

Fallback Mechanism:In scenarios where the agent’s trace lacks explicit node\-level error signals \(i\.e\., modules fail silently without raising exceptions\), STRACE seamlessly adapts\. It bypasses the local node status and clusters the traces relying on the global task outcome combined with thestructural path patternsof the module invocations\. This ensures the selected exemplar set continues to rigorously capture distinct behavioral deviations\.

### 3\.4Phase 3: Causal Localization

While the filtering phase successfully isolates a compact trace set, massive amounts of irrelevant information within these individual trajectories still make it difficult to locate the true root cause node\. STRACE performs efficient causal localization to systematically pinpoint the core defect as an optimization target\. To achieve this precision, the framework shifts the analytical focus: instead of just locatingwherean error visibly manifests, it extractswhatexact context is causally responsible for it\. This naturally leads us to distinguish between theManifestation Nodevmv\_\{m\}\(where the error explicitly surfaces, such as a code interpreter throwing a syntax exception; or the terminal node if no explicit error exists\) and theRoot Cause Nodevrv\_\{r\}\(the module harboring the actual logical defect\)\. This phase bridges the gap between the two via a two\-step process\.

Step 1: Causal Context Distillation via Backward Slicing\.Given a representative trace and its manifestation node, STRACE extracts a minimalCausal Slicecontaining only the historical steps that directly or indirectly influenced the failure\. STRACE utilizes the EDG to traverse the trace in reverse\. Starting from the failure state atvmv\_\{m\}, the algorithm recursively traces theData DependencyandControl Dependencyedges backward\. By retaining only steps that can reach the manifestation node through the dependency closure \(→∗\\rightarrow^\{\*\}\), the system prunes nodes with no structural influence on the failure, thereby discarding mere temporal antecedents\.

To illustrate, consider an agent executing multiple independent exploration branches\. Because divergent reasoning paths are data\-independent, an error manifesting on one specific branch possesses no causal link to the others\. The backtracking mechanism bypasses nodes from those parallel, irrelevant explorations\. The resulting high\-SNR slice𝒞s​l​i​c​e\\mathcal\{C\}\_\{slice\}removes non\-causal noise, capturing only the trajectory of the corrupted information flow\.

Step 2: Root Cause Isolation from the Causal Slice\.Armed with the noise\-free𝒞s​l​i​c​e\\mathcal\{C\}\_\{slice\}, STRACE performs causal deduction to pinpoint where the execution first deviated from the intended logic\. The system traces the flow of corrupted context backward from the manifestation node\. For instance, while aCode Interpreter\(vmv\_\{m\}\) might manifest the error by crashing, semantic reasoning over𝒞s​l​i​c​e\\mathcal\{C\}\_\{slice\}systematically reveals that an upstreamPlannergenerated a hallucinated parameter several steps earlier\. Upon locating this originating logical defect, the system formally designates the module as the trueRoot Cause Nodevrv\_\{r\}\.

### 3\.5Phase 4: Inductive Policy Optimization

By grouping the highly purified causal slices by their verified root cause nodes \(vrv\_\{r\}\), the final phase transforms episodic errors into persistent policy upgrades, executing the actual optimization of the agent\.

For each targeted modulevrv\_\{r\}, STRACE analyzes the aggregated causal slices to synthesize high\-order generalized rules\. Rather than translating recurring errors into instance\-specific failure records \(which risk overfitting\), the optimizer performs inductive abstraction to formulate robust, reusable heuristics for future executions\. STRACE then injects these newly discovered rules directly into the textual prompt policy ofvrv\_\{r\}\. This guarantees that the targeted policy update resolves the exact structural deficiency at its source\. The instruction templates are provided in Appendix[B\.4](https://arxiv.org/html/2607.07702#A2.SS4), and examples of synthesized heuristics are provided in Appendix[D](https://arxiv.org/html/2607.07702#A4)\.

## 4Experiments

Table 1:Performance of STRACE versus baselines on HotpotQA, WebArena, and VeruSAGE\-Bench\. HotpotQA is evaluated by Exact Match \(EM\), while WebArena and VeruSAGE\-Bench are evaluated by Success Rate \(SR\)\. Parentheses in ALL indicate absolute gains over the Base Agent\. Best results are highlighted in bold\. TextGrad is omitted for VeruSAGE\-Bench due to context\-budget limits\.
### 4\.1Experimental Setup

Datasets\.We evaluate STRACE on three distinct benchmarks\. For general multi\-hop reasoning, we employHotpotQAYanget al\.\([2018](https://arxiv.org/html/2607.07702#bib.bib36)\)in the multi\-document setting, using a random150/300150/300train\-test split\. For long\-horizon agent optimization, we consider two complementary benchmarks\.WebArenaZhouet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib79)\)represents general\-purpose web interaction, where agents complete realistic tasks across Shopping, CMS, Reddit, and GitLab tasks\.VeruSAGE\-BenchYanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib35)\)represents domain\-intensive formal verification, consisting of five real\-world Rust projectsLattuadaet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib48)\)with extreme context lengths \(avg\. 947 lines\): IronKV, Memory Allocator, Node Replication, NRKernel, and Storage\. We enforce an80%/20%80\\%/20\\%split per project to test generalization\.

Base Agent Implementation\.The optimization targets the set of instructions𝒫\\mathcal\{P\}that governs the modules in each workflow\. For HotpotQA, we use a DSPy\-basedKhattabet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib1)\); Agrawalet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib5)\)four\-stage multi\-hop reasoning workflow with 4 optimizable modules andGPT\-4oOpenAI \([2024a](https://arxiv.org/html/2607.07702#bib.bib50)\)\. For WebArena, we use the original Chain\-of\-Thought \(CoT\) web\-navigation agent with one tunable instruction andGPT\-4oas the backbone\. For VeruSAGE\-Bench, we use the hierarchical router\-executor multi\-agent frameworkYanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib35)\)with 16 optimizable modules ando4\-miniOpenAI \([2025b](https://arxiv.org/html/2607.07702#bib.bib49)\)as the backbone\. Each task is solved through an iterative verification\-repair loop that runs for up to 20 repair attempts or 20 minutes\. Detailed architectures and optimizable components are provided in Appendix[A](https://arxiv.org/html/2607.07702#A1)\.

Baselines\.We compare STRACE against the unoptimized Base Agent, and three categories of optimization baselines\. Forstatic strategies, we utilize Naive Few\-shotBrownet al\.\([2020](https://arxiv.org/html/2607.07702#bib.bib10)\), and a Failure\-Aware RAG baselineLewiset al\.\([2021](https://arxiv.org/html/2607.07702#bib.bib11)\)that retrieves traces via a BM25 indexRobertsonet al\.\([2009](https://arxiv.org/html/2607.07702#bib.bib12)\)and appends them as instruction references\. Forautomated optimizers, we select two representative methods\. TextGradYuksekgonulet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib38)\)represents the gradient\-based paradigm, which feeds the full execution trace to the optimizer to compute error attributions, and GEPAAgrawalet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib5)\)represents the evolutionary paradigm, which typically applies context truncation to fit recent history into the optimizer window\. Forcontext management baselines, we include two common trace compression strategies for handling extremely long traces during optimization: Summary\-based and Retrieval\-based optimization\. Both use the same optimizer as STRACE but construct the optimization context without causal localization: the former summarizes the full trace before inductive abstraction, while the latter retrieves the most relevant steps as optimizer input\.Note: TextGrad is excluded from VeruSAGE\-Bench due to prohibitive context costs \(\>100k tokens\)\.

Metrics & Configuration\.We report Exact Match \(EM\) for HotpotQA and Success Rate \(SR\) for WebArena and VeruSAGE\-Bench\. Optimization cost is reported in USD for one full optimization run, estimated from token usage under API pricing\. For the optimizer, we employClaude Sonnet 4\.5\(temp=1\.0\) as the meta\-controller for all methods to ensure fairness, with a bottleneck thresholdk=5k=5and exemplar counts=5s=5\.

### 4\.2Main Results

Table[1](https://arxiv.org/html/2607.07702#S4.T1)summarizes the performance of STRACE across benchmarks that cover both general reasoning and complex long\-horizon agentic tasks\. Across these settings, STRACE achieves the strongest overall performance compared to all baselines\. The pattern across baseline categories helps explain where the gains of STRACE come from\. Static strategies can provide additional examples or failure cases, but they fail to identify which part of the current behavior should be revised\. Automated optimizers such as TextGrad and GEPA still rely on provided context quality: using full trajectories can exceed the context budget or dilute local signals, whereas simple truncation or relevance\-based slicing may miss the upstream root cause\. Context management methods attempt to reduce the trace context, but summaries may discard fine\-grained failure signals, while retrieval can be misled by semantic similarity\. In contrast, STRACE addresses this context\-noise trade\-off through a dependency\-guided optimization framework that provides localized yet context\-aware signals, enabling the optimizer to focus on root causes rather than noisy downstream symptoms and thereby achieve the strongest overall performance across benchmarks\.

Beyond the overall comparison, STRACE also shows strong adaptability to two optimization needs in agentic tasks\. On WebArena, the key difference lies in the task\-specific demand for optimization signals: Shopping and CMS require more workflow guidance, while Reddit and GitLab require more failure\-aware rules\. In the former domains, STRACE remains competitive with the strongest baselines by preserving useful procedural context\. In the latter domains, STRACE achieves clearer improvements, suggesting that STRACE leverages both workflow\-level patterns and failure\-aware optimization signals\. The advantage of STRACE becomes more pronounced on the longer\-horizon and more domain\-intensive VeruSAGE\-Bench, where STRACE achieves the highest average success rate of58\.5%, outperforming the base agent by\+16\.0%and the strongest baseline, GEPA, by\+11\.3%\. These results demonstrate the effectiveness of STRACE especially in complex agentic settings, where failures may propagate across multiple components and require root\-cause localization rather than shallow reuse of prior traces\.

### 4\.3Optimization Scalability and Cost Analysis

![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/tradeoff.png)

Figure 3:Success rate on 50 independent tasks and optimization cost for STRACE, GEPA, and TextGrad full\-trace prompt optimization, as the number of training cases scales from 1 to 453\.Long\-horizon prompt optimization must balance performance with cost, as naively increasing context quickly becomes prohibitive\. Figure[3](https://arxiv.org/html/2607.07702#S4.F3)plots the success rate and optimization cost against the number of training trajectories\. For a fair comparison, all methods are optimized on the same trajectory subset at each scale point\. We include two representative baselines:TextGrad\(full\-trace optimization\) andGEPA\(current node slicing and batch optimization\)\.

As the training set scales, STRACE achieves the most favorable cost–performance trend\. While TextGrad incurs rapidly increasing costs due to full\-trace processing and GEPA reduces cost by restricting optimization to local\-node batches, STRACE maintains both efficiency and effectiveness\. This favorable trade\-off is enabled by theStatistical Bottleneck Diagnosismodule, which summarizes dataset\-level failure patterns and selects only a small set of representative, high\-value exemplars for optimization\. As a result, even when scaling to the full set of453trajectories, STRACE controls context growth while preserving the failure evidence needed for effective repair, yielding the strongest overall cost–performance trend among all methods\.

### 4\.4Case Study: Tracing Symptoms to Root Causes

![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/casestudy.drawio.png)

Figure 4:Distinguishing Symptoms from Root Causes\.Top:Causal localization remaps 25 traces from 5 manifest nodes to 6 targets, exposing an upstream source\.Bottom:Acompute\_repairloop is traced toassertion\_reasoning\_pipeline, enabling a targeted policy optimization to bypass the recursive path\.To empirically validate the distinction betweensymptom\(vmv\_\{m\}\) andcause\(vrv\_\{r\}\), we present two analyses from the VeruSAGE\-Bench optimization process in Figure[4](https://arxiv.org/html/2607.07702#S4.F4)\. These cases illustrate how root cause isolation redirects optimization from surface\-level failures to upstream logical defects\.

Re\-mapping Target Nodes\.As formalized in Section[3\.4](https://arxiv.org/html/2607.07702#S3.SS4), effective optimization requires targeting the root\-cause node rather than the manifestation node\. In the 200\-case setting, STRACE selects 5 high\-impact manifest modules and 5 representative traces for each, yielding 25 traces in total\. Without causal localization, these traces would be attributed to the modules where failures surface naturally\. However, by applying root cause isolation, 12 of the 25 traces are re\-mapped to upstream root\-cause actions, expanding the optimization targets to 6 distinct nodes, with an additional upstream “assertion\_reasoning\_pipeline” module\. This redistribution confirms that relying solely on crash location \(vmv\_\{m\}\) can lead to “optimizing the wrong target” for a subset of failures, whereas STRACE disperses the diagnosis to the true logical origins\.

Breaking the Loop\.We further examine a representative IronKV failure\. The agent repeatedly invokes a downstream repair module until timeout, making the visible failure appear local to that module\. Causal slicing instead traces the loop back to an earlier routing error: the upstream controller dispatched the task to an unsuitable repair path\. By repairing this root\-cause decision, STRACE breaks the loop and enables successful verification\.

### 4\.5Ablation Study

Table 2:Ablation results with Success Rate and stage\-wise cost breakdown\.We ablate STRACE to isolate the contributions of structure modeling, trace filtering, and causal localization\. Each variant is optimized under the same protocol with the same training traces\. Table[2](https://arxiv.org/html/2607.07702#S4.T2)reports the resulting Success Rate and overall cost\. Removing structure modeling leads to lower effectiveness and higher cost, suggesting that the dependency graph provides a useful prior for organizing trace failures and narrowing the search space before optimization\. Removing trace filtering further degrades both performance and efficiency, as the optimizer must process more redundant or low\-value traces rather than a compact set of representative failures\. The causal localization variants reveal the context\-noise dilemma: using only the current node may miss upstream causes, while using the full trace introduces unnecessary noise and cost\. In contrast, STRACE combines these components to preserve root\-cause evidence while keeping the optimization context bounded\. Detailed cost\-component analyses are deferred to Appendix[C\.1](https://arxiv.org/html/2607.07702#A3.SS1)\.

## 5Conclusions

We introduce a novel method STRACE for long\-horizon agent optimization under the context\-noise trade\-off\. By combining failure pattern mining with causal localization, STRACE breaks this dilemma, enabling targeted policy optimization that is both cost\-efficient and high\-performing\. Results on HotpotQA, WebArena, and VeruSAGE\-Bench show consistent gains in success rate and efficiency, outperforming all baselines and demonstrating the effectiveness of our method\. Ablation studies and analysis further validate the contribution of each phase\. Importantly, STRACE can be readily transferred to harness engineering, where its localized diagnoses can guide updates to tunable agent components such as skills, tool\-use policies, and other editable harness elements\. This transferability makes STRACE a flexible framework for improving complex long\-horizon agents\.

## Limitations

A main limitation of STRACE is that it assumes sufficient visibility into the target agent system\. The dependency prior is constructed from codebase\-level or harness\-level artifacts, including agent definitions, tool interfaces, configuration files, prompts, skills, and execution logs\. Therefore, STRACE is most directly applicable to systems where the optimizer can inspect the implementation or harness, rather than fully black\-box agents with hidden components and control flow\. Notably, this does not require access to model weights, but it does require enough system\-level visibility to identify the components involved in long\-horizon failures\. Extending STRACE to purely trace\-only or black\-box settings remains future work\.

## Ethical considerations

In this study, all datasets, models, and software artifacts used in our experiments are publicly available, and we follow their respective licenses or terms of use\. The use of these resources is strictly confined to academic research and benchmarking purposes\. We do not collect new human\-subject data, and all reported results are presented in aggregate form\. While STRACE is designed to improve the efficiency and reliability of long\-horizon agent optimization, we acknowledge that stronger agent optimization methods could be misused if applied to unsafe or malicious agent systems\. In addition, execution traces collected from real deployments may contain sensitive information\. For practical deployment, we recommend that traces be anonymized or access\-controlled, and that optimized prompts, skills, or harness components be reviewed before being applied to high\-stakes or user\-facing systems\.

## References

- L\. A\. Agrawal, S\. Tan, D\. Soylu, N\. Ziems, R\. Khare, K\. Opsahl\-Ong, A\. Singhvi, H\. Shandilya, M\. J\. Ryan, M\. Jiang, C\. Potts, K\. Sen, A\. G\. Dimakis, I\. Stoica, D\. Klein, M\. Zaharia, and O\. Khattab \(2025\)GEPA: reflective prompt evolution can outperform reinforcement learning\.External Links:2507\.19457,[Link](https://arxiv.org/abs/2507.19457)Cited by:[§A\.1](https://arxiv.org/html/2607.07702#A1.SS1.p1.1),[§1](https://arxiv.org/html/2607.07702#S1.p3.1),[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p2.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p3.1)\.
- Developing a computer use model\.Note:Anthropic Research BlogExternal Links:[Link](https://www.anthropic.com/news/developing-computer-use)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- Anthropic \(2024b\)Introducing computer use, a new Claude 3\.5 Sonnet, and Claude 3\.5 Haiku\.Note:Anthropic Research BlogExternal Links:[Link](https://www.anthropic.com/news/3-5-models-and-computer-use)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- Anthropic \(2025a\)Claude Agent SDK\.Note:[https://github\.com/anthropics/claude\-agent\-sdk\-python](https://github.com/anthropics/claude-agent-sdk-python)Python SDK for building agents with Claude Code capabilities\. Accessed: 2026\-05\-22Cited by:[§B\.1](https://arxiv.org/html/2607.07702#A2.SS1.p1.1)\.
- Anthropic \(2025b\)Introducing Claude Haiku 4\.5\.Note:Accessed: 2026\-07\-07External Links:[Link](https://www.anthropic.com/news/claude-haiku-4-5)Cited by:[Table 3](https://arxiv.org/html/2607.07702#A2.T3.1.1.3.2.1)\.
- Anthropic \(2025c\)Introducing Claude Sonnet 4\.5\.Note:Accessed: 2026\-07\-07External Links:[Link](https://www.anthropic.com/news/claude-sonnet-4-5)Cited by:[Table 3](https://arxiv.org/html/2607.07702#A2.T3.1.1.2.1.1)\.
- J\. A\. Arjona\-Medina, M\. Gillhofer, M\. Widrich, T\. Unterthiner, J\. Brandstetter, and S\. Hochreiter \(2019\)RUDDER: return decomposition for delayed rewards\.InProceedings of the 33rd International Conference on Neural Information Processing Systems,Cited by:[§2\.3](https://arxiv.org/html/2607.07702#S2.SS3.p1.1)\.
- S\. Barke, A\. Goyal, A\. Khare, A\. Singh, S\. Nath, and C\. Bansal \(2026\)AgentRx: diagnosing AI agent failures from execution trajectories\.arXiv preprint arXiv:2602\.02475\.Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p2.1)\.
- T\. B\. Brown, B\. Mann, N\. Ryder, M\. Subbiah, J\. Kaplan, P\. Dhariwal, A\. Neelakantan, P\. Shyam, G\. Sastry, A\. Askell, S\. Agarwal, A\. Herbert\-Voss, G\. Krueger, T\. Henighan, R\. Child, A\. Ramesh, D\. M\. Ziegler, J\. Wu, C\. Winter, C\. Hesse, M\. Chen, E\. Sigler, M\. Litwin, S\. Gray, B\. Chess, J\. Clark, C\. Berner, S\. McCandlish, A\. Radford, I\. Sutskever, and D\. Amodei \(2020\)Language models are few\-shot learners\.External Links:2005\.14165,[Link](https://arxiv.org/abs/2005.14165)Cited by:[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p3.1)\.
- M\. Cemri, M\. Z\. Pan, S\. Yang, L\. A\. Agrawal, B\. Chopra, R\. Tiwari, K\. Keutzer, A\. Parameswaran, D\. Klein, K\. Ramchandran,et al\.\(2026\)Why do multi\-agent LLM systems fail?\.Advances in Neural Information Processing Systems38\.Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p2.1)\.
- M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. P\. de Oliveira Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman, A\. Ray, R\. Puri, G\. Krueger, M\. Petrov, H\. Khlaaf, G\. Sastry, P\. Mishkin, B\. Chan, S\. Gray, N\. Ryder, M\. Pavlov, A\. Power, L\. Kaiser, M\. Bavarian, C\. Winter, P\. Tillet, F\. P\. Such, D\. Cummings, M\. Plappert, F\. Chantzis, E\. Barnes, A\. Herbert\-Voss, W\. H\. Guss, A\. Nichol, A\. Paino, N\. Tezak, J\. Tang, I\. Babuschkin, S\. Balaji, S\. Jain, W\. Saunders, C\. Hesse, A\. N\. Carr, J\. Leike, J\. Achiam, V\. Misra, E\. Morikawa, A\. Radford, M\. Knight, M\. Brundage, M\. Murati, K\. Mayer, P\. Welinder, B\. McGrew, D\. Amodei, S\. McCandlish, I\. Sutskever, and W\. Zaremba \(2021\)Evaluating large language models trained on code\.External Links:2107\.03374,[Link](https://arxiv.org/abs/2107.03374)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- J\. Cheng, G\. Xiong, R\. Qiao, L\. Li, C\. Guo, J\. Wang, Y\. Lv, and F\. Wang \(2025\)Stop summation: min\-form credit assignment is all process reward model needs for reasoning\.External Links:2504\.15275,[Link](https://arxiv.org/abs/2504.15275)Cited by:[§2\.3](https://arxiv.org/html/2607.07702#S2.SS3.p1.1)\.
- DeepSeek\-AI \(2025\)DeepSeek\-V3\.1 release\.Note:[https://api\-docs\.deepseek\.com/news/news250821](https://api-docs.deepseek.com/news/news250821)Accessed: 2026\-05\-20Cited by:[Table 3](https://arxiv.org/html/2607.07702#A2.T3.1.1.5.4.1)\.
- Q\. Guo, R\. Wang, J\. Guo, B\. Li, K\. Song, X\. Tan, G\. Liu, J\. Bian, and Y\. Yang \(2025\)EvoPrompt: connecting llms with evolutionary algorithms yields powerful prompt optimizers\.External Links:2309\.08532,[Link](https://arxiv.org/abs/2309.08532)Cited by:[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1)\.
- A\. Harutyunyan, W\. Dabney, T\. Mesnard, M\. Azar, B\. Piot, N\. Heess, H\. van Hasselt, G\. Wayne, S\. Singh, D\. Precup, and R\. Munos \(2019\)Hindsight credit assignment\.External Links:1912\.02503,[Link](https://arxiv.org/abs/1912.02503)Cited by:[§2\.3](https://arxiv.org/html/2607.07702#S2.SS3.p1.1)\.
- S\. Hu, C\. Lu, and J\. Clune \(2025\)Automated design of agentic systems\.External Links:2408\.08435,[Link](https://arxiv.org/abs/2408.08435)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- Y\. Jiang, Y\. Xiong, Y\. Yuan, C\. Xin, W\. Xu, Y\. Yue, Q\. Zhao, and L\. Yan \(2025\)PAG: multi\-turn reinforced LLM self\-correction with policy as generative verifier\.External Links:2506\.10406,[Link](https://arxiv.org/abs/2506.10406)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- C\. E\. Jimenez, J\. Yang, A\. Wettig, S\. Yao, K\. Pei, O\. Press, and K\. R\. Narasimhan \(2024\)SWE\-bench: can language models resolve real\-world github issues?\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=VTF8yNQM66)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- M\. Kang, W\. Chen, D\. Han, H\. A\. Inan, L\. Wutschitz, Y\. Chen, R\. Sim, and S\. Rajmohan \(2025\)ACON: optimizing context compression for long\-horizon LLM agents\.External Links:2510\.00615,[Link](https://arxiv.org/abs/2510.00615)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p3.1)\.
- O\. Khattab, A\. Singhvi, P\. Maheshwari, Z\. Zhang, K\. Santhanam, S\. Vardhamanan, S\. Haq, A\. Sharma, T\. T\. Joshi, H\. Moazam, H\. Miller, M\. Zaharia, and C\. Potts \(2024\)DSPy: compiling declarative language model calls into self\-improving pipelines\.Cited by:[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p2.1)\.
- A\. Lattuada, T\. Hance, J\. Bosamiya, M\. Brun, C\. Cho, H\. LeBlanc, P\. Srinivasan, R\. Achermann, T\. Chajed, C\. Hawblitzel,et al\.\(2024\)Verus: a practical foundation for systems verification\.InProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles,pp\. 438–454\.Cited by:[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p1.2)\.
- P\. Lewis, E\. Perez, A\. Piktus, F\. Petroni, V\. Karpukhin, N\. Goyal, H\. Küttler, M\. Lewis, W\. Yih, T\. Rocktäschel, S\. Riedel, and D\. Kiela \(2021\)Retrieval\-augmented generation for knowledge\-intensive NLP tasks\.External Links:2005\.11401,[Link](https://arxiv.org/abs/2005.11401)Cited by:[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p3.1)\.
- N\. F\. Liu, K\. Lin, J\. Hewitt, A\. Paranjape, M\. Bevilacqua, F\. Petroni, and P\. Liang \(2023\)Lost in the middle: how language models use long contexts\.External Links:2307\.03172,[Link](https://arxiv.org/abs/2307.03172)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p3.1)\.
- A\. Madaan, N\. Tandon, P\. Gupta, S\. Hallinan, L\. Gao, S\. Wiegreffe, U\. Alon, N\. Dziri, S\. Prabhumoye, Y\. Yang, S\. Gupta, B\. P\. Majumder, K\. Hermann, S\. Welleck, A\. Yazdanbakhsh, and P\. Clark \(2023\)Self\-refine: iterative refinement with self\-feedback\.External Links:2303\.17651,[Link](https://arxiv.org/abs/2303.17651)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- MiniMax \(2026\)MiniMax M2\.5: built for real\-world productivity\.Note:[https://www\.minimax\.io/models/text](https://www.minimax.io/models/text)Accessed: 2026\-05\-20Cited by:[Table 3](https://arxiv.org/html/2607.07702#A2.T3.1.1.6.5.1)\.
- Nous Research \(2026\)Hermes Agent: the agent that grows with you\.Note:[https://github\.com/NousResearch/hermes\-agent](https://github.com/NousResearch/hermes-agent)Accessed: 2026\-05\-25Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- A\. Novikov, N\. Vũ, M\. Eisenberger, E\. Dupont, P\. Huang, A\. Z\. Wagner, S\. Shirobokov, B\. Kozlovskii, F\. J\. R\. Ruiz, A\. Mehrabian, M\. P\. Kumar, A\. See, S\. Chaudhuri, G\. Holland, A\. Davies, S\. Nowozin, P\. Kohli, and M\. Balog \(2025\)AlphaEvolve: a coding agent for scientific and algorithmic discovery\.External Links:2506\.13131,[Link](https://arxiv.org/abs/2506.13131)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- OpenAI \(2024a\)GPT\-4o system card\.External Links:2410\.21276,[Link](https://arxiv.org/abs/2410.21276)Cited by:[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p2.1)\.
- OpenAI \(2024b\)OpenAI o1 system card\.External Links:[Link](https://openai.com/index/openai-o1-system-card/)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- OpenAI \(2025a\)GPT\-5 system card\.Note:[https://openai\.com/index/gpt\-5\-system\-card/](https://openai.com/index/gpt-5-system-card/)Model release: August 7, 2025Cited by:[Table 3](https://arxiv.org/html/2607.07702#A2.T3.1.1.4.3.1)\.
- OpenAI \(2025b\)OpenAI o3 and o4\-mini system card\.Note:Accessed: 2026\-07\-07External Links:[Link](https://openai.com/index/o3-o4-mini-system-card/)Cited by:[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p2.1)\.
- Z\. Pei, H\. Zhen, S\. Kai, S\. J\. Pan, Y\. Wang, M\. Yuan, and B\. Yu \(2025\)SCOPE: prompt evolution for enhancing agent effectiveness\.External Links:2512\.15374,[Link](https://arxiv.org/abs/2512.15374)Cited by:[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1)\.
- E\. Pignatelli, J\. Ferret, M\. Geist, T\. Mesnard, H\. van Hasselt, O\. Pietquin, and L\. Toni \(2024\)A survey of temporal credit assignment in deep reinforcement learning\.External Links:2312\.01072,[Link](https://arxiv.org/abs/2312.01072)Cited by:[§2\.3](https://arxiv.org/html/2607.07702#S2.SS3.p1.1)\.
- R\. Pryzant, D\. Iter, J\. Li, Y\. T\. Lee, C\. Zhu, and M\. Zeng \(2023\)Automatic prompt optimization with "gradient descent" and beam search\.External Links:2305\.03495,[Link](https://arxiv.org/abs/2305.03495)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1)\.
- S\. Robertson, H\. Zaragoza,et al\.\(2009\)The probabilistic relevance framework: BM25 and beyond\.Foundations and trends® in information retrieval3\(4\),pp\. 333–389\.Cited by:[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p3.1)\.
- T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, L\. Zettlemoyer, N\. Cancedda, and T\. Scialom \(2023\)Toolformer: language models can teach themselves to use tools\.External Links:2302\.04761,[Link](https://arxiv.org/abs/2302.04761)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- A\. Sharma \(2025\)OpenEvolve: open\-source implementation of AlphaEvolve\.Note:[https://github\.com/algorithmicsuperintelligence/openevolve](https://github.com/algorithmicsuperintelligence/openevolve)GitHub repositoryCited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- F\. Shi, X\. Chen, K\. Misra, N\. Scales, D\. Dohan, E\. Chi, N\. Schärli, and D\. Zhou \(2023\)Large language models can be easily distracted by irrelevant context\.InProceedings of the 40th International Conference on Machine Learning,ICML’23\.Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p3.1)\.
- N\. Shinn, F\. Cassano, E\. Berman, A\. Gopinath, K\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.External Links:2303\.11366,[Link](https://arxiv.org/abs/2303.11366)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1)\.
- H\. Sun, Y\. Zhuang, L\. Kong, B\. Dai, and C\. Zhang \(2023\)AdaPlanner: adaptive planning from feedback with language models\.External Links:2305\.16653,[Link](https://arxiv.org/abs/2305.16653)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- L\. Wang, C\. Ma, X\. Feng, Z\. Zhang, H\. Yang, J\. Zhang, Z\. Chen, J\. Tang, X\. Chen, Y\. Lin, W\. X\. Zhao, Z\. Wei, and J\. Wen \(2024\)A survey on large language model based autonomous agents\.Frontiers of Computer Science18\(6\)\.External Links:ISSN 2095\-2236,[Link](http://dx.doi.org/10.1007/s11704-024-40231-1),[Document](https://dx.doi.org/10.1007/s11704-024-40231-1)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- Z\. Xi, W\. Chen, X\. Guo, W\. He, Y\. Ding, B\. Hong, M\. Zhang, J\. Wang, S\. Jin, E\. Zhou, R\. Zheng, X\. Fan, X\. Wang, L\. Xiong, Y\. Zhou, W\. Wang, C\. Jiang, Y\. Zou, X\. Liu, Z\. Yin, S\. Dou, R\. Weng, W\. Cheng, Q\. Zhang, W\. Qin, Y\. Zheng, X\. Qiu, X\. Huang, and T\. Gui \(2023\)The rise and potential of large language model based agents: a survey\.External Links:2309\.07864,[Link](https://arxiv.org/abs/2309.07864)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- G\. Xie, Y\. Shi, H\. Tian, T\. Yao, and X\. Zhang \(2025\)CAPO: towards enhancing llm reasoning through generative credit assignment\.External Links:2508\.02298,[Link](https://arxiv.org/abs/2508.02298)Cited by:[§2\.3](https://arxiv.org/html/2607.07702#S2.SS3.p1.1)\.
- C\. Yang, X\. Wang, Y\. Lu, H\. Liu, Q\. V\. Le, D\. Zhou, and X\. Chen \(2024\)Large language models as optimizers\.External Links:2309\.03409,[Link](https://arxiv.org/abs/2309.03409)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p2.1),[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1)\.
- C\. Yang, N\. Neamtu, C\. Hawblitzel, J\. R\. Lorch, and S\. Lu \(2025\)VeruSAGE: a study of agent\-based verification for rust systems\.External Links:2512\.18436,[Link](https://arxiv.org/abs/2512.18436)Cited by:[§A\.3](https://arxiv.org/html/2607.07702#A1.SS3.p1.1),[§C\.3](https://arxiv.org/html/2607.07702#A3.SS3.p1.1),[§1](https://arxiv.org/html/2607.07702#S1.p7.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p1.2),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p2.1)\.
- Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. Manning \(2018\)HotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 conference on empirical methods in natural language processing,pp\. 2369–2380\.Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p7.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p1.2)\.
- M\. Yuksekgonul, F\. Bianchi, J\. Boen, S\. Liu, Z\. Huang, C\. Guestrin, and J\. Zou \(2024\)Textgrad: automatic" differentiation" via text\.arXiv preprint arXiv:2406\.07496\.Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p3.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p3.1)\.
- M\. Zaharia, O\. Khattab, L\. Chen, J\. Q\. Davis, H\. Miller, C\. Potts, J\. Zou, M\. Carbin, J\. Frankle, N\. Rao, and A\. Ghodsi \(2024\)The shift from models to compound ai systems\.Note:[https://bair\.berkeley\.edu/blog/2024/02/18/compound\-ai\-systems/](https://bair.berkeley.edu/blog/2024/02/18/compound-ai-systems/)Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p1.1)\.
- Y\. Zhai, S\. Tao, C\. Chen, A\. Zou, Z\. Chen, Q\. Fu, S\. Mai, L\. Yu, J\. Deng, Z\. Cao, Z\. Liu, B\. Ding, and J\. Zhou \(2025\)AgentEvolver: towards efficient self\-evolving agent system\.External Links:2511\.10395,[Link](https://arxiv.org/abs/2511.10395)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- G\. Zhang, J\. Wang, J\. Chen, W\. Zhou, K\. Wang, and S\. Yan \(2025\)AgenTracer: who is inducing failure in the LLM agentic systems?\.arXiv preprint arXiv:2509\.03312\.Cited by:[§1](https://arxiv.org/html/2607.07702#S1.p4.1)\.
- S\. Zhou, F\. F\. Xu, H\. Zhu, X\. Zhou, R\. Lo, A\. Sridhar, X\. Cheng, T\. Ou, Y\. Bisk, D\. Fried,et al\.\(2024\)Webarena: a realistic web environment for building autonomous agents\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 15585–15606\.Cited by:[§A\.2](https://arxiv.org/html/2607.07702#A1.SS2.p1.1),[§1](https://arxiv.org/html/2607.07702#S1.p7.1),[§4\.1](https://arxiv.org/html/2607.07702#S4.SS1.p1.2)\.
- Y\. Zhou, S\. Levine, J\. Weston, X\. Li, and S\. Sukhbaatar \(2025\)Self\-challenging language model agents\.External Links:2506\.01716,[Link](https://arxiv.org/abs/2506.01716)Cited by:[§2\.2](https://arxiv.org/html/2607.07702#S2.SS2.p1.1)\.
- Y\. Zhou, A\. I\. Muresanu, Z\. Han, K\. Paster, S\. Pitis, H\. Chan, and J\. Ba \(2023\)Large language models are human\-level prompt engineers\.External Links:2211\.01910,[Link](https://arxiv.org/abs/2211.01910)Cited by:[§2\.1](https://arxiv.org/html/2607.07702#S2.SS1.p1.1)\.

## Appendix

## Appendix AAgent Implementation Details

Here we provide detailed specifications of the base agents used in our experiments, including their architectural workflows and the specific sub\-agents targeted for optimization\.

### A\.1HotpotQA Agent Workflow

Following the setup in GEPAAgrawalet al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib5)\)111[https://github\.com/gepa\-ai/gepa\-artifact](https://github.com/gepa-ai/gepa-artifact), our HotpotQA agent consists of four sequential sub\-agents designed to handle multi\-hop reasoning\. The workflow proceeds as follows:

1. 1\.Summarize1:This module processes the initial question and the paragraphs retrieved in the first hop\. Its goal is to extract relevant information and form a preliminary context\.
2. 2\.Create Query Hop2:Based on the initial summary and the original question, this module generates a refined search query to retrieve missing evidence required for the second hop\.
3. 3\.Summarize2:This module integrates the newly retrieved passages from the second hop with the prior context, synthesizing a comprehensive summary that consolidates evidence from both retrieval rounds\.
4. 4\.Final Answer:Finally, this module reasons over the aggregated summaries to produce the final answer string \(and supporting facts\) for the multi\-hop question\.

During optimization, STRACE optimizes the system prompts for all four modules simultaneously\.

### A\.2WebArena Agent Workflow

For WebArena, we followed the original WebArena Chain\-of\-Thought agent designZhouet al\.\([2024](https://arxiv.org/html/2607.07702#bib.bib79)\)222[https://github\.com/web\-arena\-x/webarena](https://github.com/web-arena-x/webarena)\. WebArena agent is a single prompt\-based web navigation agent rather than a multi\-agent system\. At each step, the agent observes the current webpage through a textual accessibility tree, together with the current URL, the user instruction, and the previous action\. A language model then reasons over this information and predicts the next browser action\.

The interaction loop proceeds as follows:

1. 1\.Observe:The browser environment converts the current webpage into an accessibility\-tree representation, exposing interactive elements such as buttons, links, text boxes, and menus\.
2. 2\.Reason and Act:Given the task objective and the current observation, the Chain\-of\-Thought prompt guides the language model to reason about the page state and output one concrete action, such as clicking an element, typing into a field, scrolling, navigating to a URL, or stopping with a final answer\.
3. 3\.Execute:The predicted action is executed in the browser environment, producing a new webpage state\.
4. 4\.Repeat:The agent repeats this observe–reason–act cycle until it issues a stop action or reaches the maximum interaction budget\.

During optimization, STRACE targets the prompt of this single WebArena agent\. Since the baseline does not contain explicit sub\-agents, planners, or external memory modules, the optimized component is the agent’s instruction prompt, which defines its action space, reasoning style, and few\-shot behavior examples\.

### A\.3VeruSAGE Agent Workflow

For VeruSAGE\-Bench, we utilize the VeruSAGE frameworkYanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib35)\)333[https://github\.com/microsoft/verus\-proof\-synthesis](https://github.com/microsoft/verus-proof-synthesis), which employs a more complex, iterative multi\-agent architecture to repair verification failures in Rust code\.

Iterative Repair Loop\.

The agent solves each task through a verification\-driven loop\. In each iteration:

1. 1\.The current code is submitted to the Verus verifier\.
2. 2\.If verification fails, theError Analyzerparses the error message\.
3. 3\.ARouter\(or High\-level Planner\) selects the most appropriate repair action from a pool of 35 available actions based on the error type and code context\.
4. 4\.The selectedSub\-agent\(Executor\) generates a specific patch \(e\.g\., adding a lemma function, enabling a specific prover mode, applying divide\-and\-conquer for a specific property to be proved\)\.
5. 5\.The patch is applied, and the loop repeats\.

The process terminates when the code verifies successfully or when the budget \(20 attempts or 20 minutes\) is exhausted\.

Sub\-agent Structure\.The framework comprises 15 specialized sub\-agents covering various aspects of formal verification, including but not limited to:

- •Invariant Manager:For analyzing and fixing loop invariants\.
- •Proof Strategy Applicator:For conducting proof strategies like divide\-and\-conquer \(i\.e\., case analysis\) and induction\.
- •Prover Mode Activator:For enabling special prover modes, like bit\-vector mode, non\-linear arithmetic mode, etc\.
- •Syntax Fixer:For correcting Rust\-specific compilation errors\.
- •Standard Lemma Guider:For suggesting what lemmas inside the Verus standard library might be useful\.

Optimization Scope\.Due to the domain\-intensive nature of Verus, generic prompts often fail to capture the nuances of formal reasoning\. STRACE targets the system prompts of theRouterand the top\-k most frequently triggeredExecutors, injecting synthesized domain heuristics \(e\.g\., specific strategies for handling "nonlinear arithmetic" errors\) directly into their context windows\.

## Appendix BSTRACE Implementation Details

### B\.1Architecture and Context Management

STRACE is implemented on top of the Claude\-Agent\-SDKAnthropic \([2025a](https://arxiv.org/html/2607.07702#bib.bib52)\)as a four\-phase agent workflow\. From an architectural perspective, the system separates the optimization process into four sequential phases, while adopting different context management strategies for different stages\. Phases 1–3 are executed within a shared context window\. This design is motivated by the strong continuity across these stages: all three phases rely on the same agent background, and they also need to share the textual dependency graph inferred during structural analysis\. As a result, there is a natural flow of information across the first three phases, where intermediate outputs produced in one phase directly serve as inputs to the next\. In contrast, the Phase 4 is executed in an isolated context window supported by the reason that STRACE has already identified the true root\-cause node and produced a concise explanation of why this node is the root cause within the slicing chain by the end of Phase 3\. Therefore, Phase 4 no longer needs access to the full intermediate context from the earlier stages\. Instead, it only needs the local context around the root\-cause node\. Separating Phase 4 from the earlier shared context thus reduces unnecessary context overhead and keeps the final revision step focused and modular\.

### B\.2Textual Dependency Graph Construction

In our experiments, STRACE instantiates Phase 1 with an optimizer agent built on the Claude Agent SDK under a dedicated textual dependency\-graph construction instruction\. The agent first inspects the target repository for available background artifacts, including README files, documentation, configuration files, agent definitions, and relevant source code\. It then identifies the major modules in the system, including active modules \(e\.g\., decision makers and executors\), passive shared\-state modules \(e\.g\., memory or state managers\), and the key artifacts each module produces or consumes\. Based on this repository\-level inspection, Phase 1 infers two types of dependency priors: data dependencies and control dependencies\. We refer to this textual dependency graph as the dependency prior and denote it by𝒢\\mathcal\{G\}\. Notably, the term “graph” reflects its node–edge structure, but its implementation is a text edge list rather than a learned graph object or a static\-program\-analysis graph\. Each edge is a textually specified relation between two components, together with its dependency type and brief evidence from repository artifacts\. Later diagnosis and slicing phases consume this textual graph as structural guidance\.

This construction is framework\-agnostic: the analyzed agent system may be implemented in different frameworks or coding styles, and STRACE does not require framework\-specific APIs for tools or agents\. Instead, it recovers dependency priors from repository\-level artifacts such as code, configuration, and agent definitions\.

To further analyze the role of graph quality in STRACE, we report two complementary studies: an expert\-reviewed comparison of repository\-constructed graphs across models and a graph perturbation experiment\. These studies address two questions: whether the dependency prior can be reliably constructed by different optimizer models, and whether STRACE remains effective when this prior is noisy\.

Table 3:Expert\-reviewed quality assessment of dependency graphs constructed from the repository by different models\.RQ1: Can different optimizer models construct a reliable dependency prior from the repository?

Table[3](https://arxiv.org/html/2607.07702#A2.T3)answers RQ1 by comparing dependency graphs constructed from the same repository using different models\. The expert review shows that all models recover the core dependency structure needed by STRACE\. Their differences mainly appear in granularity and the amount of extra infrastructure\-level detail: stronger models produce cleaner and more appropriately scoped graphs, while weaker models may introduce additional noisy edges\. Importantly, even the weakest graph still preserves the core dependencies and introduces only about 10% noisy edges, suggesting that the dependency\-prior construction is reasonably stable across optimizer backbones\.

RQ2: How sensitive is STRACE to noise in the dependency prior?

To answer RQ2, we conducted controlled perturbation experiments on the dependency prior, as shown in Table[4](https://arxiv.org/html/2607.07702#A2.T4)\. We randomly add or remove 10% or 25% of edges between graph nodes to simulate missing dependencies or additional noisy dependencies\. Removing the dependency graph entirely causes performance to fall back to the base\-agent level \(48%\), confirming that the structural prior is essential for effective optimization\.

In contrast, STRACE remains stable when the graph is only partially noisy: removing 25% of edges reduces success rate only slightly from 56% to 54%, while adding 25% of edges preserves the same 56% success rate\. At the smaller 10% perturbation level, performance is preserved or even improved\. These results indicate that STRACE benefits substantially from having a dependency prior, but does not require this prior to be perfectly specified\.

Table 4:Impact of dependency\-graph perturbations on Success Rate\.
### B\.3Visualization of Failure Pattern Mining

![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/Failure_Summarization.drawio.png)Figure 5:Visualization of aFailure Summarization Mapgenerated during the optimization of theIronKVproject\. STRACE first parses raw traces into structured execution records containing the global task outcome, local node status, and module invocation sequence\. The map then summarizes the trace corpus along two analytical dimensions:Statistical Severity, which estimates the conditional probability of global failure given each local node error, andStructural Path Patterns, which identifies recurring pathological trajectories such as self\-loops, oscillations, and dead ends\. These aggregated diagnostics serve as the quantitative basis for selecting high\-value traces for causal localization\.Figure[5](https://arxiv.org/html/2607.07702#A2.F5)provides a concrete example of the diagnostic summary produced by the failure pattern mining stage\. Rather than feeding raw traces directly into the optimizer, STRACE first converts heterogeneous logs into structured records and aggregates them into dataset\-level failure patterns\. This summary supports trace filtering through two complementary signals:

- •\(a\) Statistical Severity:The summary estimates the conditional failure probabilityP​\(Task Fail∣vi​Fail\)P\(\\text\{Task Fail\}\\mid v\_\{i\}\\text\{ Fail\}\), whereviv\_\{i\}denotes a local node error extracted from the structured trace record\. This identifies local failures that are strongly associated with global task failure, allowing STRACE to prioritize systemic bottlenecks over low\-impact or stochastic errors\.
- •\(b\) Structural Path Patterns:The summary also tracks module invocation sequences across traces to reveal recurring pathological trajectories\. Patterns such as self\-loops, oscillations, and dead ends indicate failure modes that cannot be captured by node\-level statistics alone, and help select traces that preserve diverse structural failure behaviors\.

Table 5:Ablation results with stage\-wise cost breakdown\.
### B\.4Instructions of Phases

For readability, we present simplified versions of the instructions for each phase in this appendix, as shown in Figures[6](https://arxiv.org/html/2607.07702#A4.F6)–[9](https://arxiv.org/html/2607.07702#A4.F9)\. To support reproducibility and reuse, the GitHub repository includes the full instruction templates together with a skill\-based version that packages the same workflow for direct plug\-in use\.

## Appendix CMore Experiments Results

### C\.1Stage\-wise Cost Breakdown for the Ablation Study

Table[5](https://arxiv.org/html/2607.07702#A2.T5)reports the stage\-wise cost of STRACE in USD\. Cost is estimated by tracking the input and output tokens consumed by optimizer\-side LLM calls and multiplying them by the Claude Sonnet 4\.5 API prices\. For stage\-wise cost, we apply the same calculation only to LLM calls within each phase, and the overall cost is the sum across phases\. Phase 1 corresponds toStructural Modeling, Phase 2 toFailure Pattern Mining and Trace Filtering, Phase 3 toCausal Localization, and Phase 4 toInductive Policy Optimization\. A dash indicates the corresponding stage is removed in that variant\.

#### STRACE\.

The overall cost is 2\.9563, dominated by Phase 4 \(1\.8052; 61\.1%\), followed by Phase 3 \(0\.8515; 28\.8%\)\. Phase 1 \(0\.1135; 3\.8%\) and Phase 2 \(0\.1861; 6\.3%\) contribute a relatively small fraction, indicating that the main cost driver is the downstream optimization stage, while diagnosis and slicing introduce only modest overhead\.

#### w/o Structural Modeling \(removing Phase 1\)\.

This variant removes Phase 1 to analyze the cost and performance impact of the dependency prior\. Although Phase 1 itself is inexpensive in STRACE \(0\.1135, only 3\.8% of the total cost\), removing it produces the largest performance degradation in the ablation study, reducing success rate from 56% to 48%\. At the same time, the overall cost increases from 2\.9563 to 5\.1045, an increase of about 2\.15\. This indicates that without the dependency prior, the optimizer must spend substantially more effort inferring relationships among different components from traces alone, inspecting more trajectory context to reason about possible causal paths\. Moreover, this inference is less reliable and can lead to incorrect failure paths\. Thus, Phase 1 has low direct cost but plays an important role in making subsequent localization and repair both more accurate and more efficient\.

#### w/o Trace Filtering \(removing Phase 2\)\.

This variant removes Phase 2 and yields an overall cost of 8\.4489, where Phase 4 alone increases to 7\.602 \(90\.0% of the total\)\. In comparison, Phase 1 \(0\.1667; 2\.0%\) and Phase 3 \(0\.6802; 8\.1%\) remain small\. The cost inflation is therefore primarily concentrated in Phase 4, consistent with the intuition that without diagnosis\-driven localization, the subsequent optimization must operate with less targeted signals and incurs substantially higher downstream search/optimization overhead\.

#### w/o Slicing \(Current Node\) \(removing Phase 3\)\.

With slicing removed, the overall cost becomes 2\.8762\. The cost is still dominated by Phase 4 \(2\.0486; 71\.2%\), while Phase 1 and Phase 2 increase to 0\.2956 \(10\.3%\) and 0\.5320 \(18\.5%\), respectively\. This suggests that when compact dependency\-preserving slices are unavailable, more computation shifts to earlier stages \(especially diagnosis\) and the optimization stage remains the major cost component\.

#### w/o Slicing \(Full Trace\) \(removing Phase 3\)\.

This variant also removes Phase 3 but uses the complete trajectory as context, resulting in an overall cost of 5\.9276\. Phase 4 rises sharply to 5\.3179 \(89\.7%\), while Phase 1 and Phase 2 are 0\.2500 \(4\.2%\) and 0\.3597 \(6\.1%\)\. Compared to STRACE, the increase is almost entirely attributable to Phase 4, consistent with token/turn blow\-up when long\-horizon, unfiltered traces are directly used in downstream prompt optimization\.

Table 6:Average Turns of STRACE and VeruSAGE\.Table 7:Performance on VeruSAGE\-Bench of STRACE and other hands\-off models\.
#### Summary\.

Across variants, the largest cost variations are concentrated in Phase 4\. Phase 2 \(trace filtering\) primarily reduces downstream optimization overhead by localizing failures, while Phase 3 \(causal localization\) avoids shifting costs to Phase 4 by providing compact, dependency\-preserving context in place of full\-trace inputs\.

### C\.2Average Turns of VeruSAGE \(STRACE\-enhanced\) Compared to the Base Agent

In VeruSAGE, a*turn*is the atomic unit of a repair attempt in the outer interaction loop, reflecting how many iterations are needed before the system succeeds or terminates\. For most failure types, invoking a single sub\-agent to propose and apply a fix counts as one turn\. For assertion failures, VeruSAGE first triggers anassertion\_reasoning\_pipelinesub\-agent that analyzes the error and selects a specialized downstream sub\-agent; in this case, theassertion\_reasoning\_pipelinetogether with its selected sub\-agent are treated as one turn, since they form a coupled decision–execution step within the same outer\-loop attempt\.

Average Turnscomplements Success Rate by characterizing efficiency among successful \(and attempted\) repairs\. Fewer turns indicate faster convergence with fewer outer\-loop iterations, which typically corresponds to fewer LLM calls, lower latency, and reduced interaction overhead under the same stopping criteria \(i\.e\., stopping early upon success or terminating at the maximum allowed attempts\)\. For each task instance, the number of turns is counted until success\. If the agent fails to solve within the allowed attempts, the maximum\-turn cutoff is recorded\. The reported value is then averaged across the evaluation set\.

As shown in Table[6](https://arxiv.org/html/2607.07702#A3.T6), VeruSAGE \(STRACE\-enhanced\) consistently requires fewer turns than the VeruSAGE base agent across all five VeruSAGE\-Bench categories, indicating faster convergence in the outer repair loop\. The reduction is most pronounced on the more challenging benchmarks \(e\.g\., IronKV and NRKernel\), while the remaining categories also exhibit steady decreases\. Overall, these results suggest that STRACE\-enhanced prompting improves per\-turn decision quality and action effectiveness within VeruSAGE, thereby reaching a valid repair with fewer interaction rounds and lower iterative overhead under the same stopping criteria\.

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

We additionally compare STRACE with hands\-off agents reported in VeruSAGE\. In VeruSAGE, the hands\-off approach instantiates a generic coding agent \(a CLI agent\) with a lightweight prompt that primarily enforces anti\-cheating constraints, while granting the model direct tool access to \(i\) running Verus, \(ii\) running a cheat checker, and \(iii\) inspecting the Verus standard library \(vstd\) as needed\. This setting intentionally provides little verification\-specific tutoring, and relies on the underlying coding capability of frontier models together with tool feedback from the verifier\.Yanget al\.\([2025](https://arxiv.org/html/2607.07702#bib.bib35)\)

We report two hands\-off baselines based on frontier models: GPT\-5 and Claude Sonnet 4\. Their hands\-off numbers are collected from the VeruSAGE study and used as reference results under the same VeruSAGE\-Bench suite and evaluation protocol\. STRACE is evaluated on the same benchmark split and compared against these hands\-off agents accordingly\.

As shown in Table[7](https://arxiv.org/html/2607.07702#A3.T7), STRACE optimized VeruSAGE achieves an overall success rate that is competitive with strong hands\-off agents\. In particular, STRACE outperforms the hands\-off GPT\-5 baseline in overall SR, and reaches a comparable overall level to Claude Sonnet 4 \(58\.5% vs 59\.4%\), despite using a substantially smaller model o4\-mini\. The gains are most evident on Memory Allocator, Node Replication, and Storage, indicating that our learned, task\-specific guidance can substantially improve repair reliability in several benchmark categories\. Meanwhile, the gap on IronKV and NRKernel suggests that some failure modes still benefit from stronger general reasoning and long\-horizon robustness\. These results demonstrate that STRACE can meaningfully close the performance gap between lightweight models and frontier hands\-off agents on VeruSAGE\-Bench\.

## Appendix DEvolution Examples in VeruSAGE Task

In this section, we present the actual generalized rules synthesized from the VeruSAGE benchmark for theassertion\_reasoning\_pipelinemodule\. Crucially, STRACE de\-contextualizes specific trace observations \(e\.g\.,"Sub\-agent A failed on input X"\) into transferable heuristics reusable across varying proof states\. In particular, the revised prompt distills three types of reusable rules:

1. 1\.Failure\-aware stopping condition and action switching\. - •Track repeated failures:Maintain awareness of how many times each action type has been attempted and rejected under the current proof context\. - •Stopping condition:If an action has been attempted 2–3 times and is consistently rejected \(especially due to syntax errors or does not fix the target assertion\),do notselect that action again in the same context\. - •Action switching:Instead, switch to a different secondary action from the candidate set; if all reasonable options are exhausted, explicitly mark the issue as requiring human intervention\. - •Example:If INDUCTION fails three times with syntax errors, switch to alternatives such as USELEMMA or CASE\_ANALYSIS rather than retrying INDUCTION again\.
2. 2\.Sub\-agent\-selection boundaries and actionable guidance\. - •General requirement:The guidance field must be specific and actionable \(avoid generic suggestions\); include concrete anchors from the visible code and the current goal structure\. - •USELEMMA:Identify specific helper lemmas/proof functions available in the file and state what each lemma establishes\. Donotselect USELEMMA if no relevant lemmas exist; prefer actions that construct the proof directly \(e\.g\., CASE\_ANALYSIS, INDUCTION, COMPUTE\)\. - •CASE\_ANALYSIS:Specify the exact variable or expression to split on and what each branch should establish \(e\.g\., which inequality or domain condition is proven in each case\)\. - •INDUCTION:State the inductive structure \(base case and inductive hypothesis\) and how the hypothesis connects to the current goal\. - •EXTENSIONAL\_EQUALITY:Indicate which collection equality/property requires element\-wise reasoning and what domain/length conditions need to be established\. - •SEQSETMAP:List the 2–3 most relevant Seq/Set/Map lemmas to invoke; avoid invoking an overly broad lemma set to prevent timeouts\.
3. 3\.Multi\-round planning strategy\. - •Build on progress:Explicitly reference what has been established by previously accepted fixes and explain how the next action extends that progress\. - •Develop a short proof plan:For complex goals, outline a minimal multi\-step plan \(e\.g\., establish a key auxiliary fact, prove the main implication, connect to the final goal\)\. - •Avoid random exploration:Do not switch between unrelated actions without a clear logical progression; each action should advance the proof toward the current failing goal\.

![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/phase1.drawio.png)Figure 6:Instruction for Phase 1–Structural Modeling\.![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/phase2.drawio.png)Figure 7:Instruction for Phase 2 – Failure Pattern Mining and Trace Filtering\.![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/phase3.drawio.png)Figure 8:Instruction for Phase 3 – Causal Localization\.![Refer to caption](https://arxiv.org/html/2607.07702v1/figure/phase4.drawio.png)Figure 9:Instruction for Phase 4 – Inductive Policy Optimization\.