How Many Triggered Agents Can a Swarm Survive? Cutoff-Based Tolerance Ratios for Backdoored Neural Swarms

When every robot in a swarm runs the same neural network, one poisoned supplier can place a backdoor in all of them. A backdoor is hidden behavior that stays dormant on normal inputs and fires when a specific trigger pattern appears. For a swarm, whether a hidden failure exists matters less than how much of it the collective can absorb. If an attacker can show the trigger to some fraction of the agents, does the group still complete its task and stay safe, and does the answer hold at 10 robots, 10,000, or any number? We propose to compute this fraction exactly and prove it holds for every swarm size. We call it the trigger-tolerance ratio: the largest fraction of agents whose sensors can be driven into a trigger region without violating a temporal safety property.

The approach joins two lines of work that have not met. Parameterized verification proves properties of systems with an unbounded number of identical components. Cutoff theorems are its main tool: they show that checking a small system of size $c$ settles the question for every larger size. This machinery already handles random or crash faults and already handles neural perception, but never an adversary acting through the network's own learned behavior. Backdoor research, meanwhile, has shown that multi-agent triggers can depend sharply on counts, firing only once enough peers carry a cue. It has no way to certify anything across population sizes. Count-dependent triggers and identical agents are exactly the setting where cutoff reasoning is strongest.

Core Claim

We claim three things. First, for swarms of identical agents with a feed-forward perception network and a symbolic action rule, the trigger-tolerance ratio can be synthesized in one shot, with a proof covering all swarm sizes. Second, this requires a new abstraction, because the one currently used for neural swarms cannot express count thresholds. Third, the resulting ratio is measurably tighter than what one gets by treating triggered agents as arbitrary adversaries. That last gap is where the neural network earns its place in the analysis.

Precisely, let $\mathcal{S}(N)$ be the swarm with $N$ agents sharing network $f$. Let $T$ be a trigger region, meaning a bounded set of perturbations to sensor inputs, such as a patch on designated sensor coordinates. Let $\varphi$ be a bounded-horizon temporal property. We seek

$$ \lambda^* = \max\{\lambda \in [0,1] : \forall N \ge c,\ \forall A \subseteq \{1..N\} \text{ with } |A| \le \lfloor \lambda N \rfloor,\ \mathcal{S}_A(N) \models \varphi\}, $$

where $\mathcal{S}_A(N)$ is the swarm in which the adversary may, at any step within the horizon, add perturbations from $T$ to the sensor inputs of agents in $A$. We want $\lambda^*$ together with a cutoff $c$ and a counterexample trace whenever $\lambda^*$ is exceeded.

Research Program

The closest work supplies most of the method. Formal Verification of Parameterised Neural-symbolic Multi-agent Systems (PANoS) models swarms of identical agents that combine neural perception with symbolic action selection. It collapses the unbounded population into a few concrete agents plus one "zero-one" proxy that records only whether zero or at least one agent occupies each configuration. It then encodes bounded-horizon checks as mixed-integer linear programs (MILPs), which the solver Gurobi handles via the VENMAS tool, and uses this to find benign emergence thresholds, such as colony survival requiring $n \ge 3$ in the Guarding Game. Symbolic Synthesis of Fault-Tolerance Ratios in Parameterised Multi-Agent Systems supplies the ratio-synthesis idea. It labels states with the minimum faulty proportion needed for a violation and uses cutoffs to lift the answer to all sizes, but its faults are fail-stop states in a symbolic template with no network and no input dependence. Verifying Fault-Tolerance in Probabilistic Swarm Systems handles independent, random malfunctions, which is the opposite of a coordinated attacker choosing which agents to trigger. The motivating evidence comes from When Collaboration Becomes a Trigger: Collective Evidence-Threshold Backdoors in Multi-Agent Systems. It shows that attack success jumps from near zero to 0.95–1.00 once the number of peers carrying the cue crosses a threshold $\theta$. It tests only fixed agent counts and offers only a statistical detector.

The first technical piece is a capped counter abstraction. Zero-one abstraction cannot tell one triggered agent from two, so it cannot see a threshold $\theta \ge 2$, and it cannot express a ratio at all. We will instead track, for each local configuration, the occupancy count saturated at a cap $\kappa$, together with a ratio variable bounding the adversary's budget. This extends the counter abstraction of A Counter Abstraction Technique for the Verification of Robot Swarms, which uses exact counts without neural components, and adapts it to PANoS's neural-symbolic semantics.

The central theorem to prove is that, for the negation-free bounded fragment PANoS already supports, the capped abstraction is sound and complete when $\kappa$ equals the largest count constant appearing in the agents' protocol or specification, plus the number of indexed agents in $\varphi$. The second term mirrors the result in A Cutoff Technique for the Verification of Parameterised Interpreted Systems with Parameterised Environments that the cutoff equals the number of agent variables in the formula. This theorem is the main risk. If completeness fails, we fall back to a sound under-approximation of $\lambda^*$ and report the gap to concrete checks.

The second piece is the adversarial MILP encoding. For each agent class, the network's response is encoded over the union of the clean input set and the input set shifted by $T$. The adversary's choices, meaning which classes and how many agents are triggered at each step, become integer variables constrained by the ratio. A binary search over $\lambda$, or a direct optimization objective where the encoding allows it, yields $\lambda^*$.

The third piece is the benchmark instances. We will train small perception networks for the Guarding Game and for a neural version of the alpha aggregation protocol. Each network gets a clean version and a version poisoned with a sensor-pattern trigger using attack recipes adapted from SCLBD/BackdoorBench. We will also build a symbolic evidence-threshold aggregation rule that mimics the count-triggered behavior reported for collective evidence-threshold backdoors.

We treat Backdoors Stuck At The Frontdoor: Multi-Agent Backdoor Attacks That Backfire as a constraint rather than a contradiction. It finds that many uncoordinated poisoners cancel each other during training, with success falling toward about 0.1 on CIFAR-10. Our threat model has a single supplier and a coordinated runtime trigger, which that effect does not cover. We therefore model the adversary as coordinated and worst-case.

Baselines

The naive reference point is concrete verification at fixed sizes. We run PANoS-style MILP checks on the explicit swarm at $N = 2, 3, \dots$ until timeout, and report the smallest violating fraction seen. PANoS itself reports that concrete checks time out as agent count and horizon grow, though no numeric cutoff of tractability is given. We run it with the same Gurobi version, time limit, and hardware as our method. Our method beats it if it returns a ratio certified for all $N$ within that budget, and if that ratio agrees with every concrete check that finishes.

The strongest existing parameterized competitor is fault-tolerance ratio synthesis in MCMAS-PFTS from Symbolic Synthesis of Fault-Tolerance Ratios in Parameterised Multi-Agent Systems, with each triggered agent modeled as an arbitrary nondeterministic (Byzantine) agent. On alpha aggregation that paper reports a 33% fault-tolerance ratio, with 986 seconds for symbolic synthesis versus 1980 seconds for iterative testing. On our neural alpha aggregation we will run it with the same protocol and specification. It yields a sound but possibly pessimistic bound. Our method beats it if our $\lambda^*$ is strictly larger for the backdoored network and simulation confirms the larger value is real, at comparable runtime.

The closest neural-swarm baseline is unmodified zero-one abstraction as in PANoS, fed our adversarial encoding. Its cost is expected to be similar. We expect it to give wrong answers for $\theta \ge 2$ protocols, and showing those disagreements against concrete checks is the ablation that isolates the capped counter. A second ablation removes the network: we replace the MILP encoding of $f$ over $T$ with unconstrained outputs. This isolates how much of the tightening comes from reasoning about the actual learned function.

For single-model certification we compare to PECAN: A Deterministic Certified Defense Against Backdoor Attacks, which reports CIFAR-10 attack success falling from 95.54% to 0.87%. We apply its partition-and-vote training to the perception network and ask whether the resulting per-agent guarantee alone implies the swarm property. For runtime detection we compare to LATTE from the collective evidence-threshold paper, which recovers post-threshold accuracy to 0.69–0.90. It serves as the empirical counterpart on the threshold protocol, measured by violation rate under attack in simulation.

Why not just…?

Why not just certify each agent's network and stop there? If every agent were provably unaffected by $T$, the swarm would be safe, and PECAN-style per-model certificates are cheap. Two things go wrong. The premise of the threat is that the network is backdoored, so a single-agent certificate over the trigger region fails, and failing tells you nothing about whether the collective tolerates the failure. PECAN also covers only single-step classification and relies on certifiers that do not scale to deep networks. We test this directly: on backdoored networks where per-agent certification fails, we report the $\lambda^*$ the swarm still tolerates, which the per-agent view would call zero.

Why not just treat triggered agents as Byzantine in the existing fault-ratio tool? This is the real threat to the proposal, because it needs no new theory and is already sound. If the Byzantine ratio equals $\lambda^*$ on our benchmarks, the network encoding is wasted effort and we will report exactly that. We expect a gap because the Byzantine model gives a backdoor behaviors its network cannot produce, for example actions unreachable from any input in $T$. The ablation that replaces the network with unconstrained outputs measures this gap on each benchmark.

Why not just simulate attacks at several swarm sizes and extrapolate? Threshold backdoors are the failure case for extrapolation, since behavior is flat below $\theta$ and jumps above it, as the 0-to-1 success jump shows. Simulation also cannot rule out a worst-case assignment of triggers. We still run large-$N$ simulation, but only as a falsification check on the certified ratio.

Why not just deploy a runtime detector like LATTE? It helps in practice, but by its authors' account it can be evaded by triggers that mimic benign latent trajectories, and it certifies nothing. The two are complementary. Our ratio tells a designer how much detection failure the protocol can absorb.

Proposed Experiments

The benchmarks are the Guarding Game from PANoS with neural perception, a neural alpha aggregation protocol for direct comparison with the 33% / 986-second MCMAS-PFTS figures, and the autonomous robot benchmark from the parameterised-environments cutoff paper as a small sanity case. There, the reported cutoff is 2 and explicit checking times out at 90 robots. For each benchmark we evaluate a clean and a backdoored network under patch triggers of increasing size.

The metrics are the synthesized $\lambda^*$, synthesis runtime, the cutoff used, the gap to the Byzantine ratio, and the gap between clean and backdoored ratios. We read that last gap as the collective damage the backdoor can do.

Three decisive checks settle the claims. First, soundness: for every $N$ at which concrete verification finishes, the abstraction's verdict must match at ratios just below and just above $\lambda^*$, and any disagreement falsifies the completeness theorem. Second, reality: adversarial simulation at $N$ = 100 and 1,000, with the attacker optimizing which agents to trigger, must find violations just above $\lambda^*$ and none below it. Third, value: $\lambda^*$ must exceed the Byzantine ratio on at least the aggregation benchmark, and zero-one abstraction must disagree with concrete checks on the threshold protocol.

If the first check fails, the contribution shrinks to a sound lower bound. If the third fails, the honest conclusion is that existing fault-ratio tools already suffice for backdoored swarms. That is also worth knowing.