PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.29015v1cs.AIcs.CLcs.DC

TL;DR

Gray failures leave decentralized agents responsive even as their task-solving ability degrades, creating a need to protect current tasks while adapting future routing and allowing recovery. MeshHeal combines ability-matched peer review across fast and slow timescales and introduces model-backed evaluation. Across three benchmarks, it reports higher degraded-phase accuracy than Symphony with fewer tokens per task.

  • Problem

    Decentralized agent networks may contain responsive agents whose task-solving ability persistently degrades, while current-task protection and later routing adaptation require evidence at different timescales.

    Source: §1 · p. 2

  • Method

    MeshHeal combines fast ability-matched review and correction with slow peer-relative degradation detection, routing restrictions, and recovery probes, and evaluates abilities through execution-model selection.

    Source: §1 · pp. 2–3

  • Results

    Across BBH, MATH, and MMLU-Pro, 0.839 degraded-phase accuracy over five seeds compares with 0.807 for Symphony, the strongest baseline.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The paper evaluates self-healing beyond accuracy and inference cost using detection delay, closure, and reintegration criteria.

    Source: §3.2 · p. 4

    The setting assumes agents have heterogeneous abilities but no global view, and health remains unchanged within each task while potentially changing across tasks.

    Source: §3.1 · p. 4, §3.2 · p. 4

Abstract

from arXiv · show

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.

1 INTRODUCTION

Decentralized LLM agent networks can face gray failures: agents remain responsive while their task-solving ability persistently degrades. MeshHeal combines peer review across two timescales with model-backed evaluation, and reports higher degraded-phase accuracy than the strongest baseline at lower token use.

1 INTRODUCTION

  • Decentralized MAS research largely assumes agents remain reliable, although backend, controller, memory, or tool problems can degrade agents that continue communicating normally.Because such agents remain protocol-compliant, their degradation must be inferred from output quality or downstream effects rather than connectivity alone.Source: §1 · pp. 1–2
  • Existing per-task output-improvement methods do not track persistent producer-specific evidence, while history-based routing cannot protect the current task or gather recovery evidence after bypassing an agent.Self-healing therefore requires current-task protection, accumulated evidence for future routing, and reintegration after recovery.Source: §1 · p. 2
  • MeshHeal uses ability-matched peer review at a fast timescale and accumulated task- and ability-conditioned evidence to escalate routing restrictions at a slow timescale.Recovery probes provide fresh reviewed evidence for gradually returning recovered agents to normal routing.Source: §1 · pp. 2–3
  • 83.9% mean accuracy during degradation over five seeds, versus 80.7% for Symphony, with 51k tokens per task versus 115k for Symphony and 178k for SAC.The experiments cover BBH, MATH, and MMLU-Pro.Source: §1 · p. 3
  • Model-Backed MAS Evaluation assigns abilities through execution-model selection because prompt-only assignments can let incorrect routes produce correct answers and hide routing errors.Backend selection also provides known failure ground truth while keeping gray-failed agents responsive.Source: §1 · p. 3

2 RELATED WORK

Prior work addresses output quality, adaptive routing, and distributed recovery, but these strands leave distinct gaps for decentralized MASs facing gray failures.

LLM multi-agent coordination and robustness

  • Repeated inference, deliberation, peer review, and robust aggregation improve outputs within individual tasks but do not identify persistent agent failures.Without persistent-failure detection, degraded agents may continue participating in task solving.Source: §2 · p. 3

Adaptive routing strategies

  • History-based routing, adaptive selection, and reputation methods adapt agent use, but cannot protect the current task or gather recovery evidence after bypassing an agent.The passage names AgentNet, Symphony-Coord, and RAPS as examples.Source: §2 · p. 3

Distributed recovery and gray failures

  • Gray-failure research motivates inferring hidden degradation from peer observations rather than availability, and this paper uses reviewed output quality as the signal for LLM agents.Source: §2 · p. 3

3 PROBLEM FORMULATION

The formulation considers decentralized LLM agents with heterogeneous abilities, task sequences, and latent health states that can change between tasks. It defines self-healing goals and criteria for evaluating detection, continued isolation, and reintegration.

3.1 DECENTRALIZED MAS ARCHITECTURE

  • The MAS is an undirected communication graph whose agents each comprise an LLM backend and a local controller.An edge permits two neighboring agents to send information to one another.Source: §3.1 · p. 3
  • Agents have different ability sets, tasks require matching abilities, and each agent coordinates using only neighbor communication rather than a global view.Source: §3.1 · p. 4
  • The task sequence provides each task’s question and benchmark category, while the abilities required to solve it must be inferred by an agent.Source: §3.1 · p. 4
  • Local coordination policies use task state, local interaction history, and neighbor messages to optimize average correctness across tasks under execution randomness.Source: §3.1 · p. 4

3.2 GRAY FAILURE AND SELF-HEALING

  • A gray failure leaves an agent available and protocol-compliant while reducing its effective ability to solve some tasks; health is latent and may change between tasks, not within one task.Recovery is the restoration of an agent from degraded to healthy.Source: §3.2 · p. 4
  • Self-healing aims to route tasks to healthy agents with matching abilities while returning recovered agents to future tasks matching their abilities.The formulation evaluates this goal beyond accuracy and inference cost.Source: §3.2 · p. 4
  • Detection delay measures the gap from degradation to first isolation, while closure requires isolation to continue until recovery.Source: §3.2 · p. 4
  • Reintegration is the return of a recovered agent to normal routing, with reintegration delay measured from recovery to that return.Source: §3.2 · p. 4

4 MESHHEAL: REVIEW AT TWO TIMESCALES

MeshHeal combines a decentralized task-routing workflow with fast review and correction and slow degradation detection, rerouting, and recovery. Its detector compares agents with peers doing the same task type and ability, while recovery probes provide fresh reviewed evidence for reintegration.

4.1 BASE TASK EXECUTION AND ROUTING (NO FAILURES)

  • Tasks move sequentially through agents with matching abilities, using distributed shortest-hop routes to reach agents that can supply still-missing abilities.Agents hand off when they cannot contribute, contribute when they can cover some remaining abilities, and finalize when they can cover them all.Source: §4.1 · p. 5

4.2 TASK EXECUTION AND ROUTING UNDER GRAY FAILURES

  • Normal agents follow the base workflow, watched agents receive mandatory committee review on every output, and isolated agents leave task execution but remain available for message relay.Isolation temporarily sets an agent’s abilities to the empty set, after which shortest-hop distances are recomputed.Source: §4.2 · p. 5

4.2.1 FAST TIMESCALE: REVIEW AND CORRECTION

  • Every contribution and final output is reviewed before use, escalating low-scoring, high-disagreement, watched-agent, or recovery-probe outputs to committee review and, when needed, correction.The initial score is the median of three independent reviews; committee scores above the acceptance threshold are accepted, while lower scores trigger takeover and correction.Source: §4.2.1 · p. 6

4.2.2 SLOW TIMESCALE: DETECTION, REROUTING AND RECOVERY

  • For each task type and ability, the detector averages the latest eight peer-relative shortfalls and normalizes them against normal-neighbor variation, enabling shared thresholds across model backends.The reference comes from normal neighbors with recent reviews on the same task type and ability; a positive shortfall means the agent scored below that reference.Source: §4.2.2 · pp. 6–7
  • With at least three matched observations, α=1.2 and β=2 govern watched and isolated transitions; isolated agents become recovery-probe eligible every 10 tasks and can return first to watched, then normal.Isolation requires two consecutive updates at or above β; recovery probes receive mandatory committee review and update the same detector.Source: §4.2.2 · p. 7

5 MODEL-BACKED MAS EVALUATION

The evaluation tests whether system prompts reliably constrain assigned abilities and uses execution models to realize ability assignments and degradation. Across five BBH models, prompt-based assignment produced only a small increase in the assigned–unassigned accuracy gap.

5 MODEL-BACKED MAS EVALUATION

  • 0.015–0.058: across five BBH models, prompts increased the assigned–unassigned accuracy gap by only this amount; unassigned accuracy remained substantial, and assigned accuracy fell for four models.Table 1 compares prompts with no competence statement against prompts declaring unassigned abilities unreliable.Source: Table 1 · p. 7, §5 · p. 7
  • Execution models realize ability assignments: healthy agents use strong models for assigned abilities and weak models otherwise, while degradation replaces the strong backend without changing interfaces.This setup preserves responsiveness while reducing task competence, providing known failure ground truth and making routing errors visible in end-to-end accuracy.Source: §5 · p. 7
  • The protocol covers seven task groups from each of BBH, MATH, and MMLU-Pro, with two complementary abilities assigned to disjoint agent sets and at least two agents required per task.Each task group represents one task type.Source: §5 · p. 7

6 EXPERIMENTS

The experiments compare MeshHeal with matched baselines on persistent degradation, staggered recovery, and sparse-network scaling, measuring accuracy, model-token cost, and agent isolation and reintegration.

6 EXPERIMENTS

  • Five-seed comparisons hold tasks, agents, ability assignments, models, degradation targets, and schedule constant across decentralized and centralized baselines.Reported measures include accuracy, token consumption, and detection delay.Source: §6 · p. 8

6.1 PERSISTENT DEGRADATION: ACCURACY AND COST

  • 0.839 ± 0.012 degraded-phase accuracy and 51 ± 5k total model tokens per task compare with Symphony’s 0.807 ± 0.014 and 115 ± 9k.Values are means ± standard deviations across datasets and seeds.Source: §6.1 · p. 8, Table 2 · p. 8

6.2 DEGRADATION AND RECOVERY: DETECTION, CLOSURE, AND REINTEGRATION

  • Across 504 post-degradation MATH tasks, MeshHeal reaches 0.812 accuracy at 49k tokens per task versus Symphony’s 0.806 at 105k, though Symphony leads in A5-only and fully recovered phases.The five phases include healthy operation, staggered degradation, and backend restoration.Source: §6.2 · p. 8, Table 3 · p. 9
  • Both agents stay isolated through all five seeds except recovery probes; detection takes 8.0 ± 5.2 tasks for A5 and 12.4 ± 6.2 for A3, reintegration 46.0 ± 11.7 and 45.0 ± 3.5.Baseline methods do not fully isolate degraded agents.Source: §6.2 · p. 8, Table 3 · p. 9

6.3 SCALING WITH LOCAL INFORMATION

  • At 576 agents, sparse networks isolate all degraded agents, use 0.88% of complete-graph edges, and reach 0.814 accuracy; sparse and complete accuracy differs by at most 0.010.Review, summary exchange, and routing updates remain local.Source: §6.3 · p. 9

6.4 COMPONENT AND DETECTOR STUDIES

  • Single-reviewer evaluation lowers degraded-phase accuracy by 0.035; removing Takeover lowers degraded- and healthy-phase accuracy by 0.056 and 0.020, respectively.Takeover corrected 15 of 32 wrong answers while turning 1 of 32 correct answers incorrect.Source: §6.4 · p. 9
  • Relative peer comparison detects both degraded agents without false isolation under both model pairs, while absolute thresholds and CUSUM produce false isolations or misses.The detector comparison uses fixed rubrics and parameters.Source: §6.4 · p. 9
  • Across milder-degradation and weaker-healthy-model tests, MeshHeal beats Symphony by 0.040 on Pair A, stays within 0.004 on Pair B, and uses 52–56% as many tokens.Both degraded agents are detected without false isolation across the two settings.Source: §6.4 · p. 9

7 CONCLUSION

MESHHEAL combines fast output review and correction with slower degradation detection and routing updates, while using model-backed ability assignments to evaluate routing. Its conclusion reports improved degraded-phase accuracy at lower token cost than Symphony and a staged recovery procedure.

7 CONCLUSION

  • 0.839 degraded-phase accuracy at 51k tokens per task, versus Symphony’s 0.807 at 115k, across three benchmarks and five seeds.The evaluated degradation-and-recovery schedule met the three self-healing criteria, and scaling experiments isolated every degraded agent in networks up to 576 agents.Source: §7 · p. 10

B.1 FULL PROCEDURE

  • The task procedure routes work locally, reviews each contribution, replaces outputs when Takeover is triggered, and updates future routing from attributed review evidence.A committee is triggered by low initial scores, watched status, recovery probes, or high reviewer disagreement; low final committee scores lead to Takeover synthesis.Source: §7 · p. 10, §B.1 · p. 16

A ABILITY ASSIGNMENT THROUGH SYSTEM PROMPTS

  • Prompt-based ability assignments do not reliably restrict performance to assigned abilities, motivating controlled backend selection to evaluate routing.Declaring unassigned abilities unreliable increased the accuracy gap by 0.015–0.058 across five models, while assigned-ability accuracy declined for four.Source: §7 · p. 10, A ABILITY ASSIGNMENT THROUGH SYSTEM… · p. 14

B.2 AGENTS AND ABILITIES

  • Each task’s complementary required abilities are assigned to disjoint agent sets, so at least two agents are needed to cover both.The mappings pair abilities by dataset, including mathematical operations with reasoning and domain knowledge with the operation needed to apply it.Source: §B.2 · pp. 16–17

B.3 MODELS, DATA, AND DEGRADATION

The appendix specifies the task stream, shared baseline evaluation, review and detection rules, and sparse-network conditions, then describes the detailed results and the persistent-degradation table’s scope.

B.3 MODELS, DATA, AND DEGRADATION

  • The 504-task stream has 252 healthy tasks followed by 252 degraded tasks, with A3 and A5 switched to the weak model while their declared abilities remain unchanged.The phases use different questions from the same task-type distribution, and the model change preserves agent identities, abilities, and communication links.Source: §B.3 · pp. 17–18

B.4 BASELINES

  • Baseline comparisons retain each method’s native logic while sharing task order, agent identities, abilities, models, degradation schedule, prompts, and task interface.Token accounting includes all model calls and input and output tokens across routing, execution, review, and aggregation.Source: §B.4 · p. 18

B.5 REVIEW, ACCEPT, AND TAKEOVER

  • Ability-matched normal peers review outputs; low scores, watched status, recovery probes, or reviewer disagreement trigger a committee, and sufficiently low committee scores trigger Takeover.The final review score remains attributed to the agent that generated the original output under both Accept and Takeover, supplying evidence for later routing updates.Source: §B.5 · pp. 18–19
  • The detector compares an agent’s shortfall for a task type and ability against peer-relative normal ranges, requiring three matched observations before state changes.Isolation requires two consecutive threshold crossings; recovery applies the thresholds in reverse, and routing state is retained when evidence or comparison sets are unavailable.Source: §B.5 · pp. 19–20

B.6 PARAMETERS

  • The review and detection parameters remain fixed across datasets, model pairs, and network sizes unless an ablation explicitly varies them.Isolated agents become probe-eligible after 10 tasks; low initial scores and high uncertainty trigger committee review, while Takeover requires a final score at or below 0.40.Source: §B.6 · p. 20

B.7 SPARSE NETWORKS

  • Sparse graphs preserve local review and routing conditions: agents have an ability-matched reviewer and can reach a healthy holder of each required ability within the routing limit.Across the evaluated graph sizes, edge density falls from 5.00% at 96 agents to 0.88% at 576 agents.Source: §B.7 · p. 21

C DETAILED RESULTS

  • The detailed-results appendix separates accuracy by dataset and reports inference cost before varying model pairs, degradation timing, topology, committee, and detector.Table C1 reports persistent-degradation results as mean ± standard deviation over five seeded task streams per dataset, with healthy and degraded phases stacked in each entry.Source: C DETAILED RESULTS · p. 21, Table C1 · p. 21

MESHHEAL

MESHHEAL maintains the highest mean degraded-phase accuracy across the three datasets while using fewer tokens per task than the higher-cost comparison systems.

MESHHEAL

  • 0.839 ± 0.012 degraded-phase accuracy, the highest mean on all three datasets, with a paired healthy-to-degraded change of +0.007 ± 0.012.Aggregate healthy-phase accuracy is 0.831 ± 0.013.Source: MESHHEAL · p. 21
  • (51 ± 5)k mean total model tokens per task in the degraded phase, compared with Symphony’s (115 ± 9)k and SAC’s (178 ± 13)k.MESHHEAL’s mean model calls rise from 12.4 ± 0.2 to 13.6 ± 0.3 after degradation onset, while mean tokens are (51 ± 3)k and (51 ± 5)k across the two phases.Source: MESHHEAL · pp. 21–22, Table C2 · p. 22

C.2 MODELS AND RECOVERY

Results vary with the model pair, while the staggered-recovery experiment and larger-network evaluation report continued isolation of degraded agents and reintegration after recovery.

C.2 MODELS AND RECOVERY

  • 0.905 ± 0.016 degraded-phase accuracy for MESHHEAL under pair A, versus 0.865 ± 0.021 for Symphony; under pair B, the means are 0.782 ± 0.023 and 0.786 ± 0.021.MESHHEAL uses fewer tokens than Symphony under both pairs; under pair B it uses 52% of Symphony’s mean tokens.Source: Table C3 · p. 22, §C.2 · p. 22, Table C4 · p. 22
  • 0.812 pooled accuracy across the 504 tasks after the first agent degrades at 49k tokens per task, compared with Symphony’s 0.806 at 105k.Mean accuracy rises from 0.770 with both targets degraded to 0.841 after A5 recovers and 0.857 after both recover; all methods complete the 630-task stream.Source: §C.2 · p. 22
  • In the representative trajectory, A5 is isolated five tasks after degradation begins and A3 after 15; both remain isolated throughout their degraded intervals and return to normal after recovery.Their reintegration delays are 51 tasks for A5 and 45 for A3.Source: §C.2 · p. 22, Table C5 · p. 23

C.3 LARGER NETWORKS

  • Every degraded agent is isolated in all evaluated topologies, while sparse-graph accuracy ranges from 0.803 to 0.818 and complete-graph accuracy from 0.808 to 0.827.The largest accuracy difference is 0.010 at 288 agents; sparse-graph accuracy is 0.006 higher at 576 agents.Source: §C.3 · p. 23

C.4 ABLATIONS

The ablations show that committee review and Takeover improve degraded-phase accuracy, while peer-relative detection avoids the errors seen with fixed-threshold alternatives in the tested model pairs.

Fast timescale ablations

  • The full configuration exceeds Single reviewer and No Takeover by 0.035 and 0.056 in mean degraded-phase accuracy, respectively.Paired phase changes are +0.001 ± 0.016, −0.044 ± 0.024, and −0.035 ± 0.030; No Takeover also lowers healthy-phase accuracy by 0.020.Source: Table C6 · p. 23, §C.4 · p. 23

Detector comparison

  • Relative peer comparison produces no missed degraded agents or false isolations under either tested model pair, unlike the absolute and CUSUM rules.The peer-relative reference adapts to healthy-neighbor scores for the same task type and ability, while decision thresholds remain fixed.Source: Table C7 · p. 24, §C.4 · p. 24

Overall finding

  • Together, the component and detector studies support using review scores for both current-task correction and future routing.The component study tests fast-timescale committee review and Takeover; the detector comparison tests slow-timescale routing under two model pairs.Source: §C.4 · p. 24

C.5 REVIEW AND TAKEOVER AUDIT

The audit measures how review distinguishes injected healthy and degraded conditions, how committee reassessment and Takeover affect outputs, and how the runtime prompts and case traces implement review and routing.

C.5 REVIEW AND TAKEOVER AUDIT

  • Initial review assigns mean scores of 0.89 ± 0.01 to healthy-agent outputs and 0.08 ± 0.01 to degraded-agent outputs; it misses 2–4 of 31–33 degraded outputs per seed.Committee escalation is higher than the initial low-score decision because watched status or disagreement can also trigger review.Source: §C.5 · p. 24
  • Committee reassessment changes recall from 0.90 ± 0.03 to 0.88 ± 0.01 and false-alarm rate from 0.053 ± 0.007 to 0.044 ± 0.008.It clears 0.33 ± 0.07 of initially flagged healthy-agent cases and retains 0.95 ± 0.02 of initially flagged degraded-agent cases.Source: §C.5 · p. 24
  • Among 32 initially wrong Finalize answers entering Takeover, 15 are corrected; among 32 initially correct answers, one is changed to an incorrect answer.Of 18 changed initially wrong answers, 15 changes are correct; 14 initially wrong answers are left unchanged.Source: §C.5 · p. 24

D.1 REVIEW PROMPTS

D.2 ABILITY PROMPTS

  • Before execution, the entry LLM infers the task’s required ability pair, which the controller stores and compares with each agent’s declared abilities.The evaluation selects the strong or weak model from the ability match and injected condition; the prompt directive communicates the match to the LLM.Source: §D.2 · p. 27

Case 1: Complementary abilities across two agents

Case 2: Multi-hop routing around an isolated agent

Case 3: Fluent but incorrect output, committee reassessment, and Takeover

What this case shows

A watched agent’s coherent-looking solution can contain one localized error; committee review identifies the failing step, and Takeover repairs the current task without restarting its trajectory.

Case 4: A localized error inside an otherwise coherent solution

Committee review identifies the failing step

What this case shows

  • This localized error complements the more visible semantic error in Case 3, where committee reassessment resolves reviewer disagreement.The comparison is between an otherwise coherent solution with one wrong transition and a more visible semantic error.Source: What this case shows · p. 31

Related papers

Loading 2609.29015v1…