Reliability-Contagion Feasibility Window

Properties

family: propagation
severity: systemic
triggerError: A multi-agent network's communication topology is chosen or scaled up specifically to improve reliability, because agents aggregate their neighbours' claims by majority vote and denser connectivity supplies more corroborating signals per node.
mechanism: The paper models claim-level spread as a susceptible/exposed/infectious/corrected contagion process on the network graph and proves the claim-free state is stable only when R_err, the spectral radius of the next-generation matrix K = P T Gamma^-1, stays below 1. Because majority-vote reliability and error contagion are driven by the same connectivity parameter, a graph needs at least k* neighbours per node to clear its reliability target; but any graph meeting that target also satisfies R_err(G) >= q*tau*k*. If q*tau*k* >= 1, no graph in the reliable class can stay below the contagion threshold, so raising connectivity to hit a reliability bar can itself hand an erroneous claim the spread it needs to invade the network.
blastRadius: Agents within the propagating neighbourhood of an erroneous claim: those that receive it via majority-vote aggregation from neighbours and go on to assert or retransmit it once the network's error reproduction number R_err exceeds 1. Mean first-generation offspring rose from 0.667 to 1.333 to 1.667 as node degree increased from 2 to 4 to 5, showing that the same connectivity increase used to hit a majority-vote reliability target also expands the set of agents an erroneous claim can infect.
mast: [Cat 1][Cat 2]
detection: Estimate R_err from the network's topology and each agent's measured reliability/majority-vote parameters (q, tau) and compare it against the q*tau*k* threshold; track first-generation offspring count and cumulative infectious fraction at runtime rather than relying on final-answer agreement alone.
mitigation: When q*tau*k* < 1, use a connected, simple k*-regular graph: the paper proves this class is simultaneously reliable, strictly subcritical, and minimises R_err over every graph meeting the reliability target. When q*tau*k* >= 1, no topology in the reliable class avoids contagion risk, so the reliability target itself, not just the graph, has to change.
source: Reliability-Contagion Feasibility in LLM Multi-Agent Networks (arXiv:2607.21912)

Provenance

Source: https://arxiv.org/abs/2607.21912

Properties

family

propagation

severity

systemic

triggerError

A multi-agent network's communication topology is chosen or scaled up specifically to improve reliability, because agents aggregate their neighbours' claims by majority vote and denser connectivity supplies more corroborating signals per node.

mechanism

The paper models claim-level spread as a susceptible/exposed/infectious/corrected contagion process on the network graph and proves the claim-free state is stable only when R_err, the spectral radius of the next-generation matrix K = P T Gamma^-1, stays below 1. Because majority-vote reliability and error contagion are driven by the same connectivity parameter, a graph needs at least k* neighbours per node to clear its reliability target; but any graph meeting that target also satisfies R_err(G) >= q*tau*k*. If q*tau*k* >= 1, no graph in the reliable class can stay below the contagion threshold, so raising connectivity to hit a reliability bar can itself hand an erroneous claim the spread it needs to invade the network.

blastRadius

Agents within the propagating neighbourhood of an erroneous claim: those that receive it via majority-vote aggregation from neighbours and go on to assert or retransmit it once the network's error reproduction number R_err exceeds 1. Mean first-generation offspring rose from 0.667 to 1.333 to 1.667 as node degree increased from 2 to 4 to 5, showing that the same connectivity increase used to hit a majority-vote reliability target also expands the set of agents an erroneous claim can infect.

mast

[Cat 1][Cat 2]

detection

Estimate R_err from the network's topology and each agent's measured reliability/majority-vote parameters (q, tau) and compare it against the q*tau*k* threshold; track first-generation offspring count and cumulative infectious fraction at runtime rather than relying on final-answer agreement alone.

mitigation

When q*tau*k* < 1, use a connected, simple k*-regular graph: the paper proves this class is simultaneously reliable, strictly subcritical, and minimises R_err over every graph meeting the reliability target. When q*tau*k* >= 1, no topology in the reliable class avoids contagion risk, so the reliability target itself, not just the graph, has to change.

source

Reliability-Contagion Feasibility in LLM Multi-Agent Networks (arXiv:2607.21912)