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

Encheng Su; Pengze Li; Ziheng Hua; Qiucheng Yu; Jianyu Wu; Chen Tang; Yizhou Wang; Lintao Wang

cs.CLOct 13, 2026

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

Authors: Encheng Su, Pengze Li, Ziheng Hua, Qiucheng Yu, Jianyu Wu, Chen Tang, Yizhou Wang, Lintao Wang,

Organizations: University of Science and Technology of China · Shanghai Artificial Intelligence Laboratory · Fudan University · City University of Hong Kong ·

Abstract

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 \method, a verifiable runtime control framework that treats handoff repair as selective intervention over explicit dependency graphs. Central to \method is an integrated fault-attribution and calibration pipeline, \dataset, which decouples execution dependencies and injects counterfactual handoff perturbations to provide empirical supervision for runtime intervention. Leveraging this diagnostic foundation, \method 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 \method boosts task success by up to 12.3 absolute percentage points on SILO-BENCH and 11.1 on TeamBench. Across both backbones, \method maintains strict cost-effectiveness, adding as little as 2.0% marginal token overhead. Furthermore, on 562 handoff-relevant traces from the MAST benchmark, \method achieves 69.8% F1 in a single pass, establishing a reliable operational boundary for verifiable coordination repair.

Figures & tables

Figure 1: Overview of HandoffProbe calibration and BRIDGE runtime control. HandoffProbe injects handoff faults into offline trajectories and branches a shared faulted prefix into native and repaired continuations. An external verifier evaluates final task success for each continuation, and the paired outcomes are aggregated into frozen calibration priors. At runtime, BRIDGE constructs a provenance graph, identifies unresolved frontiers, and uses the frozen priors to gate candidate repairs.

Figure 2: Illustration of a missing-evidence repair. Agent A omits Records from its handoff to Agent B; BRIDGE retrieves the missing item via ASK and releases the revised handoff only after verifying its delivery in the provenance graph.

Action Primitive	Prerequisite Condition	Intended State Change
ASK	Identified owner and valid query	Target evidence acquired from sender
INTEGRATE	Available evidence in recipient scope	Target evidence woven into outgoing message
VERIFY	Declared contract constraint	Verification certificate recorded in graph
DECOMPOSE	Complex unmet obligation	Message rewritten using visible local sources
RETRIEVE	Accessible local or public state	Missing context fetched into recipient scope

Table 1: Domain-agnostic repair actions, prerequisites, and expected state changes.

	TeamBench		SILO-BENCH
Method	Full Pass (%) $\uparrow$	Partial (%) $\uparrow$	Full Success (%) $\uparrow$	Partial (%) $\uparrow$
DeepSeek-V4.1-flash
Native	48.9	81.3	$63.3\pm 3.3$	65.8
AgentAsk	53.3	84.3	$61.1\pm 3.3$	78.9
Self-Refine	51.1	83.7	$63.3\pm 1.9$	78.9
MOC	54.4	84.4	$\underline{65.6}\pm 1.9$	82.2

Table 2: End-to-end collaborative performance on TeamBench and SILO-BENCH (%). Success denotes full task acceptance; Partial denotes benchmark progress score. Best results are in bold ; second-best results are underlined .

	DeepSeek-V4.1-flash		GPT-5.6-Terra
Method	F1 (%) $\uparrow$	Tokens/trace $\downarrow$	F1 (%) $\uparrow$	Tokens/trace $\downarrow$
Direct Prompting	62.5	6,686	67.5	6,488
AgentAsk	68.4	14,268	68.4	13,982
Self-Refine	67.4	13,262	67.9	12,359
MOC	68.7	13,738	68.6	13,507
VeriMAP	64.2	13,478	69.4	14,917

Table 3: Diagnostic performance on 562 handoff-relevant MAST execution traces (%). All reference baselines require two-stage prompt chains; BRIDGE operates strictly via a single diagnostic pass. Best results are in bold ; second-best results are underlined .

Configuration	Success Rate (%) $\uparrow$	Net $\Delta$ vs. Native
Native (Unassisted Host)	63.3	—
BRIDGE (Full System)	75.6	+12.3
w/ Flat Checklist ( No Graph Provenance )	68.9	+5.6
w/ LLM Self-Gate	70.0	+6.7
w/ Aggregate Utility Gate	73.3	+10.0
w/o Historical Experience Adjustment	70.0	+6.7

Table 4: Component ablations on SILO-BENCH (DeepSeek-V4.1-flash). Net

\Delta

indicates margin over unassisted Native execution.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Execution Event	Graph Representation
Declared requirement	Obligation and fact identifier, with owner/recipient metadata
Message	Message/fact node with sender and recipient edges
Tool invocation	Action node linked to calling agent and tool schema
Tool execution output	Evidence node linked to producing action
Evidence consumption	Directed edge between fact node and consuming operation
Public verifier outcome	Verification relation within verifier’s declared scope

Appendix

Table 5: Execution events and their graph representations.

Parameter	Value	Description
$w_{h}$	1.0	Weight on verifier-helped outcomes ( $V(x^{\mathrm{rep}})=1\wedge V(x^{\mathrm{nat}})=0$ )
$w_{n}$	0.25	Penalty on neutral/unchanged executions (latency and state perturbation)
$w_{x}$	2.0	Penalty on verifier-harmed executions ( $V(x^{\mathrm{rep}})=0\wedge V(x^{\mathrm{nat}})=1$ )
$w_{c}$	0.25	Weight on normalized resource cost
$\epsilon$	0.05	Empirical harm-rate tolerance threshold ( $r_{\mathrm{harm}}\leq 0.05$ )
$m_{\min}$	5	Minimum required sample support per action–frontier segment

Appendix

Table 6: Base utility parameters and calibration settings.

Backbone	Route / Segment	Episodes	Helped	Harmed	Utility	Admitted
DeepSeek-V4.1-flash	ASK	52	8 (15.4%)	0	$-0.31$	No
DeepSeek-V4.1-flash	INTEGRATE	25	12 (48.0%)	0	$+0.10$	Yes
GPT-5.6-Terra	ASK	40	10 (25.0%)	0	$-0.19$	No
GPT-5.6-Terra	INTEGRATE (aggregate)	12	4 (33.3%)	0	$-0.08$	No
GPT-5.6-Terra	INTEGRATE $\times\mathcal{F}_{\mathrm{use}}$	6	4 (66.7%)	0	$+0.33$	Yes

Appendix

Table 7: Empirical calibration statistics across candidate routes. Utility is computed under base parameters; admission requires positive utility, empirical harm rate

\leq\epsilon

, and sample support

\geq m_{\min}

Multi-Agent Framework	Positive Traces	Stratified Controls	Total Traces
MetaGPT	182	182	364
AG2	46	46	92
Magentic	43	43	86
HyperAgent	7	7	14
OpenManus	2	2	4
AppWorld	1	1	2

Appendix

Table 8: Distribution of the 562 curated MAST evaluation traces across agent architectures.

	DeepSeek-V4.1-flash		GPT-5.6-Terra
Method	F1 (%) $\uparrow$	Tokens/trace $\downarrow$	F1 (%) $\uparrow$	Tokens/trace $\downarrow$
Direct Prompting	62.5	6,686	67.5	6,488
AgentAsk (adapted)	68.4	14,268	68.4	13,982
Self-Refine (adapted)	67.4	13,262	67.9	12,359
MOC (adapted)	68.7	13,738	68.6	13,507
VeriMAP (adapted)	64.2	13,478	69.4	14,917

Appendix

Table 9: Diagnostic metrics on 562 MAST traces. BRIDGE operates strictly via a single inference pass, while adapted baselines require two-stage prompt chains.

	SILO-BENCH		TeamBench
Specification	DeepSeek	GPT	DeepSeek	GPT
Evaluation rollouts per task	1	3	1	1
Instances / $n$	90 / 90	90 / 270	90 / 90	90 / 90
Policy configuration	Corpus-calibrated	Corpus-calibrated	Zero-shot transfer	Zero-shot transfer
Max actions per boundary	1	1	1	1

Appendix

Table 10: Evaluation settings across benchmark suites.

	DeepSeek-V4.1-flash		GPT-5.6-Terra
Method	Pass (%)	Partial (%)	Pass (%)	Partial (%)
Native	48.9	81.3	46.7	79.6
AgentAsk	53.3	84.3	48.9	80.9
Self-Refine	51.1	83.7	47.8	79.6
MOC	54.4	84.4	48.9	81.3
VeriMAP	51.1	83.6	47.8	79.7

Appendix

Table 11: TeamBench reference baseline evaluations. Pass denotes benchmark pass rate (%); Partial denotes mean partial progress score (%).

Benchmark	Evaluated Model	Discordant ( $W/L$ )	Significance Test
SILO-BENCH	DeepSeek-V4.1-flash	16 / 5	$p=0.027$
SILO-BENCH	GPT-5.6-Terra (pooled)	36 / 12	$p<0.001$
TeamBench	DeepSeek-V4.1-flash	12 / 3	$p=0.035$

Appendix

Table 12: Paired discordant outcomes between BRIDGE and unassisted Native execution.

Task Identifier	Gate Decision	Candidate Action	Local Verification	Final Verdict
CR1_review_respond	Admitted ( $u>0$ )	RETRIEVE	Verified	Pass
CR6_review_checklist	Admitted ( $u>0$ )	RETRIEVE	Verified	Fail

Appendix

Table 13: Representative runtime interventions on TeamBench. Local verification requires formal satisfaction of postconditions; final verdict denotes task-level evaluation.

	GPT-5.6-Terra		DeepSeek-V4.1-flash
Component / Stage	Tokens/task	% of Native	Tokens/task	% of Native
Native Baseline Execution	25,198	100.0%	22,460	100.0%
Standard Agent Operations
Prompt context variation	+523	+2.1%	+818	+3.6%
Output response variation	+65	+0.3%	+598	+2.7%
Subtotal: Agent Communication Channel	25,786	+2.3%	23,876	+6.3%

Appendix

Table 14: End-to-end token accounting per task rollout on SILO-BENCH. Controller operations are decoupled into deterministic graph tracing, boundary diagnostic evaluations, and active repair executions.

Multi-Agent Coordination

Multi-agent coordination studies how autonomous agents align actions, share information, and divide work to achieve individual or collective goals.

See all 520 papers

Meta-Agent: From Task Descriptions to Verified Multi-Agent Systems
May 24, 2026Andy Xu, Yu-Wing TaiMulti-Agent Orchestration Multi-Agent Systems
Dartmouth College
ARIA: Runtime Inspection and Amendment for Multi-Agent Systems
Oct 14, 2026Bolin Shen, Yushun DongMulti-Agent LLM Systems Multi-Agent Systems
Florida State University
COOP $^2$ : Defining, Observing, and Repairing Cooperation in LLM Multi-Agent Systems
Feb 27, 2026Hanqing Yang, Narjes Nourzad, Shiyu Chen +3Multi-Agent Collaboration Multi-Agent Coordination
CMU · USC · SUTD +1

May 24, 2026J/K move · Enter open · S save

Meta-Agent: From Task Descriptions to Verified Multi-Agent Systems

Andy Xu, Yu-Wing Tai

Dartmouth College

Multi-Agent Orchestration Multi-Agent Systems Multi-Agent Planning LLM Agent Reliability

Open paper AskPDF arXiv

AI agents are increasingly used to solve complex, multi-step tasks, but existing multi-agent frameworks remain brittle as workflows grow in scale and depth. Small errors at intermediate stages can propagate through agent interactions, while insufficient grounding and weak verification mechanisms further limit reliability. We present Meta-Agent, a two-phase framework that automatically constructs and executes specialized multi-agent systems from natural-language task descriptions. In the construction phase, a task planner decomposes a problem into a directed acyclic graph of agent specifications with explicit input/output contracts and verification criteria. A web search module grounds each specification with external evidence, and a code generation module produces system prompts and tool configurations. A construction-time verification stage then validates generated artifacts and triggers targeted regeneration when failures are detected. In the execution phase, a coordinator dispatches subtasks across the agent graph while execution-time verification gates intermediate outputs. We further introduce a three-level error attribution mechanism that distinguishes local, upstream, and structural failures, enabling targeted recovery strategies ranging from localized retries to partial re-execution and re-decomposition. We evaluate Meta-Agent across coding, contextual learning, and open-ended reasoning tasks. Experiments against strong multi-agent baselines and ablation studies demonstrate consistent improvements in task success rate, error recovery, and workflow stability. The results highlight the importance of tightly integrating planning, grounding, and verification for building reliable multi-agent systems.

Abstract

Multi-Agent Coordination

Explore similar work

Meta-Agent: From Task Descriptions to Verified Multi-Agent Systems

ARIA: Runtime Inspection and Amendment for Multi-Agent Systems

COOP2^22: Defining, Observing, and Repairing Cooperation in LLM Multi-Agent Systems

COOP $^2$ : Defining, Observing, and Repairing Cooperation in LLM Multi-Agent Systems