Learned safety certificates for robot swarms are trained on a handful of agents and then deployed on hundreds or thousands. The certificate is a neural network that scores each robot's situation as safe or unsafe and vetoes dangerous commands. It reads the robot's neighbors through a graph neural network, a model that summarizes each robot's surroundings by passing and averaging messages along the "who is near whom" graph. When the swarm gets dense, each robot's summary has to absorb many more neighbors than it ever saw in training. This proposal tests a specific worry: in that regime the summary blurs, and the one neighbor that is about to hit you becomes hard to tell apart from the dozens that are not. The certificate then reports "safe" while losing sensitivity to the threat. This is a density-driven cousin of over-smoothing. Over-smoothing is the well-documented tendency of graph networks to make all node representations look alike, and it is usually blamed on stacking too many layers.
The claim has two parts, and each can be tested and can fail. First, the residual safety violations that appear when learned graph certificates scale zero-shot to dense swarms are preceded by a measurable collapse in the diversity of the messages each agent receives. That collapse is best captured by a rank measure rather than an energy measure. Second, each robot can compute this rank locally from messages it already receives. It can then act as a runtime trust signal that hands control to a conservative fallback controller only when the learned certificate has stopped discriminating. The goal is a cheap, decentralized "do not trust me now" signal. A new barrier architecture is not the goal. That is deliberate, because simple architectural fixes such as truncating to the nearest few neighbors may cure the symptom just as well. The proposal is designed so that this possibility is measured rather than argued away.
Background and Gap
Three systems define the current practice, and each plays a different role here. GCBF+ uses a graph network to parameterize both a distributed control barrier function and a policy. A control barrier function is a scalar score whose sign marks the safe set and whose rate of change is constrained so that the system cannot leave that set. GCBF+ trains on 8 agents and reports over 98% success at 256 agents and 128 obstacles. It is the system whose failures we want to explain. HJB-GNN adds an infinite-horizon value function to resolve the deadlocks that myopic barriers cause. It reports a safety rate above 90% with 320 agents in dense 3D simulation, against baselines below 60%. That leaves roughly a tenth of episodes unsafe, and the paper never inspects the representations to see why. MDBC avoids message passing entirely and max-pools over one-hop neighbors. It reports a safety rate near 99% on a 32-agent 3D maze and admits non-zero violations under distribution shift. All three motivate the gap: they evaluate only success and safety rates and never ask what happens inside the neighbor summary as density grows. MDBC also constrains the design, because max-pooling is exactly the kind of aggregator that should resist dilution, so it must appear as a competitor.
The over-smoothing literature supplies the measurement method. Are we measuring oversmoothing in graph neural networks correctly? shows that Dirichlet energy, the classic smoothness score, stays deceptively flat in trained networks even while accuracy collapses. It argues that the real symptom is rank collapse of the feature matrix. Effective rank, an entropy over normalized singular values, tracks node-classification accuracy with an average Pearson correlation of 0.91 in that paper. The same paper is also a warning for this proposal. High rank is necessary but not sufficient, since white noise has maximal rank and no use. A rank signal therefore has to be paired with a task-grounded sensitivity measure. Architectural remedies supply candidate fixes. Filterbank networks add a high-pass channel that keeps "the missing half" of the signal (Complete the Missing Half). PairNorm keeps pairwise embedding distances from shrinking. Both target depth-driven collapse on static graphs. Neither has been tested on the case studied here: one or two layers over a proximity graph whose degree shifts sharply between training and deployment.
No work in the file measures rank or sensitivity inside safety certificates. None uses such a measure as a runtime switch. The closest runtime-switching work is the distributed simplex architecture, which swaps between an unverified controller and a certified fallback using hand-designed triggers. We reuse its switching structure and replace the trigger.
Core Claim and Mechanism
For agent $i$ with $d_i$ neighbors, let $M_i \in \mathbb{R}^{d_i \times k}$ stack the $k$-dimensional messages it receives in the barrier network's first layer. Define its normalized local effective rank as
$$\rho_i = \frac{\exp\left(-\sum_j p_j \ln p_j\right)}{\min(d_i, k)}, \qquad p_j = \frac{\sigma_j(M_i)}{\sum_l \sigma_l(M_i)},$$
where $\sigma_j(M_i)$ are the singular values of $M_i$. The normalization matters because raw effective rank grows mechanically with neighbor count. Dividing by the maximum achievable rank makes $\rho_i$ measure how distinct the messages are, not how many there are. Each agent can compute this from information it already holds.
The paired task-grounded quantity is nearest-threat sensitivity, $s_i = \lVert \partial h_i / \partial r_{i,j^*} \rVert$. Here $h_i$ is agent $i$'s barrier value and $r_{i,j^*}$ is the relative position of its closest neighbor or obstacle point. The mechanistic hypothesis has three steps. As $d_i$ rises past the training range, $\rho_i$ falls. Then $s_i$ falls with it. Then states with $h_i \ge 0$ that nonetheless lead to collision within a short horizon become more frequent. With plain mean aggregation, the nearest neighbor's share of the summary shrinks roughly as $1/d_i$, which is where the expected decay comes from. Attention aggregation can in principle escape this. Whether the attention used in GCBF+ actually does so at 10–50× training density is an empirical question, and it is the first thing we measure.
Research Program
The first stage is diagnosis. We retrain GCBF+ and HJB-GNN on their published 8-agent settings and roll them out across the published scaling ladder of 16 to 1,024 agents, with obstacle counts up to 128. For every agent at every step we log $d_i$, $\rho_i$, Dirichlet energy over the local neighborhood, $s_i$, $h_i$, and the residual of the barrier's decrease condition. We then label each agent-step by whether a collision follows within $H$ steps. We also intervene to test causation rather than mere correlation. Holding the geometry of the closest threat fixed, we add distant, non-threatening neighbors inside the sensing radius. If $s_i$ and the false-safe rate degrade while the danger itself is unchanged, dilution is causal. We repeat the diagnosis on a deeper three-to-five-layer variant. This tests the depth-versus-foresight tension directly, asking whether deeper message passing buys foresight before it buys collapse.
The second stage is the monitor. Each agent switches from the learned policy to a decentralized hand-crafted quadratic-program barrier filter whenever $\rho_i$ falls below a threshold calibrated on training-density rollouts. A conformal-style quantile works for calibration and requires no test-density data. The fallback is conservative, and conservatism costs liveness, so the monitor is valuable only if it fires rarely and fires at the right moments.
The third stage is the remedy comparison. Here we ask whether the collapse can be prevented instead of detected. Candidate fixes are nearest-$k$ truncation, max pooling, a filterbank-style residual channel that passes the closest-threat message around the aggregator, and training at elevated density. The candidates are ordered by simplicity, and we adopt the simplest one that closes the gap.
Baselines
The do-nothing reference is GCBF+ exactly as published, with no monitor and no architectural change, trained on 8 agents and 8 obstacles. The number to beat in its regime is the reported success rate of over 98% at 256 agents and 128 obstacles from GCBF+. In the dense 3D regime the reference is HJB-GNN, whose reported safety rate is above 90% with 320 agents. It is the strongest existing method on this question because it already addresses the main known failure, deadlock, and still leaves residual unsafety at density. Both are retrained from the authors' settings with three or more seeds, and every variant gets the same training data, training compute, and hyperparameter budget.
For the monitor, the strongest naive competitor is a degree-only trigger, which falls back whenever $d_i$ exceeds the training maximum. It costs nothing and directly captures "out of distribution in density". Further competitors are triggers based on Dirichlet energy, on the barrier value $h_i$ alone, and on the barrier condition residual, plus an always-on fallback that sets the floor on liveness. Every trigger is calibrated on the same training-density rollouts with the same false-alarm budget. Beating these means two things. The monitor must achieve a higher area under the ROC curve for predicting collisions within $H$ steps than degree alone. In closed loop, it must deliver a higher safety rate than the do-nothing reference at 320 and 1,024 agents, with a fallback activation fraction and deadlock frequency clearly below the always-on fallback.
For remedies, MDBC-style max pooling (MDBC) is the strongest "just aggregate differently" competitor. Nearest-$k$ truncation is the simplest. The key ablation isolates the rank signal itself. We replace $\rho_i$ with unnormalized effective rank, and then with $d_i$. If either performs as well, the normalization or the rank adds nothing.
Why not just…?
Why not just use neighbor count as the trust signal? This is the most serious threat. If degree predicts violations as well as $\rho_i$ does, the rank machinery is unnecessary. The bet is that degree is a poor proxy in both directions. Many neighbors arranged in a geometrically diverse ring are fine, while a few nearly collinear neighbors in a corridor can already collapse the summary. The added-distant-neighbors intervention and the degree-only trigger comparison settle this directly. If degree wins, we report that as the finding, and it would still be the first clear diagnosis of why these certificates fail at scale.
Why not just truncate to the nearest few neighbors? Truncation bounds degree by construction and may remove dilution entirely. It could also cut off the multi-hop congestion information that Resolving Deadlocks in Constrained Multi-Agent Navigation and HJB-GNN show is needed to avoid freezing. Its cost should therefore appear as more deadlocks, not more collisions. The remedy stage measures both. If truncation matches on safety without raising deadlocks, it becomes the recommended fix, and the monitor remains useful only for certificates that cannot be truncated.
Why not just train at deployment density? Training at high density probably helps, but it defeats the main appeal of these methods, which is that they are trained small and deployed large. It also pushes the collapse to a higher density instead of removing it. We include a 64-agent-trained model and check whether the $\rho_i$–violation relationship persists one order of magnitude above its own training density.
Why not just use HJB-GNN's long-horizon value function? HJB-GNN fixes deadlocks, not dilution, and it shares the same aggregation step. If its residual unsafety at 320 agents also shows low $\rho_i$, the monitor applies to it unchanged. That makes HJB-GNN a host for this work rather than an alternative to it.
Proposed Experiments and Decisive Checks
The benchmarks are the GCBF+ and HJB-GNN navigation suites. They cover 2D and 3D obstacle fields, antipodal swaps, and the X-shaped bottleneck, with agent counts of 16, 32, 64, 128, 256, 320, and 1,024. We add MDBC's 3D maze at 32 agents for comparison with its reported near-99% safety rate. The metrics are success rate, safety rate, deadlock frequency, per-step inference time, collision-prediction area under the ROC curve, false-safe rate, and fallback activation fraction. The rank-based monitor has no reported result on Lacuna in any safety setting, so its numbers will be new. Hardware is out of scope until the simulation checks pass.
Three outcomes are decisive. The first is the causal check: adding distant neighbors, with the closest threat held fixed, should lower both $\rho_i$ and $s_i$ and raise the false-safe rate. If none of these move, the dilution hypothesis is false and the project stops there. The second is the predictive check: $\rho_i$ must beat degree and Dirichlet energy at predicting short-horizon collisions at test densities above 64 agents. The third is the closed-loop check: the monitored system must exceed the do-nothing safety rate at 320 and 1,024 agents while activating its fallback in a small minority of agent-steps and without raising deadlock frequency above the unmonitored policy. If all three hold, learned swarm certificates gain a decentralized way to know when they have stopped listening. If only the first holds, the simplest remedy that closes the gap becomes the contribution.
References
- GCBF+: A Neural Graph Control Barrier Function Framework for Distributed Safe Multiagent Control
- Learning Distributed Safe Multi-Agent Navigation via Infinite-Horizon Optimal Graph Control
- Learning Safe Multi-agent Control with Decentralized Neural Barrier Certificates
- Are we measuring oversmoothing in graph neural networks correctly?
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- PairNorm: Tackling Oversmoothing in GNNs
- A Distributed Simplex Architecture for Multi-agent Systems
- Efficient multi-agent global navigation using interpolating bridges