When a pipeline of cooperating language-model agents fails, current debugging tools ask one question: which single step caused this? That framing breaks when two steps are broken at once. An early agent's corrupted tool output can cause a downstream failure that hides a second, independent bug in a later agent. Two individually harmless mistakes can also combine into a failure that neither causes alone. We propose diagnosing such failures the way classical hardware diagnosis handles concurrent faults. Each failed check in the execution trace yields a conflict set, meaning a group of steps of which at least one must be faulty. The candidate explanations are the smallest sets of steps that touch every conflict. The system then disambiguates among them by choosing cheap, targeted counterfactual replays, where one agent step is re-run on repaired inputs, so that each probe gives the most information per token and per second spent.
The opportunity matters because multi-agent systems are now deployed in settings where re-running the whole workflow is expensive and a missed latent bug resurfaces later. The single-cause shortcut is attractive because it reduces a search over all $2^N$ fault combinations among $N$ steps to a search over $N$ candidates. Our bet is that the structure of agent traces keeps the multi-fault search small enough to solve exactly. That structure is explicit message passing, natural module boundaries at agent edges, and the ability to replay a step in isolation. The real cost then lies in choosing which replays to pay for, and that choice is a multi-objective budgeting problem rather than a combinatorial one.
Core Claim
On multi-agent traces containing two or three concurrent injected faults, a diagnoser that combines conflict-set reasoning with cost-aware counterfactual replay will recover the full set of root causes more often than single-cause rankers, and at lower token and latency cost than repeated localize-fix-rerun loops. The gain should concentrate in two cases. The first is masking, where an upstream fault hides a downstream one. The second is joint faults, where only the combination triggers the failure. On independent, non-interacting faults we expect little or no gain, and the experiments are designed to show that boundary honestly.
Positioning Against Prior Work
The closest work is AgentTrace. It builds a causal graph of a multi-agent run with sequential, communication, and data-dependency edges, walks backward from the error, and ranks ancestors with a weighted feature score. It reaches 94.9% Hit@1 on 550 synthetic single-fault scenarios, and its limitations section explicitly names the "Single Root Cause Assumption." We reuse its trace graph and its ranking features as a prior over which steps are likely faulty. We replace "return the top-ranked node" with "return the most probable minimal set of faulty nodes, refined by probes."
Software and operations debuggers motivate the gap from the other side. AgentFL, UniDebugger and RCLAgent split fault localization across specialized agents. AgentFL uses a fixed three-stage procedure, UniDebugger escalates through three levels of agents, and RCLAgent uses recursive trace and metric agents for microservices. All three are evaluated on single-defect or single-incident benchmarks, and all three spend compute through fixed pipelines or fail-then-escalate rules rather than by choosing actions for their value per cost. They are agents doing diagnosis. We diagnose agents, and we make the spending decision explicit.
The method comes from model-based diagnosis. Diagnosing a Strong-Fault Model by Conflict and Consistency combines conflict sets with consistency sets, which record evidence that a component behaved correctly, to prune multi-fault search on a 20-component spacecraft model. Sensor Placement for Online Fault Diagnosis chooses minimal observations for active diagnosis and scales by partitioning the system into modules, though only for single-component faults. We transfer three ideas from these papers: conflict and consistency reasoning, the idea of choosing observations under cost, and modular partitioning, here along agent boundaries. The new element relative to both is a probe action that only exists in software agents, which is replaying a step with its inputs held fixed or repaired.
Self-Resource Allocation in Multi-Agent LLM Systems shows that planner agents cannot infer which workers are degraded without explicit capability hints. We use this as motivation and as a secondary testbed, not as a method. DRIFT-BENCH constrains our design. It shows that long multi-turn dialogue in tool environments causes context overload and malformed tool calls, which argues against diagnosis by open-ended agent discussion and in favor of short, structured probes.
Research Program
The diagnoser works in four stages.
Building conflicts and diagnoses. The diagnoser first builds the AgentTrace-style graph of a failed run. It then turns every failed check into a conflict over that check's ancestors in the graph. Checks include the final error, intermediate validators, schema checks on tool calls, and a downstream agent rejecting an upstream message. Checks that pass yield consistency evidence, but only for fault types with known signatures, such as malformed JSON or a wrong tool name. For semantic errors, a passing check does not prove health. Diagnoses are the minimal hitting sets of the conflicts. A hitting set is a set of steps that includes at least one member of every conflict. Traces have tens to a few hundred steps, and agent boundaries split the graph into weakly coupled modules, so we expect an exact solver to enumerate these sets cheaply. Measuring that is part of the work, and an approximate enumerator is the fallback if it fails. Each diagnosis is scored with a prior built from AgentTrace's features plus a per-step fault rate.
Probing. A probe $q$ re-executes one step under an intervention. The step's recorded inputs can be replaced by inputs regenerated from upstream steps currently believed healthy. Alternatively, its output can be substituted with a reference model's output and the downstream steps re-run. Each probe has a token cost $c_{\text{tok}}(q)$ and a wall-clock cost $c_{\text{time}}(q)$. Probes are chosen greedily by
$$q^* = \arg\max_q \frac{H(D) - \mathbb{E}_{o \sim q}\,[H(D \mid o)]}{\lambda\, c_{\text{tok}}(q) + (1-\lambda)\, c_{\text{time}}(q)},$$
where $D$ is the current distribution over diagnoses, $H$ is its entropy, $o$ is the probe outcome, and $\lambda \in [0,1]$ sets the weight between token cost and latency. Sweeping $\lambda$ and the stopping threshold traces a frontier of accuracy against cost against latency, rather than a single operating point.
Why the probes break masking. Replaying step B on repaired inputs tests B's own health regardless of whether upstream A is faulty, so a fault hidden behind A becomes visible. Replaying A alone with B's original output held fixed exposes jointly necessary faults, since the failure persists or vanishes depending on whether both are present.
Benchmark construction. No multi-fault benchmark for agent traces exists in the material, so building one is a deliverable. We follow AgentTrace's protocol of injected faults across many task domains. Faults include corrupted tool outputs, hallucinated or truncated messages, wrong parameters, and dropped context. We inject them in pairs and triples, and each instance is labeled by interaction type: independent, masking, or jointly necessary. Ground truth is known by construction. We will also keep a single-fault split so that regressions against AgentTrace's setting are visible.
Baselines
The naive reference point is the error-manifestation node plus the earliest-ancestor heuristic. AgentTrace reports that positional features alone reach 87.3% Hit@1 in the single-fault setting, which makes this the "do nothing clever" bar. On multi-fault data we predict it finds at most one of the faults per instance.
The strongest existing method is AgentTrace's full five-feature ranker. In its own paper it reports 94.9% Hit@1 on its synthetic benchmark, against 68.5% Hit@1 for a GPT-4 baseline. The file does not say whether its code or data are released. We will reimplement the ranker from the paper's description, confirm on our single-fault split that we land near its reported accuracy, and then extend it to multi-fault output in the most generous way. That extension returns the top-k ranked nodes with k set by an oracle to the true fault count. No reported result was found on Lacuna for any method on multi-fault agent traces.
The iterative baseline localizes one fault with AgentTrace, repairs it with an oracle fix, re-runs the full workflow, and repeats until the run succeeds. It receives the same token and time accounting as our probes.
A monolithic frontier model sees the whole trace with chain-of-thought and is asked for the set of faulty steps. A structured multi-agent debugger, adapted from AgentFL's three stages and limited to the same budget, is a further comparison.
Three ablations isolate the key ingredients. The first removes probes, leaving passive hitting-set diagnosis only. The second keeps probes but chooses them uniformly at random under an equal budget, which isolates cost-aware selection. The third drops consistency evidence.
All methods use the same backbone model for replays and the same trace data. Every method that has thresholds gets a matched tuning budget on a held-out split, and every method is charged the same per-token price. Beating the field means two things. Our method must achieve higher exact-set match and set-level F1 than top-k AgentTrace with oracle k on the masking and joint splits. It must also match or beat the iterative loop's accuracy at clearly lower median cost, judged as a dominated point on the cost–accuracy frontier.
Why not just…?
Why not just take AgentTrace's top-k candidates? For independent faults this may well be competitive, and we expect it to be. Under masking, however, the hidden fault often has weak positional and flow features, because its effects were overwritten by the upstream error. Ranking alone has no evidence to promote it. Comparing the masking split against the independent split, with oracle k granted to this baseline, settles whether the probes add anything beyond better ranking.
Why not just fix the first fault and re-run? This is the most serious threat, because for "either fault alone causes failure" cases it eventually finds everything. It has three weaknesses. It pays for a full workflow rerun per fault. It needs a correct repair, which a deployed diagnoser often does not have. On jointly necessary faults it stops after one fix, because the failure disappears and the second fault stays latent. The point made in the research file on multi-misconfigurations, that each setting looks valid in isolation, describes exactly this case. If the iterative loop matches us on the frontier even on the joint split, we will report that the probe machinery is unnecessary.
Why not just give a frontier model the whole trace? AgentTrace already shows GPT-4 at 68.5% Hit@1 against 94.9% for structured tracing in the easier single-fault setting. It also shows the model tending to blame the node where the error appears rather than its cause. Multi-fault traces should make this worse, and we include the baseline to measure by how much.
Why not just use a general multi-objective optimizer such as NSGA-II over probe sets? It would be a valid way to compute the frontier offline, and we will use it on small instances to check how far the greedy rule falls from the true frontier. Diagnosis is sequential, though: each probe outcome changes the value of every other probe. A population search that is rerun after every observation spends far more than the probes it is choosing, so greedy information-per-cost is the practical online rule. That design choice is checked empirically rather than assumed.
Proposed Experiments
The primary experiment runs every method on the constructed benchmark and reports exact-set match, set F1, per-fault recall, tokens and dollars per diagnosis, and wall-clock time, broken down by interaction type and fault count. The decisive check has a clear pass condition. The full method must improve set F1 over oracle-k AgentTrace on masking and joint instances. The random-probe ablation at equal budget must lose most of that gain. If the random-probe ablation matches the full method, cost-aware selection is not doing the work, and the claim reduces to "replays help."
A second check measures scaling. It records hitting-set enumeration time and probe count as traces grow, comparing partitioning along agent boundaries with no partitioning, by analogy to the modularity result in the sensor-placement work.
A third, smaller transfer test uses CuisineWorld from Self-Resource Allocation in Multi-Agent LLM Systems. Two workers are silently degraded at once, and the diagnoser's output replaces the hand-written capability hints. The paper reports efficiency rising from 1.67 to 4.44 when hints are given, so the question is how much of that gap inferred diagnoses close without hints.
We will also report the single-fault split. A method that wins on multi-fault data but loses noticeably to AgentTrace on single faults would not be a practical replacement.
References
- AgentTrace: Causal Graph Tracing for Root Cause Analysis in Deployed Multi-Agent Systems
- AgentFL: Scaling LLM-based Fault Localization to Project-Level Context
- UniDebugger: Hierarchical Multi-Agent Framework for Unified Software Debugging
- Adaptive Root Cause Localization for Microservice Systems with Multi-Agent Recursion-of-Thought
- Diagnosing a Strong-Fault Model by Conflict and Consistency
- Sensor Placement for Online Fault Diagnosis
- Self-Resource Allocation in Multi-Agent LLM Systems
- DRIFT-BENCH: Diagnosing CoopeRative Breakdowns in LLM Agents under Input Faults via Multi-Turn Interaction