TL;DR
When Large Language Model (LLM) multi-agent systems fail, pinpointing the exact "decisive error" in a long interaction trace is notoriously difficult. This paper introduces a framework based on Conformal Prediction that guarantees, with user-defined confidence, a contiguous sequence of steps containing the error. This allows systems to reliably roll back and correct their own mistakes without wasting compute.
What Problem Does This Paper Address?
Multi-agent systems (MAS) are increasingly deployed for complex tasks like software engineering and scientific discovery. However, their long interaction traces make them prone to compounding errors. When a task fails, identifying the decisive error—the earliest point of no return—is critical for debugging and automated recovery.
Existing error attribution methods typically rely on "point predictions" (e.g., an LLM-as-a-judge guessing a single responsible step). These methods offer no principled uncertainty quantification; if the guess is wrong, any automated recovery attempt will fail. Furthermore, standard uncertainty frameworks don't account for the sequential nature of agent trajectories, often outputting scattered, non-contiguous sets of steps that are impossible to use for system rollbacks.
Methods
The authors leverage Conformal Prediction (CP), a framework that provides finite-sample, distribution-free coverage guarantees. To adapt CP for sequential data, they introduce three novel filtration-based algorithms that ensure the predicted uncertainty set is always a contiguous sequence of steps:
-
Left Filtration (LF): Progressively removes steps from the left (start) of the trajectory until the remaining suffix scores below a calibrated threshold. Left filtering progressively removes steps from the left as the threshold decreases.
-
Right Filtration (RF): Progressively removes steps from the right (end), returning a valid prefix.
- Two-Way Filtration (TWF): Computes the intersection of LF and RF, allowing the system to isolate errors that occur in the middle of a trajectory. Two-way filtering intersects left and right filtrations to isolate errors.
These algorithms are paired with LLM-based scoring functions (Naive, Role-Prompted, and Fine-Tuned) to evaluate step-level error likelihoods. Finally, the authors implement Conformal Agent Rollbacks: when a failure is detected, the MAS state is automatically rolled back to the first step of the conformal prediction set, providing a reliable window for the agent to replan and self-correct. Conformal rollbacks reset the agent state to the earliest step in the predicted set.
Datasets
The framework was evaluated on both real-world and synthetic multi-agent failure traces:
- Who&When: A small-scale, real-world benchmark consisting of 184 multi-agent execution traces annotated by humans with step-level errors.
- Synthetic Datasets (MATH & GSM8k): 1,200 failed trajectories generated via targeted error injection across two multi-agent architectures (MACNET and DyLAN). To thoroughly test the filtration algorithms, the authors created positional variants: Left Dense, Mid Dense, and Right Dense, reflecting different temporal distributions of errors. Distribution of decisive error positions across the benchmarks.
Key Insights and Ideas
- Contiguity is Essential for Sequences: While standard CP algorithms output arbitrary sets of labels, forcing the prediction sets to be contiguous blocks aligns perfectly with the ordinal nature of time and agent states, making the outputs actionable for rollbacks.
- Filtration Saves Compute: Unlike baseline methods that must score every single step in a trajectory, LF and RF stop evaluating steps once their calibrated threshold is crossed. This significantly reduces the Number of Function Evaluations (NFE) at inference time.
- Algorithm-Distribution Matching: The efficiency of the filtration method depends heavily on matching the algorithm to the dataset's error bias. For example, if errors tend to happen early in a trajectory (as in the Who&When dataset), Right Filtration yields the smallest, most precise prediction sets.
Key Results
- Guarantees Validated: Empirical testing confirmed that all proposed filtration methods strictly satisfy the theoretical coverage guarantees, maintaining the user-specified error tolerance (e.g., 80% target coverage).
- Fine-Tuning Wins: A specialized, fine-tuned Qwen3-1.7B scoring function achieved an AUROC of 0.762, drastically outperforming a naive GPT-4o-mini judge (0.519 AUROC).
- High Removal Rates: The filtration methods successfully filtered out up to 60-70% of the failed trajectories while maintaining the required coverage, drastically narrowing down the search space for human debuggers or automated systems.
- Successful Self-Correction: In automated rollback trials, using Left Filtration to determine the restart point achieved higher task recovery success rates than standard point-prediction baselines, while providing explicit statistical control over the rollback window.
Limitations and Future Work
- Exchangeability Dependency: The proofs rely on the standard CP assumption that calibration and test data are exchangeable. Real-world deployment facing severe distribution shifts will require adaptive CP extensions.
- Prior Knowledge of Error Distribution: Practitioners must have some prior understanding of their system's error distribution to choose the optimal filtration direction (Left, Right, or Two-Way).
- Single Decisive Error Assumption: The current framework assumes a single fatal error per trajectory. The authors note that expanding this to handle multiple cascading errors via recall-level conformal guarantees is a promising next step.
Summary updated