Learned safety certificates now let swarms of robots trained with a handful of agents fly in groups of a thousand. These certificates are graph neural networks, meaning networks that compute each robot's output by combining messages from its neighbors. The way neighbor messages are combined is the weak point. Current systems average neighbors with attention weights. An average has a specific failure: when one neighbor is dangerously close and many harmless neighbors are also within sensing range, the harmless ones dilute the dangerous one, and the certificate reports the robot as safer than it is. The alternative of summing neighbor messages lets values grow without limit as crowds get denser. This proposal argues that a safety certificate needs a combination rule with three properties. It should be monotone: adding a neighbor can never make a robot look safer. It should be compactly supported: neighbors beyond a safety band contribute exactly zero. And it should be smooth, so the controller can take its derivatives. We build such a rule. We prove that, because robots physically cannot overlap, it bounds the number of neighbors that matter, which turns certificate verification into a check over a fixed, small configuration space that does not depend on swarm size. We then test whether this closes the gap between "scales empirically" and "is guaranteed to scale."
The idea in two sentences: attention-averaged barrier networks can be fooled by crowds, because harmless neighbors dilute the dangerous one. A certificate built as a smooth, nonnegative, compactly supported sum of per-neighbor penalties cannot be fooled this way, and it only ever depends on as many neighbors as can physically fit in a small band, so checking it once on small configurations certifies swarms of any size.
Background and the gap
A control barrier function (CBF) is a scalar function $h$ of the state that is nonnegative exactly on the safe set. Safety holds if the controller always keeps the time derivative of $h$ above a decreasing function of $h$. At runtime this is enforced by a one-step quadratic program that minimally corrects a nominal action, so $h$ must be differentiable. Two papers learn such certificates for multi-agent systems as graph networks. Neural Graph Control Barrier Functions Guided Distributed Collision-avoidance Multi-agent Control learns a decentralized certificate and policy with distance-weighted attention, chosen so that $h$ stays smooth as agents enter and leave sensing range. GCBF+ adds QP-filtered teacher targets and actuation-aware look-ahead. It reports over 98% success when a model trained on 8 agents is deployed on 1024, and argues that a locally learned certificate certifies arbitrary-size swarms. These papers supply the problem and the benchmark. Their certificate remains an attention-pooled black box, and its behavior at neighbor counts never seen in training is not checked.
The graph-expressivity literature explains why this matters and constrains the design. Almost Surely Asymptotically Constant Graph Neural Networks proves that networks built from weighted-mean aggregation, including attention, converge to constants as graphs grow, because averaging washes out individual elements. Their theorem assumes growing degree and i.i.d. features, so it does not literally apply to a physical swarm, where degree stays bounded. We take from it the finite-size mechanism of dilution, not the asymptotic statement. Some Might Say All You Need Is Sum shows the opposite failure: sum-aggregation networks cannot uniformly approximate mean or max, and they diverge outside the training range. On their unbounded-feature star task, sum networks showed relative errors exceeding 1.0. Principal Neighbourhood Aggregation mixes several aggregators with log-degree scalers normalized by the training-set average degree. That normalization is tied to the training distribution and does not by itself guarantee monotone behavior.
Finally, Unifying approach to uniform expressivity of graph neural networks shows that uniform expressivity is well characterized under bounded counting, where count distinctions are capped at a threshold. We use this as the theoretical lever. Physical packing supplies exactly such a cap.
Core Claim
Let $x_i$ be agent $i$'s state and $N_i$ its sensed neighbors (agents and obstacle points). We parameterize the certificate as
$$h_i = s_\theta(x_i) - \sum_{j \in N_i} c(d_{ij})\,\phi_\theta(x_i, x_j),$$
where:
- $s_\theta$ is a learned self term.
- $\phi_\theta \ge 0$ is a learned per-neighbor penalty that can depend on relative position and velocity.
- $d_{ij}$ is the inter-agent distance.
- $c$ is a continuously differentiable cutoff equal to one inside a safety band of radius $\rho$ and exactly zero beyond it. The band is chosen smaller than the sensing radius.
Collision states are forced negative by construction: on contact, $\phi_\theta$ is lower-bounded by $s_\theta$.
Three properties follow directly.
- Monotonicity. Adding a neighbor never raises $h_i$.
- Locality. Neighbors outside $\rho$ have no effect on $h_i$ or its gradient.
- Bounded crowding. Agents of radius $r$ that are not colliding can fit at most $K(\rho) \approx (\rho/r+1)^{\dim}$ in the band. So on the safe set at most $K(\rho)$ terms are nonzero, and $h_i$ stays bounded independently of swarm size $N$.
The theoretical result we will prove follows from these. The CBF condition for agent $i$ depends only on a configuration of at most $K(\rho)$ neighbors, plus those that can enter the band within one step. Verifying it on that fixed compact space therefore certifies it for every $N$. Monotonicity further lets the verification focus on the worst case: the densest admissible configurations.
This is a sum aggregator, which Some Might Say All You Need Is Sum warns against. The difference is that the packing bound converts the unbounded-degree regime, where sum diverges, into the bounded-counting regime, where uniform expressivity holds. The count of robots crowding $i$ is still visible to the certificate, which is precisely what averaging destroys.
Research Program
The work has four parts.
Theory. We formalize the dilution failure for attention certificates. We construct configurations with one neighbor inside the collision-imminent region and $k$ neighbors in the benign part of the sensing disk, and bound how fast an attention-pooled $h$ drifts upward in $k$. We then prove the monotonicity, locality and finite-verification statements above for our parameterization, including the one-step entry region needed for the Lie-derivative condition.
Architecture. We embed the aggregator in the GCBF+ training pipeline unchanged: same QP-filtered teacher, same look-ahead labels, same policy network. The only change is the certificate's combination rule. We enforce $\phi_\theta \ge 0$ with a softplus output and keep tanh-free layers where possible. The latter choice respects the saturation limits that Is uniform expressivity too restrictive? proves for smooth bounded activations.
Verification. Because the domain is fixed, we run dense sampling plus adversarial counterexample search over configurations with up to $K(\rho)$ neighbors. We report violation rates binned by neighbor count. With attention certificates the domain is effectively unbounded in $k$, so this kind of exhaustive binning has no natural endpoint.
Expressivity limits. A sum of pairwise penalties cannot represent genuinely cooperative structure, such as "boxed in on all sides" requiring joint reasoning. We will measure whether this costs liveness in GCBF+'s known deadlock settings.
Baselines
The naive reference is a decentralized handcrafted pairwise-distance CBF in the same QP filter. It is monotone by construction but ignores velocity and actuation limits. Neural Graph Control Barrier Functions and GCBF+ report that handcrafted variants underperform: GCBF+ beats the best handcrafted CBF by up to 20% at up to 256 agents. We rerun it on our scenes rather than relying on that figure.
The strongest competitor is GCBF+ itself with its attention aggregator. Its reported numbers are over 98% success scaling from 8 to 1024 agents, and 95% success with up to 128 obstacles versus 20% for GCBFv0 (GCBF+). We retrain it with the authors' recipe on identical dynamics, with the same training agent count, number of gradient steps and hyperparameter search budget as our model.
We also include three aggregator controls under the same pipeline:
- an unnormalized sum without cutoff, which isolates boundedness;
- a PNA-style multi-aggregator with log-degree scalers (Principal Neighbourhood Aggregation);
- a dense-augmented GCBF+, trained with phantom neighbors injected to cover the packing-bound degree range.
The key ablations remove one ingredient at a time. One drops the nonnegativity constraint on $\phi_\theta$, testing monotonicity. The other drops the cutoff $c$, testing locality.
Beating GCBF+ means two things. First, statistically higher success and a lower CBF-condition violation rate in the high-density bins at matched training cost. Second, no loss of more than one point of success on the reported standard-density scenes. Parity at standard density combined with a clear win under crowding is the expected and sufficient outcome.
Why not just…?
Why not just train GCBF+ on denser scenes? This is the real threat. Since packing caps degree, augmentation could in principle cover the whole range. The dense-augmented baseline tests exactly this. Even if it matches our success rates, it offers no guarantee for configurations absent from training, and attention retains the dilution direction. The dilution probe below and binned verification would show whether augmentation removes the failure or merely hides it at the sampled densities. If augmentation matches us on every probe, we will report the contribution as the verification result alone.
Why not just use PNA's multi-aggregators? PNA's scalers normalize by the training-set average degree, and its mean and standard-deviation channels are not monotone. On the multitask algorithmic benchmark it reached an average log-MSE of -3.13 (Principal Neighbourhood Aggregation), but that measures general graph reasoning, not conservative safety under crowding. It runs as a direct baseline here.
Why not just use a hard max or min over neighbors? A min over pairwise terms is monotone and does not dilute, but it is non-differentiable where the closest neighbor switches. That breaks the gradient the quadratic program needs. We include a hard-min variant to measure how much chattering or QP infeasibility this causes in practice. If it causes none, the smoothness argument weakens, and we will say so.
Proposed Experiments
All experiments use the GCBF+ SimpleCar, DubinsCar and Drone environments. Training uses 8 agents. Tests cover 8 to 1024 agents and 0 to 128 obstacles. Hardware validation uses the eight-Crazyflie setup if access permits.
Dilution probe (the decisive check). We fix one neighbor in the collision-imminent region, then inject $k = 1$ to $K(\rho)$ benign neighbors and obstacle points. We record the change in $h_i$, the QP-filtered action, and whether the filter still brakes. The hypothesis fails if GCBF+'s attention certificate shows no upward drift.
Density stress. We hold swarm size fixed while shrinking the arena, which raises per-agent neighbor counts past the training maximum. We report success rate, collision rate and deadlock rate.
Binned verification. We report the CBF-condition violation rate over sampled and adversarially searched states, binned by neighbor count up to the packing bound.
Liveness under bottlenecks. We use corridors and dense obstacle fields to quantify what pairwise decomposability costs.
Each result is reported over at least five seeds with confidence intervals. Positive results on the dilution probe and density stress, without regression at standard density, would establish that the choice of combination rule, not only training data, decides whether learned swarm certificates are trustworthy at scale.
References
- Neural Graph Control Barrier Functions Guided Distributed Collision-avoidance Multi-agent Control
- GCBF+: A Neural Graph Control Barrier Function Framework for Distributed Safe Multiagent Control
- Almost Surely Asymptotically Constant Graph Neural Networks
- Some Might Say All You Need Is Sum
- Principal Neighbourhood Aggregation for Graph Nets
- Unifying Approach to Uniform Expressivity of Graph Neural Networks
- Is uniform expressivity too restrictive? Towards efficient expressivity of GNNs