MeshHeal Reliability in multi-agent systems
MeshHeal: Two-Timescale Self-Healing for Gray Failures in Decentralized LLM Agent Networks
arXiv preprint · September 24, 2026
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.
Original abstract · arXiv:2609.29015v1
Problem statement
An agent can keep answering messages even after its answers become unreliable. A network that checks only whether the agent is available will continue to send it work, allowing poor outputs to affect other agents. We call this persistent, protocol-compliant degradation a gray failure.
The network faces two decisions at different times. It must protect the task already in progress, before it has enough evidence to diagnose persistent degradation. It must also decide whether to route future work elsewhere. Excluding an agent creates a third problem: without new observations, the network cannot tell when that agent has recovered.
Method
MeshHeal connects these decisions through ability-matched peer review. Within a task, reviewers assess an output before it is used. Uncertain or low-scoring outputs receive repeated review, then committee deliberation and correction when needed. Across tasks, a detector accumulates the same review scores, comparing each producer with peers on matched tasks and abilities. Sustained underperformance changes the producer’s routing eligibility.
The score stays attributed to the original producer even if another agent replaces its answer. This preserves evidence of the failure. Reviewed recovery probes then supply fresh evidence from excluded agents, allowing recovered agents to return to ordinary routing.
Key findings
1. Higher degraded-phase accuracy with fewer model tokens
In six-agent networks evaluated on BBH, MATH, and MMLU-Pro, MeshHeal reaches 0.839 ± 0.012 degraded-phase accuracy, compared with 0.807 ± 0.014 for Symphony, the strongest baseline. The evaluation swaps degraded agents from GPT-OSS-120B to Llama-3.2-1B and averages five seeds. Token counts include both input and output tokens. Table 2(a)
| Method | Degraded-phase accuracy | Total model tokens per task |
|---|---|---|
| Symphony | 0.807 ± 0.014 | 115k ± 9k |
| MeshHeal | 0.839 ± 0.012 | 51k ± 5k |
2. Exclusion and reintegration close the recovery loop
In a staggered 630-task MATH experiment, both degraded agents complete detection, exclusion, and reintegration in 5/5 seeds. Mean detection delays are 8.0 ± 5.2 and 12.4 ± 6.2 tasks; reintegration delays after backend recovery are 46.0 ± 11.7 and 45.0 ± 3.5 tasks, respectively. These are observed delays under the evaluated schedule. Table 3
3. Sparse networks can retain the required local evidence
In the 576-agent scaling experiment, a sparse graph uses 0.88% of the complete graph’s edges, isolates 192/192 degraded agents, and reaches 0.814 accuracy. The complete graph reaches 0.808. The sparse construction retains the local ability coverage required by the protocol. Table 2(b)
4. Correcting current outputs contributes to accuracy
On BBH, degraded-phase accuracy is 0.900 for the full method, 0.865 with a single reviewer, and 0.844 without Takeover, the mechanism that replaces an unreliable output. This ablation separates the benefit of immediate correction from the slower routing decision. Table 4(a)
Relation to prior work
Per-task review and deliberation can improve the answer currently being produced, but they do not necessarily retain evidence that the same producer has degraded across tasks. History-based routing can avoid a persistently weak agent, but it acts after evidence accumulates and can stop observing that agent once it is excluded. MeshHeal reuses review evidence across both timescales and adds probes for recovery.
The evaluation also distinguishes a declared role from an executable ability. If a capable model can solve every task despite its role prompt, a routing error may have little effect on accuracy. Model-Backed MAS Evaluation ties assigned abilities to execution models so that routing decisions have measurable consequences. Sections 2 and 5
Limitations
The experiments induce degradation through controlled backend changes. They do not establish recovery from every kind of memory corruption, tool failure, or adversarial behavior. The protocol also needs suitable healthy reviewers and reachable agents with the required abilities; sparse connectivity is useful only when those conditions remain available.
The detector relies on representative healthy-peer scores. Correlated degradation or a poor reference group can weaken that comparison. Reported detection and recovery outcomes are empirical results for the tested networks and schedules. Network conditions, detector limitations
Resources
- Paper PDF, including appendices
- Algorithms and experimental settings
- Agent and reviewer prompts
- Review, exclusion, and recovery traces
The citation below follows the arXiv title record. The manuscript heading uses the shorter title MeshHeal: Self-Healing Decentralized LLM Agent Networks under Gray Failures.
BibTeX
@misc{chen2026meshheal,
title = {{MeshHeal}: Two-Timescale Self-Healing for Gray Failures in Decentralized LLM Agent Networks},
author = {Chen, Keru and Lin, Sen and Liang, Yingbin and Bastian, Nathaniel D. and Zou, Shaofeng},
year = {2026},
eprint = {2609.29015},
archivePrefix = {arXiv},
primaryClass = {cs.AI},
doi = {10.48550/arXiv.2609.29015},
url = {https://arxiv.org/abs/2609.29015}
}