MeshHeal: Two-Timescale Self-Healing for Gray Failures in Decentralized LLM Agent Networks

Keru Chen; Sen Lin; Yingbin Liang; Nathaniel D. Bastian; Shaofeng Zou

cs.AISep 24, 2026

MeshHeal: Two-Timescale Self-Healing for Gray Failures in Decentralized LLM Agent Networks

Authors: Keru Chen, Sen Lin, Yingbin Liang, Nathaniel D. Bastian, Shaofeng Zou

Organizations: School of ECEE Arizona State University · Computer Science Department University of Houston · Department of ECE The Ohio State University · Whiting School of Engineering Johns Hopkins University

Abstract

Decentralized LLM-based multi-agent systems coordinate through local interactions, but an agent can remain responsive while its task-solving quality persistently degrades. Such gray failures require protecting current tasks before sufficient evidence exists to alter future routing, while still allowing recovered agents to rejoin. We introduce MeshHeal, a fully decentralized self-healing framework that couples ability-matched peer review across two timescales. At the fast timescale, an adaptive hierarchy escalates uncertain or low-scoring outputs from repeated single-reviewer evaluation to committee deliberation and, when needed, correction before use. At the slow timescale, a task- and ability-conditioned peer-relative detector aggregates scores to distinguish persistent degradation from ordinary output variation, trigger mandatory committee review, and eventually exclude degraded agents from ordinary routing; recovery probes provide fresh evidence for reintegration. To faithfully evaluate routing, we introduce Model-Backed MAS Evaluation, which ties ability assignments to execution models, since prompt-based ability assignments alone can leave routing errors hidden. Across BBH, MATH, and MMLU-Pro, MeshHeal achieves 0.839 degraded-phase accuracy using 51k total model tokens per task, versus the strongest baseline Symphony's 0.807 accuracy using 115k per task. Under staggered degradation and recovery, MeshHeal isolates degraded agents, keeps them excluded from ordinary task execution until recovery, and returns them to normal routing.

Figures & tables

Figure 1: Overview of MeshHeal . (a) Agents route and complete complementary work. (b) Review by agents with the relevant ability either keeps or replaces the current output, while scores accumulated across tasks update routing eligibility and probes allow recovered agents to return. (c) Model-Backed MAS Evaluation ties execution models to declared abilities and the agent’s healthy or degraded condition, making routing errors affect accuracy.

Model	Unassigned ability acc.	Assigned ability acc.	$\Delta_{\mathrm{gap}}$
DeepSeek-Chat	$.812\!\rightarrow\!.775$	$.800\!\rightarrow\!.792$	.029
Llama-3.1-70B	$.781\!\rightarrow\!.750$	$.783\!\rightarrow\!.767$	.015
GPT-4o-mini	$.744\!\rightarrow\!.675$	$.708\!\rightarrow\!.667$	.027
GPT-OSS-120B	$.869\!\rightarrow\!.831$	$.825\!\rightarrow\!.833$	.046
Qwen-2.5-7B	$.494\!\rightarrow\!.219$	$.558\!\rightarrow\!.342$	.058

Table 1: BBH ability-assignment test. Arrows show no competence statement

\rightarrow

unassigned abilities declared unreliable;

\Delta_{\mathrm{gap}}

is the resulting increase in the accuracy gap between assigned and unassigned abilities.

Method	H acc.	D acc.	Tokens
MeshHeal	$\mathbf{.831\!\pm\!.013}$	$\mathbf{.839\!\pm\!.012}$	$51\!\pm\!5$
Symphony	$.827\!\pm\!.013$	$.807\!\pm\!.014$	$115\!\pm\!9$
SAC	$.822\!\pm\!.014$	$.746\!\pm\!.021$	$178\!\pm\!13$
RAPS	$.800\!\pm\!.019$	$.653\!\pm\!.041$	$48\!\pm\!3$
AgentNet	$.729\!\pm\!.023$	$.557\!\pm\!.039$	$43\!\pm\!2$
AutoGen	$.787\!\pm\!.014$	$.424\!\pm\!.023$	$15\!\pm\!0$

Table 2: (a) Accuracy and total model-token cost under persistent degradation (mean

\pm

std. over three datasets, each with five seeds). H/D denote healthy/degraded phases; tokens are thousands per degraded-phase task. (b) Scaling in complete and sparse networks over five seeds.

I/D

denotes isolated/degraded agents; edge fraction is relative to the complete graph.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Model	Condition	Unassigned ability acc.	Assigned ability acc.	Accuracy gap	Additional gap
DeepSeek-Chat	No statement	0.812	0.800	$-0.012$	–
	Told unreliable	0.775	0.792	0.017	0.029
Llama-3.1-70B	No statement	0.781	0.783	0.002	–
	Told unreliable	0.750	0.767	0.017	0.015
GPT-4o-mini	No statement	0.744	0.708	$-0.035$	–
	Told unreliable	0.675	0.667	$-0.008$	0.027

Appendix

Table A1: Results of ability assignment by system prompt on BBH.

Agent	Declared abilities
A1	reasoning, mathematical, knowledge
A2	reasoning, mathematical, knowledge
A3 (degraded)	mathematical, knowledge, sequence, inference
A4	language, sequence, spatial, inference
A5 (degraded)	reasoning, language, spatial
A6	language, sequence, spatial, inference

Appendix

Table B1: BBH ability assignment in the six-agent setting.

Task type	Required abilities
causal_judgement	reasoning + inference
formal_fallacies	reasoning + inference
tracking_shuffled_objects_five_objects	reasoning + sequence
geometric_shapes	mathematical + spatial
object_counting	mathematical + spatial
date_understanding	mathematical + language

Appendix

Table B2: BBH task types and required abilities.

Agent	Declared abilities
A1	symbolic_manipulation , numeric_computation , theorem_knowledge
A2	symbolic_manipulation , numeric_computation , theorem_knowledge
A3 (degraded)	numeric_computation , theorem_knowledge , enumeration , multi_step_deduction
A4	enumeration , multi_step_deduction , problem_translation , figure_reasoning
A5 (degraded)	symbolic_manipulation , problem_translation , figure_reasoning
A6	enumeration , multi_step_deduction , problem_translation , figure_reasoning

Appendix

Table B3: MATH ability assignment.

Subject	Required abilities	Rationale
prealgebra	numeric_computation $+$ problem_translation	word-problem modeling + arithmetic
algebra	symbolic_manipulation $+$ multi_step_deduction	expression transformation + multi-step solving
geometry	numeric_computation $+$ figure_reasoning	geometric relations + numerical calculation
number_theory	symbolic_manipulation $+$ enumeration	algebraic constraints + systematic cases
counting_and_probability	symbolic_manipulation $+$ enumeration	counting expressions + complete case coverage
intermediate_algebra	symbolic_manipulation $+$ multi_step_deduction	deeper transformations + longer deduction

Appendix

Table B4: MATH subjects, required abilities, and assignment rationale.

Agent	Declared abilities
A1	humanities_knowledge , science_knowledge , quantitative_methods
A2	humanities_knowledge , science_knowledge , quantitative_methods
A3 (degraded)	science_knowledge , quantitative_methods , scenario_inference , stepwise_analysis
A4	scenario_inference , stepwise_analysis , text_comprehension , structural_reasoning
A5 (degraded)	humanities_knowledge , text_comprehension , structural_reasoning
A6	scenario_inference , stepwise_analysis , text_comprehension , structural_reasoning

Appendix

Table B5: MMLU-Pro ability assignment.

Domain	Required abilities	Rationale
health	science_knowledge $+$ text_comprehension	medical knowledge + comprehension of long questions
history	humanities_knowledge $+$ scenario_inference	historical facts + contextual inference
biology	science_knowledge $+$ structural_reasoning	biology knowledge + structural/process reasoning
psychology	humanities_knowledge $+$ scenario_inference	theory + scenario judgment
philosophy	humanities_knowledge $+$ scenario_inference	doctrine + argumentative stance
economics	quantitative_methods $+$ text_comprehension	interpretation + model/calculation

Appendix

Table B6: MMLU-Pro domains, required abilities, and assignment rationale.

Dataset	BBH	MATH	MMLU-Pro	Overall
Exact pair match	100%	100%	100%	100%

Appendix

Table B7: Exact match between inferred ability pairs and the documented task-type mappings.

Execution condition	Model
Declared ability, healthy agent	openai/gpt-oss-120b
Missing ability or degraded agent	meta-llama/llama-3.2-1b-instruct

Appendix

Table B8: Models used for task execution and induced degradation.

Dataset	Scoring rule
BIG-Bench Hard	Exact answer extraction and matching
MATH	Mathematical equivalence with math_equal
MMLU-Pro	Extracted option letter

Appendix

Table B9: Datasets and scoring rules.

Label	Source	Implementation used in our framework
AgentNet	Yang et al. (2025b)	Native decentralized routing with adaptive edge weights and pruning.
RAPS	Li et al. (2026)	Peer reputation updates local links and routing avoids low-reputation peers.
AutoGen	Wu et al. (2023)	A mandatory GroupChatManager-style hub delegates work, receives worker outputs, and produces the final answer.
SAC	Lee et al. (2026)	Three teams produce answers, run two filtering and refinement rounds, and aggregate by majority.
Symphony	Guan et al. (2026)	GlobalLinUCB selects agents with the required abilities; three plans run in parallel; the final result is selected by voting and used to update routing statistics.

Appendix

Table B10: Baseline implementations.

Parameter	Value
Committee reviewer slots	2
Committee deliberation rounds	2
Takeover correction candidates	2
Routing hop limit	4 hops
Maximum agents per task	6
Maximum reviewed outputs per task	3

Appendix

Table B11: Main MeshHeal parameters.

Agents	Sparse edges	Fraction of complete graph	Maximum ability distance
96	228	5.00%	3
288	705	1.71%	3
576	1454	0.88%	3

Appendix

Table B12: Sparse graph size. Edge counts treat each bidirectional connection as one undirected link.

Method	BBH	MATH	MMLU-Pro	Mean	Change
MeshHeal	$.899\pm.027$ $\mathbf{.900\pm.014}$	$.821\pm.019$ $\mathbf{.802\pm.021}$	$.774\pm.016$ $\mathbf{.814\pm.018}$	$\mathbf{.831\pm.013}$ $\mathbf{.839\pm.012}$	$\mathbf{+.007\pm.012}$
Symphony	$.896\pm.022$ $.889\pm.007$	$.818\pm.020$ $.790\pm.022$	$.766\pm.018$ $.742\pm.026$	$.827\pm.013$ $.807\pm.014$	$-.020\pm.018$
SAC	$.896\pm.016$ $.894\pm.007$	$.794\pm.026$ $.639\pm.045$	$.778\pm.020$ $.706\pm.034$	$.822\pm.014$ $.746\pm.021$	$-.076\pm.026$
RAPS	$.884\pm.029$ $.740\pm.070$	$.726\pm.034$ $.627\pm.061$	$.790\pm.024$ $.591\pm.067$	$.800\pm.019$ $.653\pm.041$	$-.147\pm.045$
AgentNet	$.862\pm.035$ $.668\pm.066$	$.631\pm.041$ $.476\pm.056$	$.694\pm.034$ $.528\pm.061$	$.729\pm.023$ $.557\pm.039$	$-.172\pm.047$
AutoGen	$.898\pm.013$ $.525\pm.034$	$.665\pm.030$ $.214\pm.029$	$.796\pm.019$ $.532\pm.043$	$.787\pm.014$ $.424\pm.023$	$-.363\pm.028$

Appendix

Table C1: Full persistent-degradation results, reported as mean

\pm

standard deviation over five seeded task streams per dataset. Each stacked entry gives H above D for the healthy and degraded phases. The Mean column averages the three datasets within each seed, and Change is computed within seed before aggregation. Bold marks the best mean.

Method	H calls	D calls	H tokens (k)	D tokens (k)
MeshHeal	$12.4\pm 0.2$	$13.6\pm 0.3$	$51\pm 3$	$51\pm 5$
Symphony	$18.1\pm 0.1$	$23.4\pm 0.1$	$86\pm 5$	$115\pm 9$
SAC	$30.3\pm 0.1$	$39.9\pm 0.6$	$116\pm 4$	$178\pm 13$
RAPS	$8.2\pm 0.5$	$10.9\pm 0.3$	$39\pm 5$	$48\pm 3$
AgentNet	$7.8\pm 0.7$	$10.3\pm 0.2$	$34\pm 4$	$43\pm 2$
AutoGen	$6.1\pm 0.0$	$6.0\pm 0.0$	$15\pm 0$	$15\pm 0$

Appendix

Table C2: Healthy- and degraded-phase cost per task, reported as mean

\pm

standard deviation over five seeds after averaging datasets within seed. Tokens include both input and output tokens; their means and standard deviations are rounded to the nearest thousand.

Method	Healthy acc.	Degraded acc.	Change	Tokens/task
MeshHeal	$\mathbf{0.929\pm 0.018}$	$\mathbf{0.905\pm 0.016}$	$\mathbf{-0.024\pm 0.014}$	$56{,}687\pm 2{,}431$
Symphony	$0.917\pm 0.020$	$0.865\pm 0.021$	$-0.052\pm 0.017$	$100{,}685\pm 4{,}782$
SAC	$0.917\pm 0.019$	$0.829\pm 0.030$	$-0.088\pm 0.026$	$130{,}938\pm 6{,}214$
RAPS	$0.877\pm 0.031$	$0.623\pm 0.064$	$-0.254\pm 0.055$	$35{,}746\pm 2{,}963$
AgentNet	$0.857\pm 0.037$	$0.694\pm 0.056$	$-0.163\pm 0.048$	$36{,}978\pm 3{,}284$
AutoGen	$0.905\pm 0.016$	$0.734\pm 0.041$	$-0.171\pm 0.038$	$15{,}377\pm 1{,}126$

Appendix

Table C3: Model pair A: GPT-OSS-120B is the strong model and Gemma-3-4B is the weak model. Results are mean

\pm

standard deviation over five seeded task streams; Change is paired within seed and tokens include both input and output tokens.

Method	Healthy acc.	Degraded acc.	Change	Tokens/task
MeshHeal	$0.790\pm 0.025$	$0.782\pm 0.023$	$\mathbf{-0.008\pm 0.015}$	$50{,}802\pm 2{,}317$
Symphony	$\mathbf{0.806\pm 0.023}$	$\mathbf{0.786\pm 0.021}$	$-0.020\pm 0.017$	$96{,}982\pm 4{,}563$
SAC	$\mathbf{0.806\pm 0.022}$	$0.754\pm 0.032$	$-0.052\pm 0.027$	$122{,}234\pm 5{,}908$
RAPS	$0.790\pm 0.030$	$0.571\pm 0.061$	$-0.219\pm 0.053$	$30{,}761\pm 2{,}684$
AgentNet	$0.774\pm 0.038$	$0.476\pm 0.065$	$-0.298\pm 0.056$	$29{,}487\pm 2{,}792$
AutoGen	$0.754\pm 0.028$	$0.349\pm 0.042$	$-0.405\pm 0.038$	$12{,}986\pm 956$

Appendix

Table C4: Model pair B: Llama-3.3-70B is the strong model and Llama-3.2-1B is the weak model. Results are mean

\pm

standard deviation over five seeded task streams; Change is paired within seed and tokens include both input and output tokens.

Agent	True degraded interval	State sequence
A5	127–378	first evidence at task 3; normal during warm-up $\rightarrow$ 129 watched $\rightarrow$ 132 isolated $\rightarrow$ 422 watched $\rightarrow$ 430 normal
A3	253–504	first evidence at task 4; normal during warm-up $\rightarrow$ 267 watched $\rightarrow$ 268 isolated $\rightarrow$ 548 watched $\rightarrow$ 550 normal

Appendix

Table C5: Inferred routing-state changes in a representative run with degradation and recovery at different times.

Metric	Full method	Single reviewer	No Takeover
Healthy accuracy	$0.899\pm 0.027$	$0.909\pm 0.022$	$0.879\pm 0.021$
Degraded-phase accuracy	$\mathbf{0.900\pm 0.014}$	$0.865\pm 0.029$	$0.844\pm 0.036$
Paired phase change	$\mathbf{+0.001\pm 0.016}$	$-0.044\pm 0.024$	$-0.035\pm 0.030$

Appendix

Table C6: Component study, reported as mean

\pm

standard deviation over five seeded task streams. Phase change is paired within seed.

		Pair A		Pair B
Rule	Evidence	Missed	False	Missed	False
Absolute threshold	Own scores	0/2	4/4	0/2	0/4
CUSUM	Own scores	0/2	2/4	1/2	0/4
Relative peer comparison	Scores relative to peers	0/2	0/4	0/2	0/4

Appendix

Table C7: Detector performance across two BBH model pairs. Missed counts are out of two degraded agents and false-isolation counts are out of four healthy agents; each setting uses the full 504-task stream.

(a) Initial review
Metric	Value
Mean score, healthy-agent outputs	$0.89\pm 0.01$
Mean score, degraded-agent outputs	$0.08\pm 0.01$
Recall on degraded-agent outputs	$0.90\pm 0.03$
False-alarm rate on healthy-agent outputs	$0.053\pm 0.007$
Committee escalation rate for degraded-agent outputs	$0.98\pm 0.02$

Appendix

Table C8: Agent review performance and Takeover outcomes.

Explore similar work

Robust Multi-Agent LLMs under Byzantine Faults
May 9, 2026Haejoon Lee, Vincent-Daniel Yun, Dimitra Panagou +1Multi-Agent Large Language Model Systems Byzantine Attacks
Department of Robotics, University of Michigan, Ann Arbor, USA · Thomas Lord Department of Computer Science, University of Southern California, USA
Who Broke the System? Failure Localization in LLM-Based Multi-Agent Systems
Jul 8, 2026Yufei Xia, Anjun Gao, Yueyang Quan +2Model-Based Multi-Agent Systems
University of Louisville · University of North Texas
Self-Evolving Multi-Agent Systems via Decentralized Memory
May 21, 2026Guangya Hao, Yunbo Long, Zhuokai ZhaoMulti-Agent Evolution Nativemem
University of Cambridge · University of Chicago

May 9, 2026, cs.MAJ/K move · Enter open · S save

Robust Multi-Agent LLMs under Byzantine Faults

Haejoon Lee, Vincent-Daniel Yun, Dimitra Panagou, Sai Praneeth Karimireddy

Department of Robotics, University of Michigan, Ann Arbor, USA · Thomas Lord Department of Computer Science, University of Southern California, USA

Multi-Agent Large Language Model Systems Byzantine Attacks Reasoning Errors

Open paper AskPDF arXiv

Large language model (LLM) agents increasingly collaborate over peer-to-peer networks to improve their reliability. However, these same interactions can also become a source of vulnerability, as unreliable or Byzantine agents may sway neighboring agents toward incorrect conclusions and degrade overall system performance. Existing methods rely on leader-based coordination or self-reported confidence, both of which are susceptible to adversarial manipulation. We study decentralized LLM multi-agent systems (LLM-MAS) and propose Self-Anchored Consensus (SAC), a fully decentralized iterative filter-and-refine protocol in which agents iteratively exchange responses, locally evaluate and filter unreliable messages, and refine their own outputs. We present

(F{+}1)

-robustness conditions for the communication graph that ensure honest agents preserve and propagate reliable information despite Byzantine influence. Experiments on mathematical and commonsense reasoning benchmarks show that SAC effectively suppresses Byzantine influence and consistently improves performance across diverse communication topologies, whereas prior methods degrade under adversarial conditions.

Abstract

Explore similar work

Robust Multi-Agent LLMs under Byzantine Faults

Who Broke the System? Failure Localization in LLM-Based Multi-Agent Systems

Self-Evolving Multi-Agent Systems via Decentralized Memory