Designing a Good Virtual Node: Addressable and Cardinality-Preserving Global Memory for Message Passing Architectures

# Addressable and Cardinality-Preserving Global Memory for Message Passing Architectures
Source: [https://arxiv.org/html/2608.02709](https://arxiv.org/html/2608.02709)
## Designing a Good Virtual Node: Addressable and Cardinality\-Preserving Global Memory for Message Passing Architectures

###### Abstract

Virtual nodes give message\-passing neural networks a simple global communication route, but the standard node–VN–node pipeline compresses the graph into one homogeneous state and broadcasts it identically to every node\. Building on the Two\-Radius analysis of Mishayev et al\.\[[15](https://arxiv.org/html/2608.02709#bib.bib8)\], we ask how auxiliary virtual memory can relieve this finite\-capacity bottleneck without self\-attention\. We identify two requirements\. First, the global memory should be factorized into independently writable and readable states: this can be achieved using addressable cross\-attention slots\. Second, addressability alone does not preserve multiplicity, because softmax attention is invariant to uniform replication\. Inserting each slot query as a private key/value anchor recovers the discarded normalization mass and yields, on bounded color domains, an injective multiset representation able to implement a 1\-WL refinement\. Experiments on multiplicity\-aware Two\-Radius, motif counting, and constrained link\-set prediction support this addressable and cardinality\-preserving virtual memory atO​\(n​M​d\)O\(nMd\)arithmetic cost\.

## 1Introduction

Message\-passing neural networks \(MPNNs\) remain a natural default for learning on graphs\. Their computation follows observed edges, scales with graph sparsity, and encodes the assumption that local relations should be processed locally\[[8](https://arxiv.org/html/2608.02709#bib.bib1)\]\. The same locality can create a communication bottleneck: many distinct signals may have to cross a small number of intermediate node representations\. This phenomenon is usually discussed as*oversquashing*\[[1](https://arxiv.org/html/2608.02709#bib.bib4),[22](https://arxiv.org/html/2608.02709#bib.bib5),[7](https://arxiv.org/html/2608.02709#bib.bib6)\]\.

Most standard examples combine a large graph radius with a rapidly expanding receptive field\. The Two\-Radius construction of Mishayev et al\.\[[15](https://arxiv.org/html/2608.02709#bib.bib8)\]separates these effects\. It hasnnsources,nntargets, and one or several central nodes\. Every source is only two hops from every target, yet each target must recover the label carried by the source with the same identifier\. The task therefore requires a global table ofnnassociations to pass through the central representation\. Accuracy deteriorates withnneven though depth, distance, and node\-to\-node Jacobian path length remain constant\. This is short\-range oversquashing: the difficulty is a finite\-capacity channel, not merely long\-distance attenuation\. The central nodes are part of the input graph, whereas a virtual node is an auxiliary state introduced by the architecture\. The two are distinct, but both act as finite\-dimensional channels across the same source–target cut\.

A conventional virtual node \(VN\)\[[8](https://arxiv.org/html/2608.02709#bib.bib1),[10](https://arxiv.org/html/2608.02709#bib.bib25)\]does not fundamentally change this setting\. It shortens graph paths and improves mixing in long\-range tasks, an effect characterized spectrally in\[[21](https://arxiv.org/html/2608.02709#bib.bib22),[9](https://arxiv.org/html/2608.02709#bib.bib24)\], but Two\-Radius already has radius two\. More importantly, the standard node–VN–node operation forms one homogeneous summary and broadcasts the same global message to every target\. Several cloned VNs also remain identical under shared initialization, connectivity, and updates\. The empirical study in\[[15](https://arxiv.org/html/2608.02709#bib.bib8)\]therefore finds only a modest improvement\.

Increasing the width of this state increases its raw information capacity, so a sufficiently wide VN is not intrinsically incapable of storing the complete table\. A fully additive broadcast, however, contributes the same global term to every target and cannot realize arbitrary target\-specific lookup\. Exploiting a wide VN therefore requires a joint non\-separable decoder that uses the target representation to partition and select its feature coordinates\. Generic nonlinear decoders can synthesize this operation in principle, but they must discover both the hidden factorization and its gating implicitly\. We instead expose the factorization as an architectural memory axis with separately routed writes and reads\.

Dense self\-attention is an effective escape route: every target can interact directly with every source\. It is nevertheless a strong architectural intervention\. It introduces quadratic all\-pairs interactions, and in hybrid graph Transformers it can partially replace rather than simply support edge\-based message passing\[[23](https://arxiv.org/html/2608.02709#bib.bib13),[18](https://arxiv.org/html/2608.02709#bib.bib18)\]\. This is not always undesirable, but it makes the answer to the bottleneck problem depend on a different global computation primitive\.

This paper considers a narrower question:

> What properties should a virtual node have in order to provide useful global communication while retaining an MPNN as the primary graph feature aggregator?

We identify two expressivity requirements and one practical integration principle\.

#### Addressability\.

A useful global memory should expose several independently queryable states rather than one homogeneous summary\. We represent these states asMMlatent virtual nodes, or*slots*\. Slots aggregate graph information by cross\-attention and are queried by graph nodes through a second cross\-attention\. The mechanism is related to induced set attention and latent arrays\[[12](https://arxiv.org/html/2608.02709#bib.bib14),[11](https://arxiv.org/html/2608.02709#bib.bib15)\]; RANGE similarly relays graph information through attention nodes with positional encodings\[[4](https://arxiv.org/html/2608.02709#bib.bib23)\]\. Our focus is the factorization itself: which capacity is gained over a homogeneous broadcast, which decoder interaction is required for target\-specific lookup, and how compact dot\-product addresses realize the write–read partition\.

#### Multiplicity preservation\.

A slot may be addressable and still discard absolute counts\. Softmax attention produces a normalized weighted mean and is unchanged when every key/value is repeated the same number of times\. This limitation is the attention analogue of the gap between mean and injective sum aggregation in WL\-style expressivity analyses\[[26](https://arxiv.org/html/2608.02709#bib.bib2),[5](https://arxiv.org/html/2608.02709#bib.bib26),[28](https://arxiv.org/html/2608.02709#bib.bib12)\]\. We introduce a counted Two\-Radius task in which labels and their multiplicities must both be recovered\.

A practical broadcast should also preserve the local representation while the global route is being learned\. We use a short identity\- or near\-identity\-initialized Slot\-FiLM update for this purpose\.

The resulting analysis provides four contributions: \(i\) an effective factorization bound and an invariant–equivariant construction with per\-slot widthO​\(\(n/M\)​log⁡n/b\)O\(\(n/M\)\\log n/b\); \(ii\) a characterization of homogeneous broadcast, implicit target\-conditioned addressing, and compact dot\-product routing, including anMM\-versus\-O​\(log⁡M\)O\(\\log M\)address\-dimension comparison; \(iii\) an anchored read that restores the normalization mass discarded by softmax and recovers cardinality\-sensitive, 1\-WL\-style aggregation; and \(iv\) controlled benchmarks for address retrieval, multiplicity recovery, motif counting, and constrained link generation\.

Figure[1](https://arxiv.org/html/2608.02709#S1.F1)separates the structural Two\-Radius bottleneck from the auxiliary virtual memory and contrasts a homogeneous VN with an addressable Cross\-Attn VN\.

\(a\) VNsourcestargets⋮\\vdots⋮\\vdotsVNcc\(b\) Cross\-Attn VNsourcestargets⋮\\vdots⋮\\vdotsz1z\_\{1\}z2z\_\{2\}⋮\\vdotszMz\_\{M\}cc

Figure 1:Structural and auxiliary communication in Two\-Radius\.\(a\)The real central nodeccremains the graph bottleneck, while a conventional VN adds one homogeneous auxiliary state broadcast to every target\.\(b\)A Cross\-Attn VN keeps the original graph path unchanged and addsMMseparately queryable slots; the highlighted route illustrates a source\-specific write followed by a target\-specific read\.

## 2Background and Design Objective

### 2\.1Message passing and the Two\-Radius task

An MPNN layer updates nodevvas

mv\(ℓ\)\\displaystyle m\_\{v\}^\{\(\\ell\)\}=⨁u∈N​\(v\)ψℓ​\(hv\(ℓ\),hu\(ℓ\),eu​v\),\\displaystyle=\\bigoplus\_\{u\\in N\(v\)\}\\psi\_\{\\ell\}\\\!\\left\(h\_\{v\}^\{\(\\ell\)\},h\_\{u\}^\{\(\\ell\)\},e\_\{uv\}\\right\),\(1\)hv\(ℓ\+1\)\\displaystyle h\_\{v\}^\{\(\\ell\+1\)\}=ϕℓ​\(hv\(ℓ\),mv\(ℓ\)\),\\displaystyle=\\phi\_\{\\ell\}\\\!\\left\(h\_\{v\}^\{\(\\ell\)\},m\_\{v\}^\{\(\\ell\)\}\\right\),\(2\)where⨁\\bigoplusis permutation invariant\. Depending on the choice of aggregation and update, this model class is at most as discriminative as 1\-WL on unlabeled graphs\[[26](https://arxiv.org/html/2608.02709#bib.bib2),[16](https://arxiv.org/html/2608.02709#bib.bib3)\]\.

In permutation\-valued Two\-Radius, the graph contains sources𝒮=\{s1,…,sn\}\\mathcal\{S\}=\\\{s\_\{1\},\\ldots,s\_\{n\}\\\}, targets𝒯=\{t1,…,tn\}\\mathcal\{T\}=\\\{t\_\{1\},\\ldots,t\_\{n\}\\\}, and a nonempty central set𝒞\\mathcal\{C\}\. Every central node is adjacent to every source and target, with no direct source–target edges\. Sourcesis\_\{i\}carries identifieriiand labelπ​\(i\)\\pi\(i\), whereπ\\piis a permutation of\[n\]\[n\]\. Targettjt\_\{j\}carries identifierjjand must output

ytj=π​\(j\)\.y\_\{t\_\{j\}\}=\\pi\(j\)\.\(3\)All useful information can arrive in two rounds, yet the intermediate state must encode one ofn\!n\!assignments\.

#### Structural bottleneck versus auxiliary memory\.

The nodes in𝒞\\mathcal\{C\}are real nodes of the Two\-Radius input graph and form its structural bottleneck\. A VN is an auxiliary state introduced by the architecture\. These objects are distinct, although both transmit finite\-dimensional summaries across the source–target cut\. A conventional VN adds another homogeneous summary; it does not replace the central nodes or factorize their information\. The proposed slots add a parallel virtual route whose states are explicitly distinguished and separately queried\. The local MPNN continues to process the original graph in every model\.

The original analysis establishes a width requirement for fixed\-precision MPNNs and shows that simply adding standard VNs does not convincingly resolve the empirical bottleneck\[[15](https://arxiv.org/html/2608.02709#bib.bib8)\]\. We retain this task because it isolates global communication without confounding it with deep propagation\.

### 2\.2Why not simply use global self\-attention?

A graph Transformer can create a direct path between each source and each target\. This changes the communication graph from sparse to complete, usesO​\(n2\)O\(n^\{2\}\)node–node attention pairs, and hasO​\(n2​d\)O\(n^\{2\}d\)arithmetic cost\. Sparse and linearized variants can reduce this cost, but they still introduce a global node\-to\-node processing path that may become the dominant computation\[[18](https://arxiv.org/html/2608.02709#bib.bib18),[20](https://arxiv.org/html/2608.02709#bib.bib28)\]\. In the uniform\-expressivity setting, moreover, self\-attention and VN\-augmented message passing are in general incomparable\[[19](https://arxiv.org/html/2608.02709#bib.bib17)\], so replacing one primitive by the other is not a strict upgrade\.

We study the complementary regime in which edge\-based message passing remains unchanged, global computation is restricted toMMlatent states, and nodes interact globally only through these states\. One local layer followed by a bidirectional node–slot block costsO​\(\|E\|​d\+n​M​d\)O\(\|E\|d\+nMd\)\.

### 2\.3Design criteria for a good VN

A single global vector can be expressive on bounded graphs when width and precision are unconstrained, and MPNN\+VN can even approximate attention under suitable non\-uniform constructions\[[3](https://arxiv.org/html/2608.02709#bib.bib16)\]\. Our concern is a practical finite\-width channel\. The relevant obstruction is the classical Deep Sets bottleneck: sum\-decomposable multiset encoders require a latent dimension that grows with the multiset size to remain injective\[[27](https://arxiv.org/html/2608.02709#bib.bib9),[24](https://arxiv.org/html/2608.02709#bib.bib10)\], and finite communication capacity bounds what constant\-width states can transmit across a graph cut\[[13](https://arxiv.org/html/2608.02709#bib.bib7)\]\. We use the following criteria\.

###### Definition 2\.1\(Addressable global memory\)\.

A collection of virtual states is addressable when different input queries can select different states, and the states are allowed to evolve differently under permutation\-equivariant computation\.

###### Definition 2\.2\(Multiplicity\-preserving read\)\.

A source\-to\-memory aggregation is multiplicity preserving on a task family when relevant changes in the multiplicities of indistinguishable inputs remain recoverable from its output\.

The first criterion controls*where*information is stored\. The second controls*what*survives aggregation\. Their combination separates routing capacity from multiset fidelity\.

## 3Addressable Virtual Nodes

### 3\.1Architecture

LetH∈ℝ\|V\|×dH\\in\\mathbb\{R\}^\{\|V\|\\times d\}denote the states of all real graph nodes, including the structural central nodes, after a local MPNN block\. The local MPNN operates only on the original graph\. LetS\(0\)∈ℝM×dS^\{\(0\)\}\\in\\mathbb\{R\}^\{M\\times d\}beMMdistinct learned slot states\. For a single attention head, the node\-to\-slot write is

QS\\displaystyle Q\_\{S\}=S\(0\)​WQ,KX=H​WK,VX=H​WV,\\displaystyle=S^\{\(0\)\}W\_\{Q\},\\qquad K\_\{X\}=HW\_\{K\},\\qquad V\_\{X\}=HW\_\{V\},\(4\)Ain\\displaystyle A^\{\\mathrm\{in\}\}=softmaxnodes⁡\(QS​KX⊤τin​d\),\\displaystyle=\\operatorname\{softmax\}\_\{\\mathrm\{nodes\}\}\\\!\\left\(\\frac\{Q\_\{S\}K\_\{X\}^\{\\top\}\}\{\\tau\_\{\\mathrm\{in\}\}\\sqrt\{d\}\}\\right\),\(5\)Z\\displaystyle Z=S\(0\)\+\(Ain​VX\)​WO\.\\displaystyle=S^\{\(0\)\}\+\\left\(A^\{\\mathrm\{in\}\}V\_\{X\}\\right\)W\_\{O\}\.\(6\)The last line is the standard cross\-attention residual: it retains the learned slot identity while adding data\-dependent graph content\. It does not keep address and content in formally disjoint subspaces\.

In the controlled Two\-Radius experiments, the write attends only to source states, soHHis replaced byH𝒮H\_\{\\cal S\}inKXK\_\{X\}andVXV\_\{X\}\. Targets and structural central nodes are excluded from this attention set to isolate the source–memory–target channel\. In the multiplicity experiment, this also prevents fixed, non\-replicated nodes from acting as implicit anchors inside the softmax normalization\.

Targets then query the updated slots:

QT\\displaystyle Q\_\{T\}=HT​UQ,KZ=Z​UK,VZ=Z​UV,\\displaystyle=H\_\{T\}U\_\{Q\},\\qquad K\_\{Z\}=ZU\_\{K\},\\qquad V\_\{Z\}=ZU\_\{V\},\(7\)Aout\\displaystyle A^\{\\mathrm\{out\}\}=softmaxslots⁡\(QT​KZ⊤τout​d\),\\displaystyle=\\operatorname\{softmax\}\_\{\\mathrm\{slots\}\}\\\!\\left\(\\frac\{Q\_\{T\}K\_\{Z\}^\{\\top\}\}\{\\tau\_\{\\mathrm\{out\}\}\\sqrt\{d\}\}\\right\),\(8\)OT\\displaystyle O\_\{T\}=Aout​VZ\.\\displaystyle=A^\{\\mathrm\{out\}\}V\_\{Z\}\.\(9\)The block is permutation invariant in source order and equivariant in target order\. This follows from the usual cancellation between a column permutation of the attention weights and the same row permutation of the values\.

At this stage, the residualS\(0\)S^\{\(0\)\}lies outside the attention normalization\. The block is therefore addressable but remains invariant to uniform replication of its source keys and values\. Section[4](https://arxiv.org/html/2608.02709#S4)adds a private slot\-derived key/value*inside*the attention set to recover the missing normalization mass\.

The architecture is close to induced set attention\[[12](https://arxiv.org/html/2608.02709#bib.bib14)\]and latent\-array attention\[[11](https://arxiv.org/html/2608.02709#bib.bib15)\]\. The distinction emphasized here is semantic: the latent states are treated as virtual graph nodes whose purpose is to supplement the MPNN’s global communication\. There is no real\-node self\-attention\.

### 3\.2Capacity and effective factorization

A width\-DDbottleneck providesD​bDbbits of raw finite\-precision storage, but this capacity is not automatically exposed asDDindependently usable memory locations\. In a fully additive broadcast, meaning a separable prediction of the form

y^j=f​\(hj\)\+g​\(z\),\\widehat\{y\}\_\{j\}=f\(h\_\{j\}\)\+g\(z\),the same global contribution is delivered to every target, so arbitrary target\-specific retrieval cannot be realized\. This statement does not cover a message that is merely added before a joint nonlinear map: nonlinear decoders can in principle create a non\-separable interaction betweenhjh\_\{j\}andzz\. When they succeed, however, the encoder must separate contents across feature subspaces and the decoder must learn which subspace to select from the target representation\. The factorization and its gating are then implicit in the feature coordinates, without an architectural mechanism that directly supports them\. We call this organization a factorization of the bottleneck\. A conventional broadcast leaves it implicit, whereas addressable slots expose it directly as a memory axis with separately routed writes and reads\.

The relevant quantity is therefore not the number of physical virtual nodes, but the number of states that can carry different contents and be used separately by the target decoder\.

###### Definition 3\.1\(Effective factorization degree\)\.

A source–target transcript has effective factorization degreeLeffL\_\{\\mathrm\{eff\}\}if all source\-dependent information available to the targets is represented by

T​\(X𝒮\)=\(u1,…,uLeff\)∈𝒜Leff×d,\|𝒜\|≤2b,T\(X\_\{\\cal S\}\)=\(u\_\{1\},\\ldots,u\_\{L\_\{\\mathrm\{eff\}\}\}\)\\in\\mathcal\{A\}^\{L\_\{\\mathrm\{eff\}\}\\times d\},\\qquad\|\\mathcal\{A\}\|\\leq 2^\{b\},where theuℓu\_\{\\ell\}may vary independently on the task family and are separately usable by the decoder\. Physical copies constrained to be identical count as one effective state\.

The fixed structural path of Two\-Radius contributes only a constant number of such states\. A conventional VN adds one homogeneous state\. Likewise,MMcloned VNs with identical initialization, neighborhoods, and shared updates remain equal and do not produce anMM\-fold factorization\. Addressable slots are designed precisely to make theMMauxiliary states distinguishable, separately writable, and separately readable\.

###### Theorem 3\.3\(Effective finite\-capacity requirement\)\.

Any deterministic architecture whose complete source\-dependent transcript has effective factorization degreeLeffL\_\{\\mathrm\{eff\}\}, widthdd, andbb\-bit coordinates, and that solves all permutation\-valued Two\-Radius instances exactly, satisfies

Leff​d​b≥log2⁡\(n\!\)\.L\_\{\\mathrm\{eff\}\}db\\geq\\log\_\{2\}\(n\!\)\.\(10\)Consequently,

d=Ω​\(n​log⁡nLeff​b\)\.d=\\Omega\\\!\\left\(\\frac\{n\\log n\}\{L\_\{\\mathrm\{eff\}\}b\}\\right\)\.

The proof is the usual injectivity argument: different permutations require different complete transcripts\. In the baseline architectureLeff=O​\(1\)L\_\{\\mathrm\{eff\}\}=O\(1\), so the required width remainsΩ​\(n​log⁡n/b\)\\Omega\(n\\log n/b\)\. The construction below realizesMMseparately usable auxiliary states, soLeff=M\+O​\(1\)L\_\{\\mathrm\{eff\}\}=M\+O\(1\)after including the fixed structural route\. This reduces the required width of each state by a factorMM, up to that constant structural contribution, while leaving the total information requirement unchanged\.

A single VN of widthD=M​dD=Mdhas the same raw finite\-state capacity asMMslots of widthdd\. The distinction is therefore not additional bits at fixed total width, but whether the required factorization is hidden in feature coordinates or exposed as a memory axis\.

###### Theorem 3\.5\(Constructive addressable upper bound\)\.

LetM≤nM\\leq nand assume each coordinate stores at mostbbbits\. There exists a permutation\-invariant encoder withMMaddressable slots and a permutation\-equivariant target decoder that solves permutation\-valued Two\-Radius using

d≤⌈nM⌉​⌈log2⁡nb⌉\+⌈log2⁡Mb⌉\+O​\(1\)d\\leq\\left\\lceil\\frac\{n\}\{M\}\\right\\rceil\\left\\lceil\\frac\{\\log\_\{2\}n\}\{b\}\\right\\rceil\+\\left\\lceil\\frac\{\\log\_\{2\}M\}\{b\}\\right\\rceil\+O\(1\)\(11\)coordinates per slot\.

#### Construction\.

Partition the public identifier set into balanced groupsI1,…,IMI\_\{1\},\\ldots,I\_\{M\}\. Letg​\(i\)g\(i\)denote the group of identifieriiandr​\(i\)r\(i\)its position inside that group\. Slotmmstores a fixed address code and one label\-code block for each identifier inImI\_\{m\}\. Sourceiiwrites the code ofπ​\(i\)\\pi\(i\)into blockr​\(i\)r\(i\)of slotg​\(i\)g\(i\); targetjjqueries slotg​\(j\)g\(j\)and reads blockr​\(j\)r\(j\)\. The write is invariant to source order because destinations depend only on identifiers, and the read is equivariant because all targets apply the same identifier\-conditioned decoder\. A full proof appears in Appendix[A](https://arxiv.org/html/2608.02709#A1)\.

The construction usesM​d=O​\(n​log⁡n/b\)Md=O\(n\\log n/b\)total auxiliary width\. A wide VN of that total width could represent the same table, but its decoder would have to discover an equivalent decomposition of the coordinates and a target\-specific selection rule\.

### 3\.3From homogeneous broadcast to explicit addressing

A standard VN sends the same global statezzto every target\. This alone does not prohibit lookup, but the decoder must make the global contribution depend on the target representation\.

###### Proposition 3\.6\(Limitation of separable broadcast\)\.

Let the exact target output be represented by a label vector and suppose

y^j=f​\(hj\)\+g​\(z\),\\widehat\{y\}\_\{j\}=f\(h\_\{j\}\)\+g\(z\),\(12\)wherezzis broadcast identically, the target stateshjh\_\{j\}depend only on their fixed identifiers, and no other path carries source information to the targets\. Forn≥2n\\geq 2, this decoder cannot realize every permutation\-valued Two\-Radius instance\.

###### Proof\.

Choose two permutations that differ by exchanging the labels of targetsppandqq\. The changeg​\(zπ\)−g​\(zπ′\)g\(z\_\{\\pi\}\)\-g\(z\_\{\\pi^\{\\prime\}\}\)is identical for every target, whereas the required changes atppandqqare opposite nonzero label\-vector differences\. ∎

A general decoderF​\(hj,z\)F\(h\_\{j\},z\)can escape Proposition[3\.6](https://arxiv.org/html/2608.02709#S3.Thmtheorem6)\. For example, a bilinear map, FiLM, or a sufficiently expressive MLP can usehjh\_\{j\}to select an identifier\-specific subspace of a wide VN\. EvenMLP⁡\(Wh​hj\+Wz​z\)\\operatorname\{MLP\}\(W\_\{h\}h\_\{j\}\+W\_\{z\}z\)is not generally separable after the joint nonlinearity\. Such a successful solution is best understood as*implicit addressing*: the memory partition and selection operation are synthesized inside the feature coordinates and decoder rather than supplied by the VN broadcast\.

A literal implementation storesMMpayload blocks in one vector and uses a one\-hot gate to select one block\. Exact linear generation of that gate has a large address interface\.

###### Proposition 3\.7\(Linear one\-hot addressing\)\.

Leta1,…,aM∈ℝpa\_\{1\},\\ldots,a\_\{M\}\\in\\mathbb\{R\}^\{p\}be target addresses\. If a linear mapW∈ℝM×pW\\in\\mathbb\{R\}^\{M\\times p\}satisfiesW​am=emWa\_\{m\}=e\_\{m\}for everymm, then

###### Proof\.

WritingA=\[a1,…,aM\]A=\[a\_\{1\},\\ldots,a\_\{M\}\]givesW​A=IMWA=I\_\{M\}, henceM=rank⁡\(IM\)≤rank⁡\(A\)≤pM=\\operatorname\{rank\}\(I\_\{M\}\)\\leq\\operatorname\{rank\}\(A\)\\leq p\. ∎

Dot\-product addressing does not require this one\-hot representation\. It compares a compact query against the keys of all slots and normalizes the resulting similarities\.

###### Proposition 3\.8\(Soft partition routing\)\.

Letg:\[n\]→\[M\]g:\[n\]\\rightarrow\[M\]define groupsIm=\{i:g​\(i\)=m\}I\_\{m\}=\\\{i:g\(i\)=m\\\}\. Suppose unit address vectorsa1,…,aM∈ℝpa\_\{1\},\\ldots,a\_\{M\}\\in\\mathbb\{R\}^\{p\}satisfy

am⊤​am′≤1−Δfor​m≠m′,Δ\>0\.a\_\{m\}^\{\\top\}a\_\{m^\{\\prime\}\}\\leq 1\-\\Delta\\quad\\text\{for \}m\\neq m^\{\\prime\},\\qquad\\Delta\>0\.Assign keyki=ag​\(i\)k\_\{i\}=a\_\{g\(i\)\}to sourceiiand queryqm=amq\_\{m\}=a\_\{m\}to slotmm\. At temperatureτ\\tau, the attention mass assigned outsideImI\_\{m\}is bounded by

δm≤n−\|Im\|\|Im\|​exp⁡\(−Δ/τ\)\.\\delta\_\{m\}\\leq\\frac\{n\-\|I\_\{m\}\|\}\{\|I\_\{m\}\|\}\\exp\(\-\\Delta/\\tau\)\.\(14\)For target\-to\-slot reading, the weight assigned by addressama\_\{m\}to its matching slot is at least

ρm​m≥11\+\(M−1\)​exp⁡\(−Δ/τ\)\.\\rho\_\{mm\}\\geq\\frac\{1\}\{1\+\(M\-1\)\\exp\(\-\\Delta/\\tau\)\}\.\(15\)

###### Proof\.

Matching logits equal1/τ1/\\tau, while every non\-matching logit is at most\(1−Δ\)/τ\(1\-\\Delta\)/\\tau\. Summing the corresponding exponentials gives both bounds\. ∎

Constant\-margin binary or spherical codebooks containMMaddresses inp=O​\(log⁡M\)p=O\(\\log M\)dimensions\. Conversely, underbb\-bit precision, merely representingMMdistinct addresses requiresp​b≥log2⁡Mpb\\geq\\log\_\{2\}M\. Thus dot\-product cross\-attention realizes near\-disjoint addressing with an asymptotically logarithmic address dimension, whereas exact linear one\-hot gating requiresp≥Mp\\geq M\. The payload capacityM​dMdis unchanged; the gain concerns the interface used to organize and retrieve it\.

Distinct slot embeddings remove the exact symmetry obstruction, and lower temperature sharpens routing\. In our implementation, static addresses are kept separate from dynamic contents and the same identifier\-derived address space is used for source writes and target reads\.

#### Reading and integrating the slot memory\.

Once the slots have gathered the global information, it must be returned to the graph\. A shared global FiLM read\[[17](https://arxiv.org/html/2608.02709#bib.bib19),[2](https://arxiv.org/html/2608.02709#bib.bib27)\],

\[γ,β\]=Φ​\(Z1,…,ZM\),hj\+=\(1\+γ\)⊙hj\+β,\[\\gamma,\\beta\]=\\Phi\(Z\_\{1\},\\ldots,Z\_\{M\}\),\\qquad h\_\{j\}^\{\+\}=\(1\+\\gamma\)\\odot h\_\{j\}\+\\beta,\(16\)is already non\-separable: althoughγ,β\\gamma,\\betaare broadcast, their multiplicative interaction withhjh\_\{j\}can implement an implicit target\-dependent gate\. It can therefore decode a factorized wide state when target addresses are aligned with its feature coordinates\.

Our default is an explicit target\-to\-slot read,

ρj​m=softmaxm⁡\(qr​\(hj\)⊤​kr​\(Zm\)d\),Oj=∑m=1Mρj​m​vr​\(Zm\),\\rho\_\{jm\}=\\operatorname\{softmax\}\_\{m\}\\\!\\left\(\\frac\{q\_\{\\mathrm\{r\}\}\(h\_\{j\}\)^\{\\top\}k\_\{\\mathrm\{r\}\}\(Z\_\{m\}\)\}\{\\sqrt\{d\}\}\\right\),\\qquad O\_\{j\}=\\sum\_\{m=1\}^\{M\}\\rho\_\{jm\}v\_\{\\mathrm\{r\}\}\(Z\_\{m\}\),\(17\)which places the selection on the memory axis rather than inside hidden feature blocks\. Source\-to\-slot attention determines where information is written; Equation \([17](https://arxiv.org/html/2608.02709#S3.E17)\) determines which compartments each target reads\. This introduces no direct real\-node attention and costsO​\(n​M​d\)O\(nMd\)\.

The target\-specific context may be added tohjh\_\{j\}, or integrated through a small Slot\-FiLM map,

\[γj,βj\]=MLPfilm⁡\(\[hj,Oj\]\),hj\+=\(1\+γj\)⊙hj\+βj\.\[\\gamma\_\{j\},\\beta\_\{j\}\]=\\operatorname\{MLP\}\_\{\\mathrm\{film\}\}\(\[h\_\{j\},O\_\{j\}\]\),\\qquad h\_\{j\}^\{\+\}=\(1\+\\gamma\_\{j\}\)\\odot h\_\{j\}\+\\beta\_\{j\}\.\(18\)The multiplicative branch aligns retrieved content with local features\. Zero\-initializing its final map giveshj\+=hjh\_\{j\}^\{\+\}=h\_\{j\}and∂hj\+/∂hj=I\\partial h\_\{j\}^\{\+\}/\\partial h\_\{j\}=I; a small near\-zero initialization preserves this direct path while allowing gradients to reach the routing branch\.

## 4Multiplicity\-Preserving Virtual Nodes

Addressability determines where information is stored, but a normalized write can still discard how many nodes contributed\. One direct solution is an unnormalized weighted sum, as in cardinality\-preserved attention and the ACAM tokens of NetDiff\[[28](https://arxiv.org/html/2608.02709#bib.bib12),[14](https://arxiv.org/html/2608.02709#bib.bib20)\]\. Such reads preserve additive mass, but their norm can grow with graph size and score concentration, which requires additional scaling or clipping\. We instead retain softmax normalization and place the querying latent inside its own attention set\.

### 4\.1Replication blindness of normalized attention

Standard cross\-attention writes

Att⁡\(q,X\)=∑x∈Xexp⁡\(s​\(q,x\)\)​v​\(x\)∑x∈Xexp⁡\(s​\(q,x\)\)\.\\operatorname\{Att\}\(q,X\)=\\frac\{\\sum\_\{x\\in X\}\\exp\(s\(q,x\)\)v\(x\)\}\{\\sum\_\{x\\in X\}\\exp\(s\(q,x\)\)\}\.\(19\)For a multisetXX, letr​XrXrepeat every elementrrtimes\.

###### Proposition 4\.1\(Replication invariance\)\.

For everyqq, every integerr≥1r\\geq 1, and arbitrary learned score and value functions,

Att⁡\(q,r​X\)=Att⁡\(q,X\)\.\\operatorname\{Att\}\(q,rX\)=\\operatorname\{Att\}\(q,X\)\.\(20\)The result holds independently for every head and every slot\.

###### Proof\.

Uniform replication multiplies both numerator and denominator of Eq\. \([19](https://arxiv.org/html/2608.02709#S4.E19)\) byrr\. ∎

Thus normalized attention represents a weighted empirical distribution rather than its absolute counting measure\. Increasing slot width, slot count, or downstream depth cannot reconstruct multiplicity once all source\-to\-memory paths satisfy Proposition[4\.1](https://arxiv.org/html/2608.02709#S4.Thmtheorem1); a formal induction over stacked layers is given in Appendix[B](https://arxiv.org/html/2608.02709#A2)\. A residual outside the attention,z\+Att⁡\(z,X\)z\+\\operatorname\{Att\}\(z,X\), remains replication invariant wheneverzzis unchanged\.

### 4\.2Anchoring the latent query inside its attention

Figure[2](https://arxiv.org/html/2608.02709#S4.F2)shows the modification relative to the normalized Cross\-Attn VN write\. Let the slot query beqq, let the same latent state produce a private anchor key/value\(k0,a\)\(k\_\{0\},a\), and let node keys/values be\(ki,vi\)\(k\_\{i\},v\_\{i\}\)\. Anchored attention is

z​\(X\)=es0​a\+∑iesi​vies0\+∑iesi,s0=q⊤​k0,si=q⊤​ki\.z\(X\)=\\frac\{e^\{s\_\{0\}\}a\+\\sum\_\{i\}e^\{s\_\{i\}\}v\_\{i\}\}\{e^\{s\_\{0\}\}\+\\sum\_\{i\}e^\{s\_\{i\}\}\},\\quad s\_\{0\}=q^\{\\top\}k\_\{0\},\\quad s\_\{i\}=q^\{\\top\}k\_\{i\}\.\(21\)Each slot has its own private anchor, and anchors do not mix across slots\.

qmq\_\{m\}\(km​0,am\)\(k\_\{m0\},a\_\{m\}\)x1x\_\{1\}x2x\_\{2\}x3x\_\{3\}x4x\_\{4\}

Figure 2:Anchored Cross\-Attn VN write for slotmm\. The slot queryqmq\_\{m\}attends jointly to the source keys/values and to one private slot\-derived anchor\(km​0,am\)\(k\_\{m0\},a\_\{m\}\)\. Because the anchor participates in the same softmax normalization, its weightαm​0=esm​0/\(esm​0\+∑iesm​i\)\\alpha\_\{m0\}=e^\{s\_\{m0\}\}/\(e^\{s\_\{m0\}\}\+\\sum\_\{i\}e^\{s\_\{mi\}\}\)reveals the source normalization mass\.###### Proposition 4\.2\(Density\-induced displacement\)\.

Assumekkidentical matching nodes have scoressand valuevv, while the anchor has scores0s\_\{0\}and valuea≠va\\neq v\. Then

zk=es0​a\+k​es​ves0\+k​es=\(1−λk\)​a\+λk​v,λk=k​eses0\+k​es\.z\_\{k\}=\\frac\{e^\{s\_\{0\}\}a\+ke^\{s\}v\}\{e^\{s\_\{0\}\}\+ke^\{s\}\}=\(1\-\\lambda\_\{k\}\)a\+\\lambda\_\{k\}v,\\qquad\\lambda\_\{k\}=\\frac\{ke^\{s\}\}\{e^\{s\_\{0\}\}\+ke^\{s\}\}\.\(22\)The mapk↦zkk\\mapsto z\_\{k\}is injective for finitek≥0k\\geq 0\.

###### Proof\.

λk\\lambda\_\{k\}is strictly increasing inkk, so distinct multiplicities occupy distinct points on the segment betweenaaandvv\. ∎

The representation therefore moves away from its private reference as the density of matching nodes increases\. More generally, the anchor exposes the complete softmax normalization mass\.

###### Proposition 4\.3\(Recovery of normalized content and mass\)\.

Let

Z=∑iesi,μ=1Z​∑iesi​vi\.Z=\\sum\_\{i\}e^\{s\_\{i\}\},\\qquad\\mu=\\frac\{1\}\{Z\}\\sum\_\{i\}e^\{s\_\{i\}\}v\_\{i\}\.Assume the anchor value occupies a dedicated coordinate in which all node values are zero\. From the anchored output and known anchor logits0s\_\{0\}, one recovers

α0\\displaystyle\\alpha\_\{0\}=es0es0\+Z,\\displaystyle=\\frac\{e^\{s\_\{0\}\}\}\{e^\{s\_\{0\}\}\+Z\},Z\\displaystyle Z=es0​1−α0α0,\\displaystyle=e^\{s\_\{0\}\}\\frac\{1\-\\alpha\_\{0\}\}\{\\alpha\_\{0\}\},μ\\displaystyle\\mu=z⟂1−α0\.\\displaystyle=\\frac\{z\_\{\\perp\}\}\{1\-\\alpha\_\{0\}\}\.\(23\)Consequently, the unnormalized weighted sumZ​μZ\\muis recoverable\.

In implementation, we exposeα0\\alpha\_\{0\}as a separate mass channel before LayerNorm\. The semantic channel uses the conditionally normalized node weights

α~i=αi1−α0=esiZ,\\widetilde\{\\alpha\}\_\{i\}=\\frac\{\\alpha\_\{i\}\}\{1\-\\alpha\_\{0\}\}=\\frac\{e^\{s\_\{i\}\}\}\{Z\},while the count pathway receives

log⁡Z=s0\+log⁡\(1−α0\)−log⁡α0\.\\log Z=s\_\{0\}\+\\log\(1\-\\alpha\_\{0\}\)\-\\log\\alpha\_\{0\}\.This decomposition keeps label content invariant to replication and isolates multiplicity for counting\.

### 4\.3A 1\-WL characterization on bounded multisets

The preceding result gives a direct characterization in the multiset setting underlying 1\-WL\. LetΣ\\Sigmabe a finite color alphabet and letXXbe a nonempty multiset overΣ\\Sigmawith bounded size\.

###### Theorem 4\.5\(Injective anchored multiset read\)\.

Anchored attention followed by a sufficiently expressive post\-processing map can implement an injective representation ofXX\. Consequently, on bounded colored neighborhoods it can realize one 1\-WL refinement step\. Standard normalized attention without an additional cardinality path is not injective on any domain containing both a multisetXXand one of its uniform replicationsr​XrX,r\>1r\>1\.

###### Proof\.

Set every node logit to zero and encode colorc∈Σc\\in\\Sigmaby the canonical vectorece\_\{c\}\. Standard normalized attention then returns

μ​\(X\)=1\|X\|​∑x∈Xex,\\mu\(X\)=\\frac\{1\}\{\|X\|\}\\sum\_\{x\\in X\}e\_\{x\},the normalized color histogram\. Hence

μ​\(r​X\)=μ​\(X\),\\mu\(rX\)=\\mu\(X\),so this representation is not injective whenever bothXXandr​XrXbelong to the task domain\.

Now add an anchor with logits0=0s\_\{0\}=0\. Give the anchor value11in a dedicated coordinate and zero in all color coordinates, while node values are zero in the anchor coordinate and equal toexe\_\{x\}in the color coordinates\. The anchored output is then

z​\(X\)=\[α0,\(1−α0\)​μ​\(X\)\],α0=11\+\|X\|\.z\(X\)=\\left\[\\alpha\_\{0\},\\,\(1\-\\alpha\_\{0\}\)\\mu\(X\)\\right\],\\qquad\\alpha\_\{0\}=\\frac\{1\}\{1\+\|X\|\}\.Therefore both the multiset size and its normalized color histogram are recoverable:

\|X\|=1−α0α0,μ​\(X\)=zcolor1−α0\.\|X\|=\\frac\{1\-\\alpha\_\{0\}\}\{\\alpha\_\{0\}\},\\qquad\\mu\(X\)=\\frac\{z\_\{\\mathrm\{color\}\}\}\{1\-\\alpha\_\{0\}\}\.Their product gives

\|X\|​μ​\(X\)=∑x∈Xex,\|X\|\\mu\(X\)=\\sum\_\{x\\in X\}e\_\{x\},which is the integer color histogram and uniquely determinesXX\.

A 1\-WL refinement is an injective function of the current node color and the multiset of neighbor colors\. Since both the color alphabet and neighborhood size are bounded, the set of possible inputs is finite, and a sufficiently expressive post\-processing MLP can represent the corresponding injective update\. ∎

The theorem identifies the exact statistic missing from ordinary softmax: normalized attention retains color proportions, while the anchor additionally reveals the total mass needed to recover the counting measure used by 1\-WL\.

###### Corollary 4\.7\(Multiplicity\-aware Two\-Radius\)\.

Consider a bounded Two\-Radius family in which source type\(i,π​\(i\)\)\(i,\\pi\(i\)\)occurscic\_\{i\}times and targettit\_\{i\}must predict\(π​\(i\),ci\)\(\\pi\(i\),c\_\{i\}\)\. Then:

1. 1\.colored 1\-WL solves the task in two refinement rounds;
2. 2\.a normalized global read satisfying Proposition[4\.1](https://arxiv.org/html/2608.02709#S4.Thmtheorem1)cannot distinguish\(π,c\)\(\\pi,c\)from\(π,r​c\)\(\\pi,rc\)when no parallel path reveals cardinality;
3. 3\.addressable anchored slots with sufficient width solve the task by combining the partition of Theorem[3\.5](https://arxiv.org/html/2608.02709#S3.Thmtheorem5)with the injective multiset read of Theorem[4\.5](https://arxiv.org/html/2608.02709#S4.Thmtheorem5)\.

###### Proof sketch\.

In the first 1\-WL round, each structural central node receives the complete multiset

\{\(i,π​\(i\)\)ci:i∈\[n\]\}\.\\bigl\\\{\(i,\\pi\(i\)\)^\{c\_\{i\}\}:i\\in\[n\]\\bigr\\\}\.Its refined color therefore determines both the label and multiplicity associated with every identifier\. In the second round, targettit\_\{i\}combines this global color with its own identifieriiand recovers\(π​\(i\),ci\)\(\\pi\(i\),c\_\{i\}\)\.

The failure of normalized global attention follows directly from Proposition[4\.1](https://arxiv.org/html/2608.02709#S4.Thmtheorem1): uniformly multiplying all multiplicities does not change the normalized source\-to\-memory representation\.

For the anchored construction, partition identifiers across slots as in Theorem[3\.5](https://arxiv.org/html/2608.02709#S3.Thmtheorem5)\. Within slotg​\(i\)g\(i\), assign identifieriithe private blockr​\(i\)r\(i\), so that a source of type\(i,π​\(i\)\)\(i,\\pi\(i\)\)is represented by the slot\-local color\(r​\(i\),π​\(i\)\)\(r\(i\),\\pi\(i\)\)\. By Theorem[4\.5](https://arxiv.org/html/2608.02709#S4.Thmtheorem5), the anchored write recovers the exact histogram of these slot\-local colors\. Consequently, blockr​\(i\)r\(i\)records multiplicitycic\_\{i\}in label coordinateπ​\(i\)\\pi\(i\)\. Targettit\_\{i\}selects slotg​\(i\)g\(i\)and blockr​\(i\)r\(i\), recovering\(π​\(i\),ci\)\(\\pi\(i\),c\_\{i\}\)\. ∎

## 5Benchmarks

The experiments evaluate the two requirements jointly and then test counting in a separate graph\-level setting\. For multiplicity\-aware Two\-Radius, all four variants use the same categorical inputs, three\-layer mean\-MPNN backbone, prediction heads, optimization schedule, and random seed; only the global communication module changes\. The exact data\-generation, architecture, and training configuration used for Table[1](https://arxiv.org/html/2608.02709#S5.T1)is given in Appendix[C](https://arxiv.org/html/2608.02709#A3)\.

### 5\.1Benchmark A: multiplicity\-aware Two\-Radius

The multiplicity\-aware task jointly evaluates the two theoretical requirements\. Its label component is exactly the original address\-retrieval problem: targettit\_\{i\}must recover the label associated with identifierii\. Its count component additionally tests whether the global read preserves absolute multiplicity\. This removes the need for a separate permutation\-only benchmark while retaining a direct diagnostic for addressability\.

We next add repeated source types\. For every identifierii, sample a labelπ​\(i\)\\pi\(i\)and a base multiplicityai∈\{1,…,A\}a\_\{i\}\\in\\\{1,\\ldots,A\\\}\. Each base instance is rendered at several global replication scalesr∈\{1,…,R\}r\\in\\\{1,\\ldots,R\\\}, giving

indistinguishable copies of source\(i,π​\(i\)\)\(i,\\pi\(i\)\)\. Targettit\_\{i\}predicts both

\(π​\(i\),ci\)\.\(\\pi\(i\),c\_\{i\}\)\.The paired scales guarantee that standard normalized attention observes identical relative source distributions while the absolute targets differ\.

For Table[1](https://arxiv.org/html/2608.02709#S5.T1), we usen=12n=12source–target identifiers, one structural central node, permutation\-valued labels over\[12\]\[12\],A=4A=4, and the three replication scalesr∈\{1,2,3\}r\\in\\\{1,2,3\\\}\. Thus the largest target count is1212\. Each minibatch samples3232latent assignments and renders every assignment at all three scales, yielding9696paired graphs\. Graphs are padded to at most157157node positions \(144144sources, one center, and1212targets\), with all padding masked from message passing and global attention\.

We reportLabelaccuracy, exactCountaccuracy, andBoth, which requires both predictions to be correct for the same target\. We additionally track exact graph recovery as a diagnostic\. The comparison crosses the two properties directly: the VN remains a homogeneous bottleneck, the Cross\-Attn VN is addressable but replication blind, and the Anchored Cross\-Attn VN preserves both address and mass\. An outer residual does not change the replication invariance\.

One subtlety in reading Table[1](https://arxiv.org/html/2608.02709#S5.T1): by Proposition[4\.1](https://arxiv.org/html/2608.02709#S4.Thmtheorem1), the count predictions of the Cross\-Attn VN*cannot*depend on the replication scalerr\. Its nonzero count accuracy therefore does not reflect recovered multiplicity, but residual correlations between the paired\-scale protocol and the base multiplicitiesaia\_\{i\}, which are visible to any distribution\-level read\. The meaningful contrast is that only the anchored variant can, in principle and in practice, track the paired scales\.

#### Optimization protocol\.

All variants are trained for200200epochs with5050minibatches per epoch, for10,00010\{,\}000optimizer updates\. We use AdamW with learning rate10−410^\{\-4\}for the shared backbone and prediction heads and2×10−42\\times 10^\{\-4\}for the global module, zero weight decay and dropout, and gradient clipping at norm55\. The count\-loss weight is zero for the first3030epochs, is linearly increased to0\.50\.5over the next4040epochs, and then remains fixed\. Cross\-attention variants use1212slots,44heads, address temperature0\.350\.35, and a Slot\-FiLM final\-layer initialization with standard deviation10−310^\{\-3\}\. At every epoch, validation metrics are averaged over88freshly sampled minibatches \(768768rendered graphs\), and the reported checkpoint maximizes validationBoth\. Table[1](https://arxiv.org/html/2608.02709#S5.T1)reports the single run with seed0; no variance estimate is implied\.

Table 1:Multiplicity\-aware Two\-Radius validation accuracy \(%\)\. Single run with seed0\. For each variant, we report the epoch with the highest validationBothaccuracy, evaluated on88freshly sampled minibatches per epoch\.

### 5\.2Benchmark B: planted motif census

To test whether the effect extends beyond duplicated key–value pairs, we use a graph\-level motif census\. A connected graph contains a random background, distractor gadgets, and planted occurrences of six rooted motifs \(triangle, square, star, path, clique, and diamond\)\. An MPNN must recognize local rooted structure; the global readout predicts the six motif counts\. Counts, background size, and motif composition have separate OOD splits\.

This is an inductive\-bias and extrapolation test rather than a strict impossibility result\. Mean pooling and standard cross\-attention mainly encode relative motif prevalence, sum pooling is an additive count\-aware control, and anchored slots expose query\-dependent soft masses\. Graph size is deliberately*not*provided as an input feature, so that any mass sensitivity must arise from the aggregation mechanism itself rather than from a side\-channel scalar\. To keep this auxiliary benchmark compact, Table[2](https://arxiv.org/html/2608.02709#S5.T2)reports only IID evaluation and jittered\-replication OOD, where replicated motif instances are perturbed by local rewiring and node\-feature jitter\. We report macro log\-MAE and macro log\-R2R^\{2\}; the benchmark construction and controls are summarized in Appendix[D](https://arxiv.org/html/2608.02709#A4)\.

Table 2:Motif counting\. All readouts share the same training budget and are selected by early stopping on validation log\-MAE; we report the selected checkpoint\. Jittered OOD perturbs replicated motifs while preserving the counting target\.
### 5\.3External validation: constrained link\-set prediction

We further evaluate the global module on constrained link\-set prediction, a task derived from the NetDiff benchmark\[[14](https://arxiv.org/html/2608.02709#bib.bib20)\]\. Given a set of nodes with geometric and categorical features, the model predicts a binary link for each candidate pair\. Valid solutions must satisfy several coupled constraints, including link symmetry, absence of self\-links, bipartite compatibility, bounded node degree, and a limited number of links per angular sector\. Hence, the decision for one pair depends on the links selected elsewhere in the graph\.

We remove the local MPNN and compare virtual\-node readouts directly\. The Cross\-Attn VN reaches an F1 score of0\.7510\.751, while the Anchored Cross\-Attn VN reaches0\.8160\.816\. The mass\-aware virtual node produces more confident and globally coherent link predictions, indicating that multiplicity\-sensitive global aggregation is useful beyond explicit counting tasks\. We stress the scope of this experiment: it compares two readouts on a single seed of a specialized benchmark, and should be read as a proof of concept that the anchored read transfers to coherent global decisions—not as a definitive benchmark\. A broader baseline suite and variance analysis are left to future work\.

Table 3:Constrained link\-set prediction without local message passing\. Single\-seed proof of concept; see Section[5\.3](https://arxiv.org/html/2608.02709#S5.SS3)for scope\.

## 6Related Work

#### Oversquashing and finite\-capacity bottlenecks\.

Oversquashing was identified as a consequence of exponentially growing receptive fields and graph curvature\[[1](https://arxiv.org/html/2608.02709#bib.bib4),[22](https://arxiv.org/html/2608.02709#bib.bib5),[7](https://arxiv.org/html/2608.02709#bib.bib6)\], and bounded\-capacity cuts were shown to limit what constant\-width MPNNs can transmit\[[13](https://arxiv.org/html/2608.02709#bib.bib7)\]\. The Two\-Radius construction of\[[15](https://arxiv.org/html/2608.02709#bib.bib8)\]isolates the capacity component from long\-range attenuation: distances and Jacobian path lengths stay constant while the required content grows\. We adopt that task and ask which*auxiliary*memory organization resolves it\.

#### Virtual nodes and global graph memory\.

Virtual nodes were introduced as a global communication shortcut\[[8](https://arxiv.org/html/2608.02709#bib.bib1),[10](https://arxiv.org/html/2608.02709#bib.bib25)\]; spectral analyses characterize how they improve mixing\[[21](https://arxiv.org/html/2608.02709#bib.bib22),[9](https://arxiv.org/html/2608.02709#bib.bib24)\], and expressivity comparisons show that MPNN\+VN and attention are related but in general incomparable primitives\[[3](https://arxiv.org/html/2608.02709#bib.bib16),[19](https://arxiv.org/html/2608.02709#bib.bib17)\]\. RANGE relays information through attention nodes with positional encodings\[[4](https://arxiv.org/html/2608.02709#bib.bib23)\]\. Our contribution is complementary: rather than proposing a new global layer, we characterize which properties \(addressability, multiplicity preservation\) a VN must have, and supply a minimal mechanism for each\.

#### Latent arrays and set attention\.

Slots written and read by cross\-attention are structurally close to induced set attention blocks and Perceiver\-style latent arrays\[[12](https://arxiv.org/html/2608.02709#bib.bib14),[11](https://arxiv.org/html/2608.02709#bib.bib15)\], and to the Deep Sets analysis of injective multiset encoders\[[27](https://arxiv.org/html/2608.02709#bib.bib9),[24](https://arxiv.org/html/2608.02709#bib.bib10)\]\. Full and sparse graph Transformers instead give real nodes a direct global attention path\[[23](https://arxiv.org/html/2608.02709#bib.bib13),[18](https://arxiv.org/html/2608.02709#bib.bib18),[20](https://arxiv.org/html/2608.02709#bib.bib28)\]\. We keep real\-node computation purely local and restrict global computation to the latent axis\.

#### Expressivity, counting, and cardinality\.

MPNN expressivity is bounded by 1\-WL\[[26](https://arxiv.org/html/2608.02709#bib.bib2),[16](https://arxiv.org/html/2608.02709#bib.bib3)\]; principal neighborhood aggregation and cardinality\-preserving attention show that multiplicity must be encoded explicitly\[[5](https://arxiv.org/html/2608.02709#bib.bib26),[28](https://arxiv.org/html/2608.02709#bib.bib12)\], and the ACAM tokens of NetDiff apply this idea to constrained generation\[[14](https://arxiv.org/html/2608.02709#bib.bib20)\]\. The anchor mechanism achieves the same goal while retaining softmax normalization, and admits the inverted reading of register tokens and attention sinks\[[6](https://arxiv.org/html/2608.02709#bib.bib29),[25](https://arxiv.org/html/2608.02709#bib.bib30)\]discussed in Section[4](https://arxiv.org/html/2608.02709#S4)\.

#### Feature\-wise modulation\.

FiLM conditions features on auxiliary signals through affine modulation\[[17](https://arxiv.org/html/2608.02709#bib.bib19),[2](https://arxiv.org/html/2608.02709#bib.bib27)\]\. Our Slot\-FiLM integration uses the same primitive with identity\-preserving initialization, so that the local representation is protected while the global route is learned\.

## 7Discussion and Conclusion

The analysis separates raw storage capacity from usable factorization\. A VN of widthDDhasD​bDbfinite\-precision bits, and one wide VN withD=M​dD=Mdhas the same raw capacity asMMslots of widthdd\. Nevertheless, the standard homogeneous broadcast exposes no target\-specific memory axis\. Under a separable decoder its global contribution is identical for every target and cannot realize arbitrary lookup\. A sufficiently expressive non\-separable decoder may succeed, but it must then construct an implicit addressing mechanism by partitioning feature coordinates and selecting them from the target representation\.

Addressable VNs make this operation structural\. Physical multiplicity becomes an effective factorization degree only when states can evolve differently and be used separately; symmetric VN clones remain one channel\. Cross\-attention supplies both write and read routing, and separated dot\-product codes addressMMcompartments inO​\(log⁡M\)O\(\\log M\)dimensions rather than through an exactMM\-dimensional linear one\-hot interface\. This does not reduce the total information needed by Two\-Radius, but it reduces the required width per compartment and exposes the organization that a successful wide\-VN decoder would otherwise learn implicitly\.

Addressability and multiplicity preservation remain complementary\. Standard softmax slots recover target\-specific labels but are invariant to uniform replication\. A private anchor exposes the missing normalization mass; together with normalized semantic content it reconstructs the counting measure and, on bounded color domains, an injective 1\-WL multiset representation\. The Two\-Radius results reflect this separation: standard slots solve label retrieval but not counting, while anchored slots solve both\. Motif counting and constrained link prediction provide additional evidence that the mass\-aware read improves coherent global decisions beyond duplicated key–value pairs\.

#### Limitations\.

Three scope decisions delimit our claims\. First, the capacity results are exact\-recovery, worst\-case counting arguments \(Remark[3\.4](https://arxiv.org/html/2608.02709#S3.Thmtheorem4)\); approximate recovery and stochastic decoders would require a rate–distortion treatment we do not provide\. Second, the positive results are constructive expressivity statements \(Remark[4\.6](https://arxiv.org/html/2608.02709#S4.Thmtheorem6)\): they remove representation\-level obstructions but do not characterize the optimization dynamics that reach them, and our experiments probe learnability only on controlled tasks\. Third, the empirical evidence is deliberately narrow: the benchmarks are synthetic or semi\-synthetic, the link\-set experiment is a single\-seed proof of concept on a specialized task, and we do not include the most direct ablation—a wide VN of matched total width paired with a strong non\-separable decoder \(e\.g\. global FiLM\)—which would quantify how much of the gain comes from exposing the factorization architecturally rather than letting it be learned implicitly\. We consider that ablation the most important next experiment\.

The resulting module keeps edge\-based message passing as the local processor\. It addsO​\(n​M\)O\(nM\)node–memory attention pairs, withO​\(n​M​d\)O\(nMd\)arithmetic cost, rather than anO​\(n2\)O\(n^\{2\}\)real\-node attention path; choosingM=Θ​\(\|V\|\)M=\\Theta\(\\sqrt\{\|V\|\}\)already balances the global term against dense attention up to width factors, though the useful number of slots, routing temperature, and optimization scale remain task dependent\. The overall design principle is consistent: a good virtual node should expose a compact addressable memory axis, preserve multiplicity, and return global information without replacing the graph’s local inductive bias\.

## References

- \[1\]U\. Alon and E\. Yahav\(2021\)On the bottleneck of graph neural networks and its practical implications\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=i80OPhOCVH2)Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px1.p1.1)\.
- \[2\]M\. Brockschmidt\(2020\)GNN\-FiLM: graph neural networks with feature\-wise linear modulation\.InProceedings of the 37th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.119,pp\. 1144–1152\.Cited by:[§3\.3](https://arxiv.org/html/2608.02709#S3.SS3.SSS0.Px1.p1.3),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px5.p1.1)\.
- \[3\]C\. Cai, T\. S\. Hy, R\. Yu, and Y\. Wang\(2023\)On the connection between MPNN and graph transformer\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 3408–3430\.Cited by:[§2\.3](https://arxiv.org/html/2608.02709#S2.SS3.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[4\]A\. Caruso, J\. Venturin, L\. Giambagli, E\. Rolando, Z\. El\-Machachi, F\. Noé, and C\. Clementi\(2026\)Extending the range of graph neural networks with global encodings\.Nature Communications17,pp\. 1855\.External Links:[Document](https://dx.doi.org/10.1038/s41467-026-69715-3)Cited by:[§1](https://arxiv.org/html/2608.02709#S1.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[5\]G\. Corso, L\. Cavalleri, D\. Beaini, P\. Liò, and P\. Veličković\(2020\)Principal neighbourhood aggregation for graph nets\.InAdvances in Neural Information Processing Systems,Vol\.33\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.
- \[6\]T\. Darcet, M\. Oquab, J\. Mairal, and P\. Bojanowski\(2024\)Vision transformers need registers\.InInternational Conference on Learning Representations,Cited by:[Remark 4\.4](https://arxiv.org/html/2608.02709#S4.Thmtheorem4.p1.1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.
- \[7\]F\. Di Giovanni, L\. Giusti, F\. Barbero, G\. Luise, P\. Liò, and M\. M\. Bronstein\(2023\)On over\-squashing in message passing neural networks: the impact of width, depth, and topology\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 7865–7885\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px1.p1.1)\.
- \[8\]J\. Gilmer, S\. S\. Schoenholz, P\. F\. Riley, O\. Vinyals, and G\. E\. Dahl\(2017\)Neural message passing for quantum chemistry\.InProceedings of the 34th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.70,pp\. 1263–1272\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p1.1),[§1](https://arxiv.org/html/2608.02709#S1.p3.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[9\]E\. Hwang, V\. Thost, S\. S\. Dasgupta, and T\. Ma\(2022\)An analysis of virtual nodes in graph neural networks for link prediction\.InThe First Learning on Graphs Conference,Note:Extended abstractExternal Links:[Link](https://openreview.net/forum?id=dI6KBKNRp7)Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p3.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[10\]K\. Ishiguro, S\. Maeda, and M\. Koyama\(2019\)Graph warp module: an auxiliary module for boosting the power of graph neural networks in molecular graph analysis\.External Links:1902\.01020Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p3.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[11\]A\. Jaegle, F\. Gimeno, A\. Brock, O\. Vinyals, A\. Zisserman, and J\. Carreira\(2021\)Perceiver: general perception with iterative attention\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 4651–4664\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.SS0.SSS0.Px1.p1.1),[§3\.1](https://arxiv.org/html/2608.02709#S3.SS1.p5.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[12\]J\. Lee, Y\. Lee, J\. Kim, A\. R\. Kosiorek, S\. Choi, and Y\. W\. Teh\(2019\)Set transformer: a framework for attention\-based permutation\-invariant neural networks\.InProceedings of the 36th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.97,pp\. 3744–3753\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.SS0.SSS0.Px1.p1.1),[§3\.1](https://arxiv.org/html/2608.02709#S3.SS1.p5.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[13\]A\. Loukas\(2020\)What graph neural networks cannot learn: depth vs width\.InInternational Conference on Learning Representations,Cited by:[§2\.3](https://arxiv.org/html/2608.02709#S2.SS3.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px1.p1.1)\.
- \[14\]F\. Marcoccia, V\. Fagoo, G\. Monzat de Saint Julien, C\. Adjih, T\. Watteyne, and P\. Mühlethaler\(2026\)NetDiff: graph diffusion with improved global capabilities to generate and update mobile network topologies\.InProceedings of the 43rd International Conference on Machine Learning,Note:Accepted at ICML 2026; proceedings forthcomingCited by:[§4](https://arxiv.org/html/2608.02709#S4.p1.1),[§5\.3](https://arxiv.org/html/2608.02709#S5.SS3.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.
- \[15\]Y\. Mishayev, Y\. Sverdlov, T\. Amir, and N\. Dym\(2025\)Short\-range oversquashing\.Note:Accepted at the Fourth Learning on Graphs Conference \(LoG 2025\); proceedings forthcomingExternal Links:2511\.20406Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p2.4),[§1](https://arxiv.org/html/2608.02709#S1.p3.1),[§2\.1](https://arxiv.org/html/2608.02709#S2.SS1.SSS0.Px1.p2.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px1.p1.1)\.
- \[16\]C\. Morris, M\. Ritzert, M\. Fey, W\. L\. Hamilton, J\. E\. Lenssen, G\. Rattan, and M\. Grohe\(2019\)Weisfeiler and leman go neural: higher\-order graph neural networks\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 4602–4609\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v33i01.33014602)Cited by:[§2\.1](https://arxiv.org/html/2608.02709#S2.SS1.p1.2),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.
- \[17\]E\. Perez, F\. Strub, H\. de Vries, V\. Dumoulin, and A\. Courville\(2018\)FiLM: visual reasoning with a general conditioning layer\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.32\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v32i1.11671)Cited by:[§3\.3](https://arxiv.org/html/2608.02709#S3.SS3.SSS0.Px1.p1.3),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px5.p1.1)\.
- \[18\]L\. Rampášek, M\. Galkin, V\. P\. Dwivedi, A\. T\. Luu, G\. Wolf, and D\. Beaini\(2022\)Recipe for a general, powerful, scalable graph transformer\.InAdvances in Neural Information Processing Systems,Vol\.35\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p5.1),[§2\.2](https://arxiv.org/html/2608.02709#S2.SS2.p1.2),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[19\]E\. Rosenbluth, J\. Tönshoff, M\. Ritzert, B\. Kisin, and M\. Grohe\(2024\)Distinguished in uniform: self\-attention vs\. virtual nodes\.InInternational Conference on Learning Representations,Cited by:[§2\.2](https://arxiv.org/html/2608.02709#S2.SS2.p1.2),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[20\]H\. Shirzad, A\. Velingker, B\. Venkatachalam, D\. J\. Sutherland, and A\. K\. Sinop\(2023\)Exphormer: sparse transformers for graphs\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 31613–31632\.Cited by:[§2\.2](https://arxiv.org/html/2608.02709#S2.SS2.p1.2),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[21\]J\. Southern, F\. Di Giovanni, M\. Bronstein, and J\. F\. Lutzeyer\(2025\)Understanding virtual nodes: oversquashing and node heterogeneity\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p3.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px2.p1.1)\.
- \[22\]J\. Topping, F\. Di Giovanni, B\. P\. Chamberlain, X\. Dong, and M\. M\. Bronstein\(2022\)Understanding over\-squashing and bottlenecks on graphs via curvature\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=7UmjRGzp-A)Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px1.p1.1)\.
- \[23\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\. 5998–6008\.Cited by:[§1](https://arxiv.org/html/2608.02709#S1.p5.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[24\]E\. Wagstaff, F\. B\. Fuchs, M\. Engelcke, I\. Posner, and M\. A\. Osborne\(2019\)On the limitations of representing functions on sets\.InProceedings of the 36th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.97,pp\. 6487–6494\.Cited by:[§2\.3](https://arxiv.org/html/2608.02709#S2.SS3.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[25\]G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. Lewis\(2024\)Efficient streaming language models with attention sinks\.InInternational Conference on Learning Representations,Cited by:[Remark 4\.4](https://arxiv.org/html/2608.02709#S4.Thmtheorem4.p1.1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.
- \[26\]K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka\(2019\)How powerful are graph neural networks?\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=ryGs6iA5Km)Cited by:[§1](https://arxiv.org/html/2608.02709#S1.SS0.SSS0.Px2.p1.1),[§2\.1](https://arxiv.org/html/2608.02709#S2.SS1.p1.2),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.
- \[27\]M\. Zaheer, S\. Kottur, S\. Ravanbakhsh, B\. Póczos, R\. Salakhutdinov, and A\. J\. Smola\(2017\)Deep sets\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\. 3391–3401\.Cited by:[§2\.3](https://arxiv.org/html/2608.02709#S2.SS3.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px3.p1.1)\.
- \[28\]S\. Zhang and L\. Xie\(2020\)Improving attention mechanism in graph neural networks via cardinality preservation\.InProceedings of the Twenty\-Ninth International Joint Conference on Artificial Intelligence,pp\. 1395–1402\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2020/194)Cited by:[§1](https://arxiv.org/html/2608.02709#S1.SS0.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2608.02709#S4.p1.1),[§6](https://arxiv.org/html/2608.02709#S6.SS0.SSS0.Px4.p1.1)\.

## Appendix ACapacity Proofs

### A\.1Proof of Theorem[3\.3](https://arxiv.org/html/2608.02709#S3.Thmtheorem3)

For each permutationπ∈Sn\\pi\\in S\_\{n\}, letTπT\_\{\\pi\}be the complete source\-dependent transcript available to all targets\. Ifπ≠π′\\pi\\neq\\pi^\{\\prime\}butTπ=Tπ′T\_\{\\pi\}=T\_\{\\pi^\{\\prime\}\}, then fixed target identifiers and a deterministic decoder produce the same joint output on both instances, contradicting exact recovery\. Henceπ↦Tπ\\pi\\mapsto T\_\{\\pi\}is injective and the transcript must realize at leastn\!n\!values\.

An effectively factorized transcript withLeffL\_\{\\mathrm\{eff\}\}states,ddcoordinates per state, and at most2b2^\{b\}values per coordinate has at most

2Leff​d​b2^\{L\_\{\\mathrm\{eff\}\}db\}possible values\. Therefore

2Leff​d​b≥n\!,2^\{L\_\{\\mathrm\{eff\}\}db\}\\geq n\!,which proves Eq\. \([10](https://arxiv.org/html/2608.02709#S3.E10)\)\. Stirling’s approximation giveslog2⁡\(n\!\)=n​log2⁡n−O​\(n\)\\log\_\{2\}\(n\!\)=n\\log\_\{2\}n\-O\(n\)\. For several global layers,Leff​d​bL\_\{\\mathrm\{eff\}\}dbis replaced by the capacity of their complete source\-dependent transcript\. Bounds for average rather than exact recovery would require a rate–distortion argument \(Remark[3\.4](https://arxiv.org/html/2608.02709#S3.Thmtheorem4)\)\.

### A\.2Why symmetric virtual nodes do not factorize memory

###### Lemma A\.1\(Persistence of virtual\-node symmetry\)\.

ConsiderMMVNs with identical initial states, identical neighborhoods, and shared permutation\-equivariant update functions\. Their states remain identical at every layer\.

###### Proof\.

The property holds at initialization\. If all VNs are identical at layerℓ\\ell, they receive identical neighbor multisets and aggregated messages\. The shared update therefore produces identical states at layerℓ\+1\\ell\+1\. ∎

Their joint state is always\(z,…,z\)\(z,\\ldots,z\), so it has the same number of reachable values as one VN and contributes one effective compartment\. The factorMMrequires a mechanism, such as addressability, that distinguishes writes, states, and reads\. Independently initialized clones escape the exact symmetry of the lemma but provide no selection interface; see Remark[3\.2](https://arxiv.org/html/2608.02709#S3.Thmtheorem2)for the operational reading of this case\.

### A\.3Proof of Theorem[3\.5](https://arxiv.org/html/2608.02709#S3.Thmtheorem5)

Letk=⌈n/M⌉k=\\lceil n/M\\rceiland fix a public partitionI1,…,IMI\_\{1\},\\ldots,I\_\{M\}with\|Im\|≤k\|I\_\{m\}\|\\leq k\. Letg​\(i\)g\(i\)andr​\(i\)r\(i\)denote the group and within\-group position of identifierii\.

A label in\[n\]\[n\]usesq=⌈log2⁡n/b⌉q=\\lceil\\log\_\{2\}n/b\\rceilcoordinates ofbbbits\. Slotmmstores its⌈log2⁡M/b⌉\\lceil\\log\_\{2\}M/b\\rceil\-coordinate address andkklabel blocks of lengthqq\. Sourceiiwrites the code ofπ​\(i\)\\pi\(i\)into blockr​\(i\)r\(i\)of slotg​\(i\)g\(i\)\. Since each destination depends only on the identifier, source order is irrelevant\. Targetjjselects slotg​\(j\)g\(j\)and blockr​\(j\)r\(j\), recoveringπ​\(j\)\\pi\(j\)\. Permuting target order permutes the reads, which proves equivariance and Eq\. \([11](https://arxiv.org/html/2608.02709#S3.E11)\)\.

For labels independently drawn from an alphabet of sizeCC, the analogous capacity requirement isLeff​d​b≥n​log2⁡CL\_\{\\mathrm\{eff\}\}db\\geq n\\log\_\{2\}C, and the construction usesO​\(\(n/M\)​log⁡C/b\)O\(\(n/M\)\\log C/b\)label coordinates per slot\.

## Appendix BAdditional Results on Anchored Attention

### B\.1General replication\-blind architecture

Consider any deterministic network in which all source information reaches the targets through global readsAmA\_\{m\}satisfying

Am​\(q,r​X\)=Am​\(q,X\),A\_\{m\}\(q,rX\)=A\_\{m\}\(q,X\),and suppose no parallel operation receives source cardinality\. By induction over global and local layers, the complete target output is identical onXXandr​XrX: the first global states coincide, deterministic subsequent states coincide, and repeated source copies remain indistinguishable under shared updates\. Therefore no such network can solve a task with different targets on the paired instances\.

The assumption excludes several legitimate count\-aware mechanisms: sum aggregation, explicit degree or graph\-size features, an anchor inside the normalization, batch statistics over the node axis, and unmasked padding information\. These must be controlled in the synthetic benchmark, and they motivate the protocol choices of Appendix[C](https://arxiv.org/html/2608.02709#A3): graph size is not an input feature, padding cardinality is masked out, and the write attention set contains only replicated source tokens\.

### B\.2Anchored semantic/mass decomposition

Write the anchored attention weights as

α0=es0es0\+Z,αi=esies0\+Z\.\\alpha\_\{0\}=\\frac\{e^\{s\_\{0\}\}\}\{e^\{s\_\{0\}\}\+Z\},\\qquad\\alpha\_\{i\}=\\frac\{e^\{s\_\{i\}\}\}\{e^\{s\_\{0\}\}\+Z\}\.Conditioned on selecting a real node, the semantic weights are

α~i=αi1−α0=esiZ\.\\widetilde\{\\alpha\}\_\{i\}=\\frac\{\\alpha\_\{i\}\}\{1\-\\alpha\_\{0\}\}=\\frac\{e^\{s\_\{i\}\}\}\{Z\}\.Hence the semantic channel

∑iα~i​vi\\sum\_\{i\}\\widetilde\{\\alpha\}\_\{i\}v\_\{i\}is exactly standard normalized attention, whileα0\\alpha\_\{0\}separately carries mass\. This decomposition is useful experimentally because count\-dependent variation cannot contaminate label content before the count head\.

## Appendix CDetailed Experimental Protocol

### C\.1Two\-Radius data and batching

Table[1](https://arxiv.org/html/2608.02709#S5.T1)usesn=12n=12identifiers,1212labels, one structural central node, maximum base multiplicityA=4A=4, and replication scalesr∈\{1,2,3\}r\\in\\\{1,2,3\\\}\. For every base example, the labels form a uniformly sampled permutationπ∈S12\\pi\\in S\_\{12\}, and the base multiplicities are sampled independently as

ai∼Unif⁡\{1,2,3,4\}\.a\_\{i\}\\sim\\operatorname\{Unif\}\\\{1,2,3,4\\\}\.The three paired graphs use countsci=r​aic\_\{i\}=ra\_\{i\}, so target counts lie in\{1,…,12\}\\\{1,\\ldots,12\\\}\. Source order is independently shuffled in every rendered graph, and target identifiers are placed in a random order\.

The directed communication graph contains edges from every source to the central node and from the central node to every target, with mean\-normalized aggregation and no reverse edges\. This prevents the fixed target set from entering the source summary through the local path\. The largest graph contains144144sources, one central node, and1212targets\. Smaller graphs are padded to these157157positions; node and source masks remove padding from message passing, pooling, and attention\.

Data are generated online rather than stored in a finite train/validation split\. Each training minibatch samples3232base assignments and expands each one at all three scales, for an effective batch of9696rendered graphs\. Training therefore processes320,000320\{,\}000base assignments, or960,000960\{,\}000rendered graphs, over10,00010\{,\}000updates\. Validation at each epoch uses88independently generated minibatches, corresponding to256256base assignments and768768rendered graphs\.

### C\.2Model variants

All variants use128128\-dimensional identifier, label, and role embeddings, followed by a two\-layer input MLP, LayerNorm, and three residual mean\-aggregation MPNN layers\. The label and count predictors are two\-layer MLPs\. The count head has1212classes, with classci−1c\_\{i\}\-1representing countcic\_\{i\}\.

TheMPNNbaseline has no auxiliary global state\. TheVNvariant reads the sources by masked mean pooling, updates one learned virtual state with a three\-layer MLP, and broadcasts it homogeneously to the targets through a residual target MLP with scale0\.20\.2\.

Both cross\-attention variants useM=12M=12learned static slot addresses and44heads\. Identifier embeddings are projected into a shared address space used both for source\-to\-slot writes and target\-to\-slot reads; dynamic slot content is not reused as an address\. The write attends only to source tokens, and both routing directions use temperature0\.350\.35\. Slot contents pass through an output projection, LayerNorm, a residual feed\-forward block, and a second LayerNorm\. The retrieved target context is integrated by Slot\-FiLM, with

γ=0\.5​tanh⁡\(γ^\),β=tanh⁡\(β^\),\\gamma=0\.5\\tanh\(\\widehat\{\\gamma\}\),\\qquad\\beta=\\tanh\(\\widehat\{\\beta\}\),and the final FiLM linear map is initialized from𝒩​\(0,10−6\)\\mathcal\{N\}\(0,10^\{\-6\}\), i\.e\. with weight standard deviation10−310^\{\-3\}\.

TheAnchored Cross\-Attn VNadditionally appends one private anchor logit to each slot and head before the source softmax\. Anchor logits are initialized to zero\. The per\-head log\-odds

log⁡\(1−α0\)−log⁡α0\\log\(1\-\\alpha\_\{0\}\)\-\\log\\alpha\_\{0\}are passed through a two\-layer mass MLP and added to the slot content after content normalization, so LayerNorm cannot erase the mass signal\.

### C\.3Paired replication protocol

For a fixed base assignment\(π,a\)\(\\pi,a\), the three rendered graphs differ only through the common scalerr\. Copies associated with the same identifier have identical identifier, label, role, neighborhood, and address features\. Graph cardinality is never supplied as an input feature\. Moreover, the source\-to\-slot attention set contains only source tokens: central and target nodes are excluded because their fixed, non\-replicated presence would act as an implicit softmax anchor\. Consequently, a normalized source read is exactly invariant across the paired scales, whereas the correct count labels change\.

### C\.4Optimization and model selection

All models are trained with AdamW for200200epochs and5050minibatches per epoch\. The learning rate is10−410^\{\-4\}for embeddings, the local backbone, and prediction heads\. Parameters belonging to the global block use a multiplier of22, giving learning rate2×10−42\\times 10^\{\-4\}\. Weight decay and dropout are zero, and gradients are clipped to norm55\.

The loss is

ℒ=ℒlabel\+wcount​ℒcount\.\\mathcal\{L\}=\\mathcal\{L\}\_\{\\mathrm\{label\}\}\+w\_\{\\mathrm\{count\}\}\\mathcal\{L\}\_\{\\mathrm\{count\}\}\.We usewcount=0w\_\{\\mathrm\{count\}\}=0through epoch3030, increase it linearly to0\.50\.5over epochs3131–7070, and keep it at0\.50\.5thereafter\. All reported Table[1](https://arxiv.org/html/2608.02709#S5.T1)rows use seed0\. At every epoch, metrics are averaged over88freshly sampled validation minibatches, and the reported row is the epoch maximizing validationBoth\. Because the experiment contains one seed, Table[1](https://arxiv.org/html/2608.02709#S5.T1)reports point estimates rather than means and standard deviations\.

### C\.5Diagnostics

For a single base assignment rendered at all three scales, we compare the complete global states against ther=1r=1state\. A normalized Cross\-Attn VN should have zero maximum and mean difference up to floating\-point error, whereas the anchored state should vary withrr\. We additionally record source\-to\-slot weights, anchor weights, target\-to\-slot weights, count accuracy at each scale, and exact graph recovery\.

### C\.6Reproducibility

An executable notebook containing the data generator, the four model definitions, the training and model\-selection loops, and the replication\-state diagnostic used by this protocol will be released upon publication\. Notebook output cells are not part of the protocol specification; all settings stated above are taken from the executable configuration and model code\.

## Appendix DPlanted Motif Census

Each graph contains a random connected background and several planted rooted gadgets\. The root marker is shared across motif types, so the MPNN must infer the local structure rather than read a motif label\. The target vector is

\[c△,c□,cstar,cpath,cclique,cdiamond\]\.\[c\_\{\\triangle\},c\_\{\\square\},c\_\{\\mathrm\{star\}\},c\_\{\\mathrm\{path\}\},c\_\{\\mathrm\{clique\}\},c\_\{\\mathrm\{diamond\}\}\]\.Distractor gadget families are marked but should not be counted\. OOD splits independently enlarge motif counts, background size, and change motif mixtures\. Exact replication is retained as a mechanistic unit test, while jittered replication applies degree\-preserving rewiring and node\-type perturbations\.

Compared readouts are mean, sum, standard slots, and anchored slots\. Graph size is not provided as an input feature; sum pooling is therefore the only count\-aware control, and the gap between sum pooling and anchored slots isolates the benefit of query\-dependent soft masses over a single additive channel\.