gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity
Authors: Hugh Blayney
Alvaro Arroyo
Xiaowen Dong
Michael M. Bronstein
Venue: ICLR 2026 Poster (2026)
Keywords: oversquashing
associative memory
graph neural network
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) leverage the graph structure to transmit information between nodes, typically through the message-passing mechanism. While these models have found a wide variety of applications, they are known to suffer from over-squashing, where information from a large receptive field of node representations is collapsed into a single fixed sized vector, resulting in an information bottleneck. In this paper, we re-examine the over-squashing phenomenon through the lens of model storage and retrieval capacity, which we define as the amount of information that can be stored in a node’s representation for later use. We study some of the limitations of existing tasks used to measure over-squashing and introduce a new synthetic task to demonstrate that an information bottleneck can saturate this capacity. Furthermore, we adapt ideas from the sequence modeling literature on associative memories, fast weight programmers, and the xLSTM model to develop a novel GNN architecture with improved capacity. We demonstrate strong performance of this architecture both on our capacity synthetic task, as well as a range of real-world graph benchmarks.

Published as a conference paper at ICLR 2026
GLSTM: MITIGATING OVER-SQUASHING BY INCREASING STORAGE CAPACITY
Hugh Blayney', Álvaro Arroyo', Xiaowen Dong', Michael M. Bronstein 1.2
I UUniversity Oxford
? PAITHYRA
hugh&robots.. ox. ac. uk
ABSTRACT
Graph Neural Networks (GNNs) leverage the graph structure to transmit infor- mation between nodes, typically through the peessage-aassing mechanism. While these models have found wide variety of applications, they are known to suf- fer from over-squashing, where information from large receptive field of node representations is collapsed into single fixed sized vector, resulting in an infor- mation bottleneck. this paper, we re-examine the over-squashing phenomenon through the lens of model storage and retrieval capacity, which define the amount of information that can be stored a node's representation for later use. We study some of the limitations of existing tasks used to measure over-squashing and introduce a new synthetic task to demonstrate that an information bottleneck saturate this capacity. Furthermore, ing literature on associative memories, fast weight programmers, and the XLSTM model to develop a novel GNN architecture with improved capacity. We demon- strate strong performance of this architecture both on our capacity synthetic task, well as a range of real-world graph benchmarks.
adapt ideas from the sequence model-
INTRODUCTION
Graph Neural Networks (GNNs) (Sperduti) 1993 Gori et al., 2005 Scarselli et al.) 2008 Micheli 2009 |Buuna et al.) 2014 Defferrard et al.) 2017) have emerged as standard framework for learning on graph-structured data. The majority of these models follow a message passing paradigm, where nodes iteratively exchange information with neighbors, commonly referred to as Message-Passing Neural Networks (MPNNs). Examples of this family of architectures include GCN (Kipf & Welling 2017). GAT (Veličković al. 2018). GIN (tu 2018), and GraphSAGE (Hamilton et al.) 2017)
Since each MPNN layer exchanges information between neighboring nodes to update node rep- resentations, the number of layers thus dictates the receptive field: the set of nodes information aggregated. Deep MPNNs are, in theory, desirable as they can model long-range de- pendencies, but scaling to many layers has historically been difficult due to two pervasive issues that have received significant attention in the literature: over-smoothing and over-squashing. We focus on the latter in this work.
which
Over-squashing was initially identified by Alon & Yahay (02T) as a problem of compressing in- formation from node's receptive field into fixed-size vector. This was linked with depth and long-range dependencies, since receptive fields tend to grow exponentially with depth. Later work (Topping et al., 2022, Di Giovanni al.) (023a) identified that this bottleneck could also result in low sensitivity measured by the node Jacobian, linking graph topology and aspects of model ar- chitecture via an upper bound on this Jacobian. This low sensitivity arises due to repeated degree normalization and application of contractive nonlinearity over many layers. Armaiz-Rodrigues &
Errica (2025) suggest that these two descriptions of over-squashin are not the same, and that Alon & Yahav (2021) define it problem of computational graph bottlenecks, while later work often defines it as a problem of topological bottlenecks. We discuss this separation and its relation to our A
work in Appendix

---

Published as a conference paper at ICLR 2026
Instead of separating by issues of computational tree structure and bottlenecks, we suggest alter- native separation by resultant failure mode: limited information storage capacity, and low sensitivity. In light of this, we highlight another divergence in the literature: the work of Alon & Yahav (2021) implicitly descrihed over-squashing as a capacity problem, and later work re-framed it as a problem of sensitivity. Focusing on the failure modes themselves not only allows us revisit the issue of ca- pacity originally discussed in Alon & Yahay (202I), but also to more directly motivate benchmarks and remedies, both of which we discuss in this paper. We further contextualize this issue of capacity by studying it in isolation from sensitivity issues. We believe this focus not only provides a more complete understanding of ovur-squasiing but also highlights new directions to mitigate it.
To combat over-squashing, existing research has focused on ameliorating topological bottlenecks through rewiring (Gasteiger et al., 2019; Gutteridge et al.] 2023] Nguyen et al. 2023; Saber & Salehi-Abari 2025) and controlling the flow of information (Bresson & Laurent [217]] Finkelshtein et al. 2024] Errica et al., 2025)- targeting topological and general computational bottlenecks re- spectively. However, these bottlenecks are only an issue if they harm performance in some way: in this work we discuss issues of (1) reduced sensitivity and (2) saturated storage capacity. Our proposed architecture in Section 4 targets the latter failure mode: adapting the MPNN architecture to improve its ability to store and retrieve information. Framing over-squashing as a capacity limi- tation that be addressed the architecture level exposes a previously unexplored path, and our results validate this direction.
To improve MPNN storage capacity we turn to the sequence modeling literature, which has a long history of tackling equivalent problems (Hochreiter & Schmidhuber 1997 Orvieto et al. 2023] Gu & Dao 2023 Beck et al., 2024, Arora et al. (024).. Taking inspiration from these works, we introduce an MPNN architecture that utilizes associative memory (Beck et al. 2024 Schlag et al.
2021 Hopfield
1982). and demonstrate that this exhibits improved storage capacity.
we re-characterize over- squashing into two distinet failure modes: saturating capacity and low sensitivity, which we term capacity over-squashing and sensitivity over-squashing respectively. We discuss in Section 3.1 the pitfalls of widely used over- wver-squshhin tasks, which either fail evaluate capacity at all, or evaluate the two issues in tandem and are thus unable to separate their effects. In Section 3.2 we introduce a novel synthetic task, which to our knowledge is the first that measures capacity over-squashing in isolation. In Section 4 we present new MPNN architecture based on the recent xLSTM architec- ture (Beck et al.) 2024], which uses associative memory to increase capacity, explicitly targeting this capacity oqur-squa viewpoint. Section S demmosttates that this architecture performs well on our synthetic capacity task and a range of real-world benchmarks, and Section 5.2 demonstrates occur separately from sensitivity over-squashing.
Contributions. Our main contributions are as follows. In Section 3
empirically that capacity over-squashing
2 BACKGROUND AND RELATED WORK
Message Passing Neural Networks Let a graph G be a tuple (V,E) where V is the set of nodes and E the set of edges. An edge from node to is denoted (u, v) E E. The connectivity is encoded by the adjacency matrix A E RD/x//V,, where Anv if (u, v) E E and 0 otherwise. Each node has a feature vector I. E Rdd
GNNs are functions fe: (G, {x,}) + y with parameters O trained via gradient descent to predict node- or graph-level labels y. These models typically take the form of MPNNs, which compute latent representations by composing L layers of the following node-wise operation:
h = (n (0 (u, v) E E))).
(1)
where si(() is a permutation-innarian aggregator, ((') combines neighbor messages with the previ- ous embedding and h ... Throughout, we use "GNN" and "MPNN" interchangeably. Note we depart from the more usual notation of & for layer index to avoid confusion with keys, introduced The most commonly used aggregation function takes the form
in Section 3.2
2ill) ((h(((( (u, v) E E)) ΣO o0 (1-1).
where O E | is some message-passing matrix. For GCN (Kipf & Welling 2017 O D-1/2 AD- with Ā = A + I for diagonal D RRVIx with DR: E3 Agj. We frequently
2

---

Published as a conference paper at ICLR 2026
denote the set of mnessagepasssing passing neighbors of node as N₂ fo E V maassge-passingg matrix is layer-dependent, we may superscript this with a layer index.
Our * 0} if the
Fast Weight Programmers Fast Weight Programmers (FWPs) are a class of neural network moti- vated by the idea of allowing variable network weights dependent on the input termed fast weights. One method to "program" the fast weights is to take outer products of learned projections of the
input (Schmidhuber] [992]. Schlag et al. (202I) observe that up to normalization and activation function differences linear Transformers (Katharopoulos et al. 2020) are equivalent to FWPs.
xLSTTM: Associative Memory for Language Modeling Recent work Beck et al. (0024 2025)
introduced XLSTM, development of the original LSTM Hochreiter & Schmidhuber 1997 archi-
tecture that resulted in a performant recurrent neural network capable of language modeling. Of relevance to our work are the following limitations that xLSTM aims to address: the inability to "revise storage decisions" and the limited storage capacity of the scalar cell states. The first of these is addressed through modifying the original LSTM gating use exponential activation functions. The second is addressed by introducing associative memory, updated using an outer product update rule equivalent that of FWPs store keys and values (see Appendix B for more details).
3 THE TWO FAILURE MODES OF OVER-SQUASHING
Over-squashing was initially introduced by Alon & Yahav (2021) as an issue of storage capacity. They observed that recurrent sequence models exhibit a bottleneck in representing all the informa- tion from their past inputs, and this bottleneck exists in more harmful form in GNNs, in which the information receptive field grows exponentially. They introduced a synthetic task to measure over-squashing by propagating information through various sizes of binary tree.
Later research identified that this computational graph bottleneck also resulted in low sensitivity and issues of signal propagation. [TTppiig et al. (2022) Di Giovanni et al. (202a)) quantified this low sensitivity via the Jacobian of node representations, establishing the following sensitivity bound: for an MPNN with layers, Go Lipschitz constant of the activation, w maximal entry-value over weight matrices, d embedding dimension and E V, one has
topology
ah
S
(Cowdd) (0)) uv
(3)
[0] ah
L
model
where O is the message passing matrix used by the MPNN as in Equation (2). lishes that low sensitivity results from both graph topology as well as factors intrinsic the MPNN model. In particular, sensitivity is lowered by the nature of the message-passinng successive powers of a degree-normalized adjacency matrix. It is also lowered by the contractive nature of the nonlinearity a and the values of the weight matrices, as established in (Arroyo et al., 20256). Despite this analysis being purely one of sensitivity rather than capacity, it was also termed over-squa and has been successful in establishing links to other areas, including the expressive power of MPNNs (Di Giovanni et al.) 20236) and graph effective resistance (Black et al.] 2023).
This bound estab-
where the culprit
We argue that there are two distinct problems arising from bottlenecks in MPNNs: reduced sensi- tivity (sensitivity over-squashing) and saturating storuge capacity (capacity over-squashing). Due to the influential paper of Topping et al. (2022) the sensitivity viewpoint on over-squashing has thus far been the predominant approach in the literature; in this work, we seek to revisit the storage capacity viewpoint and investigate how this issue can be avoided. We define storage capacity the amount of information that can be stored in a node's 's representation for later use: a representation is saturated when it is unable to store any more information.
Conflation With Depth The vast majority of existing research links over-squashing with depth. To an extent, this is justified: the bound of Equation (3) decreases exponentially with MPNN depth, and real-world graphs tend to exhibit receptive fields that grow exponentially in depth, leading to capacity quickly becoming a problem for deep MPNNs. However, alongside recent work (Amaizz) Rodriguez & Errica, 2025), ) we highlight that over-squashing is not exclusively problem of depth: bottlenecks can be observed in single-layer GNNs acting on high-degree nodes - we exploit this fact in our synthetic task of Section 3.2 Furthermore, in studying over-squashin only in the deep
regime, much of the literature has conflated the problem with issues of vanishing gradients, them
selves closely linked to the related problem of over-smoothing Di Giovanni et al. (002b)) Ar-
3

---

Published as a conference paper at ICLR 2026
royo et al. (2025b) give more precise treatment of how the issue of over-squashing relates to depth, through werrssgo (zero collapse) and vanishing gradients. In this work we study over- squashing in the shallow regime: this allows to isolate the issue of saturating capacity, avoiding the effects of depth on both reduced sensitivity (Equation and vanishing gradients.
3.1 EXISTING OVER- WVER-SQUASHING TASKS DO NOT (ONLY) TEST CAPACITY
An instructive way of contrasting sensitivity against capacity is via synthetic tasks. The most common of these used to assess over-squashing are the Ring- Transfer tasks of Di Giovanni et al. (2023a). The goal of these tests is for a MPNN to 'transfer' fea- tures contained at a target node to a source node, across large graph distance. Various graphs tested, in particular ring of nodes, but the common feature is that there exists long shortest-path from the source to target node. All of these exhibit an exponentially growing receptive field of least 2 for l layers, since each node is connected to at least two others; repeated aggregation and application of MPNN layers and nonlinearities makes this good test of the sensitivity-
Figure 1: Computational graphs. Left: Ring-
Transfer (Di Giovanni et al. 2023a). Middle:
(Alon & Yahav) 2021). Right: NAR, introduced in Sec-
Tree WeighhoossMteen
tion 32 Nodes with informative features are
green, background gray. Red node is trained to solve the task.
Deep Graph
Identity Tanb
ReLU
Shallow Graph
GELU
view of over- ver-squashing.
However, this task is particularly ill-equipped to test the issue of storage capacity, as the only rele- vant information in the graph is that of the target node, and all intermediate nodes are assigned con- stant vectors of ones. In this way, there is only sin- gle node's representation worth of information to be transferred. It is unclear how much this task mea- sures behavior found in real-world tasks: exponen- tially growing receptive fields will not be padded by nodes with identical representations. Figure | (left) visualizes the computational graph of RkingTransfer demonstrating that it is dominated by nodes con- taining no information. Therefore, this task exhibits a large computational bottleneck without any issues of saturating capacity: this highlights the fact that, beyond the computational bottleneck, saturated ca- pacity is at least also dependent on the information content of the task.
10
Janahinn
10-9
10-8
10
25
50
75
100
125
Lead Node Count
Figure
2: Log Jacobian norms. "Deep" graphs are binary trees of Tree-Nei Mii--NeihioorsMatc. (Alon & Yahav, 202T); "Shallow" graphs are single-level trees with the same number of leaves. A GCN of depth equal to tree depth acts on each.
Jacobian norms are [ah (L) /ah, (0) for root and leaf (red/green Figure T. Shaded area is standard deviation.
Alon & Yahav/ (2021) introduced the Tree-Ne Tree--Nei.hiooosMateee ghboos task to measure capacity by prop- agating information from the leaf nodes of variable-size binary tree. It shares similarities with the task we introduce in Section[.22jin that it controls the amount of information that is forced into single node representation. However, it propagates this information through deep binary tree, requiring variable-depth MPNNs. This significantly harms sensitivity: we visualize Jacobian norms of GCN acting on deep binary tree single layer tree with matching leaf counts Figure [] demonstrating that this sensitivity drops off far faster for deep GCNs. This is unsurprising given the bound of Equation B : deep GCNs must additionally contend with "model" squashing terms of nonlinearity and weight contraction that scale exponentially with depth. Therefore performance degradation trends are due to both 1) saturating capacity and 2) low sensitivity; deep tasks such as Tree-Me Ne ghborsMatch are impacted by both over-squashin issues, rather than isolating the issue of capacity.
3.2 NEIGHBOR ASSOCIATIVE RECALL: ISOLATING STORAGE CAPACITY
We investigate storage capacity by measuring associative recall: this is common approach taken in the sequence-modellne literature (Ba et al. 2016; [Schlag et al. 202T Arora et al.) [2224] Jelassi al. 2024), in which the question of model storage capacity also clearly of interest. These
4

---

Published as a conference paper at ICLR 2026
synthetic tasks involve presenting the model with sequence of key value pairs followed by query that corresponds to one of the presented keys, and the model must return the associated value.
To this end, we introduce task that we refer to as Neighbor Associative Recall (NAR). Whereas the sequence associative recall tasks measure the ability of a model to recall previous information from variable-length sequence, our graph adaptation is designed to measure the ability of GNN to recall information from the previous message passing round over a variable number of neighbors.
The task is designed follows. For given neighborhood size N we create graph of N + nodes. This graph consists of N "neighbor" nodes, a central node to which they are all connected, an inter- mediate node connected to the central node, and "query" node connected only to the intermediate node. An example such graph is visualized in Figure 3
For a fixed neighborhood size N we define a fixed set of keys and values, N = |K] = [V], and a pair of learned vector embedding functions es : - Rd e. V + Raa for embedding dimension demb- Each of the neighbor nodes n has a different assigned key kn E K, and also a value Un E V. randomly sam- pled with replacement. The input feature vector of these nodes is a concatenation of the two learned embeddings In = [kx(k)); e [un)] E 2den. The intermediate node and central node both have zero-valued feature vectors. Associated with the query node q is a randomly sampled key-value node m: the input feature vector for the query node consists of the corresponding key embedding con- catenated with a vector of zeroes, Fg [ex (km)): 0] e g2ddu, The model is trained such that the central node must predict the value Um associated with the sampled key node. Training via cross-entropy loss where the tar- get of the central node is one-hot vector corresponding fixed ordering of This approach can be viewed a graph adaptation of the sequence associative recall task of SShhlag et al.) (02T). Results are presented in Section [5.]] An alternative formulation of this task with regression target is discussed in Appendix D.8
(km) (e((vm)
( (o)
(ea(ki))
0
Figure 3: An example graph with N 5 from the NAR task. Key-value nodes are shown in blue, the central node in red and the query node in green. this graph, is the randomly sampled index of the key-value node associated with query node q. The target for this graph is a one-hot vector corresponding to Um-
NAR is designed such that the receptive field of the central node will comprise only the neighbor nodes in the first layer. In order to perfectly solve the task, it must store all of the key-value informa- tion in this initial receptive field, as it is impossible to limit the scope of the information that might later be required. In the second layer, the receptive field will include the query node: now, the model must selectively recall the correct value from its immediate neighbors.
This task is novel as it assesses over-squashing in the shallow regime: MPNNs tested in Section 5.1 consist of just two message passing layers. This more effectively isolates the issue of capacity, without secondary effects from low sensitivity and vanishing gradients as visualized in Figure
4 GLSTM: COMBINING GRAPH NETWORKS AND ASSOCIATIVE MEMORY
Prior work on over-squashing has focused almost exclusively on mitigating sensitivity issues, often through graph rewiring (Gasteiger et al., 2019; Gutteridge al. 2023 Nguyen et al. 2023). Some work has implicitly tackled capacity over squashing by moderating the flow of information into node representations (Bresson & Laurent 2017 Finkelshtein et al. 2024 Errica et al. 2025) thus reducing capacity requirements, but we are unaware of any work that has attempted to increase capacity at an architecture level. Motivated by memory-capacity gains in sequence models (Ba et al., 2016 Beck et al. 2024), we introduce associative memory into an MPNN architecture to explicitly enlarge its informatioon-stragee capacity: we measure this in the graph setting using the NAR task introduced above. We further introduce the gating scheme of Beck et al. (2024) to investigate its efficacy in the graph setting, given strong sequence modeling performance. Since these adaptations are inspired in part by their successful use in STM, we refer to our related graph architecture as gLSTM.
5

---

Published as a conference paper at ICLR 2026
For any node u layer in addition to the usual MPNN vector hidden state h gLSTM maintains a matrix hidden state ( The initial hidden state h is the imput node feature vector Tu. Keys and values are used to update ((O) via an FWP-style outer product rule: these are projections of the previous vector hidden state h! The next vector hidden state h determined by "querying" cl via matrix multiplication with another projection of the previous vector hidden states.
The modified gLSTM update equations given below. Highlighted in blue are the differences to XLSTM. Biases correspond exactly to XLSTM (Appendix B and are omitted for clarity.
State (and normalization) updates:
Query / Key / Value computation:
C fu cHI
1)
Σ
10
@ k
d
W
h
(1-1;;
Σ he-1)
UU
n f
n (1-1) n( +
Σ
VE
h 1
Weh
"EA
Vd
m max (f + m mm--"
U
70
Ve E u
v W. w,hh-i)
The square brackets above denote vector concatenation. Concatenating the hidden state for the node and its neighbours in this way keeps them separate and allows the query which will determine what is retrieved from the matrix memory to separately depend on both the previous state of the node itself and the previous states of its neighbours.
Gate computation:
Output:
i exp
m!
70 w h (-
qu
h max
(1)
(1) qu
( exp o
+ m
m0()
fu w/ h (1-1)
nu
(0 o (1) 2
h
(0
@ Wohl-1)
Block Structure ArrOOO et al. (025b) note that sensitivity over-squashing issues are largely caused by vanishing gradients- a phenomenon well-explored in the requence-modeling literature. In attempt address this, glSTTM uses similar block structure to the mLSTM block upon which it is based, Of particular importance is the residual connection - which brings the norm of the layer-wise Jacobian the edge of chaos and use of input and hidden norms, which regulate the magnitude of the Jacobian norms. viguriiissualizes
visualizes the block structure of gLSTM that we employ.
K-Hop Aggregation Following (2025b) we combine the memory capabilities of the xLSTM block with a highly connected message passing graph structure: employing k-hop aggregation scheme. In this setting, each node at layer I will aggregate information from the neighborhood
et al.
C
4
JUEAD
^ { (g =},
where dg V x V - Rzo is the length of the minimal walk connecting nodes and v. This approach resembles that of Ding et al. (202)). but with an additional recurrence: hid- den states are used as input at each step. This substantially changes the way information can propagate through the graph. Furthermore, it also has links to ChebNet (Defferrard et al. 2017), which has recently been found to per- form strongly on long-range tasks (Hariri et al,] 2025
Figure 4: gLSTM block structure. Gates shown in orange, query/key/value dark blue. Aggr. repre- sents aggregation across neighborhoods. Symbols O, 8 +, denote Hadamard product, outer prod- uct, vector addition, matrix multiplication.

---

Published as a conference paper at ICLR 2026
This aggregation scheme appears to greatly improve gLSTM performance: synthetic task in Section 5.1 significantly benefits from this aggregation scheme, and the ablations in Appendix D.2 demonstrate that it improves performance in all but one of the tested benchmarks. We hypothesize that - in addition to providing a highly connected computational graph that lessens over-squashing sensitivity bottleneck issues this is because it also provides extremely useful inductive bias for the recall mechanism of gLSTM. Information that has previously been stored in the associative memory is not then included in later message passing rounds, and later nodes are able query this memory in isolation.
EXPERIMENTS
5.1
NEIGHBOR ASSOCIATIVE RECALL
We train various models on NAR with varying neighbor count N, with results shown in Figure Sa Throughout this section we compare gLSTM using K-hop aggregation GCN using standard ag- gregation, since gLSTTM performs significantly better in this task when using K-hop aggregation whereas GCN performance harmed by K-hop. We present additional results in Appendix [D.7 where separate by aggregation method and include results for larger number of models. A comparison of the number of trainable parameters is shown in Figure 5b Fair comparison between matrix and vector memory nontrivial, we select these parameter counts "favor" GCN.
These results demonstrate that gLSTM shows significantly improved recall abilities compared to GCN. gLSTM retains perfect recall until the number of neighbors equals the memory dimension of the model: beyond this is where capacity over-squashing appears to become a problem. This agrees with intuition, since the maximum number of orthogonal key vectors (and separately, value vectors) is equal to the memory dimension. However, it is interesting to note how the performance decreases slowly as the neighbor count exceeds this limit, particularly for higher memory dimensions: this ap- pears to be a graph analog of the "graceful saturation" described by SSoolnsky (1990). By contrast, capacity ver-squashing starts much earlier at just N for the largest GCN model tested.
gLSSMM L.M dias.
Acconsry
0.75
gLSTTM dim. 16
gLSTM
0.50
+
GCN dim.
0.25
GCN dima 125
dim.
256
0.00
20
80
100
GCX
Number Neighhours
(a) Accuracy
(b) Parameter counts
Figure 5: Test-set mean Accuracy (standard deviation shaded) for the NAR task, for gLSTM and GCN models with various hidden dimensions shown in Figure Sa number of trainable parameters
Figure 5b Note that gLSTM uses K-hop aggregation here, whereas GCN does not; see Ap- pendix D. for separated performance by aggregation strategy.
5.2
How DOES CAPACITY RELATE TO SENSITIVITY?
In this section, we investigate empirically how capacity over-squashing - as measured by perfor- mance NAR relates to sensitivity over-squashing.
We directly measure the Jacobian norm of Topping et al. (022)) Di Giovanni et al. (003a)) com- puting the sensitivity of the output feature vector on the central (output) node to the input vectors on the key-value neighbor nodes n, jōh!" /0x,/zz. These results are visualized in Figure 6a
We see therefore that sensitivity, measured by the Jacobian norm, does not correlate with NAR performance. Given that NAR performance degradation is due to capacity over-squashing, we there- fore observe that capacity over-squashing clear from the fact that 1) sensitivity increases consistently for GCN models above point where it matches initial sensitivity, despite increase in performance and 2) sensitivity for
without sensitivity over-squashing. This is
to the

---

Published as a conference paper at ICLR 2026
gLSTM tends to carry increasing beyond where performance starts to degrade. We note these trends - as with all observations we make this section hold true for the NAR regression task in Appendix D.8.1
However, if we examine the difference in Jacobian norms between the neighbor nodes which are selected (those which have key corresponding to the query node) vs background, align with our notion of capacity. Figure viguraieavvssualizes visualizes the ratio of Jacobian norms for selected nodes that for background nodes. We observe that for all GCN models this ratio quickly falls unity at the point where capacity over-squashing starts to occur, and gLSTM ratios consistently plateau and start slowly decrease at their memory dimension, similarly coinciding with capacity over- squashing. It appears therefore that capacity over- wwurshqu harms model's s ability to be selectively sensitive different nodes in the NAR task.
trends that
Fall Jaobian Noma
Jocohin Norm Rotion
104
XL8133 cim.
318TM
10²
c15TM dim. 52
GCN 64
10'
GCN dim.
GCN dim. 256
20
40
60
90
100
20
40
50)
100
Neighhoours
Noig Monur
(a) Jacobian
(b) Jacobian norm ratios
Figure 6: Left: Mean Jacobian norms for different SLSTM and GCN models, with varying number of neighbors in the NAR task. Right: Mean ratio between the Jacobian norms the selected (key corresponds to query) to background (key is different from query) neighbor nodes, for varying model dimensions. Standard deviation shaded in both plots.
Another over-squashing sensitivity metric is that of Di Giovanni et al. (2023b), who introduce the maximal mixing metric. For node-level function Rxxa gaxa the mixing of features associ- ated with nodes u, at a given node i is defined as
03
(x))
mix(i, u. max
Although motivated through intuition of mixing, we observe the mixed partial derivative can equally be viewed as composition of partial derivatives quantifying selective sensitivity how much the sensitivity with respect to one node feature varies with respect to another node feature. In this respect, we expect be highly relevant to the sensitivity ratios visible in Figures [ and I0
To study this empirically for NAR, we take the maximum over the measured Hessians for different models. These Hessian 3-tensors are large, so we further limit to subset of the overall tensor in order to compute them available hardware: we are most interested in how the output sensitivity the neighbor value vectors varies with the query vector, so we limit to the corresponding input dimensions. For the central, neighbor and query nodes n, g this adapted mixing metric is
82
he
mix(e, n.g)
max OSa<N,
b (xx.)) 3 (
05
dust S2d
which we plot in Figure 7 We see that gLSTM consistently exhibits greater maximum Hessian values than GCN, and that this collapses for GCN models above neighbors, consistent with the drop in performance. As with the Jacobian ratios, we see plateauing and slow decrease of maximum Hessian values above the memory dimension, but these trends are less pronounced.
8

---

Published as a conference paper at ICLR 2026
Hessiun Value
g.STM dim.
gLSTM dim.
10-9
gLSTM dim. 32
GCN diz.. 61
GCN dim. 128
GUN
Number Nelghhours
Figure 7: Mean of the maximum Hessian values for different gLSTM and GCN models, averaged across test set examples and different neighbor nodes. Standard deviation shaded.
5.3 LONG RANGE BENCHMARKS
Table 1: Mcan and standard deviation of 1o (MSE), averaged over 4 random weight initializations on the GPP tasks from Gravina et al. (2023). from which we report baselines. See Appendix D.1 for discussion of baseline choice. Top score in bold, second underlined. Lower is better.
Method
Diam.
Ecc.
SSSP
GCN
0.742 = 0.047
0,846 = 0.003
0.950 = 0.000
GAT
0.822 + 0.075
0.695 # 0.150
GraphSAGE
0.865 : 0.40
0.286 0.184
0.786 0.021
GIN
0.613 0.099
0.000
GCNII
0.529 # 0.057
-1.132 0.034
DGC
0.603 # 0.005
0.826
-0.148 + 0.023
GRAND
0.672 # 0.049
0.660 0.139
-0.094 # 0.340
A-DGN
-0,546 + 0.033
0.305 0.118
-3.402 # 0.137
gLSTM (ours)
-0.715 + 0.030
-4.036 + 0.311
-2,836 + 0.178
K-hop
0.042 + 0.123
0.673 = 0.021
-3.377 + 0.142
We evaluate gLSTT on the Graph Property Prediction (GPP) tasks from Gravina et al. 2023) and the Long Range Graph Benchmark (LRGB) from Dwivedi et al. (2022). These benchmarks are both designed to require long range interactions to solve, and thus are an in- teresting test of the ability of gLSTM come over-squashing and over-smoothing in real world tasks order facilitate long range interactions. Performance is reported in Table and Table respectively.
Table 2: Mean and standard deviation on LRGB (Dwivedi et al. 2022), averaged over four ran- dom weight initializations. Baselines from the LRGB reevaluation of Tönshoff et al. (2024). K- hop methods from Arroyo et (2025b). rewiring baseline from Barbero et al. (2024b). All meth- ods adhere 500k parameter limit. Top score in bold, second underlined.
Method
Peptides-Fumm Peptides-Struct
AP (t)
MAE (4)
gLSTM achieves comfortably state of the art results on the Diameter and Eccentricity GPP tasks, and very strong performance on SSSP: notably SSSP the only tested task in which k-hop decreases performance. sults show that gLSTM achieves strong per- formance in Peptides-Fune Func but relatively weak We hypothe- Peptides-
GCN
0.6860+0.0050
0.246020.0007
GatedGCN
0.6765+0.00477
0.2477+0.0009
GINE
0.6621+0.008
0.2473+0.0017
GPS
0.6534+0.0091
0.2509+0.0014
LRGB re-
K-hop methods KGCN-SSM
0.6902+0.0022 0.2581+0.0003
performance on Peptides-Strun size that the weaker performance Struct may be due to long-range interactions being less relevant for this task, which is very effectively solved by a few-layer GCN. See Appendix D.2 for gLSTM ablations on these benchmarks and Appendix D.5 for details around hyperparameters used.
DRew-GCN 0.6804#0.0144
0.2766+0.0019
Rewiring LASER
0.6440+0.0010
0.304340.0019
gLSTM (ours)
0.7250+0.0023 0.2527+0.0015
K-hop 0.6030#0.0096 0.2638+0.0010

---

Published as a conference paper at ICLR 2026
6 CONCLUSION
In this work, revisit over-squashing, disambiguating two bottleneck-relatte issues of sensitivity over-squashing and capacity over-squashing. We introduce a synthetic task that measures capacity over-squashing in isolation and we show that associative memory improve MPNN capacity. The resulting architecture achieves strong results on real-world benchmarks.
Many avenues remain open. Whereas the sensitivity issue of over-squashing has a mathematical basis via the node Jacobian, to our knowledge, the capacity issue does not. Theo- retically quantifying this capacity could afford similar directions those explored via sensitivity, establishing links to topology and model properties. With regards to architecture, we translate to graph setting the gating and associative memory of xLSTM but do not retain the efficiency and par- allel training, leaving open future work on more efficient MPNNs: we highlight that the recent work of Pöppel al. (2025) achieves these efficiency gains in the specific case of directed acyclic graphs. Another potential avenue would be to apply our findings to prevention of issues of over-mixing and Transformer architectures.
Future Work
representational collapse (Barbero al. 2024a 2025)
REPRODUCIBILITY STATEMENT
We make available all of our code and experiment configurations aid reproduction of results. Our experiments utilize the widely-used PyTorch Geometric GraphGym (You et al. 2020) framework which defines a standard framework for MPNN research.
For easiest reproduction of our results, please consult the readme in the code repository provided in Appendix [ The repository includes all necessary information to run the experiments: particular, configs containing the hyperparameters used (also reported in Appendix D.5) and code for all plots used the paper.
ACKNOWLEDGMENTS
HB acknowledges funding support from the EPSRC Centre for Doctoral Training in Autonomous Intelligent Machines and Systems No. EP/S024050/1. MB is partially supported by the EP- SRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and EPSRC Al Hub No.
EP/Y028872/1.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Adrian Arnaiz-Rodin Modiz-Rod and Federico Errica. Oversmoothing. "oversquashing".. heterophily,
long-range, and more: Demystifying common beliefs in graph machine learning. arXiv preprint arXiv:2505. 155447 2025.
Simran Arora, Sabri Eyuboglu, Aman Timalsina. Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Ré. Zoology: Measuring and improving recall in efficient language mod- cls. In Proceedings of 12th International Conference Learning Representations (ICLR). ICLR, 2024.
Álvaro Arroyo, Federico Barbero, Hugh Blayney, Michael Bronstein, Xiaowen Dong, Pietro Liò, Razvan Pascanu, and Pierre Vandergheynst. Bridging graph neural networks and large language models: A survey and unified perspective. 2025a.
Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xi- aowen Dong, Michael Bronstein, and Pierre Vandergheynst. On vanishing gradients, over- smoothing, and over-squashing in gnns: Bridging recurrent and graph learning. arXiv preprint 200i:2500..08811 2025b.
10

---

Published as a conference paper at ICLR 2026
Jimmy Ba, Geoffrey E Hinton, Volodymyr Mnih, Joel Z Leibo, and Catalin lonescu. Using fast weights to attend to the recent past. Advances in neural information processing systems, 29, 2016.
Federico Barbero, Andrea Banino, Steven Kapturowski, Dharshan Kumaran, João Madeira Araújo, Oleksandr Vitvitskyi. Razvan Pascanu, and Petar Veličkovié. Transformers need glasses! infor- mation over-squashing in language tasks. Advances in Neural Information Processing Systems, 37:98111-988 2024a.
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, and Francesco Di Gio- vanni. Locality-aware graph rewiring in GNNs. In The Twelfth International Conference Learning Representations, 2024b.
Federico Barbero, Alvaro Amoоo, Xiangming Gu, Christos Perivolaropoulos, Michael Bronstein, Petar Veličković, and Razvan Pascanu. Why do lims attend to the first token? arXiv preprint arXiv:2504.02732, 2025.
Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xlstm: Extended long short-term memory. Advances in Neural Information Processing Systems, 37:107547- 107603, 2024.
Maximilian Beck, Korbinian Pöppel, Phillip Lippe, Richard Kurle, Patrick Blies, Günter Klam- bauer, Sebastian Böck, and Sepp Hochreiter. xLSTM 7b: A recurrent LLM for fast and efficient inference. In Forty-second International Conference on Machine Learning, 2025.
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, pp. 2528-2547. PMLR, 2023.
Xavier Bresson and Thomas Laurent. Residual arXiv:1711.07553. 2017.
gated graph convnets.
arXiv preprint
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs, 2014.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal
neighbourhood aggregation for graph nets. Advances in neural information processing systems, 33:13260-1327,, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering, 2017.
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International conference on machine learning, pp. 7865-7885. PMLR, 2023a.
Francesco Di Giovanni, Konstantin Rusch, Michael Bronstein, Andreea Deac, Mare Lackenby, Siddhartha Mishra, and Petar Veličkovié. How does over-squashing affect the power of gnns? Transactions on Machine Learning Research, 2024, 2023b.
Yuhui Ding, Antonio Orvieto, Bobby He, and Thomas Hofmann. Recurrent distance filtering for graph representation learning. International Conference on Machine Learning, pp. 11002- 11015. PMLR, 2024.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22340, 2022.
Moshe Eliasof, Alessio Gravina, Andrea Ceni. Claudio Gallicchio, Davide Bacciu, and Carola- Bibiane Schönlieb. Grama: Adaptive graph autoregressive moving average models. arXiv preprint arXiv:2501. /2732, 2025.

---

Published as a conference paper at ICLR 2026
Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, and Francesco Alesiani. Adaptive message passing: A general framework to mitigate oversmooth- ing, oversquashing, and underreaching. In serty- International Conference Machine Learning, 2025.
Ben Finkelshtein, Xingyue Huang, Michael Bronstein, and ismail Ilkan Ceylan. Cooperative graph neural networks. In Proceedings of the 41 International Conference on Machine Learning, pp- 13633-13659, 2024.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, 2005., volume 2, pp. 729-734 IEEE, 2005.
Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Anti-symmetric DGN: a stable architec- ture for deep graph networks. In The Eleventh International Conference on Learning Represen- tations, 2023.
Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, and Carola-Bibiane Schönlieb. On oversquashing in graph neural networks through the lens of dynamical systems. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 19906-16914, 2025.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dy- namically rewired message passing with delay. In International Conference Machine Learning, pp. 12252-12267. PMLR, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Ali Hariri, Álvaro Arroyo, Alessio Gravina, Moshe Eliasof, Carola-Bibiane Schönlieb, Davide Bacciu, Kamyar Azizzadenesheli, Xiaowen Dong, and Pierre Vandergheynst. Return of cheb- net: Understanding and improving overlooked gnn on long range tasks. arXiv preprint arXiv:2506.07624, 2025.
Simon Heilig, Alessio Gravina, Alessandro Trenta, Claudio Gallicchio, and Davide Bacciu. Port- hamiltonian architectural bias for long-range propagation deep graph networks. In The Thir- feenth International Conference on Learning Representations, 2025.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
John J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 7955):5554-2558 1982.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 1112218-22111 8-22133, 2020.
Samy Jelassi, David Brandfonbrener, Sham M Kakade, and Eran Malach. Repeat after Trans- formers are better than state space models at copying. In International Conference on Machine Learning, pp. 11502221521. PMLR, 2024.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International conference ma- chine learning, pp. 5156-5165. PMLR, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference Learning Representations, 2017.
12

---

Published as a conference paper at ICLR 2026
Alessio Micheli. Neural Network for Graphs: A Contextual Constructive Approach. IEEE Trans- actions on Neural Networks, 20(3):498 -11888551111111111111111 2009.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In In- lernational Conference on Machine Learning, pp. 25956-25979, PMLR, 2023.
Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pas- canu, and Soham De. Resurrecting recurrent neural networks for long sequences. In International Conference Machine Learning, pp. 26670-26698, PMLR, 2023.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint ar arXiv:2302. 2023.
Korbinian Pöppel, Richard Freinschlag, Thomas Schmied, Wei Lin, and Sepp Hochreiter. PLSTM: parallelizable linear source transition mark networks. In ICML 2025 Workshop on Long-Context Foundation Models, 2025.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:4451--14, 2022.
Danial Saber and Amirali Salehi-Abari. Over-squashing in gnns and causal inference of rewiring strategies. arXiv preprint arXiv:2508.044 09265, 2025.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80) 2008.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers secretly fast weight programmers. In International conference on machine learning, pp. 9355-9366. PMLR, 2021.
Jürgen Schmidhuber. Learning to control fast- memories: memories An alternaivve to dynamic recurrent networks. Neural Computation, 4(1):131-139, 1992.
Paul Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial intelligence, 46(1-2):159-2) 1990.
Alessandro Sperduti. Encoding labeled graphs by labeling raam. Advances in Neural Information Processing Systems, 6, 1993.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassess- ing the long-range graph benchmark. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs curvature. Interna- tional Conference on Learning Representations, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ArXiv, 2018.
Keyulu Xu. Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rX0v:1810.000 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Design space for graph neural networks. In NewrIPS, 2020.
13

---

Published as a conference paper at ICLR 2026
A RELATIONSHIP TO COMPUTATIONAL (AND TOPOLOGICAL) BOTTLENECKS
Linaiz-RRdrigee & Errica 2025) identify a separation in the over-squashing literature between the
initial work of Alon & Yahav (202T) and the later work of Topping et al. (2022); Di Giovanni et al.
(023a). They point out that the original over-squashing definition of (Alon & Yahay (022]) was associated with the computational tree, and Topping et al. (2022) later connected over-squashing to the existence of topological bottlenecks. They suggest that these definitions constitute different
problems, and that as community we should discard the term "over-squashing" and separate it
into (at least) two separate terms: (1) computational tree bottlenecks and (2) topological bottlenecks (in the underlying graph).
This makes a valuable point: topological bottlenecks may or may not be involved when structural issues exist with the computational tree. The authors fairly point out that the umbrella term "over- squashing" has sometimes hidden some of the complexity of the problem, and the field may ben- efit from work identifying explicitly whether it is dealing with topological bottlenecks (as is the case with e.g. rewiring) or bottlenecks of the computational tree (e.g. adaptive message passing). We're unsure that framing these as sepurate is helpful, since topological bottlenecks must be me- diated through the computational tree in order to impact message passing, but the point stands that some methods to combat veerssua specifically target topological bottlenecks (and as such any changes to the computational graph are implicit), and some methods target general computational bottlenecks, and that this is not always clear.
Despite the complexity, we believe the term ""ver-squashhng" still has utility describes issues that arise from the presence of bottlenecks and depth in the computational tree. The distinction made by ArrnazzRRdrriuez & Errica (2025) clarifies that sometimes these issues arise due to topological bottlenecks in the underlying graph, and sometimes they do not. The relevance of our work is then in exploring how this structure manifests as performance issues, and the main body of our paper argues that this is due to separate issues of capacity and sensitivity.
umbrella term that
Precisely how issues of capacity and sensitivity relate the structure of the computational tree and the presence of bottlenecks is complex, although we take initial steps to clarify this in our paper. would not be correct to suggest for example that capacity issues correspond computational bottlenecks and low sensitivity to topological bottlenecks. In particular:
Our RingTTransee discussion of Section 3.1 highlights that computational bottlenecks can exist without capacity issues.
Arnaiz & Errica (2025) highlight that low sensitivity does not necessarily imply the existence of computational tree bottlenecks (or topological bottlenecks).
On the other hand, both topological bottlenecks and general computational bottlenecks can cause low sensitivity. This clear since the Equation (3) defines an upper bound on sensitivity in terms of the computational tree (defined by successive powers of the message- passing matrix), and we refer the reader to the work of Topping al. (2022) for proofs in the case of specifically topological bottlenecks.
Additionally, while the discussion in this Appendix has so far focused on the computational tree, we highlight that the causes of the failure modes discussed in our work extend beyond structural issues: issues of capacity also depend at least on (1) information content of the task and (2) storage capacity of the model, as explored in Sections 3.1 and 3.2 respectively, and issues of sensitivity are highly dependent the model dynamics, explored in e.g. |Arroy et al. (2025b); Heilig et al. 2205
Gravina et al. (2023 2025)
B XLSTM UPDATE EQUATIONS
Beck et al. (2024) initially designed xLSTM as a combination of sLSTM blocks and mLSTM blocks using scala ar memory and matrix (associative) memory respectively. However, their follow up work (Beck et al. 2025) uses only mLSTM blocks, and these form the inspiration for gLSTM. Therefore, will exclusively introduce the ml STS block update equations in this section.
14

---

Published as a conference paper at ICLR 2026
The update equations, presented in similar manner to Section 4 State (and normalization) updates:
given below.
C f'C +'''t @ k²
(4)
n' f'n'=1 + i'kk"
(5)
m' max jt + +m mm'1133
(6)
Query / Key Value computation:
q¹ Wgy + by
k² 1
Wexx + bb
(8)
Vd
0² W.w' + bv
(9)
Gate computation:
cxp (i' - -m²)
= w x² + b;
(10)
f exp 8r + +m'-1- -m²)
f w x¹ + bj
(11)
o σ (od')
0' Wox' + bo
(12)
Output:
h' C² max {n'Tq'l:1]
(13)
h' = ④ h.
(14)
C DATASET DETAILS
In table Table 3
we present a summary of the statistics of the datasets used throughout this work. We use the standard splits provided for each of the datasets, using the standard loading functionality from GraphGym (and PyTorch Geometric). For GPP (without a default implementation in Py Torch Geometric) we use the original splits of Gravina et (2023): 5120 graphs as training set, 640 as validation set, and 1280 as test set.
For the NAR task (for all neighbor values), we use split of 8,000 train graphs, 1,000 validation graphs and 1,000 test graphs. We note that when testing gLSTM on this dataset, we vary the memory (matrix) dimension as described the main text, and set the vector dimension to twice that of the matrix dimension.
D ADDITIONAL EXPERIMENTS
Our code for reproducing all experimental results in the main paper and appendices is publicly available at /https://githii http.//uggghllaaeeegggg....
D.1 ADDITIONAL GPP BASELINES
We note that due to a subtle PyTorch issue in the original GPP code implementation, normalization not applied to the dataset targets. A refactor appears to have unknowingly fixed this issue in later iterations of the code so later experiments are run on a normalized variant of the dataset. Unfor- tunately, this results in unfair comparison, results can be substantially different between the two variants of the dataset.
Therefore, in the main body of the paper test only the baselines provided in the original GPP paper (Gravina et al.] 2003). as we are confident these use the un-normalized variant of the dataset, and this provides with the largest number of baselines test against. We additionally ensure
15

---

Published as a conference paper at ICLR 2026
Table Summary datasets used throughout this work. Node and edge values are the average per graph, where applicable. LRGB statistics retrieved from Dwivedi et al. (022), OGB statisties from
Hu al. (2020) Heterophilous from Platonov al. (2023). GPP statisties computed; dataset from
Gravina et al. (2023); Corso al. 2020)).
Dataset
Group
Task
Setting
#Graphs
Nodes
Edges
Peptides-Fums Func
LRGB
Graph cls. Graph reg.
Inductive
15,535
150.94
307.30
Peptides-Struct
LRGB
Inductive
15,535
150.94
307.30
Diameter
GPP
Graph reg-
Inductive
7,040
28.82
98.95
Eccentricity
GPP
Node reg.
Inductive
7,040
28.82
98.95
SSSP
GPP
Node reg.
Inductive
7,040
28.82
98.95
arXiv
OGB
Node cls. Node cls.
Transductive
1
169,343
1, 1,166,243
Products
OGB
Transductive
1
2,449,029
61,859,144
Amazon-Rating"
Heterophilous Heterophilous
Node cls. Node cls. Heterophilous
Transductive Transductive
1
24,492
93,050
Roman- Roman-Empire
1
22,662
32,927
Minesweeper
Node Transductive
10,000
39,402
that our method uses the same, un-normalized GPP variant. We separately test on the normalized version of the dataset, with results presented in Tad hyperparameters in Table This allows us to additionally test against a range of more recent methods that specifically target sensitivity over- squashing. We achieve state of the results the normalized variant of this benchmark.
Table 4: Mean and standard deviation of log (MS)), averaged over random weight initializations on the Normalized version of the GPP tasks from Gravina et al. (2023). Baselines reported from Arroyo al. (2025b); Eliasof al. (0255) Top score in bold. Lower better.
Method
Diam.
Eec.
SSSP
Differential Equation Inspired GNNs
SWAN
-0.598 + 0.115
-0.074 + 0.219
-3.543 + 0.083 -4.299 + 0.072
PH-DGN
-0.547 + 0.107
0.935 + 0.210
K-hop methods
DRew-GCN
-2.402 + 0.110
2..29 = 0.024
- -1.602 0.008
KGCN-SSM
-3.075 + 0.055
-4.265 + 0.178
-3.604 + 0.029
GPS
-0.512 = 0.043
0.608 + 0.028
-3599 + 0.155
GRAMA
-0.866 = 0.051
1.301 + 0.126
-3.335 = 0.070
gLSTM (ours)
-3.684 = 0.057
-5.912 # 1.116
-5.321 + 0.603
D.2 ABLATIONS
To identify what elements of the gLSTM architecture most important for performance on these benchmarks, we perform ablations on the GPP and LRGB datasets. For LRGB, task with param- eter limit, we ablate in different settings: the first is simply removing the ablated component, for which results are presented in Table 6 The second is to scale the hidden dimension h to keep the parameter count as close as possible to the 500k limit i.e. when removing gating, this will correspondingly increase the hidden dimension. We include these experiments as they more accu- rately represent the reality of testing a model variant on a task with a parameter limit; these results presented in Table 7 These two ablation settings show very similar results. GPP ablations
presented in Table 5
We that ablating gating only significantly reduces performance Peptides- Fupne other than this, it either leaves performance the same or in some cases, improves performance (GPP Ecc. in particular).
16

---

Published as a conference paper at ICLR 2026
Table 5: Ablation of gLSTM performance on Diam, Ecc, and SSSP from the GPP benchmark. Mean and standard deviation are reported, averaged over four random weight initializations. Other than ablation, all other model settings are held constant; thus ablations with gating removed have reduced parameter count.
Model
Diam.
Ecc.
SSSP
gLSTM
-0,715 0.030
-4.036 + 0.311
-2.836 0.178
Output gate
-0.70 0.05
-3.71 + 0.16
-2.77 0.19
Input gate
-0.75 + 0.01
-4.72 + 0.36
-3.27 + 0.16
- Forget gate
-0.71 0.03
-4.30 + 0.21
-3.14 + 0.07
All gates
-0.75 0.03
-4.14 + 0.42
-3.16 + 0.15
K-hop aggregation
0.04 + 0.12
0.67 + 0.02
-3.38 + 0.14
Table 6: Ablation of gLSTM performance on Peptides-Fuu and Peptides- Strruct from the LRGB. Mean and standard deviation are reported, averaged over four random weight initializations. Other than ablation, all other model settings are held constant; thus ablations with gating removed have reduced parameter count.
Model
Peptides-Func
Peptides-Struct
AP (1)
MAE (L)
gLSTM
0.7250 + 0.0023
0.2527 + 0.0015
Output gate
0.7086 + 0.0049
0.2540 + 0.0016
Input gate
0.7186 + 0.0029
0.2524 + 0.0027
Forget gate
0.7236 + 0.0063
0.2522 + 0.0011
All gates
0.7180 + 0.0088
0.2526 + 0.0012
Positional encoding
0.7208 + 0.0072
0.2539 + 0.0036
K-hop aggregation
0,6030 + 0.0096
0.2638 + 0.0010
Table 7: Ablation of gLSTM performance Peptides-Fung and -trrides-SStuct from the LRGB. Mean and standard deviation are reported, averaged over four random weight initializations. All methods adhere count as close to this as possible.
500k parameter limit such that hidden dimension varies keep parameter
Model
Peptides-Func
Peptides-Struct
AP (1)
MAE (L)
gLSTM
0.7250 +: 0.0023
0.2527 +: 0.0015
Output gate
0.7202 + 0.0056
0.2537 + 0.0011
Input gate
0.7193 + 0.0110
0.2518 + 0.0027
Forget gate
0.7148 + 0.0107
0.2545 + 0.0043
All gates
0.7188 + 0.0060
0.2528 + 0.0035
PPosiiional encoding
0.7211 + 0.0062
0.2601 + 0.0017
K-hop aggregation
0.6030 + 0.0096
0.2638 + 0.0010
17

---

Published as a conference paper at ICLR 2026
Table 8: Mean and standard deviation Heterophilic Datasets, averaged over four random weight initializations.
Model
Roman-empire
Amazon-ratings Minesweeper
Acc 1
Acc
AUC
MPNNs
GAT
+0.30
49.09
92.01 68
GAT (LapPE)
84.80=0.16
44.90+0.73
93.50+0.55
GAT (RWSE)
86.62
48.58 10.41
92.53
Gated-GCN
74.46
43.00
87.54
GCN
73.69 20.74
48.70
89.75
GCN (LapPE)
83.37
44.35
94.2640.49
GCN (RWSE)
84.84
46.40
93.84400.4
CO-GNN(E, ))
91.57
51.28++0.56
95,09+1.18
CO-GNN(H, pt)
91.37=0.35
54.17+0.37
90.31
SAGE
85.74
53.6310.25
93.51 10.57
Graph Transformers
Exphormer
89.03
53.51 10.46
90.74
NAGphormer
10.74
11.76
84.19
GOAT
71.59
44.61 +0.50
81.09+1.02
GPS
82.00
53.10
90.6340.67
GPSacN*Perfomeer (LapPE)
83.9640.58
48.20 40.207
93.8540.41
GPSaCN+Partomeer (RWSE)
84.72-0.65
48.08
92.88+00.50
GPS (LapPE)
OOM
OOM
91.82++0.0
GPS Grnarr--ree
(RWSE)
OOM
OOM
91.17 10.51
GT
86.51
51.17
91.85 10.76
GT-sepp
87.32
12.18
92.29 10.47
Polynormer
92.55
54.81 54.81 40.49
97. 97.4640.36
Heterophily-Dessinatte GNNs
CPGNN
63.9640.62
39.7940.77
52.03
FAGCN
65.22
42.13.0..00
88. 88.174.073
ESGNN
79.92-0.56
52.74
90.08
GBK-GNN
74.57
45.98
90.85+0.58
GloGNN
59,63
36.89+0.11
51.08++..2
GPR-GNN
64.85 10.27
14.88
86.24
H2GCN
60. 10.52
36.4710.23
89.71
JacobiCony
71. 21.14
43.55
89.6640.40
Graph SSMs
GMN
87.69 10.50
54.07 +0.31
91.01
GPS + Mamba
83. 13.22
45.13
89.93
GRAMAGCN
88.61 10.43
53.48 53.48 1.062
95.27 10.71
MP-SSM
90.9 +0.48
53.65
95.33
Ours
gLSTM (ours)
88. 0.35
51.98 0.45
92.08 + 0.88
K-hop
83.48 + 0.30
52.25 + 0.31
87.55 + 0.78
D.3 HETEROPHILIC BENCHMARKS
We additionally evaluate gLSTTM on the heterophilic datasets Platonov al. (2023), shown in Table 8 Hyperparameters and sweeps are documented in Appendix D.5 13).
gLSTM achieves good MPNN-level performance, but outperformed by some Graph Transformer architectures. Notably, the addition of K-hop aggregation here actually harms performance signif- icantly two of the three datasets. We suggest this may be due in part to the lack of long-range dependencies in these datasets, whereas the GPP and LRGB datasets evaluated in the main text designed specifically to contain long range dependencies. This explanation would imply that K-hop provides useful inductive bias for long range dependencies specifically.
18

---

Published as a conference paper at ICLR 2026
Table 9: Mean and standard deviation OGBN, averaged over four random weight initializations.
Method
Arxiv
Products
GCN
71.74 + 0.29 75.64 + 0.21
ChebNet
73.27 = 0.23
ChebNetll
72.32 0.23
GraphSAGE
71.49 + 0.27 78.29 + 0.16
GAT
72.02 79.45 0.59
NodeFormer
59.90
72.93 0.13
GraphGPS
00M
GOAT
7 82.00
NAGphormer
7 73.55
Exphormer
0.28
0OM
SGFormer
74.16 + 0.31
Polynormer
73.46+
83.82 + 0.11
gLSTM (ours) 71.91 = 0.32 81.52 0.29
D.4 LARGE GRAPH BENCHMARKS AND SCALING EXPERIMENTS
This section investigates the scaling of gLSTM to large graphs, for which we use the Arxiv and Prod- uets node classification datasets from the Open Graph Benchmark (Hu et al. 2020). ogbn- aaxiv comprises 169.343 nodes and 1,166,243 edges. while nodes and 61,859.140 edges. We evaluate gLSTM on these graphs without K-hop aggregation, which would be prohibitively expensive to compute on these graphs. However, as noted in Ap- pendix D.3 appears that K-hop aggregation of particular importance for long-range dependen- cies, so it is unclear whether it would improve performance on these benchmarks anyway.
comprises 2,449,029
Results on these datasets are presented Table Hyperparameters and sweeps are documented in Appendix D.5 (Table 12).
We highlight that although the model which achieves best validation-set performance on ogbn-arxiv is large, thus incurring high runtime and VRAM usage, significantly smaller mod- els achieve comparable results with only a small decrease in accuracy: in particular, a model with memory dimension 8, 8 heads and 4 layers achieves accuracy of 71.31 0.25.
We use ogbn-arxiv to empirically measure gLSTM epoch time and VRAM scaling with number of heads and memory dimension: these results are visualized in Figure 8 reporting both absolute values and multiples of the corresponding metric for a GCN model with layers and hidden dimension 256 the same dataset. As expected, these values appear scale linearly with the number of heads and quadratically with the (matrix) memory dimension.
We highlight that have not optimized any of the gLSTM code for CUDA efficiency, the relative epoch times and VRAM usages may be overstated, and future improvements are likely possible.
D.5 HYPERPARAMETERS
In Tables TO and we present the hyperparameter sweeps and chosen hyperparameters for results in the main body of the paper: GPP and LRGB respectively. In Tables we present the hyper- parameter sweeps and chosen hyperparameters for the normalized version of GPP (Appendix D.I)
Heterophilic benchmarks (Appendix D.3) and OGBN benchmarks (Appendix D.4 respectively.
D.6 OVERSMOOTHING AND LONG RANGE DEPENDENCIES
We test empirically that gLSTM is able to learn long range dependencies by evaluating on the Ring Transfer task introduced in Di Giovanni et al. (023a)). Results for gLSTM, GCN and GNN- SSM (Arroyo et al. 2025b) are shown for various ring sizes (and corresponding number message passing layers) in Figure))
19

---

Published as a conference paper at ICLR 2026
Table 10: Hyperparameter sweeps for gLSTM LRGB tasks. In bold are the hyperparameters that achieved the best validation set performance, and thus were those used the main results of the paper. Note that hidden dimension configuration such that the model remained within the 500k parameter budget. Due to compute limitations, hyperparameter sweeps were not exhaustive, but used Weights and Biases Bayesian Optimization routine with Hyperband early termination.
not directly swept over, as this maximized for each
Hyperparameter
Peptides-Fune
Peptides-Struet
Memory Dimension
8, 16, 32 1-2-8
8, 16, 32
Number of Heads
1-5-8
Message Passing Layers
10-27-50
4-23-40
Input Norm Type
Layer
Layer, None Group GeLU, ReLU, None 0.0, 0.1, 0.2 42
Hidden Norm Type
Group
Act. Func. (between block)
GeLU, ReLUU, None 0.1
Dropout
Hidden Dimension
45
Table 11: Hyperparameter sweeps for gLSTM on GPP tasks. bold are the hyperparameters that achieved the best validation set performance, and thus were those used in the main results of the paper. Hyperparameters were tested exhaustively via grid search.
Hyperparameter
Diam.
Ecc.
SSSP
Memory Dimension
8, 16
8, 16
8, 16
Number Heads
1, 2, 4
2, 3,
1, 2,
Message Passing Layers
1, 5, 10, 20
1, 5, 10, 20
1, 10, 20
Input Norm Type
None
None
None
Hidden Norm Type
Group
Group
Group
Act. Fune. (between block)
Tanh, ReLU, None 0.0
Tanh, ReLU, None 0.0 10. 20, 30
Tanh, ReLU, None
Dropout
0.0 10, 20, 30
Hidden Dimension
10, 20, 30
Table 12: Hyperparameter sweeps for gLSTM on OGBN (Hu et al. 2020 tasks. Bold entries indicate the hyperparameters that achieved the best validation performance and used in the main experiments.
Hyperparameter
ogbn-arxiv
ogbn-products
Memory Dimension
8,16.32
8,16.32
Number of Heads
4.8
4,8
Message Passing Layers
4.6.8,10
4.6,8.10
Input Norm Type
Batch
Layer
Hidden Norm Type
Group ReLU
Group
Act. Func. (between block)
ReLU
Dropout
0.5
0.5
Hidden Dimension
256
256
20

---

Published as a conference paper at ICLR 2026
Table 13:
Hyperparameter sweeps for gLSTM on the heterophilous datasets of Platonov et al.
2023). Bold entries indicate the hyperparameters selected based on validation performance. Sweep ranges were identical across datasets.
Hyperparameter
Amazon Ratings
Minesweeper
Roman Empire
Memory Dimension
8,16.32
8,16,32
8,16,32
Number of Heads
4,8
4,8
4,8
Message Passing Layers
4,6,8,10,11 10,12
4,6,8.10,11
4,6,8,10,12
Input Norm Type
Batch
Batch
Batch
Hidden Norm Type
Group ReLU
Group
Group
Act. Fune. (between block)
ReLU
ReLU
Dropout
0.5
0.2
0.5
Hidden Dimension
512
64
512
Table 14: Hyperparameter sweeps for gLSTM on the Normalized-GPP tasks: sweep is performed only over Normalized-Dian and these parameters are used for all other experiments. In bold are the hyperparameters that achieved the best validation set performance, and thus were those used for test set evaluation.
Hyperparameter
Normalized-Dian
Memory Dimension
16, 32
Number of Heads
1-4-8
Message Passing Layers
4- 4-10-40
Input Norm Type
Layer
Hidden Norm Type
Group
Act. Fune. (between block)
GeLU, None
Dropout
0.0 0.1 0.2 512
Hidden Dimension
21

---

Published as a conference paper at ICLR 2026
Fale
0.0
Gasgalike Gxie-Tir
Gutteg
MiR gin 02% Veux Rted Tex
0.0
Eynch Thmn
0.23
Malpje OON
015
Naxdoo Tlck
Ein
(a) Mean epoch time vs. number of heads
(b) Mean epoch vs. memory dimension
Latitic Chice GalkgeeTeee
Gartar Tale
310
Makue OUT Sie 11. Shage
Gulay-Tia
100
VILAA
(c) Max memory usage vs. number heads
(d) Max memory usage vs. memory dimension
dataset (Hu al, 2020 Mean epoch time and max memory usage is reported, both in absolute terms and relative to GCN with 4 layers and hidden dimension of 256. All parameters other than that being varied are
Figure 8: Scaling behavior of gLSTM, empirically reported on the
fixed to that of the top-performing model: see Table
0.8
Aceuacy
STM
0.0
GNN-S5M
0.2
250
Layees
Figure 9: Performance on the Ring Transfer task.
D.7 ADDITIONAL NAR CLASSIFICATION RESULTS
In this section, we present various additional results from the NAR task presented in the main body of the paper.
We visualize the Jacobian norms separated by selected vs background nodes - for the mixed ag- gregation strategies used in the main paper in Figure 10 This is, in effect, the more granular plot of Figure 6b
D.7.1 COMPARISON AGAINST (GRAPH) TRANSFORMER BASELINES
In addition to the MPNN comparisons presented in the main body of the paper and Appendix D.7.3 we compare gLSTM against two Transformer baselines: GraphGPS (Rampášek et al. 2022) and regular Transformer /Vaswani al. 2017) block utilizing softmax attention. These results visualized Figure
From this figure, solve the task perfectly, as expected. Curiously, GraphGPS fails significantly earlier, at 32 neighbors for all hidden dimensions tested: while unsure of the precise reason for this, speculate that
that softmax attention with sufficiently high hidden dimension is able to
22

---

Published as a conference paper at ICLR 2026
gLSTM dim. 16
GCN dim. 61
Ratios
1400
Selected Bac logroend
Selected Background
175
150
Full Janohian Norm Ratio
Pull Jacokian Noma
Ful Jackkian Nomm
125
100
75
400
10
200
aLSTM GUN
8
16
32
48
64
80 96
16 32 48
64
80
96
8 16 32 48 64 80 96
Number Neigh
Number Neighhours
Neighhouss
Figure 10: Left: Mean Jacobian norms for gLSTM of memory dimension 16, with varying number of neighbors in the NAR task, separated by whether the neighbor node corresponds to the given query (selected) or not (background). Middle: Same, with GCN of hidden dimension 64. Right: Mean ratios of Jacobian norms for selected nodes to background nodes, for these two models. Stan- dard deviation visualized in bar chart eтror bars and line chart shaded area.
dhe Traskoosr del
dl du cad Treaforur des
Figure 11: Comparison of STM performance against Transformer baselines: GPS (Rampášek) al. 2022) and a standard Transformer baseline with softmax attention. Both of these use Laplacian positional encodings appended to the node feature vectors. Test-set mean accuracy is shown, with standard deviation shaded, averaged over 3 runs. Note that gLSTM uses K-hop aggregation here, whereas GPS does not.
the GCN aspect of the architecture may be actively harming performance. We note however that GraphGPS does outperform all MPNNs tested, other than gLSTM.
is also interesting to note that at lower dimensions, softmax attention reaches a neighbor count which it also starts to fail. It seems clear that this arises simply from the initial embedding of the integer key, query and value symbols: when the size of these alphabets exceeds half the hidden dimension (recall half of the embedding vector is used to encode the key, the other half the query), is no longer possible for each symbol to have a learned orthogonal vector and there will be overlap.
D.7.2 TRAINING CURVES: FAILURE AT NAR IS AN ISSUE OF GENERALIZATION
This section investigates further what exactly causes GCN and other models to fail at NAR. We observe in Figure [2 that for several models, above the point where test set accuracy decreases, train set accuracy remains high: thus, the failure mode seems to be one of generalization. We suggest that this is consistent with the capacity intuition: at the point at which the model is no longer able to separably store the neighbor representations, it collapses instead memorizing the aggregated neighbor representation and corresponding value. Since these specific combinations are not shared with the test set, this does generalize.
23

---

Published as a conference paper at ICLR 2026
Neighhouss
32 Neighbour
09
0.-
0.4
00
125
2.0
200
Epods
Roadi
1.0
0.1
0.5
3--TX
0.6
Figure 12: Train and test accuracies plotted against epoch count. Left columm contains the results for experiments using 8 neighbor nodes, right column for 32 neighbors. Top row visualises GCN results, second GPS, third gLSTM. gLSTM the only one that remains able to generalize at 32 neighbors (and beyond).
24

---

Published as a conference paper at ICLR 2026
315TM dr.
CAT
GanolOCN
68
Accance
60
Nilghhor
Figure 13: NAR Accuracy where all models do not use K-hop aggregation, for expanded set of models.
JARTEAL dia..
LAAE
JUSTM die. CAT
2LSTM das. 32 EAT
DCN cles 6 CasalOCN das. 06
DCN dee. 125 LandtDCC dee 120
DCN din
LanodOCCN des 200
10
68
56
Nogllorrr
Figure 14: NAR Accuracy where all models do use K-hop aggregation, for expanded set of models.
D.7.3 PERFORMANCE SEPARATED AGGREGATION STRATEGY
We next separate out h-o and K-hop aggregation, and plot results for larger set of models, in Figures 13 and 14 respectively.
We additionally verify that the number of layers the reason behind GCN being unable to solve NAR at higher neighbor counts. Figure 16 visualizes the performance of GCN models with hidden
CCN
GAT
Figure 15: Number of trainable parameters for the expanded set of models tested in Figures 13
and 14
25

---

Published as a conference paper at ICLR 2026
layers
* 4 layers
layers
layers
1.0
Accuracy
0.5
0.0
60
100
Number of Neighbours
Figure 16: NAR Accuracy for GCN hidden dimension 128, no K-hop, for varying numbers of GCN layers.
dimension 128 and various layer counts; transpires that layers performs best out of the tested layer counts.
D.7.4 ADDITIONAL. SENSITIVITY METRIC RESULTS
We plot in this section the sensitivity metric trends of gLSTM vs GCN, both using K-hop aggrega- tion.
Figure 17a visualizes the Jacobian norms for different model sizes and numbers of neighbors; Fig- ure I shows the ratios between selected and background node Jacobian norms. Figure 18 separates out the Jacobian norms for gLSTM memory dimension 16 and GCN hidden dimension 64. Figure I9 visualizes the Hessian mixing metric for all models.
Full Jacobian Norm
102 10"
Jucokan Nora Batios
10.
gLST51
315TTM dim. 16
21.TT
GCN dim. 64
207
10
GCN dim. 256
20
60
100
Number of Neigghoomss
Nember Neighlomrs
(a) Jacobian norms
(b) Jacobian norm ratios
Figure 17: Left: Average Jacobian norms for different gLSTM and GCN models, with varying number neighbors in the NAR task. Right: The ratio between the Jacobian norms of the selected (key corresponds query) background (key is different from query) neighbor nodes, for the different models see Figure 18] This plot differs from that in the main body of the paper in that both gLSTM and GCN use K-hop aggregation.
D.8 NEIGHBOR ASSOCIATIVE RECALL REGRESSION RESULTS
In this section, we present results for the regression variant of the NAR task presented in the main body of the paper. We refer to this as Neighbor Associative Recall Regression (NARR).
Similarly to NAR, for given neighborhood size N we create graph of N + 3 nodes. This graph consists of N "neighbor" nodes, central node to which they are all connected. and an intermediate node connected to the central node and "query" node connected only to the intermediate node.
Each of the neighbor nodes has a feature vector representing key and a value. The values consist of fixed-ding fxed-dimennional vector of length V where each element is randomly sampled from a standard normal distribution. The keys are each unique one-hot vectors of dimension N. The query node's feature vector contains single one-hot vector, equal to one of the one-hot vectors of the neighbor nodes. The target of the graph is for the central node to predict the value of the neighbor node, corresponding to the key that matches the query node. Each node is therefore equipped with an input feature vector æ e VV2N, where the first elements comprise the value, the next N elements the key and the final N elements the query. Where node does not have of these features, the
26

---

Published as a conference paper at ICLR 2026
gLSTM dim. 16
GCN dim. 61
Ratios
1400
Selected Background
Selected
Background
Pull Jacokaan
Full Jacobian
Full Juniiii
400
10a
200
elSTMM
8
16
32
48
64
80
96
16
32
48
64
80
96
16 32 48 80 96
Number Neighbours
Number Neighhours
Number Neighhours
Figure 18: Left: Jacobian norms for gLSTM of memory dimension 16, with varying number of neighbors in the NAR task, separated by whether the neighbor node corresponds to the given query (selected) or not (background). Middle: Same, with GCN of hidden dimension 64. Right: Ratios of Jacobian norms for selected nodes to background nodes, for these two models. This plot differs from that in the main body of the paper in that both gLSTM and GCN use K-hop aggregation.
Hoxian Max Value
gLSTM
3LSTM dim. 16
10-1
g gLSTM dim. 32
*
GCN dim. 64
10-1
GCN dim. 128
dim.
20
-0
80
100
Namber Neighhours
Figure 19: Mean of the maximum Hessian values for different gLSTM and GCN models, averaged across test set examples and different neighbor nodes. This plot differs from that the main body of the paper in that both gLSTM and GCN use K-hop aggregation.
vector elements are set to We note the of one-hot encoding for keys and values means that the first linear layer of the model acts as a learned embedding function, where multiplication with the one-hot encoding simply selects the corresponding column of the weight matrix. For experiments, we use V 16.
Since the value vectors lack the sparsity of NAR, this appears be "harder" task in the sense that it is more taxing on memory capacity. This means that some of the over-squashing trends are more defined, particularly trends in sensitivity-bait our experiments suggest that the regression target means that NARR becomes too hard for vector- memory MPNNs effectively solve, visible in Figures 20 and
measures see Appendix D.8.1 However,
Performance (MSE) for NARR is shown in Figures 20 and 21 for no- no-K-hop and K-hop aggregation
respectively. We note that the performance curves in Figure 21 look similar to those obtained by the sequence modeling variant of this experiment in Scclag et al. (2021). The number of trainable parameters shown Figure 22
D.8.1 RELATIONSHIP TO OVER-SQUASHING SENSITIVITY METRICS
As with NAR in the main paper, visualize the behavior of sensitivity-baat over-squashing met- rics for different neighbor counts and different models. Similarly to the main paper, we compare gLSTM using K-hop aggregation and GCN without. We note that perhaps due to the increased difficulty of the task the trends discussed Section 5.2 are actually more pronounced for the NARR task.
Figure 23a visualizes the Jacobian norms for different model sizes and numbers of neighbors; Fig- ure 23blshows the ratios between selected and background node Jacobian norms. Figure 24 separates
27

---

Published as a conference paper at ICLR 2026
0.-
40
100
Number Niihhonn
Figure 20: NARR MSE where all models do not use K-hop aggregation.
JLSTM dla. GCN dic 04 CCN
G1STM din 16
218TM cin. CCN
100
08
0.0
MSF
0.4
Netatbomm
Figure 21: NAR Accuracy where all models do use K-hop aggregation.
GUX
Figure 22: Number of trainable parameters for the expanded set of models tested in Figures 20 and 21
28

---

Published as a conference paper at ICLR 2026
out the Jacobian norms for gLSTM memory dimension 16 and GCN hidden dimension 64. Figure visualizes the Hessian mixing metric for all models.
Jacobion Norm Ratine
10"
gLSTM dias. 8
STM dims
Pall Jocobion
XLSTM dias. 82
GCN dizs 64
10"
GCN dics. 125
10'
+
GCN dica. 256
Number Neighbours
Number Neighhours
(a) Jacobian norms
(b) Jacobian norm ratios
Figure 23: Left: Average Jacobian norms for different gLSTM and GCN models, with varying number of neighbors in the NARR task. Right: The ratio between the Jacobian norms of the selected (key corresponds query) to background (key is different from query) neighbor nodes, for the different models- see Figure 24
ST dim. 16
GCN dim. 64
Ratios
Selected
Bac Baclogroun
Background
GON
250
x
Full Jarahian Norm
Fod Jacabian Noemn
200
3 10
130
10
50
Namber Neighbours
Number of Neighbours
Namber of Neigh
Figure 24: Left: Jacobian norms for gLSTM of memory dimension 16, with varying number of neighbors in the NARR task, separated by whether the neighbor node corresponds to the given query (selected) not (background). Middle: Same, with GCN of hidden dimension 64. Right: Ratios of Jacobian norms for selected nodes to background nodes, for these two models.
Hesiian Max Value
10
gLSTM dim.
gLSTM dim. 16
10
gLSTM dim. 32
GCN dim, 64
GCN dim.
10-4
GCN dim.
20
100
Number of Neighbous
Figure 25: Mean of the maximum Hessian values for different gLSTM and GCN models, averaged across test set examples and different neighbor nodes.
We note that the sensitivity difference between selected and background nodes is particularly stark here, even more so for classification-bu based NAR; SLS consistently shows a sharp drop-off in Figure 23b at the memory dimension, and GCN maintains ratio remarkably close to unity. This closely aligns with the performance these models, Figure 21 demonstttss that gLSTM perfor- mance begins drop off quickly when the number of neighbors matches the memory dimension, and Figure 20 demonstrates that GCN is never able to solve the task, for any tested number of neighbors.
We hypothesize that the strong impact the K-hop aggregation on the model's ability to selectively recall partieularly visible for NARR may partially explain the dramatic performance decrease
29

---

Published as a conference paper at ICLR 2026
when ablating this aggregation, discussed in Appendix D.2 We note that, while gLSTM consis- tently demonstrates superior performance to GCN, the improved performance is most striking when additionally using K-hop aggregation; it appears that the inductive bias introduced by the K-hop aggregation is particularly suited to the selective recall required by this task. Arroyo et al. (2025a)
30


Reviews:
[{"review_id": "S6AA5trGOd", "reviewer": "Reviewer_mSY2", "summary": "This paper addresses the over-squashing phenomenon in GNNs by focusing specifically on storage capacity as distinct from sensitivity. The authors introduce a new synthetic benchmark, NAR, designed to isolate and directly measure capacity over-squashing. Inspired by xLSTM and fast weight programmers from sequence modeling, the authors propose a new GNN architecture (gLSTM) to boost storage capacity. Empirical evaluations demonstrate the effectiveness of gLSTM on the NAR task and several long-range graph benchmarks.", "questions": "Please address the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a rigorous re-examination of over-squashing, explicitly distinguishing between storage capacity and sensitivity, with careful argumentation. It clarifies and extends understanding within the community.\n\n- The NAR task is a well-designed, controlled test for probing capacity bottlenecks. It enables discrimination between capacity and sensitivity effects, addressing limitations of prior synthetic benchmarks.\n\n- The paper provides detailed mathematical descriptions of both baseline GNNs and the proposed gLSTM mechanism.\n\n- The authors have conducted extensive ablations and sensitivity analyses to support their claims. Jacobian and Hessian analyses also enhance interpretability.\n\n- The experiments show that gLSTM achieves state-of-the-art or competitive performance in both the synthetic NAR task and real-world benchmarks.", "weaknesses": "1. The related work section omits several directly relevant recent studies [1, 2].  Besides, the authors are encouraged to discuss the difference between over-smoothing [3, 4] and over-squashing. \n\n2. While the authors propose the NAR task and empirically study capacity limits, there is a lack of formal and quantitative capacity analysis.\n\n3. The move from vector to matrix memory increases parameter counts and computational complexity. There is little analysis or discussion about it.\n\n4. Direct empirical comparison to a broader set of anti-over-squashing methods is missing.\n\nRefs:\n\n[1] Schreier-Coset Graph Propagation, Arxiv 2025.\n\n[2] Over-Squashing in GNNs and Causal Inference of Rewiring Strategies, Arxiv 2025.\n\n[3] SkipNode: On alleviating performance degradation for deep graph convolutional networks, TKDE 2024.\n\n[4] Dropedge: Towards deep graph convolutional networks on node classification, ICLR 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ybmgcdP8E7", "reviewer": "Reviewer_6dpm", "summary": "The paper identifies two distinct mechanisms behind “over-squashing” in MPNNs (message-passing graph neural networks): (i) sensitivity over-squashing and (ii) capacity over-squashing. It introduces a shallow synthetic task (Neighbor Associative Recall, NAR) that isolates capacity from sensitivity, and proposes gLSTM, an MPNN whose node states are augmented with an associative-memory matrix updated via fast-weight outer products. On NAR, gLSTM retains high recall until the number of neighbors equals the memory dimension, while vanilla GCN fails much earlier. gLSTM also obtains good performance on some real-world benchmarks.", "questions": "How would the proposed method perform when applied to deep mpnns?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and well-motivated with the synthetic tasks. The problem targeted is of real significance. \n2. It is wise to disentangling capacity from sensitivity to give an in-depth analysis of capacity over-squashing.", "weaknesses": "1. The proposed method is a simple combination of existing techniques, particularly applying xlstm to graph structures. The tech novelty should be further strengthened. \n2. The proposed method may suffer from high computational overhead, there should be relevant analysis. Moreover, it is unclear the size of the tested benchmarks. It is advised to show that the proposed method can be applied to graphs with more than 1M nodes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lznjjdiZEt", "reviewer": "Reviewer_ekHn", "summary": "This paper revisits over-squashing in message-passing neural networks by emphasizing a **capacity** perspective in addition to the usual **sensitivity** view. It introduces a synthetic evaluation, **Neighbor Associative Recall (NAR)**, designed to isolate node storage capacity in a shallow setting. Building on sequence-modeling ideas, the authors propose **gLSTM**, a GNN architecture with associative (matrix) memory and gating, paired with **K-hop aggregation**. Experiments on NAR and standard graph benchmarks suggest that increasing node-level storage capacity improves long-range reasoning while remaining competitive downstream.", "questions": "1. How does gLSTM’s time and memory footprint scale as node and edge counts grow? In practice, do you observe memory bottlenecks that differ between sparse and dense graphs.\n\n2. What motivated the choice of K-hop neighborhood specifically, and could alternative aggregation schemes provide similar or even better empirical benefits? Could the authors provide more detail/access to K-hop ablation results in the main body?\n\n3. Could the authors give more interpretative diagnosis when gLSTM or GCN \"breaks down\" (e.g., NAR neighbor count exceeding memory)?\n\n4. Please include strong capacity-oriented and rewiring baselines for both NAR and downstream tasks, or provide a clear and compelling justification for their omission. In the absence of such comparisons or reasoning, I will have to lower the score due to insufficient empirical validation.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Clear conceptual separation.** The work carefully distinguishes capacity-related vs. sensitivity-related over-squashing and makes the capacity lens the central object of study.\n2. **Purpose-built synthetic task.** NAR is a targeted probe for node storage limits that avoids confounding depth-driven sensitivity effects common in prior tests; the setup and metrics make the evaluation legible.\n3. **Methodological innovation.** gLSTM adapts associative memory and exponential gates (in the spirit of xLSTM) to graphs, coupled with K-hop aggregation to broaden accessible context. The design choices are motivated and technically transparent.\n4. **Empirical rigor and diagnostics.**\n    * On NAR, gLSTM maintains **high recall** and then **gracefully saturates** near the memory limit, consistent with the capacity hypothesis.\n    * On downstream benchmarks (e.g., GPP Diameter/Eccentricity; LRGB Peptides-Func), results are strong/competitive within a parameter budget.\n    * Jacobian/Hessian-style sensitivity analyses help separate capacity effects from sensitivity/optimization effects.", "weaknesses": "1. **Limited Theoretical Guarantees**:  \n   As noted in the conclusion, the capacity notion is supported primarily through intuition and empirical performance. There is currently no theoretical quantification or formal bounding of node storage capacity for different architectures (gLSTM, GCN).\n\n2. **Dependency on K-hop Aggregation**:  \n   Much of gLSTM's performance gain (Appendix B.2, Table 3 and onward) appears to come from K-hop aggregation, raising the question of whether capacity improvements are due to associative memory or simply enhanced information accessibility.\n3. **Baseline Limitations**:  \n   The experimental section primarily compares gLSTM to GCN and occasionally to a few other standard models (Table 1); Particularly, the lack of evaluation against strong geometric or spectrum-preserving approaches is an empirical gap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1WV822e75I", "reviewer": "Reviewer_QVwX", "summary": "The paper proposes gLSTM, a graph neural architecture that integrates an LSTM-like gating and memory mechanism into the message-passing process of GNNs. The authors argue that by maintaining global and local memory states, the model can alleviate over-squashing problem.", "questions": "Please refer to the weakness.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The idea of combining LSTM-style gating with graph message passing is conceptually intuitive and aligns with the goal of controlling information flow.\n\n2. The experiments on the synthetic Neighbor Associative Recall (NAR) task provide some evidence that the model can store multiple neighbor features effectively.\n\n3. The overall writing is easy to follow.", "weaknesses": "1. The main novelty of the paper is the adaptation of xLSTM to GNNs. While the motivation is reasonable, most design components are directly inherited from prior LSTM or xLSTM works. The paper feels more like an engineering extension rather than a fundamentally new GNN architecture. The authors should clearly articulate what is truly new in the design beyond re-using LSTM elements.\n\n2. Although the idea of using LSTM to control message passing is intuitive, the technical motivation for several design choices is insufficiently explained. For instance, the roles of 𝑛𝑢 and 𝑚𝑢 on graphs are not clearly defined—are they merely borrowed normalization and stabilization terms from xLSTM, or do they have specific graph-theoretic meaning? This ambiguity makes it difficult to understand how these terms contribute to mitigating over-squashing.\n\n3. The paper lacks a clear description of the datasets and settings. Although LRGB and synthetic graphs are mentioned, there is no systematic list of datasets, splits used or how baselines are chose. It remains unclear how results generalize to standard benchmarks such as OGB datasets or larger real-world graphs.\n\n4. The main analysis of over-squashing is performed on the synthetic NAR task. While this toy setting helps isolate capacity effects, it is unclear whether the claimed improvements hold on realistic graphs. Results on real-world datasets are necessary to substantiate the claim.\n\n5. Recent Graph Transformers and other scalable GNNs have been shown to alleviate over-squashing via global attention mechanisms. However, these models are not compared, leaving it unclear how gLSTM performs relative to current state-of-the-art methods.\n\n6. The proposed design may introduce significant computational overhead due to additional gating, normalization, and memory matrices. No runtime or complexity analysis is provided, especially for large graphs such as papers100M.\n\n7. Although the empirical intuition is sound, the paper lacks a rigorous theoretical justification for why the LSTM-style mechanism fundamentally reduces over-squashing. A formal analysis would strengthen the claims.\n\n8. The experiments only include graph-level classification and synthetic tasks. There are no results on node classification or link prediction, which are precisely the domains where over-squashing is more prominent. This omission limits the paper’s empirical impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BOujYxcELO", "reviewer": "Reviewer_6qip", "summary": "This paper redefines *over-squashing* in Graph Neural Networks (GNNs) as two distinct failure modes: **insufficient sensitivity** and **storage capacity saturation**, arguing that existing evaluations often conflate the two. The authors introduce a synthetic task called **Neighbor Associative Recall (NAR)** that isolates and measures capacity alone. Building on this task, they propose a message-passing architecture called **gLSTM**, which incorporates **matrix-based associative memory** and **xLSTM-style gating**. Additionally, they employ **K-hop aggregation** to enhance long-range interactions. The proposed method demonstrates clear capacity advantages on the NAR task and achieves competitive or state-of-the-art results on several GPP and LRGB benchmarks. The authors also analyze the relationship between capacity and sensitivity using Jacobian and Hessian-based measures.", "questions": "- Under the same K-hop and parameter budget, how does gLSTM compare to equivalent non-memory MPNNs (wider or deeper) in both performance and sensitivity metrics such as Jacobian or mixed second-order derivatives?\n\n- Please report training/inference time and peak memory consumption, and provide scaling curves showing how efficiency varies with memory dimension and the number of heads.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper clearly separates “capacity” and “sensitivity” when analyzing over-squashing, and introduces a shallow, controllable synthetic task (NAR) that isolates and measures storage capacity. The experiments and quantitative analyses strongly support this formulation.\n\n\n- The proposed gLSTM architecture combines matrix-based associative memory with fast-weight (outer-product) updates, which is well aligned with the message-passing paradigm in graphs; the derivation and implementation details are sound and well explained.\n\n\n- The method shows strong performance on multiple long-range dependency benchmarks, with comprehensive ablation studies (on gating, K-hop aggregation, positional encoding, etc.) and full hyperparameter tables.\n\n\n- The paper is reproducible and transparent: code and configurations are released, and the training framework is standardized and well documented.", "weaknesses": "- Coupling between K-hop aggregation and capacity claims:\n\nIn real-world benchmarks, the performance gains may stem not only from increased storage capacity but also from enhanced sensitivity due to the denser computation graph created by K-hop aggregation. This coupling makes it difficult to attribute improvements solely to capacity. The paper should include controlled comparisons that fix K-hop settings while varying only the memory and gating components, alongside sensitivity metrics.\n\n- Lack of efficiency and scalability analysis:\n\nThe matrix memory in gLSTM increases computational and memory costs quadratically with the hidden dimension. Although parameter counts are aligned across models, the paper does not report training/inference time or peak memory usage. Adding throughput and GPU memory comparisons with standard baselines (GCN, GIN, GCNII, GPS, etc.) would strengthen the empirical claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)