Log-Linear Attention
Authors: Han Guo
Songlin Yang
Tarushii Goel
Eric P. Xing
Tri Dao
Yoon Kim
Venue: ICLR 2026 Poster (2026)
Keywords: subquadratic architecture
triton kernel
structured matrices
Primary area: foundation or frontier models, including LLMs
TL;DR: We introduce a tensor attention framework and propose log-linear attention, which expands beyond fixed-size hidden states to achieve log-linear complexity.

Abstract: The attention mechanism in Transformers is an important primitive for accurate and scalable sequence modeling. Its quadratic-compute and linear-memory complexity however remain significant bottlenecks. Linear attention and state-space models enable linear-time, constant-memory sequence modeling and can moreover be trained efficiently through matmul-rich parallelization across sequence length. However, at their core these models are still RNNs, and thus their use of a fixed-size hidden state to model the context is a fundamental limitation. This paper develops log-linear attention, an attention mechanism that balances linear attention's efficiency and the expressiveness of softmax attention. Log-linear attention replaces the fixed-size hidden state with a logarithmically growing set of hidden states. We show that with a particular growth function, log-linear attention admits a similarly matmul-rich parallel form whose compute cost is log-linear in sequence length. Log-linear attention is a general framework and can be applied on top of existing linear attention variants. As case studies, we instantiate log-linear variants of two recent architectures---Mamba-2 and Gated DeltaNet---and find they perform well compared to their linear-time variants.

Published as a conference paper at ICLR 2026
LOG-LINEAR ATTENTION
Han Guo' Songlin Yang'*
Tarushii Guel'
Eric P. Xing
Tri Dao?
Yoon Kim
Massaacusetts Institute of Technology PPrinceton University, Together Al CCarnegie Mellon University, Mohamed bin Zayed University of AI, GenBio Al
hanguoêmit.edu
ABSTRACT
The attention mechanism in Transformers is an important primitive for accurate and scalable sequence modeling. Its quadratic-compute and linear- iimarrmmmoryy com- plexity however remain significant bottlenecks. Linear attention and state-space models enable linear-time, constant-memory sequence modeling and can moreover be trained efficiently through matmul-rie parallelization across sequence length. However, at their core these models are still RNNs, and thus their use a fixed-size hidden state model the context is fundamental limitation. This paper develops log-linear attention, an attention mechanism that balances linear attention's 's effi- ciency and the expressiveness of softmax attention. Log-linear attention replaces the fixed-size hidden state with a logarithmically growing set of hidden states. We show that with particular growth function, log-linear attention admits a similarly matmul-rich parallel form whose compute cost is log- linelr in sequence length. Log-linear attention general framework and can be applied on top of existing linear attention variants. As case studies, we instantiate log- fog-linear variants of two recent architectures Marnsa-2ammaa2 and Gated DeltaNet and find they perform well compared to their linear-time variants
INTRODUCTION
The attention layer (Bahdanau et al. 2014) is core building block of modern deep learning archi- tectures, most notably in the Transformer architecture (Vaswani et al. [017]. For training, attention can be parallelized across sequence length through reformulating the computation matrix-matrix multiplications (matmuls), which can enable efficient training on modern accelcrators such GPUs and TPUs. However, the compute cost of attention grows quadratically and its memory cost grows linearly with respect to sequence length; despite the wallclock efficiency improvements obtained from hardware-optimizze implementations (Dao al. 2022b Dao 2024 Shah et al. 20244]
series of
Liu et al. 2024 Kwon et al. 2023), this quadratic-compute linear-memory cost is a fundamental limitation in enabling new applications and serves as a significant bottleneck in existing ones.
Linear attention (Katharopoulos et al. 2020) replaces the softmax kernel with simple linear kernel (i.c.. dot product) to derive the "attention" scores. The use of linear kernel makes possible to reformulate linear attention as linear RNN with matrix-valued hidden states, and thus linear attention enables linear-time, constant constant-memory sequence modeling For training, linear attention can be parallelized across sequence length via a chunking mechanism where a sequence is split up into chunks and the computations across chunks are performed in parallel (Hua et al.) 2022] Sun et al. 2023 Yang et al. 2024b Dao & Gu 2024). The complexity of this chunkwise parallel algorithm is subquadratic in sequence length but still rich in matmuls lcading to hardware- implementations (Yang & Zhang 2024, Qin et al. 2202aa] Beck et al. 2025al that obtain practical wallelock improvements over optimized implementations of softmax attention. While early versions
of linear attention generally underperformed softmax attention (Kasai al. 2021 Peng al. 2021
"qqual contribution.
'Code available at ihttps::s iiggttthn whu... com www.//annuo97/11.oooo inwpr//altgiieeaetttttttteeee
"Thus there three senses in which linear attention linear: the use of linear kernel, reformulation as a linear RNN where the hidden state is linear function of the previous state, and its lincar-time complexity.
Unlike parallel scan (Blelloch) 1990) which can also parallelize linear attention across sequence length hut consists mostly of elementwise operations instead of matmuls.

---

Published as a conference paper at ICLR 2026
Model
A
M (Data Dependent!)
Training Algorithm/ / Time
Decoding Time and Space
Attention
a <QQ')
Mask (X)
FlasmAnemiion O(7²)
O(T)
O(T)
Linear Atiention
QK
Mask (X)
Chunk-recureat ((T)
O(1)
o(1)
RetNet
QK
Semiseparable (O)
Chunk-recurrent (T)
O(1)
((1)
Mamba-2
QK
Semiseparable (V)
Chonk-reeureeat ((T)
((1)
O(1)
Multi-Hyena
QK
Toeplitz (X)
( log T))
O(log" T)
((T)
DeltaNet
[K(QQ]
Mask (X)
Chunk-rrecrrent (
O(1)
O(1)
Galed DeliaNet
[R(QK]
Semisepurable (V)
Chunk recurrett ((T)
O(1)
O(1)
Log. Linear Mamba-2 2
QK
Hierarchical (V)
Chunk scan O log T)
(logT)
Ollog T)
Log-Linear Gated DeltaNet
TKe (K(QQ))
Hierarchical (V)
Chunk-sean OTT log T)
OllogT)
O(log T)
Table 1: Summary of efficient attention mechanisms under the unified formulation: P @ M, PV.
M is a lower-triangle (causal) matrix. We use symbol Tk (A) = (A @ L. (I+ KK @ (I - (I- for notational brevity, where L is lower-triangular matrix of 1s. Here decoding time is the time per step, and decoding space refers the overall memory complexity during generation.
Mao Qin et al. 2022 Sun et al. 2023), , modern variants with data-dependent multiplicative gates 202c)-which include state-space models (SSMs)
(Yang et al. 2024b] Qin et al., 2024b Peng et al.
such as Mamba (Gu & Dao 2024; Dao & Gu
2024)and delta-rule-based structured transition
matrices (Schlag al. 2021
Yang et al. 2024b a Grazzi et al. 2025: Siems et al.) [225 Peng et al.,
2023) have led to sigmificatt improvements. However, despite these improvements linear attention s use of a fixed-sized hidden state is a fundamental limitations when it comes certain capabilities such as associative recall over given context (Arora et al. 2024).
This paper develops log-linear attention attention. Instead of using a single hidden state matrix to represent the history (as in linear atten- tion/SSMs), log-linear attention maintains growing set of hidden states where the set size grows logarithmically with respect to sequence length. With particular choice of the growth function, we show that log-linear attention admits a matmul-rich "parallel form" for training which involves replac- ing the lower-triangular causal mask in ordinary linear attention with a data-dependent hierarchical matrix, which enables subquadratic training; particular we show that the compute cost of log-linear attention is log-linear in sequence length (hence the name), while its memory cost is logarithmic. Log-linear linear attention is a general framework for sequence modeling and can be used to generalize existing linear attention models. As case studies, we use the framework two popular recent models, Mamba-2 (Dao & Gu 2024) and Gated DeltaNet (Yang et al.] (202a), to derive log-linear variants of both models, and find that these variants perform well compared to their original linear variants.
middle ground between linear attention and full softmax
2 BACKGROUND: A STRUCTURED MATRIX VIEW OF EFFICIENT ATTENTION
Given an input sequence of length T and the corresponding key, query, value matrices K.Q.V V E Txxd softmax attention obtains the output O Fxd for all time steps via O = softmax(QR QK @ M) where M E {-o0, 0) is causal masking matrix. This in- curs (TT2) compute and (T) memory, which makes costly to apply to long sequences. As a response, there has been much recent work on efficient alternatives with sub-quadratic compute and sub-linear memory, including linear attention, state-space models, and long convolution models. Despite their differences,, many of these approaches can be captured by the following equation:
P A ④ M, O
where A E RXT is an attention- like matrix (e.g., QK in the case of ordinary linear attention) and M E RTxT is lower-triangular causal masking matrix (e.g.. M E (0, 1)7x2 for linear attention). By separating out the interaction terms A and the (potentially data-dependent) masking matrix M, this abstraction reveals commonalities across a broad class of models, as shown in Table Different structures imposed on M can lead to efficient training and inference algorithms. We now describe key models that fit within this framework.
Linear attention. Linear attention Katharopoulos et al. (2020) simply removes the softmax opera- tion, resulting in the following parallel form
O (QK O @M) V, My 1fi s.}.
'Here we work linear attention without any feature maps normalization, since most recent works have found them be unnecessary (although see (Kacham al. 2023 Buckman al. Arora 20244).
2

---

Published as a conference paper at ICLR 2026
Linear attention can be reparameterized into the following "recurrent form" for inference,
S = - + vyky o, = S.q.
which enables linear-time constant-memory sequence modeling.
Linear attention with (data-dependent) gates. Vanilla linear attention lacks forgetting mech- anism, which has been shown to be crucial in ordinary RNNs. One way to incorporate such a mechanism is through a scalar gale Or, (0, 1), which results in recurrence S. = S, 1 + v,kk This has the following corresponding parallel form:
0 (QK @ M)V,
My
II 0g- k=j+1
Originally introduced by Peng et al.
2222 gated linear attention has enjoyed resurgence in recent
years (Qin et al.) 2024b b Peng et al.
2024; Yang et al. 2023; Katsch| 2023) and are an instance of
time-varying SSMs (Gu & Dao 2024 Dao & Gu 2024). Well-known models in this family include
RetNet (Sun et al., 2023). which uses a data-independen gate dg = a, and Mamba-2 (Dao & Gu 2024), which uses the above data- data-dependent gate. Dao & Gu (2024) show that with scalar gating
factor, M has I-semiseparable structure where every submatrix in the lower triangular portion has rank at most which can enable efficient training.
Linear attention with the delta rule. DeltaNet (Schlag et al. 2021 is a type of linear attention layer which updates the hidden state via the delta rule (Widrow al. 1960 where the recurrent form is given by
S, (
v,k O: S.q.-
While the original work used purely recurrent form, Yang et al. (2024b) recently show that possible to parallelize DeltaNet across sequence length through leveraging compact representation of Householder matrices (Bischof & Loan 1985 Joffrain et al., 2006), resulting in the following parallel form (ef. (Yang et al.) 2024b $3.2)):
0
(QK o L)
(I+ KK o (L (L- OM V
where L and M are lower-triangular matrices consisting of 1s. Since A itself is already lower- triangular, the causal masking matrix M not strictly necessary in the above. However, by changing M to have 1 l-semiseparable structure as in Mamba-2, we can recover Gated DeltaNet (Yang et al.) 2024a), whose recurrence is given by S, = a, k u,k, Linear attention with such data-dependent structured transition matrices has been shown to be theoretically more expressive than linear attention with multiplicative gates when comes to certain types of state-tracking tasks (Merrill et al.) 2024 Grazzi et al.) 2025 Siems al. 2025 Peng al. (025) which make these layers attractive targets to generalize via our log-linear attention framework.
Long convolution models. Long-convolution sequence models, where the convolution kernel size equals the sequence length, can also be cast into this framework. For example. Toeplitz neural network (Qin al., (023) and MultiHyena Massaroli al. (2023) layers are given by [KKT ④ TW V where T is causal Toeplitz matrix generated by long convolution kernel E R. i.e. T [ hli j] for i 2 and otherwise. Other long convolutional variants like H3 (Fu et al. (023) and Hyena (Poli et al., 2023) also admit precise attention-style formulation Massaroli et | 2023). While the decoding speed long convolution models can be improved from O(T) to Ologg T) per step (Oncescu al. 2025). their memory cost remains linear, i.e., the same as in softmax attention. However, some long convolution models such as $4 (Gu et al. 2022) admit reparameterization into a time-invariant SSM and thus enjoy constant-memory inference. There has also been efforts distill long convolution models into RNNs (Massaroli et al. 2023 Qin & Zhong 2023), but these inherit the memory bottleneck of RNNs.
O
'I "inear attention with the delta rule also an instance a fast-weight programmer (Schmidhuber 1992). 'The actual DeltaNet recurrence is given by S, St-1(I (T- k,k,,, k, where B, data-dependent scalar value in either (0, (0, 2). but we set here for notational brevity.
3

---

Published as a conference paper at ICLR 2026
Relationship between masking structure and efficient algorithms. Using unstructured M (e.g., a random lower-triange triangular matrix) degrades both compute and memory complexity to softmax attention- despite the absence of softmax; i.c., the structure of M is essential for training/infer- ence efficiency, not just the removal of softmax. In linear attention where M is a lower-triangular matrix of I's, we can compute O chunkwise, leading an ((T) algorithm This algorithm general-
izes to the gated case where M has I-semiseparable structure as shown in Dao & Gu 2024). Long
convolution models can use FFT bring down the cost to O T).
LOG-LINEAR ATTENTION
Linear Attention
The previous section showed that the structure of the masking matrix M determines how compute and mem- ory scale with sequence length. Semiseparable struc- tures cover many efficient architectures, yielding ((T) training time and (1) decoding memory. This moti- vates two questions: (i) what additional structures allow greater flexibility while retaining subquadratic training complexity, and (ii) can such models admit a recurrent form with sublinear decoding memory?
Log-Linear Attention
We answer both by introducing log-linear attention, which shapes M to achieve O log 7) computation and Ollog T') memory. Concretely, log-linear attention replaces the semiseparable mask with hierarchical one. extending linear attention beyond semiseparable temporal structure and accommodating a broader class structures for A. As case studies, we instantiate log- linear variants of Mamba-2 and Gated DeltaNet.
Figure Standard linear attention (top) vs. log- linear attention (bottom). The input consists of query, key, and value vectors.
During decoding, log-linear attention employs Fenwick tree scheme (Fenwick) 1994) that partitions inputs into power-of-two segments. Each position summarizes its prefix, enabling queries to attend to Olog T) hidden states across multiple scales (Fig. [ This design preserves fine-grat ame-grained access to recent tokens while requiring only (log T') time and memory. We first focus on the simplest form of linear attention (without gating) in 3.11 and show how log-linear attention extends it by maintaining independent recurrent states across temporal segments. Practical gated variants are presented in 3.4
3.1 FENWICK TREE PARTITIONING AND HIERARCHICAL MATRICES
From decoding perspective, attention can be viewed a mechanism that partitions the prefix [0, f) into a set of buckets, each summarizing a portion of the past. In vanilla attention, every token forms its own bucket, resulting in buckets of size 1, each stored as fixed-size state (the KV caches. At the other extreme, linear attention (and state- space models) aggregates the entire prefix into single bucket of size I, again represented by a fixed-size state.
t=0
1=1
t=2
t=3
1=4
t=5
t=6
t=7
(0)
B
BS
Log-linear attention strikes balance by partitioning the prefix into buckets of exponentially increasing size via a Fenwick-tree decomposition (Ryabko 1992: Fenwick] 1994). This induces natural inductive bias: recent tokens are retained at high resolution, while more distant tokens summarized more coarsely. The partition contains at most L Olog T) disjoint buckets indexed
Figure 2: Fenwick tree bucket assignments.
by level Each bucket 13 has size [B(*)) = 2 for f 2 1, plus a sentinel bucket BT()) of size 1. See Fig. for illustration.
TTis algorithm depends on the chunk size C, but since C' is hyperparameter this is still linear in T. $ *More precisely. this divides the prefix [o, into up L [log, + 1] + 1 disjoint buckets. This decomposition is guided by the function Issb(t) max (e E N 2 divides f), which identifies the least significant set bit in the binary representation of t. Conceptually, the partitioning proceeds greedily, at each step
4

---

Published as a conference paper at ICLR 2026
Log-linear attention maintains separate recurrent memory ( RRddd for each bucket. At time I, the contribution of bucket to the output weighted by nonnegative coefficient x parameterized linear function of the current input æt. This allows the model to adaptively emphasize different temporal scales. The output is computed as,
L-1 Or
2 BEB(
4-1 Σ E=
N qi
TTS qi
0=
We observe that when all X are the same (or more generally when the X, and x are linearly related across time) -in-linear attention collapses linear attention. Allowing distinct x is therefore essential for capturing multi-scale temporal structure.
Parallel form. The recurrent form in Eq. is conceptually simple but inefficient modern accelerators, which are optimized for high-throughput matrix-mattre multiplication. To leverage this hardware and enable parallelization across time, we reformulate the expression in matrix- muliipiicaioon-frrenlly form in 2
o =QK M V, M (s ((t.))))
otherwise,
P
where ((t, denotes the bucket level token relative to time t under Fenwick-tree partitioning. For readability, omit explicit (t, indices when unambiguous. The matrix P is hierarchical matrix which inherits structured low-rank pattern from the hierarchical partitioning, given below. In exploit this structure design parallel training algorithm with O(T log T) complexity.
333
(0)
4o
Aso
x
41
Ano
1
qi
An
q2
Auu
x 1.0g Aaa
q3
A1
xg q5 lo
Ag Ats
x (0)
qi ka
45
Kk
lg
(1)
les
Ao ag ls
ka
46
qs
Ki
x qe kg
47
ks
x a
(3)
Re
x at
kr
Remark. The matrix M (and A) is a lower-triangular instance of hierarchical (7L) ma- trix specificiiilally of the HODLR (Hierarchically Off-Diagonal Low-Rank) type. When constructed using schemes like the Fenwick tree, it inherits the recursive partitioning and low-rank off-diagonal blocks that define matrices. This establishes direct connection between log-linear attention and hierarchical matrices: the attention operator corresponds to structured matrix multiplication with an H matrix. We refer M as quasi-H matrix specialized class lying between general and semiseparable matrices, designed to support Ollog spppee recurrence. See Section B. for details.
3.2 MEMORY-EFFICIES DECODING
Let Issb(() denote the index of the least significant set bit in the binary representation of L. The states (0)
(s()) h evolve according to the following recurrence (using linear attention for simplicity):
subtracting the largest power of two that within the remaining segment the prefix,
{b (0)
819 f
if
100 (1-1) _bo000 otherwise
8000
{b)
(1+1)
6 -13 = Issb (6(2)
otherwise
5

---

Published as a conference paper at ICLR 2026
Level O lblock diegonel)
Level 1 (block low-rank)
Level 2
Level 3 lblock
Figure 3: Left: Decomposition the matrix M Right: Chunkwise algorithm (Algorithm 1. Level handles intra-chunk computations using quadratic (in chunk size) algorithm, which is efficient due to small chunk sizes. Levels and above perform inter-chunk computations by invoking existing inter-chunk primitives multiple times, with overall complexity logarithmic in the number of chunks.
if f=0
At each step, the immediate term V,kk enters the finest level; buckets up Issb(t) merge and promote one level coarser. When is power of two the hierarchy expands by one bucket. This Fenwick-like organization enables online processing with Olog I') memory while retaining efficient multiscale access.
if o (ssb(t))
s
Ir=
if lsbb(())) if lsbb(t+)++
8
3.3 EFFICIENT ALGORITHM FOR TRAINING
Chunkwise parallelism for linear attention (Sun al. 2023 Yang et al. 2023 Dao & Gu 2024) partitions a sequence of length T' into chunks of size C. which are processed in parallei while exchanging only limited information across boundaries. This approach balances two extremes: avoids the prohibitive cost of global attention while exposing substantially more parallelism than purely recurrent execution. We extend this idea to the log-linear setting and develop an efficient chunkwise training algorithm.
For a given chunk size C, the matrix M admits the structured decomposition,
L-1
M
if E B! otherwise.
M H
D+
Σ t=lo
M
M =
(5)
10
where D is block-diagonal with T
C causal blocks (D(m)) of size (CxC), capturing intra-chunk
iC++ M The remaining (M encode inter-chunk dependencies in blockwise low-rank form. Indexing begins lc, the level aligned chunk size C; levels & < to
interactions via (D()).s = (2)
collapse into D (Fig. 3 left).
Building on this structure, propose chunkwise algorithm for log-linear attention (Algorithm) 1). As summarized Fig. (right), the method introduces only logarithmic overhead compared with standard linear attention. Computation proceeds in two stages:
Intra-chunk stage (l < tc). The block-diagonal component D is treated as a dense matrix within each chunk. Each block costs OCC*), giving total complexity of OTTC).
Inter-chunk stage (f 2 fc). The matrices (M()) reduce scaled sequentially semi-separable
structures (Eq. 5). With efficient state-passing primitives (e.g., Mamba-2, Gated DeltaNet), inter- chunk dependencies are computed using only O (log {) primitive calls. Each call requires O(T) time and memory leading to an overall complexity O(T log t)
Our algorithm extends the classical parallel pum (scan) to hierarchical setting chunkwise parallel scan, Unlike token-level scans, which often suffer from memory- bandwidth bottlenecks
At level f, O contains z - chunks of size 2 C. Redundant work can be avoided, reducing cost by constant factor of two.

---

Published as a conference paper at ICLR 2026
10
101
Flas 2
Fl 2
Mamba
Namba
Loge Mamba
10"
LogeLincar Namba-2 (naive)
Throughous tokemsis)
Logel inear Nambaa2
10
Buntinnn
2x 30
10a
5 107
4295
01.92
20:354 22798
555-30 131072
10-
4295
01.52
15:.66 32708
65536 333072
Sequence Lengeth
Sequence Length
Figure Training throughput (left; higher better) and kernel runtime for forward and backward pass (right: lower is better) across varying sequence lengths. Log-Linear Mamba-2 (naive) denotes repeated application of the existing Mamba-2 primitives, while Log-Linear Mamba-2 uses custom implementation with optimizations such as level fusion. The throughput drop at sequence length 131K is due to gradient checkpointing to reduce memory usage. Experiments were run on H100 GPU with batch size 2, 48 heads, head dimension 64, state dimension 128, and chunk size 64. use MVA (Log-Linear) Mamba-2, and GQA for F
during training (Yang et al., 2023), the chunkwise formulation reorganizes recurrent updates into parallel chunk operations. Concretely, executes (log T) independent scans (one per memory level), each implementable with standard methods such the Blelloch scan (Blelloch 1990). Layer-specific weights (e.g.. ) can easily be incorporated into these scans.
3.4 LOG-LINEAR VARIANTS OF MAMBA-2 AND GATED DELTANET
We next apply the above construction to Mamba-2 Dao & Gu 2024 and Gated DeltaNet Yang al. (2024a). As discussed in ? both models use gating mechanisms that induce a sequentially semiseparable (SSS) temporal structure in the mask M (with M,j = [Ik=5+1 agg see Eq. 2 The two architectures differ how they parameterize the transition matrix A.
Our approach preserves the original form of A in each model while composing the attention mask with its log-linear variant M M M 10 We refer to the resulting models as log-linear Mamba-2 and logllinear Gated DeltaNet. Their parallel forms are given by,
O (QK" O O @ M*) V
Log-Linear Mamba-2
O = ((QK @ KK+ O (L-
+ M @ @M") V Log- Log-Linear Gated DeltaNet
More broadly, any linear-attention mechanism with structured memory and an efficient chunkwise- parallel primitive can be "lifted" to a log-linear variant by composing its temporal mask with M
3.5 IMPLEMENTATION
We implemented the chunkwise parallel scan algorithm in Triton Tillet al. 2019). The custom kernel for lig-linear Mamba-2 outperforms FlashAttention-2 (Dao) (024) (forward + backward) sequence lengths beyond 8K. In full training setups, throughput depends on model architecture. Notably, log-linear Mamha-2 (with MLP) surpasses Transformer throughput at 32K, despite additional layers like depthwise convolutions absent in the Transformer. See Fig. 4 and Sec. Dec.Cfor for details.
4 EXPERIMENTS
We conduct a suite of experiments across both synthetic and real-world benchmarks. We emphasize that our experiments are not necessarily intended position log-linear attention as the best subquadratic architecture, but rather to highlight the promise of our framework compared to sensible haselines.
4.1 SYNTHETIC BENCHMARK
More precisely, the elementwise product of an SSS matrix and an H. matrix remains an H. matrix. We separate them here for clarity.
7

---

Published as a conference paper at ICLR 2026
We begin by evaluating models on the multi- query associative recall (MQAR) task (Arora et al. )023). a standard diagnostic bench- mark for testing in-context recall. Our setup closely follows AArora et al. 2024): models are trained and evaluated on 256-token se- quences containing 4 to 64 key-value pairs (excluding the length generalization compo- nent), with tuned learning rates. For log- linear models, we also tune the À parame- terization. We run each configuration with five seeds. Training was early stopped when accuracy exceeded 99%. Additional experimental details are provided in SD As shown in Table log-linear attention performs well-even when applied on top of associative recall-optimized models like Gated DeltaNet.
Dimension
16
32
64
Transformer
2
99
2 99
Mamba-2
46.9 (2.3)
75.1 (4.9)
89.6 (6.1)
w/ Lin-Linear
(9.1)
76.5 (4.8)
92.9 (2.7)
Gated DeltaNet
(1.0)
(2.1)
99
Log Linear
(1.4)
81.2
99
Table 2: Average accuracies and standard deviations (in parentheses) on MQAR over seeds. Training was carly stopped when accuracy exceeded 99%.
4.2 LANGUAGE MODELING
We perform academic-scale language modeling pretraining from scratch using 50B tokens on the Long- Long-Data- DDataCCollection. dataset using sequence length of 16K. All models have 21 layers and use a hidden size of 1536. We use a Transformer with 16 attention heads and a RoPE base of 500K, modified Mamba-2 with 48 heads and MLP layers, and Gated DeltaNet with 6 heads. The Transformer, Mamba-2, and Gated DeltaNet models contain 693M, 802M, and 793M parameters, respectively. For the log-linear variants, apply linear layer top of the hidden states compute the per-head values x This adds less than 3% additional parameters for Mamba-2 (825M) and less than 0.4% for Gated DeltaNet (796M). Since Mamba-2 and Gated DeltaNet have more parameters than ordinary Transformers, we also include a (roughly) parameter-matched Transformer variant with 24 layers (778M parameters) for comparison. For our log-linear variants, hyperparameters from the baselines ($D). We also evaluated parameter-matched Hyena model Poli al. (2023), which also has log-linear compute (but linear memory). As its WikiText perplexity (around 29) was substantially higher than that of the other models (<23), our main experiments focus on the Transformer, Mamba-2, and Gated DeltaNet families.
the default
Standard benchmarks. Following prior work (Dao & Gul 2024 Yang et al.] 2024a). we evaluate models on WikiText perplexity and several zero-shot commonsense reasoning benchmarks (Table These are short-context tasks and are therefore largely insensitive to model state size. As such, we generally expect the log-linear variants to perform comparably Log-Linear Mamba-2 improves upon its linear counterpart in perplexity and in half of the commonsense
Model
Wiki. ppl 4
LMB.
LMEval average 1
ppl 4
Transformer
21.56
22.14
44,0
w/ 24 Layers
21.13
21.17
45.6
Hyena
29.50
/
/
Mamba-2
22.44
24.14
44.8
w/ Log-Linear
22.11
21.86
44.9
Gated DeltaNet
21.73
19.71
45.0
to their linear counterparts.
w/ Log-Linear 21.45
18.09
45.5
Table 3: PPL and commonsense reasoning.
reasoning tasks. Log-Linear Gated DeltaNet shows stronger gains, outperforming its linear version in perplexity and in all but reasoning benchmark. Notably, it also outperforms a layer-matched Transformer on half them.
Transformer across all metries and a
Per-position loss. Following Lin et al. 22025), ), we report the model's 's loss at each token position to evaluate its ability handle long contexts (Fig. (5). If the loss steadily decreases as the token position increases, it suggests the model is effectively using the full context. However, if the loss levels off after a certain point, indicates the model struggles to make use of information that is too far back in the sequence. For this analysis, we use 39M tokens from Book-3 To improve visualization, we apply a running average with window size of 501. We observe that extending both Mamba-2 and Gated DeltaNet to their log-linear counterparts consistently reduces the (smoothed) loss across various positions, indicating improved long-range context utilization. Log-ar Gated DeltaNet
viccorrww/bbor catee.coo//aaaaee http://aww....oa.aoo.aoeeeeeeona
8

---

Published as a conference paper at ICLR 2026
2.66
Transformer
Transtorerr (24 Layers)
Detta-DeltaNNet
2.64
Log-Lineer Geted-
DelltaNe Geled-DellaNeel
2.62
2.60
Transformer
2.58
Transformer (24 Layers)
Mamba-2
Lincar Mambai2
2.56
2000
4000
600n
800D
10000
12000
14000
160n0
2000
4000
600n
8000
10000
12000
14000
16000
Position
Position
Figure 5: Per-position loss on Book3 samples (about 39M tokens) with running average window size 501.
S-NIAH-1
S-NIAH-2
S-NIAH-3
(pass-Kep key retrieval)
(number in haystack)
(uuid in haystack)
Model
4K
8K
16K
4K
8K
16K
4K
8K
16K
Transformer
72.6
76.0
16.6
100.0
99.8
90.0
77.4
67.0
44.6
w/ 24 Layers
92.4
78.4
89.8
100.0
100.0
99.6
84.0
63.6
36.4
Mamba-2
90.4
56.8
21.6
72.4
18.6
4.0
3.6
0.8
w/ Log- Log-Linear
100.0
99.8
72.4
89.8
12.8
33.6
22.6
2.0
Gated DeltaNet
100.0
100.0
100.0
95.8
46.8
5.0
66.2
14.6
6.0
w/ Log-Linear
100.0
100.0
100.0
95.6
59.6
9.2
48.8
13.0
8.8
MK-NIAH-1
MQ-NIAH (multi-query) 8K
MV-NIAH
(multi key line retrieval)
(multi-value)
Model
4K
8K
16K
4K
16K
4K
8K
16K
Transformer
79.4
83.0
61.4
58.9
48.0
29.8
37.5
34.1
21.5
w/ Layers
62.6
83.2
75.2
54.6
46.0
34.5
48.4
45.4
32.3
Mamba-2
27.2
18.6
13.6
28.7
19.4
1.3
27.9
4.4
w/ Log-Lineur
43.2
39.8
21.2
26.6
22.4
6.6
28.1
22.8
8.9
Gated DeltaNet
23.0
21.2
5.2
21.6
16.9
7.2
16.2
14.5
7.0
w/ Log- Linea
49.4
27.8
10.2
34.9
22.0
9.8
31.4
25.0
13.3
Table NIAH experiments with three single/multi-needle tasks.
also closely tracks the performance of the layer-matched Transformer, although a performance gap remains when compared to the parameter-mate matched Transformer.
We the --tllsi-----yystakkk (NIAH, Tad Fig. 10) benchmark from RULER (Asieh et al. 2024), where the model must retrieve a value (the "needle") based on key hidden long context (the "haystack"). In the simpler single- needle tasks, the log-linear variant of Mamba-2 outperformed its linear counterpart on 8 out of 9 metrics. Gated DeltaNet, which already achieved perfect accuracy several cases, saw improvements 3 metrics, with 3 remaining unchanged. For the more challenging multi-needle tasks, Log-I.inear Mamba-2 again improved in 8 out of metrics, while Log-Lineas Gated DeltaNet achieved improvements across all metrics.
Gocdle-In-A-Hayee
Other tasks. Due to space we show the results on the in-context retrieval benchmark (Arora et al.. 2023 and LongBench (Bai et al. 2023) in the appendix.
DISCUSSION AND LIMITATIONS
While log- log-linear attention improves upon linear attention in many cases, there are still quite a few tasks where it did not improve upon the linear attention baselines. Due to compute resources we were unable experiment with different parameterizations the terms (or hyperparameters in general) and it is possible that optimal parameterization of À could lead improved results. We also still observe significant performance gap compared to Transformers across all benchmarks.
We only able 700M-800M parameter language models just due compute constraints.

---

Published as a conference paper at ICLR 2026
The engineering complexity of log-lineat attention is higher. Inter-chunk computations conceptually resemble multiple applications of linear attention primitives, but intra-chunk operations require bespoke implementations. These intra-chunk mechanisms are primary factor behind the speed differences. Additionally, the backward pass is more intricate, as it requires (manually) computing the gradients not only for the standard attention components but also for the additional À terms.
The use of Fenwick-tree partitioning (3.1)) introduces an inductive bias: recent tokens are allocated more fine-grained memory, while distant tokens are compressed more aggressively. This design reflects a natural assumption rooted in hierarchical matrix which posits that interactions between distant elements can be approximated in low-rank form. While intuitive and inspired by physical phenomena. this inductive bias may not be optimal for all applications. Future work could explore extensions that enable more flexible structures while preserving computational efficiency.
Finally, in this work, we extended two existing Inear-attennioon/SSM architectures to their log-linear counterparts, namely Mamba-2 (Dao & Gu 2024) and Gated DeltaNet (Yang et al., (024a). Several other promising architectures, including xLSTM (Beck et al. [2024] (025b) and MesaNet (Von Oswald jet al., 2023] yoon Oswald et al.] 2025), may likewise benefit from log-linear formulations. Developing and evaluating log-linear variants of these models is an exciting direction for future research.
6 RELATED WORK
Structured matrices for deep learning architectures. Modern architectures combine token- and channel-mixing layers, both based on matrix multiplications. Recent work replaces dense layers with structured matrices. For channel mixing, approaches include Butterfly (Dao et al. (020)) Monarch matrices (Dao et al. 2022a), and more recently, Block Tensor-Train matrices (Qiu et al. 20024). Token mixing has been exemplified by the family of linear attention models (Katharopoulos et al. 2020)
and their various kernelizations (Xiong et al. (02T). Dao & Gu (2024) generalize these approaches by extending low-rank structures to semiseparable matrices, enabling efficient recurrent inference and subsuming many recent recurrent models. Another line uses sparse patterns like sliding- winddww
attention, alongside several hybrid methods (Nguyen et al. 2021 Arora et al. 2025 Munkhdalai
cet al. 2024).
Log-linear complexity sequence modeling. Several prior efforts have focused reducing the quadratic cost of attention to log-linear time complexity (Kitaey et al.) [2020] (Shi et al. 2023 Cunning
ham et al. 2024 Qin et al., 2023 Fu et al. 2023 Madaan al.; Ye al. 2019). Approaches such as LogSparse Transformer (Li et al. 2019) and Informer (Zhou et al. 2021 introduce sparse attention
patterns to improve computational efficiency, particularly in time-series applications. Reformer (Ki- laev et al. 2020) employs locality-sensitive hashing (LSH) to efficiently cluster similar queries and keys. Multi-resolution attention (Zeng et al., (022) adopts a hierarchical approach, progressively reñning attention scores from coarse to fine granularity. while Fast Multipole Attention (Kang et al., 2024) adapts the classical fast multipole method to efficiently model long-range interactions. A similar viewpoint connects log-linear attention to dilated convolution (Van Den Oord et al. 2016) through their hierarchical mixing structure. Dilated convolution extends convolution, which cor- responds to Toeplitz matrices, whereas we operate primarily with semi-separable and hierarchical matrices. In our work, we leverage the Fenwick tree data structure- a specialized binary indexed tree that enables efficient prefix sum caleulations and updates in logarithmic time design an efficient attention layer during both training and decoding phases. While /Zhu & Soricut (202T) also employ hierarchical matrices for attention, their formulation is fully parallel and targeted at modest sequence lengths. In contrast, our approach adopts a chunkwise-paran custom Triton implementation optimized for ong-sequence training. Concurrently, Yau et al. (2025) propose a related architecture with Ollog T') memory, using relaxed prefix-scan algorithm for state aggregation that accommodates arbitrary (potentially non-associative) functions.
strategy with a
CONCLUSION
We introduced Log-Linear Attention, general framework that extends broad class of linear attention and state-space models to their log-linear counterparts mondlls with logarithmically growing state size. This framework offers both theoretical insights and practical benefits, linking structured matrix theory with hardware-efficien computation. As a case study, we applied this approach to two recent architectures: Mamba-2 and Gated DeltaNet.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank Tinnyuan Zhang, Jyothish Pari, Adam Zweiger, and Yu Zhang for helpful discussion. This study was supported by the MIT-Google Program for Computing Innovation, MIT-IBM Watson A1 Lab, and the A12050 program at Schmidt Sciences (Grant G-25-67980). HG was supported by Microsoft PhD Fellowship.
REFERENCES
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 models. arXiv preprint arXiv:2312.04927, 2023.
Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, Dylan Zinsley, James Zou, Atri Rudra, and Christopher Ré. Simple linear attention language models balance the recall-throughput tradeoff. In Proceedings of ICML, 2024.
Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, Dylan Zinsley, James Zou, Atri Rudra, and Christopher Ré. Simple linear attention language models balance the recall-throughput tradeoff, 2025. URL https:: arxiv. org/ abs 2abs/2400 2402 18668
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. In Proceedings ICLR, 2014.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu. Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023.
Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael K Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xLSTM: Extended long short-term memory. In The Thirty- Annual Conference Neural Information Processing Systems, 2024. URL. https:
httpp::://ppeeeeeeeeee http:///eeeeeeveeeeeeeee net./ Forum wo d=wddd
Maximilian Beck, Korbinian Pöppel, Phillip Lippe, and Sepp Hochreiter. Tiled flash linear attention:
More efficient linear mn and xlstm kernels. arXiv preprint arXiv:2503. 143776363333 2025a.
Maximilian Beck, Korbinian Pöppel, Phillip Lippe, Richard Kurle, Patrick M Blies, Günter Klam- bauer, Sebastian Böck, and Sepp Hochreiter. xLSTM 7b: A recurrent LLM for fast and effi- cient inference. In Forty second International Conference on Machine Learning, 2025b. URL net forum Liierumiid=LV3DDXOO0
Christian H. Bischof and Charles Van Loan. The WY representation for products of householder matrices. In SIAM Conference on Parallel Processing for Scientific Computing, 1985. URL
hittps://api semanticsche
::: 36094006
Guy E Blelloch. Prefix sums and their applications. 1990.
Jacob Buckman, Carles Gelada, and Sean Zhang. Symmetric Power Transformers.
Harry Jake Cunningham, Giorgio Giannone, Mingtian Zhang, and Mare Peter Deisenroth. Reparame- terized multi-resolution convolutions for long sequence modelling. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URUBatpps://ooerrevvee http://ooummmdddiee
Tri Dao. FlashAttention--2: Faster attention with better parallelism and work partitioning. In Proceedings of ICLR, 2024.
Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. In Proceedings of ICML, 2024.
Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning fast algorithms for linear transforms using butterfly factorizations, 2020. URL
1 1903. 05895
11

---

Published as a conference paper at ICLR 2026
Tri Dao, Beidi Chen, Nimit Sharad Sohoni, Arjun D. Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. Monarch: Expressive structured matrices for efficient and accurate training. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICMI 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 4690-4721. PMLR, 2022a. URL htttt:::/ppoceedinng/ mllr (tess/v162/aao22...o
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and memory-efficient exact attention with aO-awareness. In Proceedings of NeurIPS, 2022b.
Peter M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience, 24, 1994. URL http::///ppp..aaaatt.c.coooooooo
9761
Daniel Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry hungry hippos: Towards language modeling with state space models. In The Eleventh International Conference on Learning Representations, 2023,
net/foruma COZDyOWYGg KGg
Riccardo Grazzi, Julien Siems, Jörg K.H. Franke, Arber Zela, Frank Hutter, and Massimiliano Pontil. Unlocking tate-tracking in linear RNNs through negative cigenvalues. In Proceedings of ICLR, 2025.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In Proceedings of CoLM, 2024.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In Proceedings of ICI.R, 2022.
Wolfgang Hackbusch, Boris N Khoromskij. and Ronald Kriemann. Hierarchical matrices based on weak admissibility criterion. Computing, 73:207-243, 2004.
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. Ruler: What's the real context size of your long-context language models? arXiv preprint arXiv:2404.0666 2024.
Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoc Le. Transformer quality in linear time. In International conference machine learning, pp. 9099-9117, PMLR, 2022.
Thierry Joffrain, Tze Meng Low, Enrique S. Quintana-Ort Robert A. van de Geijn, and Field G. Van Zee. Accumulating householder transformations, revisited. ACM Trans. Math. Softw. 32:169-177 2006. URL/attss:
Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: Fast transformers via sketching polynomial kernels. arXiv preprint arXiv:2310.01655, 2023.
Yanming Kang, Giang Tran, and Hans De Sterck. Fast multipole attention: A divide-anddcoonuee attention mechanism for long sequences, 2024. URL [RL_jtttss://rxxiv.crr/////////
11960
Jungo Kasai, Hao Peng, Yizhe Zhang. Dani Yogatama, Gabriel Ilharco, Nikolaos Pappas, Yi Mao, Weizhu Chen, and Noah Smith. Finetuning pretrained transformers into mnss. In Proceedings of EMNLP, 2021.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In Proceedings of ICML, 2020.
Tobias Katsch. Gateloop: Fully data lata-controlled linear recurrence for sequence modeling. arXiv preprint vrXiv:2311.01927, 2023.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In Proceedings of ICLR, 2020.
12

---

Published as a conference paper at ICLR 2026
Daniel Kressner, Stefano Massei, and Leonardo Robol. Low-rank updates and a divide-anddcooquue method for linear matrix equations. SIAM Journal on Scientific Computing, 41(2):A848 A876, 2019.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez. Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of SOSP, 2023.
Shiyang Li. Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, and Xifeng Yan. Enhancing the locality and breaking the memory bottleneck of transformer time series forecasting. Advances in neural information processing systems, 32, 2019.
Zhixuan Lin, Evgenii Nikishin, Xu He, and Aaron Courville. Forgetting transformer: Softmax atten- tion with a forget gate. In The Thirteenth International Conference on Learning Representations, 2025. URL
n ftte//frrmmmm...gllgggglk
Hao Liu, Matei Zaharia, and Pieter Abbeel. Ring attention with blockwise transformers for near- infinite context. In Proceedings of ICLR, 2024.
Lovish Madaan, Srinadh Bhojanapalli, Himanshu Jain, and Prateek Jain. Treeformer: Dense gradient trees for efficient attention computation. In The Eleventh International Conference on Learning Representations.
Huanru Henry Mao. Fine-Tuning Pre-trained Transformers into Decaying Fast Weights. In Proceed- ings of EMNLP, pp. 10236-10242.
Stefano Massaroli, Michael Poli, Daniel Y Fu, Hermann Kumbong, Rom Nishijima Parnichkun, David W. Romero, Aman Timalsina, Quinn Mcintyre, Beidi Chen, Atri Rudra, Ce Zhang, Christo- pher Re, Stefano Ermon, and Yoshua Bengio. Laughing hyena distillery: Extracting compact recurrences from convolutions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL Sttt::////oenveriee.eeeeeeeeeeee www.::::dddwwewweeeecmmmmm
Stefano Massei, Leonardo Robol, and Daniel Kressner. hm-toolbox: Matlab software for hodlr and hss matrices. SIAM Journal on Scientific Computing, 42(2):C43-668, 2020.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. In Proceedings of ICML, 2024.
Tsendsuren Munkhdalai, Manaal Faruqui, and Siddharth Gopal. Leave no context behind: Efficient infinite context transformers with infini-attention, 2024. URL htttps://aaxi..orgg//./
2404.07144
Tan Nguyen, Vai Suliafu, Stanley Osher, Long Chen, and Bao Wang. Fmmformer: Efficient and flexible transformer via decomposed near-field and far-field attention. In Proceedings of NeurIPS, 2021.
Costin-Andrei Oncescu, Sanket Purandare, Stratos Idreas, and Sham M. Kakade. Flash inference: Near linear time inference for long convolution sequence models and beyond. In The Thirteenth International Conference on Learning Representations, 2025. URL
n (tt.:/ooomnnddc22aaaaaao
Bo Peng, Daniel Goldstein, Quentin Anthony, Alon Albalak, Eric Alcaide, Stella Biderman, Eugene Cheah, Teddy Ferdinan, Haowen Hou, Praemystaw Kazienko, et al. Eagle and finch: Rwkv with matrix-valued states and dynamic recurrence. arXiv preprint arXiv:2404 058922 3, 2024.
Bo Peng, Ruichong Zhang, Daniel Goldstein, Eric Alcaide, Xingjian Du, Haowen Hou, Jiaju Lin, Jiaxing Liu, Janna Lu, William Merrill, al. Rwky-7" goose" with expressive dynamic state evolution. arXiv preprini arXiv:2503. 0e0e5533..445. 14456, 2025.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong. In Proceedings of ICLR, 2021.
13

---

Published as a conference paper at ICLR 2026
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 Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning. ICML. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 28043-28078. PMLR, 2023. URL httpp:://ppeee http:////cccceee...ee.e mlr press/ v202/poli23er html
Zhen Qin and Yiran Zhong. Accelerating toeplitz neural network with constant-time inference complexity. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.). Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 12206- 12215, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 1tt.5/////22..mmmmmlm main. 750. URL https: hati:::://aclaahoooogy// org/ /tt.///.......///e////////e/ 2023.002222222 emnlp-man in..inn..... 750/
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. In Proceedings of ICLR, 2022.
Zhen Qin, Xiaodong Han, Weixuan Sun, Bowen He, Dong Li, Dongxu Li, Yuchao Dai, Lingpeng Kong, and Yiran Zhong. Toeplitz neural network for sequence modeling. In Proceedings of ICLR, 2023.
Zhen Qin, Weigao Sun, Dong Li, Xuyang Shen, Weixuan Sun, and Yiran Zhong. Lightning attention- 2: A free lunch for handling unlimited sequence lengths in large language models. arXiv preprint arXiv:2401. 04658, 2024a.
Zhen Qin, Songlin Yang, Weixuan Sun, Xuyang Shen, Dong Li, Weigao Sun, and Yiran Zhong. HGRN2: Gated Linear RNNs with State Expansion. In Proceedings of CoLM, 2024b.
Shikai Qiu, Andres Potapezynski, Mare Finzi, Micah Goldblum, and Andrew Gordon Wilson
Compute better spent: Replacing dense layers with structured matrices. ArXiv, abs/2406.06248, 2024. TRLLhttss::/ http://pp..emmattcsccccccchoeoee http://a.....o.o//ooopsaaaaa/a:.
B. Ya. Ryabko. A fast on-line adaptive code. JEEE Trans. Inf. Theory, 38:1440-14444, 1992. URL
https://apls www.sttesaannnoooeeee.o http::///ppl..enaaicccchhh.....
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear Transformers Are Secretly Fast Weight
Programmers. In Proceedings of ICML, 2021.
Jürgen Schmidhuber. Learning to control fast-weight memories: An alternative to dynamic recurrent networks. Neural Computation, 4(1):131-139, 1992.
Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. FlashAttention--:: Fast and accurate attention with asynchrony and low-precision. In Proceedings of NeurlPS, 2024.
Jiaxin Shi, Ke Alexander Wang, and Emily B. Fox. Sequence modeling with multiresolution convolutional memory, 2023. URL httpt:tt////iiiii wwt////gg//////
Julien Siems, Timur Carstensen, Arber Zela, Frank Hutter, Massimiliano Pontil, and Riccardo Grazzi. Deltaproduct: Improving state-tracking in linear mns via householder products. arXiv preprint arXiv:2502. 10297, 2025.
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. arXiv preprint arXiv:2307.0862), 2023.
Philippe Tillet. -siang- Kung, and David Cox. Triton: intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop Machine Learning and Programming Languages, pp. 10-19, 2019.
Aaron Van Den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, Koray Kavukcuoglu, et al. Wavenet: A generative model for raw audio. arXiv preprint arXiv: 1609.03999 12:1, 2016.
14

---

Published as a conference paper at ICLR 2026
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Proceedings of NeurlPS, 2017.
Johannes Von Oswald, Maximilian Schlegel, Alexander Meulemans, Seijin Kobayashi, Eyvind Niklasson, Nicolas Zucchet, Nino Scherrer, Nolan Miller, Mark Sandler, Max Vladymyrov, et al. Uncovering mesa-optimization algorithms in transformers. arXiv preprint arXiv:2309.0580 2023.
Johannes von Oswald, Nino Scherrer, Seijin Kobayashi, Luca Versari, Songlin Yang, Maximilian Schlegel, Kaitlin Maile, Yanick Schimpf, Oliver Sieberling, Alexander Meulemans, et al. Mesanet: Sequence modeling by locally optimal test-time training. arXiv preprint arXiv:2506.05233 2025.
Bernard Widrow, Marcian Hoff, et al. Adaptive switching circuits. In IRE WESCON convention record, volume 4, pp. 96- 104. New York, 1960.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nystrômformer: A nyström-based algorithm for approximating self-attention. In Proceedings of AAAI, 2021.
Songlin Yang and Yu Zhang. Fla: A triton-based library for hardware-efficient implementations of linear attention mechanism, January 2024. URL httpp:://githb.ccom ora
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated linear attention transformers with hardware-efficient training. arXiv preprint (rXiv:2312.06635, 2023.
Songlin Yang, Jan Kautz, and Ali Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. In Proceedings of ICLR, 2024a.
Songlin Yang. Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing linear transformers with the delta rule over sequence length. In Proceedings of NeurIPS, 2024b.
Morris Yau, Sharut Gupta, Valerie Engelmayer, Kazuki Irie, Stefanie Jegelka, and Jacob Andreas. Sequentiia-ppraalel duality in prefix scannable models. arXiv preprint arXiv:2506. 10918, 2025.
Zihao Yc, Qipeng Guo, Quan Gan, Xipeng Qiu. and Zheng Zhang. Bp-transformer: Modelling 2019.
long-range context via binary partitioning. arXiv preprint
Zhanpeng Zeng, Sourav Pal, Jeffery Kline, Glenn M Fung, and Vikas Singh. Multi resolution analysis (mra) for approximate self-attention, 2022. URL /ttt///ttt////rrrr..o///////////
Yu Zhang and Songlin Yang. Flame: Flash language modeling made easy, January 2025. URL
www.eemmmcllaeaee fla-orggaggoooooao flame
Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of AAAI, 2021.
Zhenhai Zhu and Radu Soricut. H-transformer- ld: Fast dimedimnnl hicrarchical attention for sequences, 2021. URL http:s/s///aaal..oooaab/////////
15

---

Published as a conference paper at ICLR 2026
Model
Temporal Structure
Hidden Size Structure
Mamba-2
Semiseparable
Scaled Identity
Gated DeltaNet
Semiseparable
Identity plus Low-Rank
Log-Linear Mamba-2
Hierarchical
Scaled Identity
Log-Linear Gated DeltaNet
Hierarchical
Identity plus Low-Rank
Table 5: Structural comparison of different attention variants.
A GENERALIZING LOG-LINEAR ATTENTION TO MORE EXPRESSIVE LINEAR RNNs
The main paper adopts the following unified view of efficient attention (Eq. D
P A & M, O - PV,
This formulation reveals that the key difference between linear and log-linear attention lies in the structure of the mask matrix M E _TxT Variations among linear attention models-suce as Mamba-2 and Gated DeltaNet- stem from different parameterizations of A. While this perspective offers unifying and intuitive framework that captures wide range of attention mechanisms, it comes with an important limitation: the state-transition terms are restricted to be scalars (in the case of Mamba-2) identity-plus-eeete plus--aa------ matrices (in the case of Gated DeltaNet).
In this section, we introduce a more general framework that relaxes this scalar constraint by allowing traestrrnnstion terms (including the thus x! terms) be matrix-valued. This extension enables richer and more expressive attention mechanisms while preserving computational efficiency.
Linear Attention SSS Tensor. Consider the standard linear attention mechanism with data-dependent gating and an SSS (sequentially semiseparable) mask M
P= QK' + M O PPVV
In the main paper, extend the SSS mask M to a hierarchical form M Notice that in Mamba-2 2, the resulting matrix P also inherits the same structural property, with its SSS-rank governed by the hidden dimension d:
Pt,s Qu (Cr C+t1) where C, I.I.
We now define a 4D tensor M E (((xxT)(dxxd) such that:
Pr, Q.M,, where M..- = C.... C.+1
Each entry M... E Rdxd is matrix, making M a 4D tensor. We refer to this as an SSS tensor due its sequentially semiseparable-like structure along the temporal dimension, though this term is not yet formalized in the literature.
This tensor-centric view naturally accommodates matrix-valued state transitions arbitrary structure, offering a richer representation than scalar- or identit-plus-raa--nn--bbe approaches. particular, models such as Mamba-2 and Gated DeltaNet can be interpreted as operating on 4D tensors with different hidden-diing didden--imenion structures, while still preserving temporal semiseparability! 14
[gd with
#+1
Mamba-2:
II I, d=t
Gated DeltaNer: S
II or (I B k. v=l
Log-Linear Attention as an H Tensor.
We can apply our log linerr attention to these more flexible (linear) RNNs by incorporating matrix-valued, level- and data-dependent terms A gdxd,
s+1
#-1
Mamba-2:
H = (0)
II I
Gated DeltaNet:
M.
II ov (I Bckyk!)
Strictly speaking, Gated DeltaNet also need to include term Be from B. For clarity, omit it here, can be absorbed into other terms.
16

---

Published as a conference paper at ICLR 2026
=
1 (1,2,3,4
I (5, 6,78
1 2 (1,2)
2/- = (3,4)
1/ = (5.6)
I = (7.8)
- = (1) 1 = (2) 1300
= (3) 1. = (1) 16-0
= (5) -0 (6) 1 (7) I (8)
3=
1=2
t=1
4=0
Figure 6: Visualization adapted from Massei et al. (2020); Kressner et al. (011)) This example illustrates cluster tree of depth along with the corresponding block partitions each level. Blocks marked with stripes stored low-rank matrices in HODLR format, while those filled with solid color represent dense matrices.
This formulation highlights key insight: both Mamba-2 and Gated DeltaNet share common semiseparable structure in the temporal dimension, but differ how they structure the hidden dimension. Mamba-2 relies scaled identities, while Gated DeltaNet applies identity-minut miinssrrnnk one modifications. Table 5 summarizes these distinctions.
B LOG-LINEAR ATTENTION AS H MATRICES
We begin by introducing two classes Hierarchical matrices (H matrices) following Massei et al.) (2020): HODLR (Hierarchically Off-Diagonal Low-Rank) matrices and HSS (Hierarchically Semi- Separable) matrices. We then show how Log-Linear Attention corresponds to a specific subclass of H matrices that occupies an intermediate position between these two. Finally, we discuss a further variant H matrices that, in principle, allows for more refined partitioning partitininn--potcntially enhancing approximation quality at the cost of increased (though constant-factor) computational complexity.
B. HODLR MATRICES
HODLR (Hierarchically Off- Diagonal Low-Rank) matrices are structured matrices built via recursive partitioning, where off off-diagonal blocks low-rank every level. This structure is formalized using a cluster tree Massei et al. (202)). Let 7 be the matrix dimension, and let be a perfectly balanced binary tree of depth L whose nodes are subsets of {I,..., .T). We say root I {1,..., T): (2) each level partitions indices into contiguous blocks; (3) every node Z(0)
cluster tree if: (1) the
at level has two children z((-1) and Z/K ((f-1) that form a disjoint partition of the parent. See Fig. for visual example of such hierarchical partitioning.
Now, let M E RTxx be a square matrix and T a cluster tree as described above. We say that M is (T, -ODLR matrix if.
rank (MI
sk
I II. E sibilings (T)
This hierarchical low-rank structure enables efficient OT log T') storage and matrix-vecta multipli- cation, making HODLR matrices a core component in fast algorithms for dense matrix computations. HODLR belongs to the broader class of rank-structured matrices known as Hierarchical matrices (H matrices).
B.2 HSS MATRICES
The OTT log T) memory complexity of HODLR matrices arises from their recursive structure: they consist of (log T) levels, each storing low-rank factorizations that require O space. In cases where these low-rank factors exhibit linear dependencies across levels, it is possible to exploit these relationships through nested hierarchical low-rank representations, potentially reducing the memory complexity to OTT) by eliminating the logarithmic factor Massei al. 2020).
17

---

Published as a conference paper at ICLR 2026
Let I and _ denote pair of sibling clusters level in the cluster tree T. Define n - as the block size at level E. The off-diagonal block corresponding to these clusters can be parameterized as:
MI I/ U
where U V E R xk E E Bakk
We call M matrix a Hierarchically Semiseparable matrices (HSS) if low-rank factors at different levels are linearly related through some "translation operators" T T
E 2k such that,
U (f-1)
((-1) J1
U
T U,
v
T
=
0
(
=
0
v
(e-1)
V.J
12
j2
More broadly, HSS matrices belong to subelass of 76 matrices known as H( matrices.
B.3 QUASI-HIERARCHIICN MATRIX.
As discussed above, when the low-rank basis matrices U and V exhibit linear relationships across levels L, the matrix M reduces to a semiseparable form. In this case, both storage and matrix-vector multiplication complexities can be reduced to O(T). Otherwise, M retains the general hierarchical structure with O I') complexity.
We define Quasi-liieaarcicall Matrix as one in which only one of the basis sequences, either U(4) or V(O, satisfies such linear nesting property across levels, while the other does not. The matrix M used in the LineLr model (Eq. is instance of this structure.
Both Hicrarchical and Quasi-Hierarchica matrices incur ( I') complexity for storage and computation during training. However, the of Quaai--Hirarcchiall matrices plays a erucial role in enabling O(log T) complexity during inference. We are not aware of a recurrent algorithm for general Hierarchical matrices that achieves logarithmic inference complexity
Reparameterization. More precisely, Eq. 4 represents Quasi-Hierarchhe matrix that has been specifically re-parameterized composition of the scalar weights (5)) and sequentially semisep- arable (SSS) matrix M This reparameterization serves two purposes: first, to highlight the connection between use of H. matrices and the SSS format adopted in prior work; and second, to enable the block decomposition into a hierarchy of SSS matrices, as shown in Eq. [5)
We present this re- peraammtterizttion below, along with its 4D tensor variant discussed in AA where we additionally assume that the matrices U, and V are invertible.
Matrix:
Tensor:
141 IIc.
M = Ri 19 uay
II ae
M U.V + A
#=
t=1
(0)
(1)
T = A
U II C, v c
A=
(0) (6) u,u;
F1-1
A ( = T U.V.
C - R
B.4 H MATRICES WITH STRONG AND WEAK ADMISSIBILITY
In the recurrent formulation of Log-Linear Attention, although there are (log states correspond- ing different hierarchical levels, roughly half of them zero in practice. This sparsity arises from the specific structure of HODLR RR matrices, which belong to a broader class of H matrices known as weakly admissible Hackbbusch et al. (2004).
In fact, our initial attempts involved using fully Hierarchical matrices, but were unable to derive recurrent formulation with O(log T) complexity. This motivated the design of Mmasi-Hierarchics matrices specifically support efficient recurrence.
18

---

Published as a conference paper at ICLR 2026
Figure Left: H. matrices with strong admissibility. Right: matrices with weak admissibility.
Figure Left:: H matrices with strong admissibility. Right: matrices with weak admissibility.
Figures and illustrate an alternative structure based on strong (or standard) admissibility. Unlike the weakly admissible variant, strongly admissible H matrices allow for finer-grained partitioning of matrix, and their corresponding recurrent forms utilize all hierarchical levels.
While strong admissibility yield computational cost Hackbusch et al. (2004). In our early experiments, using strong admissibility in Triton implementation resulted in up 4x slowdown, with only marginal improvements in accuracy. As result, we adopt the weakly admissible structure throughout this work and refer to simply the H-matrix.
accurate approximations, it comes with significant
C IMPLEMENTATIONS
Ampost
import nampy a2 ap
Inpost Loxch, che.n. lonal
deL segsun(x) (x)
I 1-11
x_aegsun c_oumsun[.... io Mone; x_cumanl None, :]
mask torch. cril (corch. ones (2, 7, devisons, devico, stype=bocll) 10
11
www.aamnneeededeeeee [i3l (snaak, torch.inf) Segggu..
12
14
15
def Javel_naskllovel 7):
reluen (yr dlypeetorch.bool)
18
19
torch meshgrid arange (?), torch.arange indexinge"1 113") hal: elisped (lavel
leval 111
22
valid (i 11 ec level) oe half) & (j half >e el cliped & (3 x ellpped)
swauen valid 23
26
def construct Runateii Sis
27
(segeunte))
securn sunitA 2I.... level, :] u-uuqqueese (-1) level_maok (lavel, foe lsvel range (int Ing.
1og2 (T)
1113
30
bactent fon B, C, 1, block (ene8):
19

---

Published as a conference paper at ICLR 2026
34 Arqunenzs:
35 X: (batch, longth, f_boads, [[hoad]
36
(batch, length, f_hoadst
(batch, longth, fLhoadd, datttto
38 C: (batch, longth, f_boods, dLstatel
39
Li (batch, lengthy f_baads, nun_ie vheze cun_leveis 2og2(1ennch) Return:
40
Y: (batch, lengthy n_hiadd,, [[hwad)
42
43
I shape[[]
44
x.diyge A.diype B.d.ype ype
ansort x.shapo[1; biock_ien
46
iaput_shage X.chape
47
Bearsange into blocka/chunka K.shapa X.shapo[1]
48
al // block_len
50
X, A, B, C, L tbs & len, sx:shape(2:11 Jor in 06 A, B, 6, 11 peremtte 10, 3, i, (batch, fLhoads, block_lon) torch..uneunn,,
51
52
(batick, ruiteads, 5, block_]enn
54
int (ap.1cg2 (biock_laa)) +1
55
run inter saaukkkllvvell
(op. (?)) 11 n.n_intrr__chunk Partition lambda into intra-chunk iater-chunk lanbda
inttra, Latater al.... ioan_intra_chank_eee
Li..., chantta__cnniieveeeeeeeee
58
Linntr "gintra.peemiii (0, 3, i, 2) (batch, nhhadds, munashankk, oun lun_levels, Mlock_len)
59
Corgutation
comat const suct Bunt iittta) Matarialias natrix dense mateix L_diag cozch. (or "belhn, bheia, bashp-bbellp",, C, B, B, X)
62
63
64
Intez chunk Corgutation dacay_stated torch. exp (A_oumsun]...> -1: cuunssu))
66
states torch.einan ("belhr, hry the belhp-sbohppr" , B decay statms, X) dheay_chunk [ored (segaun (AgeuniA_cummal..... -1113, (0, O, (.... #4, s1
67
state decay
corch.expie
70
del corpute (ot_il____of__eeellle (stales, level]; mask level mask (level + 1, c)-unequeere cengqueese (0)
71
72
desey_sthunk_eee
decay_
73
states torch einsun (*Dhae, bchpp bchpe->balge", decay_ states)
74
offf torch.einsmn *selin, brhgn, bell shellp",
25
77
states, denyy_o
78
79
innterl level),
relurn Y.uff
82
83
Yffff torch. zerox_ 1ike elegg
for sange iattur__ntttr_eenneeee iovellll
Yottt compute oft Level levellstateee istates,
86
87
(Y_ote Y_diag) reshape
Algorithm 1 Chunkwise Log-Linear Attention Algorithm
1: for E [T/C] do
2: Y|4 = (Q o M ((g)
3:
end for
4:
5:
for E [log, (T/C) do
for E [T/C]
Yu Yı + mask (8) (A e QmsSm)
7:
8:
Sp-11 mask (8) A S1)) mask (K V%r)
9:
end for
10:
end
11:
return Y
A naive implementation computes each level independently using Mamba-2-style primitive, then sums the cripuutsleadiig to redundant memory access and kernel launches. To improve efficiency, fuse computation across four levels into single Triton kemel, which we found optimal given SRAM constraints on an H100.
For backpropagation, unify gradient computation across all levels for VK and VV by analytically factoring their dependencies. This reduces kernel count and improves memory efficiency, achieving over 3x speedup compared to the naive multi-level version.
20

---

Published as a conference paper at ICLR 2026
D ADDITIONAL EXPERIMENT DETAILS
For the implementation benchmarks, all experiments were conducted on an H100 GPU with a batch size using 48 attention heads, head dimension of 64, and chunk size of 64. In Mamba-2-style models, the attention heads are applied to V (MVA pattern), whereas in FlashAttention-2, we adopt GQA-style attention by applying heads to Q. The dimensions of the Q and K states are set to 128, aligning with common training configurations.
For the MQAR experiments, we largely follow the setup described in Arora et al. (2024). Models are trained and evaluated on 256-token sequences containing between 4 and 64 key-value pairs. We do not evaluate on sequences longer than those used in training (i.e., no length generalization) In (Log-Lineaa Mamba-2 models, both the state and head dimensions are set to 16. For (Log-Linear) Gated DeltaNet, we use two attention heads by default, except for models with a dimension 16, where a single head is used, We tune the learning rate and, for Log-Linear models, also tune the parameterization of A. We run each configuration with five seeds. Training was early stopped when accuracy exceeded 99%.
For the language modeling experiments, each run was performed on 8xA100 or 8 8xH100 GPUs over the course of several days. We do not tie word embeddings, the initializer range to 0.006. Training is performed with global batch size of approximately 524K tokens for 95K steps (roughly 50B tokens). We use the wessh-iinea---a
vocabulary size of 32,000, and set
ion and f flame libraries Yang & Zhang 2024); Zhang & Yang (2025), following most of their default configurations.
Mamba-2
Ingelinear Mamba-2
80
70
Gated DeltaNet
40
Unea Gated-Dettalie DettaNet
52
32
64
Figure 9: MQAR experiments with early stopping at 99% accuracy.
Detailed Experimental Results. Figures and 10 and Tables 6 and provide detailed results.
Model
Wiki.
LMB.
LMB.
PIQA acc f
Hella. acc n
Wino. acc f
ARC-e acc f
ARC-c acc n
Avg.
ppl
ppl L
acc f
Transformer
21.56
22.14
38.8
65.1
39.6
50.7
45.6
24.5
44.0
w/ 24 Layers
21.13
21.17
39.3
66.6
40.4
53.3
47.8
26.4
45.6
Mamba-2
22.44
24.14
36.2
66.8
41.2
51.6
46.0
27.1
44.8
w/ Log-Linear
22.11
21.86
37.0
66.6
41.1
51.7
45.5
27.4
44.9
Gated DeltaNet
21.73
19.71
39.3
52.2
24.6
45.0
w/ Log- Linear
21.44
18.08
40.5
66.1
41.4
53.9
46.9
24.9
45.6
Table 6: Performance comparison on language modeling and zero-shot commonsense reasoning.
E
LLM USAGE
In this work, large language models (LLMs) were used to enhance writing by improving clarity and conciseness, to identify relevant literature across and beyond the immediate domain, and to support research ideation, particularly in mathematics and coding.
21

---

Published as a conference paper at ICLR 2026
single-1
single-2
single-3
1.0
1.0
0.8
0.6
0.4
0.4
0.2
mulli-key-1
multi-query
multi-value
0.5
0.8
0.2
0.2
0.0
4096
61.92
16384
4096
8192
16364
4096
8192
16384
Transformer
Gated- DeltaNet
Transformer (24
Log-Linear Mamba-2
Logearrear Gated-DeltaNet
Figure 10: Needle-In-A-Hayaeee experiments. See Table for details.
SWDE
SQuAD
FDA
Model
512
1024
2048
16k
512
1024
2048
16k
512
1024
2048
16k
Transformer
47.3
44.6
45.2
45.4
34.0
34.5
34.5
34.5
72.2
70.8
72.9
72.2
w/ 24 Layers
53.8
50.9
50.3
50.8
30.7
31.2
31.2
30.9
73.8
76.0
74.4
73.8
Mamba-2
42.5
37.7
30.7
30.6
21.6
21.7
21.9
22.0
53.7
38.0
23.8
21.3
Log-Linear
41.9
28.5
25.9
25.9
26.1
37.5
20.5
16.6
Gated DeltaNet
41.0
32.5
27.2
27.8
23.8
24.1
24.3
23.7
57.2
43.7
33.2
30.5
w/ Log-Lin
46.2
39.4
35.3
35.1
25.2
25.2
25.3
25.3
64.9
53.5
39.1
30.5
TriviaQA
Drop
NQ
Model
512
1024
2048
16k
512
1024
2048
16k
512
1024
2048
Transformer
48.5
49.6
48.5
48.5
22.8
22.8
22.5
22.3
24.5
24.3
24.6
w/ 24 Layers
46.9
47.0
46.8
46.8
22.7
22.4
22.7
23.0
24.0
24.4
24.5
Mamba-2
43.7
43.2
43.2
43.2
22.2
22.1
22.2
22.1
18.5
16.5
16.5
Log-Linear
44.9
45.0
45.5
45.5
20.2
20.6
20.3
19.9
20.0
19.9
20.4
Gated DeltaNet
45.6
45.6
45.6
45.6
21.1
21.7
21.4
21.8
20.1
18.4
18.7
w/ Log- Linear
45,9
45.6
46.0
46.0
20.7
20.8
20.8
21.0
22.5
21.8
21.3
Table 7: Accuracy retrieval tasks w/ input truncated to different lengths.
Single-Doc QA
Multi-Doc QA
Summarization
Few-shot
Code
Model
NQA
QQA
MPQ
HQA
2WM
QMS
TQA
Transformer
11.7
9.7
20.8
22.4
29.8
6.7
13.1
9.4
3.2
27.5
28.0
16.2
23.7
29.8
w/ Layers
18.4
26.1
25.7
11.6
16.8
9.4
10.3
16.5
45.2
31.5
30.9
Mamba-2
9.1
17.4
10.9
11.2
20.9
4.3
8.3
6.0
4.9
2.0
22.6
8.8
38.1
34.6
w/ Log-Linear
9.8
9.6
15.4
11.5
22.0
5.1
5.4
11.1
4.5
16.5
21.6
14.9
31.2
30.3
Gated DeltaNet
8.5
11.9
16.4
14.4
24.5
6.6
9.2
11.7
11.6
36.5
25.3
23.1
31.1
31.1
w/ Log-Linear
9.9
6.1
17.6
17.7
25.2
7.5
5.5
11.9
1.9
8.0
41.1
23.2
28.3
29.6
Table 8: Accuracy on LongBench tasks 2WikiMultiAA. Musique, GovReport, QMSum, MultiNews, TREC, TriviaQA, SamSum, LCC, and RepoBench-
Bai et al.
2023):
Narrative QA, QasperQA, MultiField QA, HotporQA.
22


Reviews:
[{"review_id": "NeYEPIrrLZ", "reviewer": "Reviewer_xdQ7", "summary": "This work proposes a method to improve the modeling performance of modern SSMs/ Linear RNNs such as Mamba and Gated DeltaNet, whose recurrent state can be formulated as $S_{t} = \\alpha_t * S_{t-1} + (KV)_t$. To get final output, these algorithms multiply query $Q_t$ by a single state matrix $S_t$, which aggregates information about all previous KV states up to step $t$. Log-linear attention instead disaggregates $S_t$ into $O(\\log T)$ states of the same size, each containing information about a disjoint contiguous subsequence of  $\\{0, …, t\\}$. Then the query gets multiplied independently by each state and also by an input-dependent scalar coefficient $\\lambda_i, \\; i \\in \\{0, …, O(\\log T)\\}$, corresponding to that state. Finally, the results sum up. A pure linear attention variant is equivalent to log-linear attention where $\\lambda_i=1$ for all i.\n\nThe partitioning of the sequence proceeds according to Fenwick tree scheme, where each subsequence can have at most $2^i$ consecutive timesteps, and the shortest subsequences is located at the latest step t, while longer subsequences’s boundaries go toward the sequence start.\n\nI feel excited about this novel method (see strengths) and vote for its acceptance.", "questions": "1. Can you come up with a theoretical explanation why log-linear attention offers performance improvements in comparison with pure linear variants?\n\n2. Did you try any other partition schemes besides Fenwick Tree partitioning? I could think of other schemes, with overlapping and disjoined partitions. There could even be some schemes that recover $O(T)$ complexity (e.g., proceed as usual until sequence length is X, then keep placing the oldest tokens into the outermost bucket instead of creating new levels of hierarchy). As such, why did you choose this specific scheme?\n\n3. A follow-up question: could there be some trade-off, where this algorithm could run in linear time at the expense of an arbitrary higher memory consumption?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* Potent sub-quadratic runtime alternatives to Transformers is an important open area of research, and this work provides a promising way to improve modeling quality of such architectures, hopefully bringing us closer to an algorithm capable of fully replacing Transformer in autoregressive language modeling.\n\n* The proposed method is coherent and intuitive: if we want to increase long-range performance in comparison with pure linear-time algorithms such as Mamba and DeltaNet, it is plausible that we have to execute a higher relative amount of computations, than for short sequences.\n\n* Log-linear attention is a meta-algorithm, which is compatible with many linear-time alternatives to softmax attention.\n\n* I believe the proposed approach has a potential to be extended and generalized by using other partitioning schemes which could bring further performance gains.\n\n* I’d like to specifically praise comprehensive and fair comparisons which don’t shy away from presenting both positive and negative results. They help to build an honest and complete picture of the method’s strong and weak sides and possible areas of application.\n\n* The validation shows meaningful improvements relative to pure linear counterparts on a large subset of tested benchmarks, effectuated by log-linear extension.", "weaknesses": "My judgement is that the paper doesn't have major problems. There are some minor issues mostly related to exposition/ formatting which I listed below. \n\n1. Did you perform any measurements of the memory footprint of the algorithm during inference (prefill, decode) and training workloads? A comparison for different sequence lengths with vanilla Mamba-2 and Gated DeltaNet, as well as with FlashAttention would be helpful. I understand that it’s likely to be $O(\\log(T))$ times greater than aforementioned algorithms, but that’s an expected trade-off, which is easily tolerated given log-linear attention’s superior modeling quality. Nonetheless, these numbers would be important for finding out the most fitting conditions to use the algo.\n\n2. It’s not clear to me from the paper how the log-linear part of the algorithm modifies the underlying linear part, both in chunk-wise parallel and recurrent algos. For example, what happens when two states for neighboring filled buckets get merged after a recurrent step? Since the states are created independently, $S_{[t_1:t_2)} + S_{[t_2:t_3)} \\neq S_{[t_1:t_3)}$, although the underlying algorithm requires precisely $S_{[t_1:t_3)}$. Similar ambiguities emerge when considering chunk-wise form. \n\n3. There is no formal definition of the exact functional form of $\\lambda_i$s. Are they simply linear projections of input vector query $q_t$? Or are they calculated using the same laws as alphas (i.e. in a different manner for each underlying architecture)? How does the algorithm handle that the number of lambdas $max(i)$ is not bounded from above and can extrapolate beyond the maximal value during pre-training?\n\n4. Minor typos/ formatting problems:\n* Line 189 – why is the right bound $t$ open? From the text it follows that the t-th token itself is a part of the partition.\n\n* Line 213 – it would be clearer to mention explicitly that $b_t^{(i)}$ denotes the starting position of partition i, it was somewhat hard to infer for me at first glance.\n\n* Lines 237-246 – there’s no caption of this figure.\n\n* Line 291 – I believe it’s $\\lceil T/C \\rceil$.\n\n* Line 763 – image and table captions are overlaid.\n\n* Table 3 – There’s no mention of the table in the text, and it takes an attentive reader to understand that it’s the summary of Table 6.", "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": "TzBFbDKerL", "reviewer": "Reviewer_Zys3", "summary": "This paper identifies the fixed state size of currently best performing linear attention variants with gating, such as Mamba-2 and Gated DeltaNet as the main limitation to handle information in a long context. \nBy introducing log-linear attention - a framework with a logarithmically growing set of hidden states that can be applied to existing linear attention variants - it provides a middle ground between standard attention with linear growing memory and linear attention with a fixed state size, which is independent of sequence length.\nLog-linear attention is based on the insight that efficient attention variants depend on the structure of the structure of the masking matrix in the attention operation, and replaces existing masking structures with a hierarchical one. \nWith log-linear variants of Mamba-2 and Gated Delta Net, the authors demonstrate the general applicability of the log-linear attention framework. \nIn their experiments on small scale language modeling setups and synthetic tasks the log-linear variants show mild but consistent improvements over the standard linear RNN variants. \nIn training throughput and runtime benchmarks the authors demonstrate benefits of the log-linear Mamba-2 variant over Flash-attention 2 at longer context and only small runtime overheads compared to the default Mamba-2 implementation.", "questions": "- L.392-393: Why does the linear layer on top of the hidden states add 3% additional parameters to Mamba-2 and only 0.4% to Gated Delta Net?\n- Description of the P matrix L.236 - 245 would help understandability\n- L. 337, 997: Could the authors elaborate on the MVA pattern for Mamba-2 and/or provide references to descriptions of this?\n- Does there exist an optimized kernel implementation for the log-linear variant of Gated Delta Net?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Clear motivation\n- Well written\n- The overview of related variants and the view of efficient attention mechanisms as different parametrizations of structured masking matrices is great. It shows how this naturally results in the idea & implementation for log-linear attention.\n- To the best of my knowledge log-linear attention is a novel method for expanding the state size.\n- The paper provides simple pure PyTorch implementations and shows experiments with optimized kernels (even though code for these is missing) achieving runtime benefits over existing methods", "weaknesses": "- Only small performance improvements over linear counter parts / base methods across several tasks (admitted by authors)\n- The authors place log-linear attention as middle ground between standard attention and linear attention in terms of memory state size: Hence I would expect an exemplary calculation of the memory consumption of log-linear attention, standard linear attention and KV-cache for various sequence lengths and reasonable model sizes\n- No code provided for Mamba2 and Gated Delta Net log linear attention variants\n- The paper would further benefit from more details on the efficient kernel implementations (including code) for Mamba-2 \n\n\nDespite these weaknesses, the paper has a clear motivation, is very well written, contributes new insights on efficient attention variants and their implementation, as well as a novel method for expanding the state size of linear attention variants, which outweighs the weaknesses. Therefore I recommend acceptance.", "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": "B2rUFG5TCC", "reviewer": "Reviewer_YX7t", "summary": "Log-Linear Attention is an extension of Linear Attention to multiple timescales growing logarithmically along with a Fenwick-tree scheme. This way it introduces more memory capacity reserved for short time scales, which in turn enables a clearer separation of the longer-term memory (higher levels) for long-scale information. Through input-dependent temporal coefficients this time-scale separation can be achieved. The method shows slight performance gains on synthetic long-context and memory-capacity tasks.", "questions": "- How does your method relate to other existing hierarchical sequence architectures like WaveNet that uses dilated convolutions [1]?\n- How would this combine with compression / focusing of the inputs via exponential gating as in xLSTM [2] which has shown to be beneficial for long-context tasks in [3]?\n- Given the different temporal scales are only separated by the different temporal coefficients $\\lambda_t^{(l)}$, how can the effective network capacity exceed the one of pure linear attention based on the foundational theory of Hopfield network capacity? For a querying mechanism that should work across all temporal scales (as in MQAR), shouldn't the \"space benefit\" vanish to normal linear attention (potentially there is less noise on the shorter time-scales in Log-Linear Attention)?\n\n\n[1] van den Oord et al. (2016): WaveNet: A generative model for raw audio\n\n[2] Beck et al. (2024): xLSTM: Extended Long Short-Term Memory\n\n[3] Beck et al. (2025): xLSTM 7B: A Recurrent LLM for Fast and Efficient Inference", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- fast parallel and hardware-aware implementation\n- captures typical inductive bias on shorter time-scales (recency bias)", "weaknesses": "- theoretically unclear why the extended memory can be effectively used, except for not \"bloating\" the long-term memory at the highest level with short time-scale information that can be store in lower levels\n- mild improvements on benchmarks\n- unclear scaling behavior", "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)