Protecting What Makes Each Agent Different in Multi-Agent Set Encoders

Many multi-agent learning systems describe a scene as an unordered set of entities, such as allies, enemies and obstacles. They process that set with a graph or attention network, so that relabeling the agents does not change the answer. Two kinds of output come from the same entity embeddings. Some outputs should ignore which entity is which: a team value, or the value of moving. Others must track individual entities: the value of attacking enemy number 3, or a predicted trajectory for agent 7. The graph literature calls the loss of differences between entities "over-smoothing," meaning node embeddings drift toward a common average. It usually treats this as a problem of very deep networks.

Our observation is that in multi-agent set encoders the problem appears at shallow depth. Attention over everything a unit can see is a soft complete graph, and averaging over a complete graph is the most extreme smoothing filter possible. The training signal from the order-ignoring outputs actively rewards that averaging. We propose to measure how much entity-specific information survives in these encoders. We then add a layer that splits every embedding into its set average and its deviation from that average. The deviation is protected from collapse and is routed only to the per-entity decisions. The aim is to show that losing per-entity distinctiveness, rather than depth, explains part of the failure of current methods on large, randomized battles.

Core Claim

On a complete graph with $N$ nodes, the order-respecting linear maps are exactly $\lambda I + \gamma \frac{1}{N}\mathbf{1}\mathbf{1}^\top$. Here $I$ keeps each node's own features, $\frac{1}{N}\mathbf{1}\mathbf{1}^\top$ replaces every node by the set average, and $\lambda, \gamma$ are learned scalars. Read in graph-filtering terms, this is a two-channel filter bank. The average is the low-pass channel, and $I - \frac{1}{N}\mathbf{1}\mathbf{1}^\top$, the deviation from the average, is the high-pass channel.

This connection tells us the obvious import from the over-smoothing literature is already partly present in multi-agent work. Adding the high-pass "diversification" channel of Complete the Missing Half to a complete-graph encoder recovers the mean-plus-self structure that CommNet already uses for communication. Bolting that channel onto PIC would therefore add little.

What the existing architectures do not do is control the size of the deviation channel across layers and training. Nothing stops gradient descent from shrinking it whenever the order-ignoring outputs dominate the loss. Attention does not stop it either: Demystifying Oversmoothing in Attention-Based Graph Neural Networks proves that softmax attention cannot disconnect a graph and still collapses embeddings at an exponential rate.

Our claim has two parts. First, in encoders like HGAP, which scores attack actions by a dot product between an agent's hidden state and each enemy's embedding, the size and rank of the deviation component shrink as team size grows. That shrinkage predicts poor target selection. Second, a layer that keeps the average and the deviation as separate streams with separately controlled scale recovers that performance while keeping exact invariance for the order-ignoring outputs and exact equivariance for the per-entity outputs.

This also takes a position in a live disagreement. Setting the Record Straight on Transformer Oversmoothing shows that smoothing is controllable and can help: forced smoothing beat sharpening on CIFAR100, +2.62% versus +1.81%. We agree that smoothing helps, but only for the order-ignoring outputs. Multi-agent control needs both behaviors from one encoder, and the proposal is to stop them from competing.

Research Program

Diagnosis. We first run a measurement study with no new architecture. We take trained HGAP and PIC agents and, at each layer, extract the entity embedding matrix $H \in \mathbb{R}^{N\times d}$, one row per entity. We compute the centered effective rank, $\mathrm{Erank}(H - \mathbf{1}\bar h^\top)$, where $\bar h$ is the mean row. Effective rank is the exponential of the entropy of the normalized singular values. Are we measuring oversmoothing in graph neural networks correctly? found it tracks accuracy far better than Dirichlet energy, with an average Pearson correlation of 0.91. We also track the deviation energy, $\|H - \mathbf{1}\bar h^\top\|_F^2 / \|H\|_F^2$.

The same paper warns that high rank does not imply useful features, since random noise has full rank. We therefore pair rank with linear probes from the centered embeddings to per-entity ground truth: health, distance, and unit type. We relate both quantities to behavioral measures of per-entity decisions. These are the entropy of attack-target choices across agents, how often agents concentrate fire on one enemy, and the win rate.

Intervention. Each message-passing or attention layer is followed by a split. The mean $\bar h$ passes through unchanged into an invariant stream. The deviations are rescaled so their total squared distance stays at a learned constant. This is PairNorm's rule (PairNorm), but applied only to the high-pass part rather than to the whole embedding, so the average is never distorted. Separate learnable gains, in the style of $\alpha_L, \alpha_H$ from the filter-bank work, recombine the two streams for the next layer.

At the output, order-ignoring heads (move values, the critic, the mixing network) read the pooled invariant stream. Per-entity heads (attack scores) read the protected deviation stream concatenated with the mean. Both properties hold exactly, by construction.

Depth. Only after the shallow question is settled do we vary depth from 1 to 8 layers. The point is to test whether protection lets deeper encoders help in partially observed maps, where information must pass through several entities.

Baselines

The naive reference point is a multilayer network over concatenated entity features, with entity order shuffled during training. PIC already reports that this loses to an invariant architecture as $N$ grows. We include it to anchor scales, not as a serious competitor.

The strongest existing method is HGAP: GATv2 attention plus hypernetworks, with exact invariance and equivariance. For HGAP on SMACv2 the file gives no number; it reports only that HGAP keeps a "significant performance lead," so there is no reported win rate for HGAP on SMACv2 on Lacuna. On original SMAC super-hard maps HGAP "often achieved a 100% win rate while baselines struggled to reach 80%." SMACv2 reports that top algorithms on 20-vs-23 maps "often fall below 25%." That regime is our main target.

On the Multi-Agent Particle Environment (MPE) the reference is PIC. It reports test reward improvements of 15% to 50% over MADDPG and scales to 200 agents in cooperative navigation.

We run HGAP from its released configuration and implement our layer as a drop-in replacement for its attention blocks. Seeds, environment steps, and hyperparameter search budgets are identical. Any search over our two new gains is matched by an equal-size search over HGAP's learning rate and layer count.

Three further baselines isolate the ingredients:

  • Whole-embedding PairNorm. This checks whether protecting the deviation stream specifically matters, as opposed to normalizing everything.
  • Split without rescaling. The two streams are separated but the deviations are not rescaled, which is essentially a CommNet-style mean-plus-self layer with routed heads. This checks whether controlling scale is the active ingredient.
  • Rescaling without routing. Every head reads the recombined embedding. This checks whether separating the outputs matters.

Beating HGAP means a win-rate gain on 20v20 and 20v23 SMACv2 maps that exceeds seed variance over at least five seeds. That gain must come with a measurably higher centered effective rank and probe accuracy in the attack-scoring embeddings, and must not cost anything on 5v5 maps.

Why not just…?

Why not just keep the encoder shallow? Shallow depth does not avoid the problem we target. On a complete graph, one averaging step already maps every entity to the same vector apart from its self term. If the diagnostic shows centered rank collapsing in two-layer HGAP encoders as $N$ grows, shallowness is no remedy. If it shows no collapse at shallow depth, this objection wins. In that case we would narrow the paper to the depth regime and report the shallow result as a negative finding.

Why not just add residual connections and LayerNorm? Residual connections do preserve the self term, and this is the most serious threat. PairNorm reports that it adds gains on top of residual connections, but only on citation graphs. Dovonon et al. show that LayerNorm weight signs in pre-LN Transformers can silently flip sharpening into smoothing, so residual connections alone do not guarantee the deviation survives training. Our split-without-rescaling and rescaling-without-routing baselines both include residual connections and pre-LN. If either matches the full layer, we will report that the simpler fix suffices.

Why not just give the order-ignoring and per-entity heads separate encoders? Fully separate encoders would remove the competition we describe, at roughly twice the parameters. We run this as a parameter-matched baseline. If it matches our layer, the contribution reduces to "do not share encoders." That would still be a useful, rank-diagnosed finding, but a smaller one, and we would frame it that way.

Why not just trust attention to ignore irrelevant entities? Wu et al. prove that softmax attention keeps every edge alive and collapses embeddings exponentially, only more slowly than graph convolution. The unmodified HGAP baseline tests this empirically in our setting.

Proposed Experiments

The main testbed is SMACv2 in all three races at 5v5, 10v10, 20v20, and 20v23. Its procedurally generated team compositions and start positions rule out the open-loop memorization that inflates original SMAC results. Open-loop policies fall from near 100% on 8m_vs_9m to 0% on SMACv2. The second testbed is the vectorized MPE, with predator-prey and cooperative navigation at $N$ from 10 to 200, using PIC's critic with our layer substituted.

First decisive check: correlation. Across team sizes and seeds, centered effective rank and probe accuracy in the attack-scoring embeddings must correlate with win rate. Uncentered rank and Dirichlet energy should correlate less well, since they are dominated by the mean component.

Second decisive check: causation. Clamping the deviation scale to a small value in a trained protected model should reproduce HGAP's failure pattern: concentrated, undifferentiated target choices and lower win rate on 20-player maps. Restoring the scale should recover performance.

Third decisive check: the smoothing dichotomy. In MPE, the invariant critic's value error should improve, or at least not worsen, when its stream is deliberately smoothed. Per-entity outputs on the same encoder should degrade under the same smoothing. That pattern would confirm the dichotomy suggested by Dovonon et al.

Failure of the first check would mean that losing per-entity distinctiveness is not what limits these systems at shallow depth, and the proposal would stop at the diagnostic.