BRIDGE: Selective Boundary Repair with Dependency Graph Evidence in Multi-Agent Systems

Multi-agent collaboration has emerged as a critical paradigm for tackling complex, long-horizon tasks; however, while coordination protocols continue to advance, systemic failures at the inter-agent collaboration interface remain a pervasive bottleneck. In collaborative workflows, systems frequently suffer from broken handoffs—where critical task context is omitted, misrouted, or ignored despite each agent emitting locally plausible responses. To address this challenge, we present BRIDGE, a verifiable runtime control framework that treats handoff repair as selective intervention over explicit dependency graphs. Central to BRIDGE is an integrated fault-attribution and calibration pipeline, HandoffProbe, which decouples execution dependencies and injects counterfactual handoff perturbations to provide empirical supervision for runtime intervention. Leveraging this diagnostic foundation, BRIDGE dynamically compiles observable interaction traces into a provenance graph to pinpoint unresolved dependencies, without accessing private agent states. It then evaluates candidate repairs through an empirical gate that weighs expected gains against disruption risks, and executes repairs only when formal local postconditions hold. Extensive evaluations across demanding benchmarks demonstrate that BRIDGE boosts task success by up to 12.3 absolute percentage points on SILO-BENCH and 11.1 on TeamBench. Across both backbones, BRIDGE maintains strict cost-effectiveness, adding as little as 2.0% marginal token overhead. Furthermore, on 562 handoff-relevant traces from the MAST benchmark, BRIDGE achieves 69.8% F1 in a single pass, establishing a reliable operational boundary for verifiable coordination repair.