Minimal Repair Subtrajectories (MRS)

Official code, paper source, experimental summaries, and reproducibility materials for Minimal Repair Subtrajectories: Certified Recovery for Deterministic Failures in Long-Horizon Agent Tasks.

AAAI 2027 submission — under review.

Overview

Long-horizon LLM agents often fail through cascades across interdependent tool calls. Repairing one isolated action can be too narrow, while regenerating an entire trajectory discards a prefix that may already be correct. MRS defines a repair unit between these extremes: the shortest contiguous subtrajectory whose replacement, followed by verifier-backed replay, restores task success.

The repository contains:

• controlled DependentTools and DependentBooking environments;
• contiguous-span search and deterministic replay verification;
• strict-replay integration for tau2;
• matched repair adapters for ToolSandbox, AppWorld, and ALFWorld;
• neighboring-unit, shrink-quality, and contiguity audits;
• LoRA data preparation, training, and evaluation scripts;
• compact aggregate results, paper source, and technical supplement.

Main findings

• In the full controlled analysis, 72% of 81,920 parameterized DependentTools failures require repairing two to four steps.
• On the tau2 strict-replay subset, the framework recovers 34 of 53 eligible failures (64.2%), including five multi-step repairs.
• On a fresh 960-failure audit, MRS matches the 100% recovery of wider repair units while replacing 1.98–3.16× fewer actions.
• With matched fine-tuning examples, MRS supervision raises recovery from 51.9% to 67.3% and exact-minimal localization from 42.1% to 58.9%.
• ToolSandbox, AppWorld, and ALFWorld expose a practical routing principle: preserve and repair a trustworthy prefix; restart when the plan is globally invalid.

Repository layout

.
├── code/                          # Runnable method and experiment code
│   ├── VRSO/formal_experiments/   # MRS search, replay, and controlled tasks
│   ├── public/                    # Public benchmark repair adapters
│   ├── scripts/                   # Audits, tau2, and LoRA entry points
│   ├── configs/                   # Search and benchmark configuration
│   └── results/                   # Compact reported aggregates
├── paper/
│   ├── source/                    # AAAI LaTeX, bibliography, checklist, figures
│   └── submitted/                 # Submitted paper and checklist PDFs
├── supplement/
│   ├── TechnicalSupplement.tex    # Single-file AAAI technical supplement
│   └── aaai2027.sty               # Official AAAI style required to compile
├── docs/
│   ├── REPRODUCIBILITY.md         # Reproduction paths and requirements
│   ├── RESULTS.md                 # Result/claim map
│   └── DATA_AND_ARTIFACTS.md      # Dataset and artifact boundaries
├── LICENSE
└── README.md

Quick start

The controlled audit is CPU-only and requires Python 3.10 or newer.

python -m venv .venv
source .venv/bin/activate
python -m pip install -r code/requirements.txt
cd code
python scripts/run_dependent_tool_multiseed.py \
  --run-name reproduction \
  --seeds 3,7,11,13,17,19,23,29,31,37,41,43,47,53,59 \
  --train-count 512 --eval-count 64 \
  --max-span-length 4 --failure-set extended

The expected aggregate is in code/results/controlled_15seed_summary.json. For other paths, see docs/REPRODUCIBILITY.md. Public benchmark datasets, model weights, and API credentials are not redistributed.

Paper and supplement

• Submitted paper
• Reproducibility checklist
• Paper LaTeX source
• Technical supplement

Scope of certification

Controlled experiments can establish exact minimality within their fixed replacement space by exhausting every shorter contiguous span. Public environments report verifier-certified recovery from regenerated suffixes; they test prefix validity and practical recovery rather than exhaustive minimality.

License

Original code in this repository is released under the MIT License. Public benchmarks, datasets, models, and their assets remain governed by their respective licenses and distribution terms.