Source-linked AI summary
Localizing Emergent Failures in Agentic AI: Recovering Minimal Repair Families via Counterfactual Replay
Bingjie Li, Yumeng Song, Zhongming Yao, Tianyi Li
TL;DR
Agentic failures can require repairing combinations of interacting messages, which pointwise attribution cannot distinguish from alternative singleton repairs. The paper formulates recovery of all bounded minimal repair sets, proposes graph-constrained replay with clean counterparts, and reports exact family recovery with lower replay cost in symbolic and LLM settings.
Problem
Pointwise failure attribution cannot distinguish jointly necessary repairs from alternative singleton repairs in multi-agent interactions.
Method
GCJR slices graph-relevant events, tests graph-feasible singleton and pair interventions, and verifies them by replay with paired clean counterparts.
Results
GCJR achieves 1.000 Family Exact Match while reducing mean replay calls by 55.1% on 90 symbolic cases and mean LLM calls by 52.4% on 24 pilot cases.
Takeaways & Limitations
Set-valued repair families preserve distinctions lost by pointwise or fixed-cardinality rankings and identify jointly necessary repairs missed by single-event replay.
Abstract
from arXiv · showhide
Failures in agentic AI systems can arise from interactions among messages exchanged by multiple large language model (LLM) agents. Pointwise attribution cannot distinguish a jointly necessary repair from alternative singleton repairs. We formulate Minimal Repair Family Recovery (MRFR): recovering all inclusion-minimal event sets whose counterfactual replay restores task success within a declared size bound. We propose Graph-Constrained Joint Replay (GCJR), which slices failure-relevant events from an execution dependency graph, constructs graph-feasible singleton and pair candidates, and verifies them by replay with paired clean counterparts. For fixed replay outcomes, GCJR is exact within its declared graph domain. On 90 in-scope cases from a 120-DAG controlled benchmark, GCJR achieves 1.000 Family Exact Match while reducing mean replay calls from 56.3 to 25.3 (55.1%) relative to exhaustive search. On a 24-case, four-agent LLM pilot, it again achieves 1.000 Family Exact Match and reduces mean model calls from 21.0 to 10.0 (52.4%); single-event replay misses jointly necessary repairs.
I. INTRODUCTION
Multi-agent failures require set-level diagnosis because pointwise attribution cannot distinguish jointly necessary repairs from alternative repairs. GCJR addresses this by recovering bounded minimal repair families through graph-constrained replay and shows exact recovery with substantially fewer replay calls.
- Pointwise attribution cannot distinguish jointly necessary failures, where multiple messages must be repaired, from alternative-repair failures, where either message suffices.
- GCJR represents executions as interaction graphs, replaces selected messages with paired clean counterparts, and validates interventions by replaying from a checkpoint.
- GCJR returns every inclusion-minimal successful intervention within a declared graph-feasible search bound, preserving singleton, jointly necessary, and alternative repairs.
- The method is oracle-assisted: it localizes failures under controlled replay but does not automatically generate repair messages.
- 52–55% fewer replay calls are achieved while matching exhaustive search in repair-family recovery across symbolic workflows and a real LLM multi-agent system.
II. PROBLEM FORMULATION AND GCJR
The formulation models failed executions as dependency DAGs and defines repairs as inclusion-minimal successful interventions over declared candidates. GCJR uses replay outcomes to recover this set-valued target under explicit assumptions and bounds.
- A. Problem Formulation: A failed multi-agent execution is represented as a directed acyclic graph whose nodes are observable messages or actions and whose edges encode execution dependencies.
- A. Problem Formulation: Each event has a responsible agent, the observed failure is represented by a sink, and C is the declared set of intervenable events.
- A. Problem Formulation: For an intervention set S, replay replaces selected events with paired clean messages or removes their corruptions, then reruns the downstream workflow.
- A. Problem Formulation: Replay outcomes Y_j(S) are binary, with 1 denoting task success; common replay seeds are used across interventions.
- A. Problem Formulation: The unmodified execution is assumed to remain a failure under the replay protocol.
- A. Problem Formulation: Given a maximum repair size q, the target is the family of successful interventions whose strict subsets fail.
- A. Problem Formulation: Minimality is defined by set inclusion: {u,v} is jointly necessary, whereas {u} and {v} are alternative repairs.
B. Graph-Constrained Joint Replay
GCJR recovers minimal repair candidates by slicing failure-relevant events, imposing graph-based constraints on singleton and pair interventions, and verifying candidates through replay. The graph narrows the candidate domain but does not itself certify repair success.
- Method: GCJR studies singleton and pair repairs by recovering minimal successful interventions within a bounded candidate domain.The method sets q ≤2 and proceeds through failure slicing, graph-constrained construction, and replay verification.
- Failure slicing: Failure slicing removes events that cannot structurally affect the observed failure and restricts candidates to the backward slice of the failure output.This screening is sound when the dependency graph contains every influence path relevant to the replay outcome.
- Candidate construction: GCJR admits a pair only when events come from different agents, are causally incomparable, and meet at a downstream join.All singletons in the sliced candidate set are included before these structural pair constraints are applied.
- Replay verification: The graph proposes a bounded candidate domain but does not certify that any candidate repairs the task.Repair status is established by subsequent replay verification.
- Replay verification: GCJR evaluates candidates in increasing cardinality, retaining successful singletons and then testing remaining admissible pairs for inclusion-minimal success.Pairs containing a successful singleton are skipped because they cannot be inclusion-minimal; replay requests are memoized and use shared seeds.
C. Domain Exactness and Replay Cost
For fixed replay outcomes, GCJR exactly recovers inclusion-minimal successful sets in its admissible graph domain while reducing replay work through slicing, pair screening, and minimality pruning.
- Domain exactness: For fixed replay outcomes, GCJR returns exactly the inclusion-minimal successful sets in its declared graph domain.Every singleton is tested, and an admissible pair is skipped only after a successful singleton certifies non-minimality.
- Domain exactness: If F2,θ ⊆DG, GCJR recovers the complete bounded repair family F2,θ.The guarantee is stated for the graph-constrained candidate domain and fixed replay outcomes.
- Replay cost: Replay cost is parameterized by n = |C|, m = |Co|, p remaining admissible pairs, and r repeats per intervention.The method evaluates the empty intervention, sliced singletons, and only the remaining admissible pairs after successful-singleton pruning.
- Replay cost: The replay reduction comes from failure slicing, structural pair screening, and minimality pruning.These mechanisms reduce the number of interventions requiring replay without changing the returned family within the declared domain.
III. EXPERIMENTAL EVALUATION
The evaluation tests whether GCJR recovers complete minimal repair families and reduces replay cost without changing those families, using a symbolic benchmark and a real-agent pilot.
- Evaluation goals: GCJR is evaluated on family recovery and replay-cost reduction in both a symbolic benchmark and a real-agent pilot.The experiments assess whether graph constraints reduce replay cost without changing the recovered family.
A. Benchmarks and Protocol
The evaluation combines controlled four-agent DAG workloads with a 24-case real-agent pilot, while methods observe graph and replay information rather than fault labels or clean values.
- Controlled-DAG: The Controlled-DAG suite contains 90 in-scope DAGs across Single, Joint-AND, and Alternative-OR types, plus Sequential-Joint as an out-of-scope control.Each DAG contains 6–14 candidates, including irrelevant distractors, and uses three valid topological schedules.
- DualSolve-MAS: DualSolve-MAS is a 24-case pilot with eight program-generated arithmetic cases per in-scope type using four instantiated agents.An exact arithmetic executor supplies correct tool results, isolating communication localization from arithmetic ability.
- Protocol: The pilot corrupts numeric messages from B and/or C, and interventions restore paired clean messages before rerunning the aggregator.An irrelevant audit event serves as the third candidate.
- Protocol: Methods observe the graph, candidate set, agent identities, and replay outcomes, but not fault labels or clean values.This defines the information available to the diagnostic procedures.
- Protocol: Controlled-DAG uses deterministic replay with seed 20260826, while DualSolve-MAS uses temperature 0, at most 80 new tokens, r = 3, and θ = 2/3.Confidence intervals for Controlled-DAG use 2,000 DAG-level bootstrap samples after schedule aggregation.
B. Baselines and Metrics
The evaluation compares family recovery and replay cost against exhaustive, first-order, window-based, ranking, and log-only baselines using metrics that assess exactness, overlap, success, minimality, and schedule consistency.
- Baselines: All replay methods share candidates and an intervention backend, while baselines differ in graph constraints, intervention cardinality, log proximity, ranking, or log-only prediction.The comparisons include graph-blind exhaustive search, single-event and execution-window replay, fixed-cardinality rankings, and a one-call LLM judge.
- Metrics: Family Exact Match equals one only when the predicted antichain exactly matches the exhaustive minimal-repair family.AJ measures overlap, RS@1 tests the first returned set, MV detects non-minimal outputs, and SC measures agreement across symbolic linearizations.
- Metrics: The reported cost is replay executions for Controlled-DAG and LLM calls for DualSolve-MAS.
C. Main Results
GCJR recovers the complete minimal repair family in both the symbolic benchmark and real-agent pilot while substantially reducing replay or model-call cost relative to exhaustive search.
- Controlled-DAG results: 1.000 macro FEM: GCJR recovers all 90 in-scope symbolic families with AJ, RS@1, and SC of 1.000 and MV=0.
- Controlled-DAG results: 55.1% fewer replay calls: GCJR averages 25.3 calls versus 56.3 for exhaustive search on the controlled benchmark.The 95% confidence intervals are 23.1–27.5 for GCJR and 51.0–61.9 for exhaustive search.
- Real-agent pilot: 1.000 family match across 24 pilot cases: GCJR matches the exhaustive family with RS@1=1.000 and MV=0.
- Real-agent pilot: 52.4% fewer LLM calls: GCJR reduces mean pilot calls from 21.0 to 10.0.Single-event, execution-window, and log-only methods obtain Joint-AND FEM=0 in the pilot.
D. Ablations and Boundary Tests
Ablations show that joint interventions and minimality filtering are necessary for complete family recovery, while boundary tests expose sensitivity to graph omissions and confirm schedule invariance.
- Ablations: 1.000 to 0.000 Joint-AND FEM: singleton-only replay cannot recover jointly necessary repairs.
- Ablations: 1.000 to 0.000 Alternative-OR FEM: removing minimality filtering yields non-minimal outputs, with MV increasing from 0 to 0.783.Successful replay alone therefore does not recover the complete minimal repair family.
- Boundary tests: SC=1.000 across three topological linearizations: GCJR returns identical repair families for causally independent event orderings in the deterministic setting.
- Boundary tests: GCJR abstains on all 30 out-of-scope Sequential-Joint controls because its declared domain is restricted to causally incomparable pairs.
- Boundary tests: 10% hidden edges reduce in-scope macro FEM from 1.000 to 0.552, because missing causal links can exclude valid candidates during slicing or structural screening.At least one ground-truth minimal repair set remains fully visible in 73.3% of cases, but complete family recovery can still fail.
IV. RELATED WORK
Related work provides failure taxonomies, attribution signals, graph-guided diagnosis, replay interventions, and minimal-diagnosis foundations, whereas GCJR targets complete bounded minimal repair families.
- Failure analysis in multi-agent systems: Existing multi-agent diagnosis methods identify recurrent failure modes or responsible agents, steps, and components from execution traces.
- Graph-guided attribution and replay: GraphTracer, CHIEF, and HPFA use structural or causal graphs, while AgenTracer, DoVer, CausalFlow, and Causal Agent Replay use replay or counterfactual interventions.These systems primarily return a failure location, intervention effect, or selected repair.
- Graph-guided attribution and replay: GCJR enumerates the complete bounded minimal repair family within a declared graph domain instead of returning one location, effect, or selected repair.
- Graph-guided attribution and replay: The set-valued output distinguishes jointly necessary events from alternative singleton repairs, which a single attribution ranking cannot represent.
- Minimal diagnosis and fault localization: The contribution is a bounded multi-agent event-graph instantiation combining replay-validated repair families, an explicit antichain target, and graph-based pruning with domain-limited exactness.The paper does not claim that minimal sets or counterfactual testing are new in the abstract.