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

TL;DR Highlight

Agent 실패 로그를 인과 그래프로 분석해 진짜 근본 원인만 골라내고, 해당 모듈 프롬프트만 정밀하게 수정하는 자동 최적화 프레임워크

Who Should Read

GPT-4o, o4-mini 기반 멀티 에이전트 시스템을 운영하면서 실패 원인을 찾고 프롬프트를 개선하려는 AI 엔지니어. 특히 장기(long-horizon) 태스크에서 에이전트가 왜 실패하는지 디버깅이 어려운 상황에 있는 개발자.

Core Mechanics

Agent 실행 로그를 단순 텍스트가 아니라 의존성 그래프(Execution Dependency Graph)로 모델링해서, Step 50의 에러가 실제로는 Step 5의 잘못된 결정에서 비롯됐음을 추적할 수 있음.
배치 단위로 실패 패턴을 마이닝해서 중복 로그를 제거하고 대표 실패 케이스만 남기는 trace filtering을 수행 — 453개 로그에서 소수의 exemplar만 선택해 최적화 비용을 통제.
오류가 드러난 지점(Manifestation Node)과 실제 원인 지점(Root Cause Node)을 구분하고, 의존성 역방향 탐색(backward slicing)으로 인과적으로 관련된 스텝만 추출한 compact causal slice를 만듦.
추출된 causal slice를 바탕으로 인스턴스별 패치가 아닌 재사용 가능한 일반화된 휴리스틱 규칙을 생성하고, 해당 근본 원인 모듈의 프롬프트에만 주입 — 코드 수정 없이 프롬프트만 업데이트.
Claude Sonnet 4.5를 메타 컨트롤러로 사용하고, 실제 에이전트 백본은 GPT-4o(HotpotQA/WebArena)와 o4-mini(VeruSAGE-Bench)를 사용해 실험.
전체 파이프라인 비용은 $2.96 수준으로, Trace Filtering 없이 실행하면 $8.45, 전체 trace를 그대로 쓰면 $5.93으로 비용이 급증.

Evidence

VeruSAGE-Bench(Rust 코드 형식 검증 태스크)에서 Base Agent 42.5% → STRACE 58.5%로 +16.0%p 개선, 2위 GEPA(47.2%) 대비 +11.3%p 차이.
WebArena 전체 성공률: Base Agent 10.8% → STRACE 23.7%(+12.9%p), TextGrad 17.3%, GEPA 16.5% 대비 압도적 우위.
HotpotQA Exact Match: Base Agent 37.0% → STRACE 68.5%, 가장 강한 베이스라인인 GEPA(64.4%) 대비 +4.1%p.
STRACE로 최적화된 o4-mini가 GPT-5 hands-off 에이전트(50.0%)를 능가하고(58.5%), Claude Sonnet 4 hands-off(59.4%)와 대등한 성능 — 더 작은 모델로 더 큰 모델 수준 달성.
VeruSAGE에서 평균 수리 턴 수가 IronKV 기준 12.04 → 8.42, NRKernel 14.83 → 8.20으로 감소해 효율도 개선됨.

How to Apply

멀티 에이전트 시스템을 운영 중이라면, 실패한 실행 로그를 모아 에이전트 코드베이스에서 모듈 간 data/control dependency를 먼저 텍스트 엣지 리스트로 추출 — LLM에게 README, 설정파일, 에이전트 정의를 읽혀서 그래프 자동 생성 가능.
대량의 실패 로그가 쌓였을 때, 각 로그의 global 성공/실패 여부와 어느 노드에서 에러가 났는지를 파싱해 P(Task Fail | Node Fail) 통계를 내고 중요한 실패 패턴 클러스터에서 대표 케이스만 선별 — 나머지 중복 로그는 버려도 됨.
단일 에이전트(WebArena처럼 프롬프트 하나짜리)에도 적용 가능 — 이 경우 dependency graph 없이 causal slicing을 타임스텝 단위로 적용하고, 생성된 휴리스틱을 해당 에이전트의 instruction에 append하면 됨.

Code Example

snippet

# STRACE 4단계 파이프라인 개념 구현 스케치

# Phase 1: Execution Dependency Graph 구성
system_prompt_phase1 = """
You are analyzing an agent system repository.
Identify all functional modules (V) and infer edges (E) between them:
- Data dependency: Module B consumes artifacts produced by Module A
- Control dependency: Module A governs whether Module B is invoked

Output as a text edge list:
<edges>
module_A -> module_B : data | artifact: intermediate_plan
module_A -> module_C : control | condition: error_type == 'syntax'
</edges>
"""

# Phase 2: 실패 패턴 요약 및 trace 필터링
failure_summary_prompt = """
Given execution traces, compute:
1. Statistical Severity: P(Task Fail | Node_i Fail) for each module
2. Structural Path Patterns: recurring pathological sequences (loops, dead-ends)

Select {s} representative traces covering distinct failure clusters.
"""

# Phase 3: Causal Localization - backward slicing
causal_localization_prompt = """
Given:
- Manifestation Node (vm): where error surfaces
- Dependency Graph (G)
- Execution Trace

Step 1: Starting from vm, traverse dependency edges BACKWARD.
        Retain only steps reachable via Data/Control dependency closure.
        This is the Causal Slice (C_slice).

Step 2: Within C_slice, identify Root Cause Node (vr):
        The earliest module where execution first deviated from intended logic.
        Example: Code Interpreter (vm) crashed because Planner (vr) hallucinated
        a parameter 45 steps earlier.

Output:
- Causal Slice: [step_1, step_5, step_12, step_48]
- Root Cause Node: planner_module
- Root Cause Explanation: ...
"""

# Phase 4: 귀납적 정책 최적화
policy_optimization_prompt = """
Given causal slices from multiple failures all traced to root cause module: {vr}

Synthesize GENERALIZED heuristic rules (not instance-specific patches):
- Identify recurring failure patterns across episodes
- Abstract into reusable preventive guidelines
- Format as instruction additions for the module's system prompt

Example output:
"When attempting action X more than 2 times with consistent rejection,
 switch to alternative action Y. Track attempt counts per action type."

Inject these rules ONLY into module {vr}'s prompt.
"""

# GitHub: https://github.com/moomight/STRACE

Terminology

Long-horizon Agent수십~수백 단계의 작업을 순차적으로 수행하는 AI 에이전트. 단순 Q&A가 아니라 코드 작성, 웹 탐색, 파일 편집 등 복잡한 작업을 자율적으로 처리.

Execution Dependency Graph (EDG)에이전트의 각 모듈 간 데이터 흐름과 제어 관계를 나타내는 그래프. A모듈의 출력이 B모듈의 입력이 된다면 A→B 엣지가 생김.

Backward Slicing에러가 발생한 지점에서 거꾸로 올라가며 원인이 된 단계들만 추출하는 기법. 마치 사고 조사에서 사건 발생 시점부터 역추적하는 것과 같음.

Causal Slice전체 실행 로그에서 실패와 인과적으로 연결된 스텝만 남긴 축약본. 관련 없는 탐색 경로나 병렬 브랜치는 제거됨.

Manifestation Node에러가 표면에 드러난 모듈. 예: 코드 실행기에서 크래시가 발생했다면 코드 실행기가 manifestation node.

Root Cause Node실제 로직 결함이 시작된 모듈. Manifestation Node와 다를 수 있음. 예: 코드 실행기 크래시의 진짜 원인이 45단계 전 플래너의 잘못된 파라미터일 수 있음.

Reflexive Optimization에이전트의 실패 기록을 LLM이 분석해서 스스로 프롬프트나 정책을 개선하는 방식. 인간이 직접 디버깅하지 않아도 자동으로 개선됨.

SNR (Signal-to-Noise Ratio)신호 대 잡음비. 여기서는 최적화에 유용한 정보(signal) 대 관계없는 노이즈의 비율. SNR이 높을수록 LLM이 올바른 수정 방향을 찾기 쉬움.

Related Papers

Related Resources

Original Abstract (Expand)

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 .