Failure Recovery via Belief Updates and World Modeling for Long-Horizon Agents

AI summary

Overview

Research area: Machine learning — LLM-based long-horizon agents, failure recovery, agentic world modeling, and knowledge distillation.

Technical level: Advanced. The paper assumes familiarity with LLM agent harnesses, probabilistic belief/odds-factor updates, tree-search-style recovery with checkpoint rollback, LoRA fine-tuning, and on-policy distillation.

Scope: A framework (BeliefWeaver) that treats long-horizon failure recovery as persistent, evidence-weighted exploration over "repair hypotheses," supported by an implicit world model that is then distilled into a 9B student, evaluated on 113 terminal-based tasks across three benchmarks.

What This Paper Is About

Long-horizon agents often fail for reasons that happened many steps earlier, so when something breaks, reflecting on the most recent action or simply backtracking is not enough to find the cause. The authors argue that recovery needs two things current methods lack: memory of evidence that survives rollback and is shared across related repair attempts, and a way to reason prospectively about which untried repair direction is worth pursuing.

Their goal is a recovery controller that keeps a persistent, relational belief state over candidate repairs, uses verifier-grounded evidence to re-rank those candidates (including ones not tried in the latest attempt), and separately decides which candidates are eligible to execute. To keep this affordable, they distill the repeated model-assisted reasoning into a 9B student.

Key Contributions

1. An evidence-driven recovery controller. It maintains a relational exploration graph over frontiers (testable repair hypotheses), attempts, observations, and checkpoints, and turns retained execution evidence plus inferred relations into explicit frontier priority updates — so a failed attempt can re-rank a related hypothesis that was never executed in that attempt. Execution eligibility is handled by a separate diagnostic gate rather than by the priority score.

2. An implicit world model (IWM) for prospective reasoning. The IWM assesses repair hypotheses against available evidence, estimates potential repair progress, and infers relations among frontiers to guide generation, refinement, and reopening of hypotheses.

3. Distillation of the recurring IWM roles into a 9B student. Four recurring model-assisted roles — probe generation, evidence judgment, frontier-relation inference, and task-clause assessment — are transferred via supervised fine-tuning (SFT, LoRA) plus on-policy distillation (OPD), while the controller, executor, belief-update rules, and prospective evaluation stay unchanged.

4. A controlled empirical study. Component ablations (native continuation → structured continuation → world-model grounding → full BeliefWeaver) plus three distillation variants across three terminal benchmarks, with both task scores and resource/API accounting.

Main Findings

• Aggregate gain over the native baseline. BeliefWeaver improves Overall Final score by 5.1 percentage points over native Terminus-2 continuation (48.6 ± 6.7 → 53.7 ± 6.6), with the largest benchmark gain on TB3 (+10.1 points, 36.5 → 46.6). TB2 moves 66.9 → 71.2 and LHTB 12.3 → 14.8.

• Exploration efficiency also improves. The main text reports Overall Step-AUC up 2.8 points and Time-AUC up 1.6 points; Table 2 reports significant gains of +5.1 ± 2.7 (Final), +2.9 ± 1.7 (Step-AUC), +1.6 ± 1.7 (Time-AUC), and −17.7 ± 8.1 s execution time versus baseline.

• Components behave non-additively. Structured Continuation alone improves Overall Final, Step-AUC, and Time-AUC by 2.9, 0.9, and 1.1 points. Adding WM Grounding alone reduces Overall Final by 1.7 points with small AUC declines. Adding persistent relational beliefs and evidence-gated execution on top of grounding recovers and exceeds this: +3.9 Final, +2.4 Step-AUC, +1.0 Time-AUC. The authors note the last two components are introduced together, so their individual effects are not isolated.

• Executor savings at the cost of controller overhead. Relative to Terminus-2, BeliefWeaver reduces executor steps by 13.2%, execution time by 17.8%, and executor cost by 16.6%, reaching a higher Final score. Controller reservations rise to 33.4 per task, versus 9.1 or fewer for the ablation configurations — the stated motivation for distillation. (Table 3: 22.0 → 19.1 steps/task, 483.8 s → 397.9 s, $4.062 → $3.389 per task.)

• Distillation outperforms the matched teacher on final score. SFT + OPD reaches 58.4% Overall Final, 9.8 points above the native baseline (a significant gain per Table 2) and 4.7 points above the matched teacher (53.7%). Overall Step-AUC is 29.2 and Time-AUC 50.1 versus 26.7 and 46.8 for Terminus-2.

• SFT alone already helps. The SFT-only student reaches 55.6% Overall Final (Step-AUC 29.9, Time-AUC 50.3), indicating the structured IWM decisions can be learned from teacher supervision rather than requiring the teacher at every step.

• Large teacher API savings. SFT and SFT + OPD cut teacher requests and API cost by about 55% relative to the matched teacher (requests 32.9 → 14.6 and 15.0 per task; estimated cost $0.550 → $0.248 per task). The abstract reports a 54.8% reduction in estimated teacher API cost for the distilled student relative to the matched teacher. Moving repair-hypothesis generation to the student (SFT + OPD + Gen) reduces requests by 74.5% and API cost by 81.9% (from $0.550 to $0.100 per task), reaching 57.5% Final, 3.8 points above the matched teacher. Teacher token usage drops by 55.4%, 55.1%, and 81.1% respectively. API cost is estimated from recorded token usage at $1/$4 per million input/output tokens.

• Giving hypothesis generation to the student is not free. SFT + OPD + Gen's Final point estimate (57.5%) is below SFT + OPD (58.4%), even though it uses far fewer teacher calls.

• Benchmarks and models. 113 tasks total: 65 from Terminal-Bench 2.0, 23 from Terminal-Bench 3.0, 25 from Long-Horizon Terminal-Bench. Teacher experiments use DeepSeek V4 Pro; students are Qwen3.5-9B. Results are means with 95% bootstrap CI half-widths.

Methodology in Plain English

The agent is framed as exploring a changing set of frontiers — each a testable hypothesis about why the current solution is failing, what evidence would confirm it, and what check would prove the repair worked.

For each unresolved failure, a language model proposes candidate hypotheses using the task requirements, line-indexed source context, current diagnostics, and previous attempts. Each candidate gets a diagnostic probe: a command run in a temporary copy of the current checkpoint. A separate "evidence judge" compares the probe output to what the hypothesis predicted and returns one of three verdicts — consistent, insufficient, or contradicted. Only consistent candidates are eligible to execute; contradictions become refutation evidence.

Two prompt-based experts then estimate the consequences of pursuing a hypothesis: local_code traces relevant control and data flow to judge mechanism validity and expected progress, and contract_judge checks whether the implementation violates the cited task requirement. A relation query links candidates that share a mechanism or refine one another.

All of this is stored in a persistent graph that survives rollback. Each frontier carries a belief (priority) built from multiplicative odds factors over four kinds of evidence: repeated attempts (repeated failures lower priority), refinements (untried refinements stay promising), historical target feedback (targets that never improved are downweighted), and probe-based refutation. Crucially, graph relations decide which factors apply, so evidence from one attempt can change the priority of a related frontier that was never tried. Eligible frontiers are ranked by belief score minus a penalty for recently failed candidates; the top one is handed to the executor with its supporting evidence. A verifier scores the result — improving checkpoints are kept, unsuccessful ones rolled back — and the outcome is written back into the graph either way.

Because four IWM roles recur constantly and drive teacher cost, they are distilled: first SFT with LoRA on teacher-generated role-specific request–response pairs, then OPD, where the student explores on its own while a shadow teacher answers the same requests for supervision without overriding the student's outputs. New teacher-labeled data is merged with prior rounds and training resumes from the latest accepted adapter.

Why This Matters

Impact on research. The paper reframes failure recovery as cumulative evidence management rather than retry-and-reflect, and it makes a design argument that execution eligibility and candidate ranking should be separate mechanisms. It also shows that only a narrow slice of agentic reasoning (four recurring roles) needs to be distilled to cut teacher cost, which is a useful counterpoint to distilling whole agents.

Real-world applications:

• Coding and debugging agents operating in terminals and repositories, where a bug's root cause is many steps upstream of the visible symptom.
• Autonomous research agents that run experiments and must revise earlier assumptions when later evidence contradicts them.
• Computer-use / workflow automation agents, where a wrong early UI action silently corrupts later state.
• DevOps and CI remediation, where rollback to a known checkpoint and a different repair path is a normal operating mode.

Industry relevance. The API-cost accounting (per-task requests, tokens, and dollars; a $0.550 → $0.100 per-task reduction in the most aggressive setting) speaks directly to the economics of deploying long-horizon agents in production, where repeated frontier-model calls dominate cost. Persisting evidence across rollback is also a practical reliability property for systems that must recover without human intervention.

Future Directions

• Learned and uncertainty-aware belief updates. The current factors use fixed parameters (for example, λ_att = 0.34, set from development retry statistics); the authors propose learning these and incorporating uncertainty.
• Finer attribution among controller components. The paper explicitly notes that persistent relational beliefs and evidence-gated execution were introduced together, so their individual contributions are not isolated.
• Richer relation structure. The belief state currently models only a small set of relations between repair hypotheses, which may be too limited when several failure causes interact; the authors list this as a limitation.
• Recovery under sparse feedback or imperfect rollback. All experiments rely on terminal tasks with verifier feedback and reliable checkpoint restoration, so transfer to noisy or unavailable rollback is untested. The authors also flag that IWM prediction or relation errors can mis-rank frontiers and waste exploration effort.

Target Audience

Researchers and engineers building LLM agent systems for long-horizon tasks — particularly those working on agent memory, reflection, backtracking search, and test-time recovery — along with practitioners who need to cut inference cost by moving repeated reasoning into a smaller deployed model. Readers should be comfortable with probabilistic scoring (odds factors and beliefs), tree/graph-structured search over agent attempts, and standard fine-tuning plus distillation pipelines. Those new to agent architectures will find the framing accessible but the appendix-level detail and metric definitions (Step-AUC, Time-AUC) demanding.

Authors’ abstract

Long-horizon agents often struggle to recover from failures whose causes lie several steps earlier, beyond what local reflection or backtracking can resolve. We introduce BELIEFWEAVER, a framework that combines persistent evidence across attempts with prospective reasoning over repair directions. It maintains a relational belief state over frontiers, attempts, observations, and checkpoints. Execution evidence updates related frontier priorities across attempts and rollback, while diagnostic evidence gates execution. An implicit world model (IWM) evaluates repair hypotheses, predicts progress, and identifies relations among frontiers to guide exploration. We further distill these recurring IWM reasoning components into a 9B student through supervised fine-tuning and on-policy distillation (OPD). Across three terminal-based benchmarks, BELIEFWEAVER improves aggregate final score by 5.1 percentage points over native Terminus-2 continuation, with positive trends in exploration efficiency. The distilled 9B student improves final score by 9.8 percentage points over the reported native baseline while reducing estimated teacher API cost by 54.8% relative to the matched teacher. These results show that persistent evidence and prospective reasoning can improve recovery in long-horizon agent tasks while substantially reducing reliance on teacher-model inference.