Chimera: State Space Models Beyond Sequences
Authors: Aakash Lahoti
Tanya Marwah
Ratish Puduppully
Albert Gu
Venue: Accepted by TMLR ()

Abstract: Transformer-based deep learning methods have emerged as the standard approach to model diverse data such as sequences, images, and graphs. These methods rely on self-attention, which treats data as an unordered set of elements. This ignores the neighborhood structure or graph topology of the data and requires the use of inductive biases, such as position embeddings in sequences and images, and random walks in graphs, to incorporate topology. However, developing bespoke inductive biases for each task requires significant effort and can also introduce side-effects hindering generalization. In this work, we introduce Chimera, a unified model that directly incorporates the data topology in a principled way, obviating the need for domain-specific biases. Central to Chimera is the observation that state-space models---which naturally do not require position embeddings---can be generalized to capture any general graph topology. Our experiments demonstrate the versatility of our approach---Chimera achieves strong performance across the domains of language, vision, and graphs, outperforming BERT on GLUE by 0.7 points, ViT on ImageNet-1k by 2.6%, and all the baselines on the Long Range Graph Benchmark. Our results validate Chimera's principled methodological contributions and affirm the long-held belief that data topology is a powerful inductive bias across modalities. We further propose algorithmic optimizations to improve Chimera's efficiency while maintaining performance: 1) For the subclass of Directed Acyclic Graphs we show that Chimera can be implemented as a linear time recurrence. 2) For general graphs, we relax the method with a simple mathematical approximation, achieving Transformer's quadratic complexity without relying on domain-specific biases.

Published in Transactions on Machine Learning Research (04/2025)
Chimera: State Space Models Beyond Sequences
Aakash Lahoti'
alahoti cmnu edu
Cornegie Mellon University
Tanya Marwah Cornegie Mellon University
tmareahh@andreu.ccme edu
Ratish Puduppully University of Copenhagen
mulishpuccapppllly@ymaaalccmmmm
Albert Gu
agu@cc.
wgw.css.cm..co crau. edu
Cornegie Mellon University, Cortesia Al
Reviewed on OpenReview: https: openreview. net/ fottm? id= goOTUsssp
Abstract
Transformer-basee based deep learning methods have emerged as the standard approach to model diverse data such as sequences, images, and graphs. These mothods rely on self-attention, which breats data as an unordered set elements. This ignores the neighborhood structure or graph topology of the data and requires the use of inductive biases, such as position embeddings in sequences and images, and random walks in graphs, to incorporate topology. However, developing bespoke inductive biases for each task requires significant effort and can also introduce side-effects hindering generalization. In this work, we introduce Chimera, unified model that directly incorporates the data topology in principled way, obviating the need for domain-specific biases. Central to Chimera is the observation that state-space models which which naturally do not require position embeddings can be generalized to capture any general graph topology. Our experiments demonstrate the versatility of our approach Chimera achieves strong performance across the domains of language, vision, and graphs, outperforming BERT on GLUE by 0.7 points, ViT on ImageNet-11k by 2.6%, and all the baselines the Long Range Graph Benchmark. Our results validate Chimera's principled methodological contributions and affirm the bong belief that data topology is a powerful inductive bias across modalities. We further propose algorithmic oplimizalions to improve Chimera's efficiency while maintaining performance: 1) For the subclass Directed Acyclic Graphs we show that Chimera can be implemented as a linear time recurrence. 2) For general graphs, we relax the method with simple mathematical approximation, achieving Transformer's quadratic complexity without relying on domain-specific biases.
1 Introduction
Real-world data, ranging from sequential language and audio to high-dimensionall images and structured molecule data, often exhibit some notion of neighborhood, or graph topology, among its constituent elements. For instance, language and audio have a directed line graph topology; images possess an undirected grid-graph topology; Structured molccule data has predefined nodes (atoms) and edges (bonds) that constitute its topology. More recently, Transformer-based (Vaswani et al., 2017) methods, with self-attention at their core, are increasingly being used to model such data (Devlin et al.
2019 Dosovitskiy et al. 2021 Rampášek et al.
2022 However, self-attention is permutation invariant and treats data as an unordered set of clements,
Authors contributed equally this work.

---

Published in Transactions on Machine Learning Research (04/2025)
disregarding its topology.
Consequently, significant research effort has focused on developing domain-specific
inductive biases, such as position embeddings (Su et al. 2023 Devlin et al. 2019), and random walks (Behrouz) and Hashemi 2024 Wang et al. 2024), to incorporate data topology into the model.
However, designing these inductive biases requires navigating a large search space for each domain. For
instance, RoPE embeddings (Su et al. 2023) work well in language (Touvron et al.) 2023); in vision, absolute and 2D-RoPE embeddings are widely used (Dosovitskiy et al.] 2021 Heo et al. 2024;; while Laplacian embeddings or random walks are used in graphs (Rampášek et al. 2022). Morcover, these techniques can
produce undesirable side effects, such as poor out-of-domain generalization RoPE struggles to generalize to sequences longer than the training lengths (Kazemnejad et al.) 2024). while absolute position embeddings have inherently constrained context sizes due to their design. Furthermore, it is unclear how effectively these techniques capture the underlying graph topology.
In this paper, we introduce Chimera, a unified framework that directly incorporates data topology -.c., the underlying graph structure in a principled way. Chimera is motivated by the observation that State Space Models (SSMs) for causal language modeling Mamba-2 (Dao and Gu. 2024). RetNet (Sun et al. 2023 and Linear Attention (LA) (Katharopoulos et al. 2020) naturally capture the sequence order through recurrence, without position embeddings. We formalize this property and generalize it beyond causal sequences to any graph topology. This approach is in contrast. with existing methods that instead apply attention or SSMs as a black box to "flattened data" " augmented with heuristics to compensate for loss of topological information (Liu et al. 2024 Dosovitskiy et al., 2021). We validate our methodological innovation with empirical results that demonstrate strong performance across diverse domains. This affirms the long-hek held belief that topology is a powerful inductive bias, while providing a principled way to incorporate it into the modeling process.
We first formally show how SSMs capture the underlying directed line graph topology of language data through recurrence (Sec B. For this, we leverage the Structured Masked Attention (SMA) representation (Dao) and Gu 2024) of SSMs: methods such as Mamba-2, RetNet, and Linear Attention are equivalent to the matrix M = L O (QK") multiplied with the input, where Q, K are the query and key matrices, respectively, and L is the (data-dependent) mask matrix analogous to the causal mask in allention. We show that the mask matrix fully encodes the topology of the underlying graph structure by acting as the resolvent of the adjacency matrix, A, of a directed line graph, i.c. L == (I A)- -- A', where I is the identity matrix. This result allows us to generalize to any graph topology. Specifically, for an "appropriately parameterized" adjacency matrix, A, of the graph topology, we compute the matrix multiplication of M = L (QK"), where L= AI- with the input. Intuitively, Aij captures the "influence" " between neighbors i and j, while the resolvent aggregates this influence over all paths, thus capturing the underlying topology. In Section 3.3 we present the detailed parameterization scheme used in Chimera which is important for both empirical performance and numerical stability.
The main bottleneck lies in the computation of the mask matrix, whose naive implementation incurs a cubic cost. We propose two algorithmic optimizations to mitigate this cost while maintaining performance:
1.
We specialize the method for the subclass of directed acyelic graphs (DAGs). This is motivated by the fact that many graph topologies can be canonically decomposed into multiple DAGs, For example, an undirected line graph can be decomposed into two directed line graphs (Fig 2), while a grid graph can be divided into four directed grid graphs (Fig 3). We prove that for this subclass, the resolvent can be computed by running a recurrence that is linear in the number of nodes and edges. We further propose a squaring technique to compute the resolvent efficiently
modern hardware accelerators by leveraging matrix multiplications, at a quadratic cost in the number of vertices. This cost is optimal in the worst case, it can be improved when the underlying graph "s"sttuctured" graphs can computed in linear time via existing Mamba-2 kernels
2. We relax the exact computation of the resolvent for general graphs with finite sum approximation of the Neumann series, i.e. (I (I-A) -)- = = Ai, where d is the diameter of the graph. We can efficiently compute this approximation with a squaring technique, capturing the global topological structure. We further show that the finite sum approximation performs as well as the method with the sum of infinte terms.
Overall, we make the following contributions:
2

---

Published in Transactions on Machine Learning Research (04/2025)
We propose Chimera, a unified model that directly incorporates graph topology in a principled way by generalizing SSMs. This is in contrast with existing approaches that apply attention or SSMs as a black box on "flattened data" with additional heuristics.
We introduce algorithmic optimizations improve the method's efficiency by specializing to DAGs and approximating the resolvent using finite sum, while preserving performance. We show that for canonical modalities such as images and language, where data can be decomposed into DAGs, this finite-sum approximation becomes exact.
We demonstrate that Chimera consistently achioves strong performance across diverse domains including language, images, and graphss-otperfoonee outperrominn BERT (Devlin al. 2019) with GLUE score (Wang et al., 2019) of 0.7, surpasses ViT (Dosovitskiy et al. 2021) on ImageNet-1k (Dnng et al. 2009) classification by 2.6%. Purthermore, our method outperforms strong baselines the Long Range Graph Benchmark (LRGB) [Dwivedi et al. 2022), where we show that our model is capable of modeling both long and short range interactions nodes, while respecting the graph structure.
2 Preliminaries
We introduce State Space Models (SSMs), which are recurrent models designed to process sequential data, such as language and audio. We formulate SSMs in their recurrent form and then introduce the Structured Masked Attention (SMA) (Dao and Gu 2024 representation that unrolls and vectorizes this recurrence as a matrix M acting the input X. This SMA representation would allow us to show that SSMs inherently operate on directed line graph topology.
2.1
Overview of State Space Models
SSMs, such Mamba-2 (Dao and Gu 2024 Linear Attention (LA) (Katharopoulos et al. 2020 RetNet (Sun el al.
2023 are recurrent sequence fo-sequueee models that feature linear hidden-state transition function.
This function is typically data-dependent which is known to improve model performance (Hwang et al. 2024
Formally, let X E RTX denote the imput sequence of T tokens, where each token has D channols. Let the size of the hidden state be d. Let Y e RTDD be the output of the sequence- se-equence model. Then, SSMs first compute the following matrices:
B = fD() Sc(X), V = -x(X)
(1)
where fB, fc, fv are model specific data dependent functions. For instance, in Mamba-2 each of these functions composition of a lincar projection of X along the channel dimension, followed by a short convolution layer along the sequence dimension and Swish activation function (Ramachandran al., 2017). In Dao and Gu (2024), it was shown that we view the B, C, V matrices analogs of the key, query, value matrices in self-attention, respectively.
V [(+, E RT denole the input corresponding to channel i. Let B, = Bl4 C, = ClA:3] for any time t. Let vi = yt, i) and vf = =.[[]] Then, the model computes the following recurrence, starting with the hidden state vector h" = 0 E Rd;
Let o² =
h anhi + Be
(2)
v/ C² hi
(3)
where deybe are model-specific parameters that characterize the SSM. LA sets or = b, 1, RetNet sets a = b, 1 for learnable parameter 7. In contrast, Mamba-2 sets o,, in data-dependent manner that implicitly encodes gated memory mechanism known selectivity the selection mechanism. This allows the model to select and propagate important tokens across long sequences. Specifically,
A (X(X E R²; a; =
A, E.R
(4)
where A the selectivity matrix, A, the tth element of the vector, and fA like fB, fc, fv is a data- dependent function. Selectivity works by assigning larger values A, to important tokens, amplifying their
3

---

Published in Transactions on Machine Learning Research (04/2025)
h-
h3
42
d3
41
2
40
41
42
4g
6
1
2
4:024s
dgda
dg
Figure 1: SSMs inherently operate directed line graph topology: SSMs modeling sequence of tokens in the recurrent reprosentation (left), the structured mask matrix from the SMA reprosentation of SSMs (center), The underlying directed line graph topology (right).
contribution to the previous hidden state, while assigning smaller values A to unimportant tokens, which preserve the past hidden state with minimal influence from these lokens.
2.2 The Structured Masked Attention Representation
Dao and Gu (024) introduced the Structured Masked Attention (SMA) representation for SSMs, which vectorizes the time-stepped recurrence (Eq. 3 as matrix multiplication, Y MV. D Here, M depends the data-driven matrices B, C, and A, and can be expressed as M L o (CB"), where L is a mask derived from A. One can obtain this formulation by unrolling the recurrence across all time steps.
Formally, define B, = B,, and recall from Section 2.1 that b, = A., a = cxp(-A) for Mamba-2; b = 1,
de = 7 for RetNet; and b, 1, dt = for Linear Atlention. Then the outpul Y of the recurrence (Eq. 3 can be vectorized as,
Y= MV = -
(5)
where the mask matrix Lg 1 2 j] I1 < The SMA representation of the recurrence (Eq. is useful because it neatly isolates the effect of the underlying topology within the recurrence computation into the mask matrix L (Sec. 3) This property will allow us to generalize SSMs to arbitrary topologies by appropriately formulating the structured mask L.
3 Chimera: Incorporating Graph Topology
In this section, introduce Chimera, unified model that directly incorporates the underlying graph topology of a domain by mathematically generalizing SSMss. This contrasts to existing methods, such Behrouz and Hashemi (2024) : Devlin et al. (2019): Liu et al. (2021), that use attention or SSMss as a black-box applied to 'flattened data' and rely on inductive biases to incorporate structural information.
Our motivation stems from the fact that SSMs on causal language modeling task do not require position embeddings and naturally capture the sequence order with their recurrence. We seek to formalize this result which then allows us to generalize it arbitrary graphs. To this end, we begin by defining the resolvent of linear operator and interpret its action when this operator is the adjacency matrix.
3.1 Resolvent of an Adjacency Matrix Accumulates Influence Along All Paths
A graph consists of a set of nodes V that represent data elements, and edges that encode the underlying topological structure. We conceptualize the associated adjacency matrix A E x|V as capturing the influence between neighboring nodes. Specifically, A, is the influence that node j has on node i, for cach odge (i,j). The desideratum is to exlend the notion of influence to all node pairs by incorporating the graph's structure, accounting for all possible paths between them. To model this cumulative influence, we introduce the concept of the resolvent of linear operator
Not SSMs admit SMA representation. We focus those that do, such LA, RetNet, and Mamba-2. In this work, term "SSMs" specifically to refer this restricted class.
4

---

Published in Transactions on Machine Learning Research (04/2025)
RTxT be linear operator, I the idenlily operator, and À complex. mumber. Then, the resolvent operator is defoned as:
Definition 3.1 (Resolvent of Linear Operator (Reed and Simon 1980)). Let A
R(A, A) = = - A)
(6)
which erists for all complex: rumberrs X that are not in the spectrum of A, i.e., X Afo(A) In this work, set A == 1 to remain in the field of real numbers, and this is done without loss of generality, as any choice of X is equivalent upto scaling of the model.
We now demonstrate how the resolvent operator captures the influence between any two nodes in the graph. Observe that the resolvent operation can be expanded using the Liouville-Neuman scries the operator norm of the adjacency matrix is strictly less than 1, i.e. |||| <1,
A) (I A) -
Intuitively any lerm, A this expansion represents the influence bet ween nodes i and j accumulated across all paths of length exactly & connecting them. We formalize this the following Proposition 3.2
Proposition 3.2 (A* accumulate influence through paths of length k). Given the weighted adjacency matris A A of graph g EV.E) with [V] T, where Asj is the weight of the (i,j) edge of the graph. Then (i,j)t entry of A is given as,
(A Σ
Aipi Apipz ... Apr-15-
P1.Pa..-PP--
where (Pk-1).,PP-i)) is on ordered sequence of verlices forming a path of length k from node to j.
Therefore, the series (I A) (Eq. sums up the influence node i on node j over all possible lengths.
3.2 SSMs operate on Directed Line Graph
We now show that SSMs naturally operate on a directed line graph. Specifically, let V be the set of tokens, and be the edges connecting token & to the next token + 1. Let the weighted adjacency matrix Ag.t = 1 110s, where ag is the SSM-specific parameter defined in Section 2.2
Recall from Section 2.2 that SSMs are equivalent to the matrix action of M L ② (CB") the input. We make the key observation that L is precisely the resolvent of A, that is L (I A)-1, This mathematically lies SSMs' recurrence to the directed line graph lopology, with the mask encoding the topology (Fig D Proposition 3.3. Under the notation established in Section & consider weighted directed graph G with nodes V ....... 1}, edges & = {(i iii E V, 0}, and the edgee weights W (w((-1,0) agli E V, > 0}. Let A be the weighted adjacency matria of incoming edges,
0
@1
0
0
A
02
0
(8)
;
0...0 0...0
0
0T-1 0
then L =00 A - (I-A)-1, and consequently, = ( CB
We interpret this result intuitively: In a directed line graph, there exactly one path between the tokens i.j with < j, and the corresponding mask matrix entry Lij = II ak, reflects the cumulative influence of the intervening tokens along this path. Furthermore, L, = for < j restricts influence in the forward direction, ensuring causality. This shows that SSMs inherently operate on a directed line graph with the L matrix encoding the topology.
5

---

Published in Transactions on Machine Learning Research (04/2025)
3.3 Generalizing SSMs to Arbitrary Graph Topologies
Building on Proposition 3.3 can generalize SSMs from causal sequences to arbitrary graph lopologies. Specifically, we compute the resolvent of the adjacency matrix, A, with output ((I ((]-)-= A) o (CB")).
We focus on the paramcterization of A with the following key points: 1. It cnsures the numerical stability of the method by addressing cases of non-invertibillty or poor conditioning of resolvent; 2. It generalizes Mamba-2's selectivity that allows for modeling long-range dependencies
Formally, consider graph g (V, with |V| T nodes, where each node has D channels. Let d denote the generalized hidden state size. For each node, we compute,
B = fB(X), C fc(X), V = fx(X)
(9)
A fa(X)
(10)
where the functions fs, fc, (x),), Sa are linear projections applied to the input, followed by local graph convolution over neighboring nodes and a Swish activation as chosen in Mamba-2. Furthermore, if the data set features edge embeddings E E RR R we define A' = (Z) E TRle), where Z E TRD is an edge embedding, as the selectivity matrix correspouding to the edges. Here fa is computed similarly to fa as in equation
We parameterize the A matrix for each edge (i,j) 3 as,
A A A (4J)
A.j exp
(11)
to incorporate context from both ends of the edge (i,j) as well as the edge embeddings. Here A,, A and (1,))) are are the learned selectivity parameters for the nodes i, j and edge (i.j) respoctively. To add directionality to Ai and to further increase the representational power of our model, we can also maintain
two (diffcrent) A's such that Aij = exp ( +A +A((.)
(1)
3
Note that the malrix I - A may be non-invertible or poorly conditioned, which would inhibit inverse computation and stable training of the model. We mitigate this issue with a data-dependent normalization paramcter t = (X) E RR,, computed similarly to A, and perform a row-wise normalization of the adjacency matrix using V. Specifically, for each row i E [T], we apply:
Ai.
1 A j exp(-V.)
where is a scaling hyperparameter. The following proposition shows that this normalization guarantees the convergence of the Neumann series for the adjacency matrix A.
Proposition 3.4. Under Gaussian initialization, the row-wise normalization strategy ensures that ||||| and [[ -| is bounded with probability > ((7)))
The proof for this proposition Appendix A.1 Finally, we compute the resolvent matrix L (I (I-A)- and the output y (L LCCVV.
4 Chimera With Improved Efficiency
While Chimera supports arbitrary graph topologies, computing the resolvent, incurs cubic cost in the number of nodes, which can be prohibitively expensive for large graphs.
In this section, we propose two algorithmic optimizations to mitigate this cost: First, we specialize Chimera a tractable yet. expressive subclass of Directed Acyclic Graphs (DAGs) for which the resolvent can be computed in linear time by running a recurrence on the topologically sorted graph. Second, for general graphs, we relax the resolvent computation using a finite approximation, achicving quadratic complexity of Transformers without domain-specific heuristics.
2Qur approach applies any SSM with an SMA representation and this work, we specifically use Mamba-2.

---

Published in Transactions on Machine Learning Research (04/2025)
4.1 Chimera DAGs
In this section, introduce tailored normalization scheme well as linear-time recurrent algorithm for Chimera on DAGs. We further propose a modern secelerator-rienddl technique to compute this resolvent efficiently by leveraging matrix multiplications, although at the cost of quadratic FLOPs.
Our choice of the DAG subclass motivated by its expressivily. Topologies such as undirected line and grid graphs can be canonically decomposed into DAGs: line graph divides into two directed line graphs (Fig and grid graph divides into four directed grid graphs (Fig 3). This allows for efficient Chimera that preserves the grid topology of image.
4.1.1 Chimera on DAGs: The method
(V,E), with | T nodes, each with D channels and hidden state size of d. For any node let p(i) be the set of its parents. Let B, C, V A be the imput projections defined in Section 3 We define the adjacency matrix A as A. exp( (A)) for each (i,j) E E, and set B; = (EGJ)e Aij) B; for each node i. In this work, we define Aij = (A; + A2)/2, but more generally one take Aij [(A, Aj) for any suitable (e.g. symmetric) function of the nodewise parameters. Then the output y (L @ (CB"))V.
Formally, consider DAG,
We first show that the resolvent (I AI- exists.
Proposition 4.1. For DAG, A is nilpotent, that is A 0. Therefore, the inverse (I - -)- exists and is given by the finile sum.
L- (I-
Σ A
(12)
While the resolvent always exists, we note that its entries can become exceedingly large which can cause numerical instabilities. To show this, we first represent this method in its recurrent view in Prop. 4.2 (and is visualized in Figure 4
Proposition 4.2. Our method computes the following recurrence each channel of V:
h4 Aigh B, y1 C.
Aighy jEP()
(13)
where h; O for all leaf nodes I.
Recall from Section 3.1 that each Lij represents the cumulative sum of all paths from node j to and in the worst case, the number of such paths and its resolvent entry grows exponentially with distance. To address this, we introduce normalization scheme built directly into the recurrence: Proposition 4.3. The normalized method is:
h V Piiil jEP())
Σ
(Aigh, - B.v))
(14)
y: C h4s
(15)
This normalization ensures that Car(C h2) S 1 under the assumption that the vectors (Bur, C.ty are i.dd Gaussians, that is Bi C, ~ I.).
1
2
3
+
2
3
Figure 2: Canonical DAG decompasition of undirected line graph topology (left) into two directed line graph topologies (right).

---

Published in Transactions on Machine Learning Research (04/2025)
The assumption that for all i we have B,, U, C. NO0, Ia) is justified given that weights usually initialized with zero-mean and scaled-identity covariance (Xavier initializttion Glorot and Bengio (010 ). in addition to the fact that such distributions are approximately preserved throughout training via normalization techniques. The proof follows by induction on the time step t, ensuring that the output variance is bounded by 1, Var(C; S 1. The detailed proof Appendix A.2 representation, we define,
To incorporate this normalization in the SMA
A
A,
B
(n)
B, L= (I-A)
(16)
V V(r(S]
V VI(()
and compute the output y = (L @ (C
4.1.2 Chimera is efficient DAGs
Finally, we highlight that DAGs are a particularly important case of Chimera because additional efficiency benefits, both through recurrent and vectorized implementations.
Linear-Time Complexity in the Recurrent View The intuition for linear complexity is that the resolvent operation for DAGs is finite because of the lack of cycles. From the adjacency matrix perspective, A is nilpotent, i.e. A O, where k is the diameter of the graph (Prop 4.1). Thus, when running Chimera as recurrence on the DAG, the resolvent operation converges after one pass over the graph in the topologically-sortedd order, which takes linear time.
Proposition 4.4. The Chimero structured mask matriz L can be computed in O( + [8]) complexity where [V], [8] is the number of vertices and edges of the graph, respectively.
The proof is provided in Appendix A.3
We note that the linear-time complexity of Mamba-2 can be seen as a special case of Proposition 4.4 specialized to the directed line graph, where both [V and |E] is equal to the sequence length.
Improving Efficiency Through Matrix Multiplications Finally, note that modern hardware accelerators such GPUs and TPUs, various compulational algorithms can have different efficiency tradeoffs. For example, on directed line graphs, the naive computation of SSMs and RNNs as recurrence is not parallelizable and is inefficient in practice (Gu and Dao 2023). In the case of DAGs, we present a technique to reduce both the forward and backward pass for Chimera to leverage only matrix multiplications which are heavily optimized on modern accelerators. Although this technique is highly parallelizable, it requires the materialization of the adjacency matrix which quadratic in the number of nodes, |V]. the worst-case, i.c. [DK) this bound is tight. However, for specialized structured subclasses (e.g., line graphs) where the number of edges is O(V), this cost can be significantly reduced (e.g. via existing Mamba-2 kernels for line graphs). The proof for the following theorem in Appendix A.4
a complete transitive DAG with |F| = 2
Theorem 4.5. In case of Chimera DAGs, the forward pass can be computed with Oloog dia(G)) matrir multiplications where dia(g) is the diameter of the graph (i.e. length of the longest path), and the backward pass can be computed with O(1) matria multiplications.
4.2 Approximate Chimera for General Topology
While DAGs allow for efficient computation in structured domains like images and language, directly computing the resolvent. for general graph topology remains computationally expensive. To address this, we use a
2
3
2
3
2
3
1
2
3
1
2
3
I
1
t
t
4
5
6
=
4
5
6
+
4
5
6
+
4
5
6
+
4
5
6
8
7
8
9
7
8
9
7
8
9
7
8
9
Figure 3: Grid graph (left). The canonical 2D-DAG decomposition of the grid graph (right). These graphs are sufficient to capture the influence between all pairs nodes in the undirected grid graph.
8

---

Published in Transactions on Machine Learning Research (04/2025)
ho
h1
ao2
11
2
h2 = 1//2 (oozho + ag2ha)
B2x2/V2 (log aoz log a12)
Chimera DAGs: A visualization of the normalized recurrence. The absence of cycles in DAGs enables a recurrent view of the method which allows for fast linear-time computation.
Figure 4:
Table 1: Comparing Chimera on the undirected line graph (UG), and on DAG decomposed directed line graphs (DAG) with other stato-of-tho-art models including M2 (Fu et al. 2023), MLP-Mixer (Tolstikhin et al. 2021), FNet (Lee-Thorp et al. 2022), BERT (Devlin et al. 2019) on GLUE benchmark. Chimera outperforms all baselines including BERT with linear time complexity. Here the best numbers are highlighted in bold and the second best numbers for each task are underlined.
Method
# PParams
Pretrain
GLUE Tasks
GLUE
Cee
Aoe (%)
MNLI
QNLI
QQP
RTE
SST2
MRPC
COLA
STS
Avg
BERT-Basc
110M
1.59
67.3
84.1
89.8
91.2
77.2
91.2
87.5
54.6
88.9
83,2
MLP-Mixer
112M
1.77
63.5
77.2
82.4
87.6
67.3
90.5
86.5
43.0
85.2
77.5
FNet.
112M
1.94
61.3
74.9
82.1
85.7
63.6
87.6
86.4
42.7
83.1
75.8
M2
116M
1.65
65.9
80.5
86.0
87.0
69.3
92.3
89.2
56.0
86.9
80.9
Chimera (UG)
110M
1.49
68.5
Chimera (DAG)
110M
1.46
68.9
84.11
89.78
89.77
77.98
93.69
90.36
57.08
88.68
83.93
finite-sum relaxation of the resolvent operator and truncate its corresponding Neumann series sum (Eq. 7
at some maximum power k E N > 0. Specifically, let A be the (weighted) adjacency matrix of the graph topology defined Section 3.3 then,
L
Σ i=0
A'
i
Σ i=0
A'
(17)
We choose & = dia(G), the diameter of the graph, to ensure that has access to the global structure of the graph, that is, it includes contributions from every edge and node in the graph.
Proposition 4.6. If l 2 dia(g), then for any pair of nodes (i.j), if Lij > 0 the original method, then Lij > in the fonile-sum relazalion.
As in Section 4.1.2 we can compute this approximation efficiently using the squaring trick:
i = -I+ AZ) A+) (I AP)
(18)
where is the smallest power of 2 larger than or equal to the graph diameter dia(g). This reduces the computational cost of the method to O(log(dia({)) matrix multiplications.
For general graphs, since we cannot exploit the underlying structure adjacency matrix A to design efficient algorithms, the worst-case complexity of the finite sum approximation remains quadratic. This highlights a crucial point: as the complexity of the underlying structure increases, the computational cost of calculating the matrix L will also grow accordingly.

---

Published in Transactions on Machine Learning Research (04/2025)
5 Experiments
In this section, we will demonstrate that directly incorporating topology is powerful inductive bios for diverse domains such as language, images and graphs, climinating the need for domain-specific heuristics. Chimera consistently achieves state-of the-art performance in these domains. On language, it outperforms BERT on the GLUE benchmark (Wang et al. 2019) by a GLUE score of 0.7. On images, it surpasses ViT models on the ImageNet-lk classification (Deng et al., 2009) task by 2.6%. On general graphs, Chimera outperforms strong baselines the Long Range Graph Benchmark (Dwivedi et al. 2021 which highlights our method's s ability to model long range interactions on graphs.
5.1 Masked Language Modeling
We evaluate Chimera bidirectional language modeling, which has line graph topology (Fig. 2 We test two Chimera variants: the general method (Sec. 3 applied to an undirocted line graph, and the DAG method (Sec. 4.1.1,, applied to the canonical DAG decomposition of undirected line graphs into two directed line graphs and summiing the resolvents of both DAGs (Fig.
2 Both methods are trained on the Masked Language Modeling (MLM) (Devlin et al.] 2019) task on the C4 dataset (Raffel et al.) 2020) for 70k steps, following the recipe used in M2 (Fu et al.) 2023). The models are then fine-tuned on the GLUE benchmark. For baselines, we compare our methods with other sequence mixers such M2 Fu et al. (2023), as well models such as MLP-Mixer Tolstikhin ct al.
2021 and FNet Lec-Thorp et al. (2022) in addition to the
Transformer based BERT model Devlin et al.
2019)) We choose these baselines to highlight the performance
of our model when compared to different type of sequence mixing paradigms applied to large scaled language modeling tasks. We refer the reader to Appendix
C for the architectural and hyper-parameter details.
From Table [ observe that while BERT outperforms other linear baselines such as M2, MLP-Mixer, FNel it does so with an additional quadratic cost. In contrast, Chimera achieves the best of both worlds, incurring a linear time complexity while achieving strong performance. This capability arises from two key factors: first, our parameterization of the adjacency matrix allows the model to effectively modulate the influence between tokens in the sequence, leading to strong performance. Second, the structured nature of the adjacency matrix enables a fast, linear-time resolvent operation, improving the method's computational efficiency. Additionally, note that our undirected graph (UG) variant performs competitively with BERT while surpassing other recent linear baselines.
5.2 ImageNet-1k 1k Classification
Table 2: Top-1, Top-5 accuracies of various meth- ods on ImageNet- 1K. Chimera outperforms the stan- dard attention baseline ViT-B, as well as other sub- quadratic baselines.
Comparing 2D grid structure with 1D flattening of patches. We see that maintaining the 2D DAG structure outperforms method where the underlying topological structure is flattened, showing maintaining the topological structure matters.
Table 3: Ablation:
Top-1 (%)
Top-5 (%)
Method (88M)
Top-1 (%)
Top-5 (%)
Acc
ACCEMA
Acc
ACCEMA
Method (22M)
ViT-B
78.8
80.6
91.2
95.2
Acc
AcceMA
Ace
AcegMA
S4- VIT-B
79.4
80.4
94.2
95.1
Fwd (1D)
73.8
73.8
91.6
91.6
Hyena- ViT-B
78.4
76.4
94.0
93.0
Fwd & Rev (ID)
76.5
75.6
93.4
92.8
Chimera- VBT-B
81.4
82.1
95.4
95.9
2D DAG
77.8
76.7
93.9
93.5
We evaluate Chimera the ImageNet-1k 1k (Deng al. 2009 classification task that has grid graph topology. We compare Chimera applied to the 2D-DAG decomposition (Figure 3) topology against stale-of-the-art ViT based models, a standard architecture that is used for ImageNet classification. Specifically we use ViT-B which has 88M parameters as well as other SSM based basclines like Hyena (Poli ct al. 2023), S4 (Gu et al. 2022 in Table 2 to highlight how our method compares with other state-space model based architectures.
We use slightly modified normalization scheme for the undirected line graph method to allow for larger selectivity values in the adjaceney matrix. See Appendix R. for details
10

---

Published in Transactions on Machine Learning Research (04/2025)
Table 4: Evaluation of Chimera on LRGB Tasks (Dwivedi et al., 2022 The first section shows the best performing numbers cited in the papers that introduce the given basclines. The second section shows the result of better hyperparameter tuned baselines introduced by Tönshoff et al. (2023). Finally, we also compare with other baselines that use SSMs as blackbox replacement for a Transformer. Here the best numbers are highlighted in bold.
Peptides-Func
Peptides-Struct
PascalVOC-SP
COCO-SP
Method (< 500k params)
AP (t)
MAE
F1 (t)
F1
GCN
Kipf and Welling 2016
0.5930++0.00 0023
0.3496: 0013
0.1268=0.0000
0.0041=0.0010
GINE HHu ot al. 2019
0.549840. 0079
0.3547::0 0045
0.1265=0.0077
0.1339=0.0044
Gated-G Bresson and Laurent.
2017
0.586440.000 0077
0.3420:1:0 0013
0.2873=0.021
0.2611=0.0044
SAN SAN-LapPE Kreuzer al. 2021
0.638440.000
0.2683::0 0043
0.3230=0.0083
0.2592=0.0158
Exphormer Shirzad el al. 2023
0.6527:+0000
0.24814:0 0007
0.3975=0.0037
0.3430=0.0108
Big+BiiBBird Ramppack el al.
2022
0.5854++0.007
0.2842++0.011 0.033
0.2762+0.0065
0.2622+0.0008
GraphGPS Trarsssr-rreeee Hampaiik et al. 2022
0.6575-+0.0049
05610+00.0013
0.3689+0.0131
0.0154
GCN Tönshoff al. 2023
0,6860 + 0.0050
0,2460 + 0.0007
0,2078 = 0.0031
0.1338
0.0007
Gated-GON Tonsholl et
2023
0.6765 + 0.0047
0.2477 + 0.0009
0.3880 = 0.0040
0.2922 0.0018
GINE Tönsholl et
2023
0.6621 + 0.0067
0.2473 + 0.0017
0.2718 + 0.0054
0.2125 0.0009
PeaphGPS=TTaansooon
Tonshoff al.
2023
0.6534 + 0.0091
0.2509 + 0.0014
0.4440 + 0.0054
0.3884 0.0055
Graph-Mamba
Wang al.
2024
0.6739 0.0087
0.2478 +: 0.0016
0.4191 + 0.0126
0.3960 + 0.0175
Graph Mamba Bchrouz and Hashemi
2024
0.7071 0.0083
0,2473 1 0.0025
0.4393 + 0.0112
0.3974 = 0.0101
NelkelWalker
Chen et al.
2024
0.7096 +: 0.0078
(124468 + 0.0005
0.4912 = 0.0042
0.4398 + 0.0033
Chimera (Ours)
0.7021 = 0.003
0.2433 + 0.0006
0.4460 0.007
1.3977
We note that all these baselines flatten the image into a 1D sequence and apply 1D sequence models, and do not take into account the underlying topology. For our experiments, we simply replace the SSD layer in the Mamba block introduced in Dao and Gu (2024) with Chimera, and use the ViT-B training recipe with minimal hyperparameter tuning.
Table 2 shows that Chimera's 2D-DAG decomposition outperforms VIT by 2.6%. We note that our method does not require any additional position embeddings which are still an active area of research for ViT (Heo et al. 2024). We outperform methods such as Hyena (Poli et al. 2023 by 3%, and S4 (Gu et al. 2022 by 2% that lincarize the data and then apply an SSM on it.
Furthermore, to demonstrate the importance of incorporating topology, we perform ablation where we progressively degrade the grid-graph structure, observing a monotonic drop in performance. We consider three topologies: 2D DAG is the 2D DAG docomposition that retains the grid structure (Fig 3 right); Fwd & Rev (1D) flattens the grid into a 1D sequence with bidirectional edges like ViT (Fig 5 top); Fwd (1D) is a 1D graph with only forward edges (Fig 5 bottom). We observe from Table 3 that as the topology is lost, the accuracy drops from 77.8% (2D-DAG) to 76.5% (Fwd Rev) to 73.8% (Fwd).
5.3 Long Range Graph Benchmark
We evaluate Chimera on the Long Range Graph Benchmark (LRGB) (wiveedi et al. 2022
This benchmark comprises tasks designed to challenge models in their ability to effectively capture both local and long- range interactions within graph structures. We compare against convolution- based (GCN Kipf and Welling (2016). GatedGCN Bresson and Laurent (2017)), Transformer-baat based (GraphGPS Rampášek et al. (2022)) Mamba- based (Graph-Mamba Wang et al. (2024), Graph Mamba Behrouz and Hashemi (2024)), and other
2
4
8
2
4
6
8
Figure 5: Progressively destroying the 2D grid graph topology. Fwd & Rey (top): 1D flattened grid with bidirectional edges. Fud (bottom): 1D flattened grid graph with only forward edges.
11

---

Published in Transactions on Machine Learning Research (04/2025)
baselines like GINE Hu et al. 2001 as well their hyperparameter tuned versions introduced in Tönshoff et al. (2023). These baselines incorporate topology using variety of techniques: convolution ones use local aggregation, transformer ones use local and global aggregation via position embeddings, and Mamba ones use "data flattening" along with random walks, position emboddings, and local encodings. The diversity of these methods highlights the significant research effort dedicated to heuristics to incorporate topology, contrast to our unified approach.
We note that while recent methods like NeuralWalker Chen et al. 2024 achieves state-of-the-art results LRGB, but unlike Chimera and our chosen baselines, it modifies the graph structure by sampling subgraphs via random walks and modeling them soquentially. As our goal is to evaluate models that operate directly on the original graph. That said, Neural is complementary and could potentially be combined with Chimera layers.
We show that Chimera achieves strong performance across all LRGB tasks (Table 4
Notably, we observe that (asks such Peptides-Funce and Seplides-Struc,, where convolution-based models lypically outperform transformers, Chimera outperforms or matches their performance. Furthermore, tasks like PascalVOC and COCO where transformers do well, Chimera is competitive with the best baselines. This validates our grounded approach which effectively captures both local and global information.
In Table 5 we evaluate the approximate variant of Chimera with a finite-sum relaxation (Sec 4.2 that truncates the Neumann series at the diameter of the graph. We show that the approximation variant matches the strong transformer baseline of GraphGPS, however fully leveraging the entire graph structure in Chimera provides clear performance benefits.
6 Discussion and Future Work
We propose Chimera, a unified framework that directly incorporates the underlying graph topology in a principled way. Unlike prior approaches that apply attention or State Space Models (SSMs) by flattening the data, we instead generalize SSMs originally designed operate on sequences without position embeddings to any graph topology. We show that Chimera achieves strong performance across domains including language, vision, and graph tasks, consistently surpassing baselines, which validates our premise and the proposed solution. We further show that for the subclass of graphs which can be decomposed into DAGs, the recurrent form of Chimera affords linear complexity.
Our work has a few limitations, the most significant being that for general graphs, fully capturing all node interactions results in a cubic computational cost. This can be reduced to a quadratic cost through a straighttorward approximation that truncates the infinite sum a finite terms determined by the diameter of the graph. That said, still believe there is significant potential for hardware optimization just Mamba-based methods benefited greatly from dedicated CUDA kernels. Nevertheless, we note that the current implementation of Chimera achieves a reasonable time ratio of ~ 1.5x compared to Transformer- architectures which we believe provides a starting point for further exploration across novel domains.
We believe that developing optimized kernels for specific graph structures such as grid-graphs along with exploring graph approximations through DAG decompositions is promising direction for future work. We are hopeful that the community will apply Chimera a broader range of domains with inherent topological structures and continues to develop more efficient and performant extensions of Chimera.
Table 5: Ablation: Chimera with approximate resolvent is competitive with the Transformer baseline. This alleviates the cubic cost of evaluating the exact resolvent.
Peptides- Func
Peptides-Struct
PascalVOC-SP
COCO-SP
Method
AP (t)
MAE (1)
F1 (?)
F1 (t)
ChaphGPSSTranstommmn
0.6534 + 0.0091
0.2509 + 0.0014
0.4440 + 0.0054
0.3884 + 0.0055
Chimera (Approx)
0.6979 + 0.0057
0.2420 + 0.0013
0.4353 + 0.00307
0.3833 + 0.0006
Chimera (Ours)
0.7021 0.003
0.2433 0.0006
0.446 + 0.007
0.3977 + 0.016
12

---

Published in Transactions on Machine Learning Research (04/2025)
References
Ali Behrouz and Farnoosh Hashemi. 2024.
Graph mamba: Towards learning on graphs with state space models,
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. ar preprint arXi::1711.005553 2017.
Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks, arXiv preprint arXiv:2406.0 03386, 2024.
Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality, In International Conference on Machine Learning (ICML), 2024.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Jacob Devlin, Ming-Wat Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. NAACL, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition al scale. ICLR, 2021.
Vijay Prakash Dwivedi, Anh Than Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint Xiv:2 10.07875, 2021.
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: 2022.
Daniel Y Fu, Simran Arora, Jessica Grogan, Isys Johnson, Sabri Eyuboglu, Armin W Thomas, Benjamin Spector, Michael Poli, Atri Rudra, and Christopher Ré. Monarch mixer: A simple sub-quadratic gemm- based architecture. NewrIPS, 2023.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirleenth international conference on artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
Albert Gu and Tri Dao. Mamba: Linear-time sequence sequeeee modeling with selective state spaces. arXio preprint arXiv:2312.0075. 2023.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. ICI.R, 2022.
Byeongho Heo, Song Park, Dongyoon Han, and Sangdoo Yun. Rotary position embedding for vision transformer. arXiv preprint vrXiv:2403.13900 2024.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategics for pro-training graph neural networks. arXiv preprint arXiv:1905.I 12265, 2019.
Sukjun Hwang, Aakash Lahoti, Tri Dao, and Albert Gu. Hydra: Bidirectional state space models through generalized matrix mixers. arXiv preprint (ET.::2077.094... 2024.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are runs: Fast autoregressive transformers with lincar attention. In JCML, 2020.
Amirhosscin Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Roddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36, 2024.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 02907, 2016.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tosson. Rethinking graph transformers with spectral attention. Advonces in Neural Information Processing Systems, 34: 21618 21629, 2021.
James Lee- Thorp, Joshua Ainslic, Ilya Eckstein, and Santiago Ontanon. Fnet: Mixing tokens with fourier transforms. NAACL, 2022.
Yue Liu, Yunjie Tian, Yuzhong Zhao, Hongtian Yu, Lingxi Xie, Yaowei Wang, Qixiang Ye, and Yunfan Liu. Vmamba: Visual state space model, 2024.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin Transformer: Hicrarchical vision Transformer using shifted windows. In Proceedings of the IEEE/CVF International Conference on Compuler Vision (ICCV), 2021.
Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y. Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. In ICML, 2023.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. JMLR, 2020.
Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint arxiv: 710 710.05941, 2017.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501 14515, 2022.
Michael Reed and Barry Simon. Methods of modern mathematical physics. vol. 1. Functional analysis. Academic San Diego, 1980.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613 31632. PMLR, 2023.
Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfong Liu. Roformer: Enhanced transformer with rotary position embedding, 2023. URL httttp:://axxi..rrr/abbb//// 0984/
Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models, 2023.
Iyya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mlp-mixer: An all-mlp architecture for vision. NewrIPS, 2021.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassessing the long-range graph benchmark. arXiv preprinl arXiv:2309. 00360,,00077.00 2023.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, TimothAle Lacroix, Baptiste RoziAfre, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL
https://arre http:///axxvvv.oo/bbbaa arg/aba/2200 2302. 13971
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Miaia Polosukhin. Attention is all you need. NewrIPS, 2017.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In ICLR, 2019.
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long- range graph sequence modeling with selective state spaces, 2024.
15

---

Published in Transactions on Machine Learning Research (04/2025)
A Deferred Proofs
A.1 Proof of Proposition 3.4
Proof. Let G, ~ Ir) be ii.d. random Gaussian vectors. Assuming Gaussian initialization for the adjacency matrix A, it can be expressed as:
A
76
(19)
||, + v))
We first show that ||||| < 1. From the concentration of the Gaussian random vector norm, ||ll| 2 VT/2 for all tokens i, with probability 2 exp(T/8). Since exp( V,) 2 0, |||||| + exp(-v,) 2 vT/2. Consider
any unit vector u, then
yE! u
2e, VT
VTe
Aull
S 27
2ye < 1I
(20)
|s:|| exp( v:)
VT
i=1
with probability greater than 1 1 ( ) were C22 c No0 1). Finally, since the operator norm of ||||| is less
than one, we apply Banach's Lemma to get,
1
II - A) v 1- |A
(21)
which implies that the inverse exists.
A.2 Proof of Proposition 4.3 Proof.
Var C h.)
Σ
Air Var(C Var(C Boss)
(22)
Ip(t)
jEp(1)
Ag Var Var(C]T1) h2) + In( (n(As))
Σ
(23)
Ip(i)
jEp(1)
where we have used the fact that Var(C) h,) = Var(C, hy), and that the variance of X2 distribution with d degrees of freedom is 2d. Let d 2 4, then
Var(CTT))
Σ
Au + 2 =2 [p(i)
s
11
(24)
[p(i]
jEp(i)
jEp(1)
where we have used the fact that Aij [0, 1].
A.3 Proof of Proposition 4.4
Proof. In the structured masked atlention (SMA) framework Dao and Gu (2024), , the computational complexity is the cost of the matrix-vector multiplication by the mask matrix L (I A)-1, For DAGs, A is (up to conjugation by permutation) lower-triangular matrix with [1] nonzero entries. Computing y = (I A)- 'lx
reduces to solving the system (I A)y x via forward substitution.
We perform Gaussian elimination by iterating over the ordered list {O...., | - 1} and choosing the pivots (i, Since I-A A lower-triangular, each pivot operation affects only a single column rather than the entire row, reducing the cost per step to ((nn i])), where nnz(-) denotes the number of non-zero entries. Summing over columns, the complexity is,
M Σ mnz (1))
0
((nnz(A) = O(V + +18))
16

---

Published in Transactions on Machine Learning Research (04/2025)
For motivating example of Mamba, I - A has exactly 2|V| nonzero entries, ensuring tinear-time complexity.
A.4 Proof of Theorem 4.5
Proof. Backward pass. The local update rule of backpropagation requires applying the chain rule through the matrix inverse operation, in particular, using the following identity applied to Y (I A),
0Y Y--1 Y
OY
(25)
00
00
Because Y-1 is already computed the forward pass, can be cached, and then the marginal cost of the local backpropagation is simply two extra matrix multiplications.
Forward pass. To compute L (I A)-1 more efficiently for DAGs, leverage the equivalence of Neumann series to the series L = I + A + A +..., which comes to a finite sum for DAGs due to the nilpotence of A matrix. We compute this sum more efficiently using the "squaring trick" as,
(I+ A7) 44) ... (I A*+
(26)
where & is the smallest power of 2 larger than the graph diameter dia(G). This can be computed using O(log(dia())) matrix multiplications to compute the powers of A for powers-of-two exponents, and then (log(dia(())) matrix multiplications to multiply together the right-hand side.
17

---

Published in Transactions on Machine Learning Research (04/2025)
B Additional Experiments
B.1 MLM: Chimera on Undirected Line Graphs
For an undirected line graph (Figure)
left), the adjacency matrix A takes the following form:
0
a12
0
a21
0
d23
0
A
0
a32
0
0
0...0
0-..0
0
0
0
0
ensure the existence of (I A)-,) we introduced a row-wise sum normalization Aig strategy, wherein we normalized each row of the adjacency matrix with Σj +
As discussed in Section 3.3
constraint is designed for general graphs, it is not sufficiently expressive. Therefore, v,, However, since this instead use strictly more expressive constraint for line graphs which enforces Aij AJz V, S 1 on each simple cycle of the graph.
Proposition B.1. Under the above constraint, the inverse (I -A)- erists as for any two nodes, the sum of all paths between them is upper bounded by (1//4)) & 1/3.
B.2 Imagenet: Parameter Sharing Ablation
We study the trade-off between sharing parameters for B, C across different graphs as a domain-dependent design choice. We explore four settings: No sharing, Complete sharing, Rou-wise sharing, and Diagonal shoring across the four DAGs. From Table we observe that diagonal sharing achieves the best performance, indicating strikes the optimal tradeoff between parameter sharing and other modes of increasing expressivity for modeling image data.
Top-1 (%)
Top-5 (%)
Method (22M)
Acc
AcCeMA
Acc
ACCEMA
None
77.10
76.13
93.55
93.15
Complete
77.25
76.09
93.75
93.21
Row-wise
77.46
76.57
93.76
93.37
Diagonal
77.80
76.69
93.87
93.53
Table Ablation: Diagonal parameter sharing works best.
B.3 Chimera When Both # Layers and # Parameters Are Controlled
Chimera's architecture builds on the Mamba Block from Mamba-2, which utilizes a greater number of layers than Transformers due to its higher parameter efficiency. In this section, we conduct an ablation study where both the number of layers and total parameter count controlled by adjusting the expansion factor in compare three models the bidirectional language modeling task:
the Mamba Block to 4. Specifically,
Chimera-12L: 12 layers, baseline configuration with 70M parameters.
BERT-6L: 6-layer Transformer baseline with 70M parameters.
Chimera-6L: 6 layers with an expansion factor of 4, maintaining the same parameter count as the other models.
To reduce computational costs, we train these models on reduced ablation setting with 98M steps instead of the standard 245M steps and the results are summarized in the table below. Notably, Chimera-6L and Chimera-127 achieve nearly identical performance, both significantly outperforming BERT-6T. This
18

---

Published in Transactions on Machine Learning Research (04/2025)
Table 7: Ablation: Chimera maintains strong performance when both number layers and number of parameters are controlled.
Evaluation Metrics
Model
Masked Aocuracy (f)
Cross- Enees-Entropy Loss (U)
BERT-6L
0.6176
1.9466
Chimera- 6L
0.6360
1.8108
Chimera-12h 12L
0.6363
1.8142
demonstrates that Chimera's s improvements are not simply a result of increased depth but rather stem from its core methodological advancements.
19

---

Published in Transactions on Machine Learning Research (04/2025)
C
Architectural Details
+
Y
Z
fz
C
BT
L
V
fc
f f
B
A
X
Figure 6: Chimera's Architecture: The output of the Chimera layer is embedded within the gated block introduced in Mamba-2 (Dao and Gu 2024 Here X matrix denotes the input to the block, and fe, JB. Sa and Jv are data dependent project ions defined in Section
2 The operator @ denotes element-wise multiplications between matrices, and + defines addition. The output from the Chimera layer passed through a Gated-MLP, final projection fy, followed by residual connection.
C.1 Masked Language Modeling
In Table S we provide the architectural and training details for BERT-B and Chimera on the MLM task. For both the models, we follow the M2 recipe from Fu al. (2023), adjusting the number of layers to for BERT-B and 23 for Chimera to control for the number of parameters. We conducted small sweep to fine-tune the learning rate for Chimera, choosing 8e - over BERT-B's 5e 4.
C.2 Imagenet-11 1k Classification
For the image classification experiments, we largely follow the ViT-B recipe with the following adjustments as shown in Table g where the hyperparameters are carefully tuned and hence different from Table g in order to perform best on the image classification task. To control for the number of parameters, we adjust the number of layers from 12 for ViT-B 22 for Chimera. Additionally, we reduce the Cutmix augmentation from 1.0 to 0.1, as Chimera's stronger inductive bias mitigates the risk of overfitting.
20

---

Published in Transactions on Machine Learning Research (04/2025)
Table 8: Architectural and Training Details for BERT-B and Chimera on MLM
Parameter
BERT-B (110M)
Chimera (110M)
Model dimension (dmodel)
768
768
Layers
12
23
Max sequence length
128
128
Num Heads
12
12
Head size
64
64
Optimizer
Decoupled AdamW
Decoupled AdamW
Learning
8e
Optimizer momentum
31 0.9, 32 0.98
B1 0.9, 32 0.98
Weight decay
1e
le 5
Batch size
4096
4096
Learning rate schedule
Linear decay with warmup Linear decay with warmup 70k
Training steps
70k
MLM Probability
0.3
0.3
In Table 10 we present the reduced setting used for our ablation studies in Tables 6 and where we match
the number parameters of ViT-S (22M).
Table Hyporparameters used for ViT-B and Chimera for ImageNet- 1K classification task
Parameter
ViT-B (88M)
Chimera (88M)
Image size
224
224
Optimizer
AdamW
Adamm
Optimizer momentum
31, 82 0.9, 0.999
81, 0.9, 0.999
Weight init
trunc. normal (std=0.02)
trunc. normal (std=0.02)
Learning rate
le 3
le 3
Weight decay
0.05
0.05
Batch size
1024
1024
Training epochs
310
310
Learning rate schedule
cosine decay 10
cosine decay 10
Warmup epochs
Warmup schedule
linear
linear
Patch Size
16
16
Layers
12
22
Num Heads
12
12
Droppath
0.3
0.3
Randaugment.
(9,0.5,layers-
layers
Mixup
0.8
0.8
Cutmix
1.0
0.1
Random erasing
0.25
0.25
Label smoothing
0.1
0.25
Stochastic depth
0.1
0. 0.25
Exp. mov. avg (EMA)
0.99996
0.99996
C.3 Long Range Graph Benchmark
train Chimera on the Long Range Graph Benchmark we follow similar training recipe that provided in Rampášck al. (2022) where we replace the Transformer layers with Chimera layers. Moreover, line with the baselines, make that models have less than 500k parameters. While training Chimera
21

---

Published in Transactions on Machine Learning Research (04/2025)
Table 10: Key differences between the original and the ablation setting for Chimera
Parameter
Chimera-S (2D)
Model dimension (dmodet)
384
Number of layers
22
Number of Heads
3
Droppath
0.1
graphs we remove the Gated-MLP layer defined in Figure We did this to keep our training recipe as close that provided in Rampášck (2022) and highlight the effectiveness of Chimera. The hyperparameters used to train Chimera provided in Table 11
Table 11: Hyperparameters rumning Chimera on the Long Range Graph Benchmark
Peptides-Func
Pascal Peptides-Struct
COCO-SP
Learning Rate
0.001
0.0015
0.0035
0.0035
Optimizer
Adam
Adam
Adam
Adam
dropout
0.1
0.1
0.05
0.05
#layers
8
8
8
8
hidden dim.
64
64
64
64
hidden state dim.
96
80
64
64
mum heads
2
4
batch size
64
#epochs
200
200
200
200
norm
LayerNorm
LayerNorm
LayerNorm
LayerNorm
MPNN
GCN
GCN
GCN
GCN
# Param.
499k
504k
489k
489k
22


Reviews:
[{"review_id": "fENV2R8dOi", "reviewer": "Reviewer_z8NQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* The observation that many state-of-the-art deep learning models depend on heuristic choices of positional embeddings is crucial. As such, architectural alternatives which model data in a more principled way are a highly important and timely research direction.\n* The paper is written very clearly and is well motivated.\n* I especially appreciate that the authors consider language, vision, and general graph tasks, instead of just focussing on one. As a result, the authors convinced me of the generality of Chimera.\n* The focus on implementation efficiency, especially for modern GPU hardware, is important and greatly strengthens the contributions of the paper.\n\n### Weaknesses\n* Instead of focussing on an approximation method to reduce the complexity of Chimera on general graphs, the authors should consider efficient CUDA implementations to speed up computation, or discuss potential difficulties such an implementation.\n* The fact that, on general graphs, the approximative Chimera still requires quadratic complexity might be a limiting factor when applying Chimera to general problems in graph learning (which often require linear-time models to be feasible).\n* The selection of the baselines for the LRGB benchmark is not fully representative of the current state-of-the-art. For example, NeuralWalker (https://arxiv.org/abs/2406.03386v2) beats Chimera on 3/4 datasets and clearly outperforms it on 2 (COCO and Pascal).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors develop a generalization of state-space models (SSMs) to directly leverage the topology of the processed data, which could be sequences, pixel grids, or general graphs. Compared to the common approach of applying transformers to such data and adding appropriate positional embeddings, the authors instead design Chimera, a SSM which can process the data in a principled way. Further, the authors suggest an efficient implementation of Chimera, decomposing graph topologies into directed acyclic graphs (DAGs), a graph class for which efficient, and GPU-parallelized implementations exist. For example, line and grid graphs, such as those appearing in language modeling and vision, can be decomposed into a combination of DAGs. For general graphs, the authors propose an approximation technique which allows Chimera to run in quadratic time. A series of experiments reveals that Chimera can outperform classical deep learning models for language and vision, such as BERT or ViT. Further, on general graph tasks, Chimera is competitive with state-of-the-art graph models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following suggestions are derived from *Weaknesses* and are *not* critical to my assessment of the paper:\n\n* Adding a discussion on challenges with efficient CUDA implementations of Chimera. While the authors already list the lack of specialized implementations as limitations of Chimera, it would be highly interesting what challenges the authors faced or foresee in implementing Chimera efficiently.\n* Updating the LRGB table to include stronger baselines, e.g., NeuralWalker.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pnuUU3hJLg", "reviewer": "Reviewer_yENo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe major strength of this work lies in its principled approach to eliminating heuristics for incorporating data topology within the SSM framework. It is particularly noteworthy that the authors achieve better performance than existing SSMs, despite those models already encoding some knowledge of sequence topology. This result highlights the effectiveness of directly incorporating topology as a powerful inductive bias across diverse domains such as language, images, and graphs, without relying on domain-specific heuristics.\n\n**Weaknesses**\n\nMy primary concern with this paper is the lack of clarity in the manuscript, which would benefit from careful revision and final polishing. In particular, the discussion of time and space complexities, especially in comparison to Transformers and SSMs under general topologies, is unclear. As I understand it, for general sequence topologies, the model does not offer any complexity reduction and remains quadratic with respect to sequence length. Please refer to the requested changes section for more detailed suggestions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Chimera, a unified model that generalizes SSMs to directly incorporate graph topology in a principled manner. To enhance efficiency, the authors propose algorithmic optimizations by specializing Chimera to DAG and approximating the resolvent with a finite sum, which works well for data modalities like images and language. Experiments show that Chimera achieves strong and consistent performance across various domains, outperforming BERT on GLUE, ViT on ImageNet-1k, and competitive baselines on the Long Range Graph Benchmark, effectively modeling both local and global interactions while respecting graph structure.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Major Comments**\n\nI suggest that the manuscript should be improved along several directions.\n\nFirst, it is somewhat difficult to figure out the time and space complexities of Chimera for computing the resolvent matrix in both the language and image domains. As I understand it, the time complexity can be reduced to linear, while the memory requirement remains quadratic in the sequence length. It would be helpful to summarize the time and space complexities of the network’s forward pass in a table, as this would effectively highlight its lower computational burden compared to Transformers.\n\nAdditionally, in Section 4.1.2, it was unclear how the proposed parallelized computation of the resolvent is implemented in linear time. I had difficulty following the explanation, and it would benefit from a more detailed or illustrative description to clarify how this is implemented.\n\nFor the general topology, it appears that both time and space complexities remain quadratic with respect to sequence length. If this is the case, could the authors clarify the advantages of Chimera over Transformers in such settings? I was unable to find empirical evidence supporting this claim.\n\n**Minor Comments**\nFigure 2 contains unnecessary lines, likely artifacts from a screenshot. It would be more professional to include a clean vector graphic.\nThe placement of Figures 3 and 4 does not align well with their descriptions in the text. Consider moving them to page 7 for better readability.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S08SWAbeCz", "reviewer": "Reviewer_VABZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths:\n- The general approach taken is interesting and seems principled.\n- The experiments are compelling.\n- Most statements and approaches are straightforward.\n- Most statements are proven to be theoretically robust.\n\n# Weaknesses:\n- As far as I can see, you do not provide code while claiming state-of-the-art performances on 3 significant benchmarks. I doubt the veracity of these claims, but I cannot check their correctness. ()\n- While the used language and organization are well done, there are multiple issues with missing definitions, unclear or incorrect statements, or missing background and discussion.\n  - In the Introduction, you state, \"Typically, Transformer-based methods [...] are used to model [molecule data].\" This statement is at the very least questionable. While Transformer-based GNN approaches have become more prevalent, simple message-passing approaches, which respect graph topology naturally, are still very common.\n  - In the Introduction, you state, \"while absolute position embeddings have inherently constrained context size.\" This statement is incorrect, or at the very least requires a non-standard definition of absolute position embeddings. For instance, the random-walk structural encoding is not context-constrained for long enough walks. The resistance distance positional encoding is not context-constrained at all. Arguably, the Laplacian Positional Embedding is also not context-constrained.\n  - In Equation 4 \"\\Delta_t\" is not defined.\n  - In Proposition 3.2, \"weighted adjacency matrix\" is not defined. Specifically, the term weighted in this context is not defined.\n  - In Proposition 3.3, \"w_{i-1 \\to i}\" is not defined and is an unusual notation in GNN contexts.\n  - In between Equations 11 and 12, \"Z\" is not defined.\n  - In Equation 12, \"\\Delta' \" is not defined.\n  - After Equation 12 \"\\Delta^{(1)}\" and \"\\Delta^{(2)}\" are not defined or clearly described.\n  - Multiple functions like \"f_{\\Delta'}\" and \"f_{\\Psi}\" are said to be similarly computed to other functions, but this is not defined.\n  - The statement that line graphs and grid graphs can be canonically decomposed into multiple DAGs is not conceptualized. What does this mean in your context?\n  - It is not defined what the parents of a node in a DAG are exactly. There are two possibilities due to directedness.\n  - In Section 4.1.1, \"\\Delta_i[j]\" is not defined\n  - In Proposition 4.1, \"A^T\" is not a good choice, namely, the T resembles the transpose of matrix A, but you are referring here to the T-th power.\n  - Repeatedly, you use channels to describe the number of features, but you never define what channels are.\n  - In Proposition 4.2, \"\\mathbf{v}\" does not show up in Equation 14 unless you mean \"v_i\" to be the i-th element of \"\\mathbf v\"\n  - In Proposition 4.3, you assume that \"B_iv_i, C_i \\sym \\mathcal N(0,I_d).\" This assumption is not justified.\n  - In all tables, boldness and underlining are not defined.\n  - In Section 4.2, you refer to the adjacency matrix of a graph topology defined in Section 3.3. However, it is generally unclear when A is referring to the typical adjacency matrix and when A is referring to your modified version of Equation 12 or the Equation after Equation 12, or both.\n  - In Section 5.1, you propose for the first time to use the canonical DAG representation of line graphs by summing the resolvents. This should be made clear explicitly, how this fits into your equations.\n- Almost all figures and tables are oddly positioned. Figure 1 on page 4 is only referenced on page 5. Figure 2 on page 7 is never referenced. Figure 3 and Figure 4 on pages 8 and 9 are referenced on pages 2, 6, 9, 10, and 11. Table 1 on page 8 is only referenced on page 10. Similarly, all other tables are misplaced, except for Table 3, which is placed in a section mid-text, which I would advise against.\n- All tables and figures are not self-contained.\n- In A.1 Proof of Proposition 3.4, you state \"||\\epsilon_i||\\geq \\sqrt{T}\" whp. This is incorrect. The norm of a normal Gaussian vector is concentrated around \\sqrt{T} with its mean slightly below \\sqrt{T}. This is a significant statement required for the computation of Chimera in general and needs to be resolved. You also state that \"\\epsilon_i \\sym \\mathcal T (0, I_T).\" Why is the distribution labelled as \"\\mathcal T\" instead of \"\\mathcal N\"?\n- You do not discuss why they chose the baselines in each of their experiments, or why these baselines are appropriate, and do not discuss whether the values used in their tables are copied from previous work or computed anew.\n- Similarly, you make hyperparameter changes in tables 8 and 9, but do not justify them.\n- You do not report standard deviations in most of your tables; however, these are important to assess the significance of the difference. Even when the std is not available for other methods (because you perhaps copied them from another paper), they could justify whether your achieved performances are significantly better than previously reported averages.\n- In extension to the previous statement, you do not make use of standard deviations to asses significance of difference. For instance, in Table 2, PascalVOC-SP Chimera does not significantly outperform GraphGPS. On COCO-SP, it does not significantly outperform either Graph Mamba.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes Chimera, a general-purpose model that generalizes state space models. The authors propose to incorporate data topology (more specifically, graph topology) into the update computation of hidden states in a principled way. Additionally computational efficiency of Chimera is proven. Chimera achieves state-of-the-art performance in at least some vision, language, and graph tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Address and fix the long list of missing definitions, unclear or incorrect statements, and missing background and discussion. (critical due to their number)\n- Provide your code so we the reviewers can check the correctness of your claims (critical)\n- Adjust your figure and table placement (strengthen)\n- Make sure to make each figure and table self-contained, and make sure each figure and table is referenced appropriately (namely, Figure 2). (critical)\n- Deal with or respond to my issue with A.1, the proof of Proposition 3.4. (critical)\n- Address your choice of baselines (critical)\n- Address your choice of hyperparameters (critical because the code is not available, otherwise it might only strengthen)\n- Provide standard deviations (critical if possible)\n- Use standard deviations to highlight significant differences. A standard way to do this would be to underline those values that are not the best, but that are only insignificantly worse than the best value, sharing first place or boldness.", "broader_impact_concerns": "I have no such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)