Log-Linear Attention

ArXiv: 2506.04761

🎯 Pitch

Standard linear attention models compress their entire history into a fixed-size state, limiting long-range recall; this work shows that simply maintaining a logarithmic number of parallel states (one for each Fenwick-tree level) enables near-perfect retrieval accuracy (99.8% vs. 56.8%) with only O(log T) memory and O(T log T) training time, effectively closing the expressiveness gap with softmax attention without sacrificing efficiency.

---

1. Executive Summary

This paper introduces log-linear attention, a general framework that extends linear attention and state-space models to use a logarithmically growing set of hidden states rather than a fixed-size one, balancing linear attention's efficiency with softmax attention's expressiveness. The authors instantiate log-linear variants of two recent architectures—Mamba-2 and Gated DeltaNet—and evaluate them on synthetic associative recall (MQAR), academic-scale language modeling (50B tokens on Long-Data-Collections with ~800M parameter models), and long-context retrieval (RULER's Needle-In-A-Haystack). Log-linear attention admits a matmul-rich parallel form whose training compute is O(T log T) (hence the name) and whose decoding memory is O(log T), achieved by partitioning the prefix into Fenwick-tree buckets and maintaining independent recurrent states per bucket with learnable level-specific weighting coefficients (λ). On language modeling, Log-Linear Gated DeltaNet reduces WikiText perplexity from 21.73 to 21.45 and improves zero-shot commonsense reasoning average from 45.0 to 45.6, while on single-needle retrieval at 8K context Log-Linear Mamba-2 improves accuracy from 56.8% to 99.8% over its linear counterpart, establishing that hierarchical temporal structure provides meaningful gains on long-range tasks while preserving the practical benefits of recurrent inference.

2. Context and Motivation

The Core Problem: The Inescapable Tradeoff Between Efficiency and Expressiveness in Attention

The fundamental tension this paper wrestles with is one that has structured the entire subfield of efficient sequence modeling: how do you achieve the expressiveness of softmax attention without paying its quadratic computational and linear memory costs? Softmax attention, as introduced in the Transformer architecture (Vaswani et al., 2017), is extraordinarily powerful—it allows every token to attend to every other token with pairwise interaction scores computed through a non-linear kernel. This full-attention mechanism gives the model fine-grained access to the entire history, which is critical for tasks like associative recall where a query token needs to retrieve a specific value from an arbitrary earlier position in the sequence. However, this expressiveness comes at a steep price: the attention matrix softmax(QKᵀ ⊙ M) requires $O(T^2)$ compute and $O(T)$ memory for a sequence of length $T$, making it prohibitively expensive for long sequences. Even with hardware-optimized implementations like FlashAttention (Dao et al., 2022b; Dao, 2024) that reduce the constant factors through I/O-aware tiling, the quadratic scaling remains a fundamental bottleneck that limits context lengths in deployed systems and constrains new applications.

The paper frames this through a unifying structured-matrix lens (Section 2, Equation 1): all efficient attention mechanisms can be expressed as $O = (A \odot M) V$, where $A$ is an attention-like interaction matrix (e.g., $QK^\top$) and $M$ is a causal masking matrix. The structure of $M$ determines computational complexity. In softmax attention, $M$ is an unstructured lower-triangular matrix (all 1s below the diagonal), leading to quadratic cost. The key insight is that the structure imposed on $M$ is what enables efficient algorithms—not the removal of the softmax operation per se. Different structural choices lead to different points on the efficiency-expressiveness Pareto frontier.

The Dominant Solution and Its Fundamental Limitation

Linear attention (Katharopoulos et al., 2020) represents the extreme efficiency end of this spectrum. By simply removing the softmax and using a linear kernel ($A = QK^\top$ with $M$ as a lower-triangular matrix of 1s), linear attention can be reformulated as a linear RNN with a matrix-valued hidden state: $S_t = S_{t-1} + v_t k_t^\top$, $o_t = S_t q_t$. This enables $O(T)$ training time (via chunkwise parallelism) and $O(1)$ decoding memory—dramatic improvements over softmax attention. Modern variants have further enhanced this basic recipe:

• Gated linear attention (Peng et al., 2021; Yang et al., 2023; Qin et al., 2024b; Peng et al., 2024) introduces a scalar forget gate $\alpha_t \in (0,1)$, resulting in recurrence $S_t = \alpha_t S_{t-1} + v_t k_t^\top$. When $\alpha_t$ is data-dependent (as in Mamba-2; Dao & Gu, 2024), the mask $M$ acquires a 1-semiseparable structure where every lower-triangular submatrix has rank at most 1. This structure still permits $O(T)$ chunkwise training while giving the model a learned forgetting mechanism.

• Delta-rule-based linear attention (Schlag et al., 2021; Yang et al., 2024b;a) replaces the additive update with the delta rule: $S_t = S_{t-1}(I - k_t k_t^\top) + v_t k_t^\top$. When combined with scalar gating (Gated DeltaNet; Yang et al., 2024a), the recurrence becomes $S_t = \alpha_t S_{t-1}(I - k_t k_t^\top) + v_t k_t^\top$. These models employ data-dependent structured transition matrices that have been theoretically shown to be more expressive than simple multiplicative gates for certain state-tracking tasks (Merrill et al., 2024; Grazzi et al., 2025).

The critical limitation that motivates this entire paper, however, is structural and inescapable: all these models use a fixed-size hidden state. In linear attention, the state $S_t \in \mathbb{R}^{d \times d}$ has constant dimensionality regardless of sequence length. This means the model must compress its entire history of observations into a single fixed-capacity representation. While the matrix-valued state provides more capacity than the scalar-valued state of traditional RNNs, it still imposes a hard information bottleneck. As the sequence grows longer, the model must increasingly coarsen or overwrite its representation of earlier tokens to make room for new information.

This fixed-size state is a fundamental limitation for tasks requiring fine-grained access to arbitrary positions in the context, most notably associative recall. Arora et al. (2024) demonstrated theoretically and empirically that linear attention models struggle on multi-query associative recall (MQAR) precisely because their constant-size state cannot simultaneously maintain distinct representations of many key-value pairs. The information from earlier pairs gets blended together in the matrix state, making it impossible to retrieve a specific value given its associated key.

The Other Extreme: Long Convolution Models

Long convolution models (Poli et al., 2023; Fu et al., 2023; Qin et al., 2023; Massaroli et al., 2023) offer an alternative point in the design space. By parameterizing the attention pattern as a convolutional kernel $h \in \mathbb{R}^T$ of length equal to the sequence, these models create a Toeplitz-structured mask $M$ where $M[i,j] = h[i-j]$ for $i \geq j$. This enables $O(T \log T)$ training via FFT, which is already log-linear in complexity. Crucially, long convolution models can allocate distinct weighting to every position offset in the history—they do not suffer from the fixed-state bottleneck.

However, they face a different bottleneck: decoding memory remains linear, $O(T)$. At inference time, each step requires maintaining the key-value representations of all previous tokens (or the equivalent state), giving them the same memory footprint as softmax attention. While recent work (Oncescu et al., 2025) has improved decoding speed to $O(\log^2 T)$ per step, the memory cost is fundamentally $O(T)$. This makes long convolution models unsuitable for memory-constrained deployment scenarios where constant or logarithmic memory is essential (e.g., on-device inference, serving with limited KV-cache headroom).

Some long convolution models like S4 (Gu et al., 2022) can be reparameterized into time-invariant SSMs and thus achieve constant memory. Others have been distilled into RNNs (Massaroli et al., 2023; Qin & Zhong, 2023), but this distillation inherits the fixed-state bottleneck of the target RNN architecture. There is no free lunch: the expressiveness that comes from having position-specific weights cannot be trivially compressed into a constant-size recurrence.

The Gap: No Architecture Occupies the Middle Ground

This is the specific gap the paper identifies and addresses. The landscape of efficient sequence models consists of:

• Quadratic-attention models (Transformers): $O(T^2)$ compute, $O(T)$ memory, fine-grained access to all positions—expensive but maximally expressive.
• Linear-attention/SSM models (Mamba-2, Gated DeltaNet, RetNet): $O(T)$ compute, $O(1)$ memory, single fixed-size state—efficient but fundamentally limited by the state bottleneck on long-range recall tasks.
• Long-convolution models (Hyena, H3, MultiHyena): $O(T \log T)$ compute, $O(T)$ memory, multi-scale access but no compact recurrent state—log-linear training cost but linear decoding cost.

There is a conspicuous absence: no architecture simultaneously achieves subquadratic training, sublinear decoding memory, and multi-scale access to history. Specifically, no model provides $O(T \log T)$ training, $O(\log T)$ decoding memory, and the ability to attend to history at multiple temporal granularities through an exponentially growing set of recurrent states. This gap is what log-linear attention is designed to fill.

Why This Gap Matters

The importance of filling this gap extends beyond theoretical curiosity. The paper identifies several practical drivers:

Long-context deployment is increasingly common. Modern LLMs are being deployed with context windows of 128K tokens and beyond. In these regimes, the $O(T^2)$ cost of softmax attention becomes prohibitive even for prefill, and the $O(T)$ KV-cache memory becomes a significant hardware constraint. Linear attention/SSMs solve the memory problem but at the cost of reduced long-range recall capability, as documented by MQAR benchmarks. A model that could maintain $O(\log T)$ memory while preserving fine-grained access to recent history and coarse-grained access to distant history would be directly applicable to these deployment scenarios.

The expressiveness-efficiency tradeoff is not binary. The paper's perspective (reflected in Table 1) is that there is a rich spectrum of possible masking structures between the extremes of "fully unstructured" (softmax attention) and "maximally structured" (semiseparable/SSM). Different structures offer different points on this Pareto frontier. The field had not systematically explored hierarchical structures that occupy the middle ground—offering better expressiveness than semiseparable while maintaining better scaling than dense attention. Log-linear attention is a concrete instantiation of this middle-ground philosophy.

Recent theoretical work has clarified the limitations of fixed-state models. Merrill et al. (2024), Grazzi et al. (2025), Siems et al. (2025), and Peng et al. (2025) have provided formal analyses showing that while delta-rule-based models with structured transition matrices are more expressive than simple gated linear attention for state tracking, they still face fundamental limitations from the fixed state size. This theoretical landscape sets clear expectations: to improve long-range recall, one needs to grow the state—but to maintain efficiency, that growth must be sublinear. Logarithmic growth is the natural sweet spot.

How This Paper Positions Itself

The paper does not aim to propose an entirely new model class from scratch. Instead, it introduces log-linear attention as a general framework that can be applied on top of existing linear attention/SSM architectures to "upgrade" them from linear-time constant-memory to log-linear-time logarithmic-memory variants. The framework is compositional: any model that admits an efficient chunkwise-parallel primitive (such as Mamba-2's semiseparable scan or Gated DeltaNet's structured attention) can be extended by replacing its flat temporal structure with a hierarchical one.

The key design choice is the use of Fenwick-tree partitioning (Section 3.1). This is not an arbitrary hierarchical decomposition—it is specifically chosen because it enables two critical properties simultaneously:

1. Matmul-rich parallel training with $O(T \log T)$ complexity, achieved by decomposing the hierarchical mask $M_H$ into a block-diagonal intra-chunk component and a series of sequentially semiseparable inter-chunk components (Equation 5). Each inter-chunk level can be processed using the same efficient primitives that make linear attention fast.

2. $O(\log T)$ decoding memory, achieved because the Fenwick tree maintains exactly $O(\log T)$ independent recurrent states at any time, each summarizing a bucket of exponentially increasing size. Recent tokens are stored at fine granularity (bucket sizes 1, 2, 4, ...) while distant tokens are coarsened into larger summaries.

The elementwise product of a sequentially semiseparable (SSS) mask $M_S$ with the hierarchical mask $M_H$ yields a matrix that remains hierarchical—specifically, a quasi-H matrix (Section B.1 and B.3). This mathematical property ensures that the composition preserves the desirable computational characteristics. The resulting models (Log-Linear Mamba-2, Log-Linear Gated DeltaNet) inherit the gating mechanisms of their linear counterparts while gaining multi-scale temporal structure through the Fenwick-tree partitioning.

The paper explicitly frames this as not intended to be the best subquadratic architecture but rather a demonstration of the framework's promise relative to sensible baselines. The experiments (Section 4) are designed to test whether the hierarchical structure provides meaningful gains over flat (semiseparable) structure on tasks that stress long-range recall and context utilization—associative recall (MQAR), per-position loss across 16K tokens, and needle-in-a-haystack retrieval. The results should be interpreted as evidence for the viability of the hierarchical approach rather than as a claim that these specific instantiations beat all alternatives on all metrics.

Relationship to Prior Work on Hierarchical Attention

The paper distinguishes its approach from earlier efforts at log-linear or hierarchical attention. Kitaev et al. (2020)'s Reformer uses locality-sensitive hashing to cluster similar queries and keys, which reduces complexity but does not provide a structured, recurrent-form state for inference. The LogSparse Transformer (Li et al., 2019) and Informer (Zhou et al., 2021) introduce fixed sparse attention patterns that reduce compute but do not achieve logarithmic decoding memory. Multi-resolution attention (Zeng et al., 2022) refines attention scores from coarse to fine granularity, but operates in the parallel form without a recurrent state.

Most directly related is Zhu & Soricut (2021)'s H-Transformer-1D, which also uses hierarchical matrices for attention. However, their formulation is fully parallel (computing the entire attention matrix at each level) and targeted at modest sequence lengths. In contrast, log-linear attention adopts a chunkwise-parallel strategy that interleaves parallelism and recurrence, with a custom Triton implementation optimized for long-sequence training and efficient decoding. The distinction is significant: the chunkwise formulation is what enables the system to both train efficiently on long sequences and decode with $O(\log T)$ memory, whereas a purely parallel hierarchical approach would still require materializing or recomputing large sub-blocks during generation.

Concurrent work by Yau et al. (2025) proposes a related architecture with $O(\log T)$ memory using a relaxed prefix-scan algorithm, but their approach accommodates arbitrary (potentially non-associative) aggregation functions, whereas log-linear attention specifically leverages the associativity of linear recurrent updates to enable efficient chunkwise parallelism.

The Missing Ingredient: Learnable Multi-Scale Weighting

A crucial design element that distinguishes log-linear attention from a naive Fenwick-tree pooling scheme is the learnable level-specific weighting coefficients $\lambda_t^{(\ell)}$ (Section 3.1, Equation 3). Each bucket at level $\ell$ contributes to the output at time $t$ weighted by a non-negative coefficient $\lambda_t^{(\ell)}$, parameterized as a linear function of the current input $x_t$. This allows the model to adaptively emphasize different temporal scales based on the current context.

The paper notes a subtle but critical point: when all $\lambda_t^{(\ell)}$ are identical (or linearly related across time), log-linear attention collapses to standard linear attention. This is because the hierarchical decomposition essentially partitions the linear attention state into multiple buckets, but if the buckets are weighted uniformly during readout, the partition provides no benefit beyond the original flat representation. The distinctiveness of the $\lambda^{(\ell)}$ values is therefore essential—they are what allow the model to attend differently to recent fine-grained tokens versus distant coarse-grained summaries.

This design reflects an inductive bias: interactions between a query and recent tokens are likely to be detail-sensitive and benefit from high resolution, while interactions with distant tokens may be adequately captured by coarser summaries. This bias aligns with physical phenomena in many domains (temporal decay of influence, hierarchical structure in language) but the paper acknowledges it may not be optimal for all applications, flagging the choice of partitioning scheme and level weighting as areas for future exploration.

Summary of the Gap and Positioning

The paper addresses the specific gap of no existing architecture simultaneously providing subquadratic training, sublinear decoding memory, and multi-scale historical access through a growing representation. It positions log-linear attention as a composable framework that upgrades existing linear attention/SSM models by replacing their flat temporal structure with a Fenwick-tree hierarchy, enabling $O(T \log T)$ training and $O(\log T)$ decoding while maintaining the matmul-rich parallelism that makes linear attention hardware-efficient. The framework is validated through case studies on Mamba-2 and Gated DeltaNet, chosen as representative architectures that cover the two main parameterizations of $A$ in the unified attention formulation—multiplicative gating and delta-rule-based structured transitions—thereby demonstrating the framework's generality across the linear attention design space.

3. Technical Approach

3.1 Reader Orientation

This paper develops log-linear attention, a general framework that extends any linear attention or state-space model by replacing its single fixed-size recurrent state with a logarithmically growing set of independent states, each summarizing a temporal "bucket" of the prefix at a different granularity. The system solves the problem that linear attention models compress their entire history into one constant-sized matrix, which fundamentally limits their ability to recall fine-grained details from arbitrary past positions; log-linear attention strikes a middle ground where recent tokens are retained at high resolution while distant tokens are summarized at coarser scales, yielding O(T log T) training cost and O(log T) decoding memory rather than O(T) and O(1).

3.2 Big-Picture Architecture (Diagram in Words)

The system has four major components:

1. Fenwick-Tree Partitioner — determines which positions in the prefix belong to which exponentially-sized temporal buckets, producing a hierarchical decomposition with O(log T) levels. This component defines the structure of the masking matrix $M_H$ and is purely a positional/bookkeeping mechanism, not learned.

2. Multi-Scale Recurrent States — a set of independent matrix-valued hidden states $\{S_t^{(\ell)}\}_{\ell=0}^{L-1}$, where $L = O(\log T)$, with each state responsible for summarizing one bucket from the Fenwick-tree partition. States at level $\ell$ aggregate information from bucket size $2^{\ell-1}$ (for $\ell \geq 1$) plus a sentinel level-0 bucket of size 1.

3. Learnable Level-Weighting Coefficients $\lambda_t^{(\ell)}$ — scalar values produced by a linear projection of the current input $x_t$ that determine how much each level's state contributes to the output. These are what allow the model to adaptively attend to different temporal scales and prevent log-linear attention from collapsing to standard linear attention.

4. Chunkwise Parallel Scan Engine — the training algorithm that decomposes the hierarchical attention matrix into a block-diagonal intra-chunk component (processed densely within each chunk) and a series of sequentially semiseparable inter-chunk components (processed using existing efficient primitives, one per hierarchical level), yielding O(T log T) total cost.

Information flow at training time: input sequence of length T → queries, keys, values Q, K, V computed per position → Fenwick-tree partition maps each (query position, key position) pair to a level ℓ → per-position learnable coefficients $\lambda_t^{(\ell)}$ computed from input → the quasi-hierarchical mask $M_H$ is formed by combining position-to-level mapping with level weights → chunkwise decomposition splits $M_H$ into intra-chunk dense blocks and inter-chunk SSS blocks → existing linear-attention primitives process inter-chunk levels in parallel → outputs summed across levels → final output O.

Information flow at decoding time: new token arrives → Q, K, V computed → Fenwick-tree recurrence updates the set of states: some states merge and promote to coarser levels, the new token enters level 0, unused levels are zeroed out → query reads from each active level's state weighted by $\lambda_t^{(\ell)}$ → output $o_t$ is the weighted sum across levels. Exactly O(log T) states are maintained and accessed per step.

3.3 Roadmap for the Deep Dive

• First, the Fenwick-tree partitioning scheme and the hierarchical matrix $M_H$ it induces (Section 3.1). This is the structural core of the framework—understanding the bucket decomposition is prerequisite to understanding everything else, including why the training algorithm works and why decoding is O(log T).

• Second, the recurrent form and the per-level state update rules (Section 3.1 and 3.2). This explains how the O(log T) states evolve over time, which states get promoted or zeroed at each step, and why the total number of active states grows logarithmically. This is where the connection to Fenwick trees is made concrete.

• Third, the learnable $\lambda^{(\ell)}$ coefficients—how they are parameterized, why they are necessary to prevent collapse to linear attention, and how they enable adaptive multi-scale weighting.

• Fourth, the parallel form and the hierarchical matrix decomposition (Equations 4 and 5, Section 3.3). This shows how the recurrent computation can be expressed as structured matrix multiplication, which is the key to efficient training. The decomposition into block-diagonal plus block-low-rank components directly yields the chunkwise algorithm.

• Fifth, the chunkwise parallel training algorithm itself (Algorithm 1, Section 3.3). With the decomposition established, we can walk through how intra-chunk and inter-chunk computations are performed, why the complexity is O(T log T), and what the existing linear-attention primitives contribute.

• Sixth, the instantiation on Mamba-2 and Gated DeltaNet (Section 3.4). This shows how the framework composes with existing architectures by elementwise-multiplying the original semiseparable mask $M_S$ with the hierarchical mask $M_H$, producing quasi-H matrices that inherit the gating mechanisms of the base models while gaining multi-scale temporal structure.

• Seventh, the Triton implementation and practical optimizations (Section 3.5). This covers kernel fusion across levels, gradient computation strategies, and the engineering decisions that make the theoretical O(T log T) complexity yield practical wallclock improvements.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a framework paper whose core idea is that the masking matrix $M$ in the unified efficient attention formulation $O = (A \odot M)V$ can be given a hierarchical structure induced by Fenwick-tree partitioning, yielding a model class that sits between linear attention (semiseparable $M$, O(T) training, O(1) decoding) and softmax attention (unstructured $M$, O(T²) training, O(T) decoding) with O(T log T) training and O(log T) decoding. The framework is compositional—it can be applied on top of any existing linear attention architecture by replacing its flat temporal mask with a hierarchical one—and the authors validate it through two case studies: Log-Linear Mamba-2 and Log-Linear Gated DeltaNet.

---

Fenwick-Tree Partitioning and the Hierarchical Mask $M_H$

The core intuition. When a query token at position $t$ needs to attend to its prefix $[0, t)$, it faces a choice: attend to every past token individually (softmax attention, expensive), or attend to a single summary of the entire prefix (linear attention, lossy). Log-linear attention takes a third option: attend to a set of summaries at exponentially increasing granularities. Tokens from the very recent past (say, positions $t-1$ through $t-4$) are kept as individual tokens or small groups. Tokens from the more distant past (positions $t-32$ through $t-63$) are merged into a single summary. Tokens from the far past (positions 0 through $t/2$) are merged into an even coarser summary.

This is formalized through the Fenwick tree (also known as a binary indexed tree; Fenwick, 1994; Ryabko, 1992). The Fenwick tree provides a deterministic scheme for partitioning any prefix into a set of $O(\log T)$ disjoint buckets, where bucket sizes are powers of two. The partitioning is uniquely determined by the least significant set bit of the current position $t$, denoted $\text{lssb}(t) = \max\{\ell \in \mathbb{N} \mid 2^\ell \text{ divides } t\}$.

The partitioning algorithm. At time $t$, the prefix $[0, t)$ is decomposed greedily by repeatedly subtracting the largest power of two that fits within the remaining segment:

Let $b_t^{(0)} = t$ (the query position, not included in the prefix).
For $i = 0, 1, 2, \ldots$ until the remaining prefix is consumed:
$\quad b_t^{(i+1)} = b_t^{(i)} - 2^{\text{lssb}(b_t^{(i)})}$
$\quad$ The segment $[b_t^{(i+1)}, b_t^{(i)} - 1]$ is assigned to level $\ell = \text{lssb}(b_t^{(i)}) + 1$.

Additionally, a sentinel bucket $B_t^{(0)} = \{b_t^{(0)}\} = \{t\}$ of size 1 is maintained at level 0, representing the query's own position (which is not part of the prefix but is included for completeness in the formulation; in causal attention, self-attention at position $t$ is handled separately).

Example concretely illustrates the pattern. Consider $t = 7$ (binary 111). The decomposition proceeds:

• Start: remaining prefix = [0, 7). Largest power of two dividing 7: $\text{lssb}(7) = 0$ (since $2^0$ divides 7). Subtract $2^0 = 1$: bucket [6, 6] at level 1, remaining prefix = [0, 6).
• Next: $\text{lssb}(6) = 1$ (since $2^1 = 2$ divides 6). Subtract $2^1 = 2$: bucket [4, 5] at level 2, remaining = [0, 4).
• Next: $\text{lssb}(4) = 2$. Subtract $2^2 = 4$: bucket [0, 3] at level 3, remaining = ∅.

So at time 7, the query attends to three hierarchical summaries: a level-3 summary of positions 0–3 (size 4), a level-2 summary of positions 4–5 (size 2), and a level-1 summary of position 6 (size 1). The number of buckets is 3, which equals the number of 1-bits in the binary representation of 7, which is $O(\log 7)$.

Figure 2 in the paper visualizes this assignment for $t = 0$ through $t = 7$, showing how each time step gets assigned to different bucket levels in the prefixes of subsequent positions.

Why Fenwick and not an arbitrary dyadic tree? The Fenwick decomposition has a crucial property that arbitrary dyadic partitions do not: it is consistent across time steps in a way that enables efficient recurrent updates. Specifically, the buckets at time $t$ can be obtained from the buckets at time $t-1$ through a simple set of merge-and-promote operations (detailed below in the state update recurrence). An arbitrary hierarchical partition would require recomputing the bucket assignments from scratch at each step, destroying the O(log T) per-step decoding property. The Fenwick tree is the unique structure that simultaneously provides (a) logarithmic bucket count, (b) efficient update from one time step to the next, and (c) exponentially growing bucket sizes.

The hierarchical mask $M_H$ in matrix form. Given a sequence of length $T$, the Fenwick partitioning defines a mapping from each (query position, key position) pair to a bucket level. Let $\ell(t, s)$ denote the level of the bucket that contains key position $s$ when the query is at position $t$ (with $s \leq t$ for causal masking). The hierarchical mask $M_H \in \mathbb{R}^{T \times T}$ is then defined elementwise as:

$M_H[t, s] = \begin{cases} \lambda_t^{(\ell(t,s))} & \text{if } s \leq t \\ 0 & \text{otherwise} \end{cases}$

where $\lambda_t^{(\ell)} \geq 0$ is a learnable scalar weight for level $\ell$ at query time $t$, parameterized as a linear function of the input at position $t$.

What this matrix represents operationally. For a fixed query row $t$, the non-zero entries in $M_H[t, :]$ are segmented into $O(\log t)$ contiguous blocks, each block corresponding to one Fenwick bucket. Within each block, all entries share the same scalar weight $\lambda_t^{(\ell)}$. This means that all key positions within the same bucket are equally weighted for the purpose of the hierarchical gating—the differentiation among positions within a bucket comes from the underlying attention matrix $A$ (e.g., $QK^\top$ in Mamba-2, or the delta-rule structured $A$ in Gated DeltaNet). The $\lambda$ values modulate how much each bucket as a whole contributes, not the within-bucket attention pattern.

Why this form and not a general low-rank block. The scalar-per-bucket form $M_H[t,s] = \lambda_t^{(\ell)} \cdot 1$ (within a block) is what yields the decomposition in Equation 5 into semiseparable components. If each block were a full low-rank matrix (e.g., $U_t^{(\ell)} V_s^{(\ell)\top}$ with vector-valued $U, V$), the inter-chunk computation would no longer reduce to repeatedly applying existing linear-attention primitives—it would require a more general hierarchical matrix multiplication algorithm, which does not have the same efficient chunkwise formulation. The scalar-coefficient design is the sweet spot: expressive enough to capture level-dependent importance weighting, structured enough to retain efficient algorithms.

The paper explicitly connects this mask to HODLR (Hierarchically Off-Diagonal Low-Rank) matrices (Hackbusch et al., 2004; Massei et al., 2020). $M_H$ is a lower-triangular instance of a quasi-H matrix—specifically, a reparameterization of an HODLR matrix where the off-diagonal low-rank blocks are further specialized to be products of scalar level weights and an underlying sequentially semiseparable structure. This connection is explored in depth in Appendices B.1–B.4.

---

The Recurrent Form: Multi-Scale State Maintenance

From buckets to states. Each bucket $B_t^{(\ell)}$ maintains its own recurrent state $S_t^{(\ell)} \in \mathbb{R}^{d \times d}$ (for the simplest linear attention case). The state $S_t^{(\ell)}$ summarizes all key-value pairs whose positions fall within that bucket at time $t$. Since the bucket is just a set of temporal indices, the natural summary is the sum of outer products $v_s k_s^\top$ for all $s$ in the bucket:

$S_t^{(\ell)} = \sum_{s \in B_t^{(\ell)}} v_s k_s^\top$

where $v_s \in \mathbb{R}^{d}$ is the value vector at position $s$, $k_s \in \mathbb{R}^{d}$ is the key vector at position $s$, and the outer product $v_s k_s^\top$ is a $d \times d$ matrix that records the association between key $s$ and value $s$.

The full parallel-form output. The output $o_t$ at position $t$ is computed by having the query $q_t$ read from all active buckets, with each bucket's contribution weighted by the learned coefficient $\lambda_t^{(\ell)}$:

$o_t = \sum_{\ell=0}^{L-1} \lambda_t^{(\ell)} \; q_t^\top S_t^{(\ell)}$

where $q_t \in \mathbb{R}^d$ is the query vector, $S_t^{(\ell)} \in \mathbb{R}^{d \times d}$ is the state for level $\ell$, $\lambda_t^{(\ell)} \geq 0$ is the learned scalar weight, and $L = O(\log t)$ is the number of active levels.

What this computes operationally. The query $q_t$ performs weighted retrieval across multiple memory stores simultaneously. Each store $S_t^{(\ell)}$ has encoded a different segment of the past at a different granularity. The product $q_t^\top S_t^{(\ell)}$ extracts from store $\ell$ a vector of dimension $d$ representing "what value information is relevant to query $q_t$ from the positions in bucket $\ell$." These per-bucket vectors are then weighted by $\lambda_t^{(\ell)}$ and summed. If $\lambda_t^{(3)}$ is large and $\lambda_t^{(1)}$ is small, the query is attending more to coarse, distant summaries than to fine-grained recent tokens.

Why the $\lambda$ coefficients are essential. The paper observes that if all $\lambda_t^{(\ell)}$ are identical (or more generally, if they are linearly related across time—e.g., $\lambda_t^{(1)} = c \cdot \lambda_t^{(2)}$ for some constant $c$), then log-linear attention collapses to standard linear attention. This is because linear attention with a single state $S_t = \sum_{s=0}^{t} v_s k_s^\top$ can be expressed as reading from the hierarchical decomposition with uniform weights: the sum of hierarchical states weighted equally is algebraically equivalent to the single flat state. The distinctiveness of the $\lambda$ values across levels is what breaks this equivalence and gives log-linear attention its additional expressiveness. The model can learn, for example, to ignore the coarse bucket (small $\lambda^{(\ell)}$ for high $\ell$) when the query requires recent detail, or to upweight the coarse bucket when the query requires long-range context.

Parameterization of $\lambda_t^{(\ell)}$. The coefficients are computed as a learned linear function of the input representation at position $t$. Specifically, for each head, a linear layer maps the hidden state $x_t \in \mathbb{R}^{d_{\text{model}}}$ to the per-level weights $\lambda_t^{(0)}, \ldots, \lambda_t^{(L-1)}$. The paper uses a non-negative activation (e.g., softplus or ReLU) to ensure $\lambda_t^{(\ell)} \geq 0$, though the exact activation is not specified in detail. For the language modeling experiments (Section 4.2), this adds less than 3% additional parameters for Mamba-2 (from 802M to 825M) and less than 0.4% for Gated DeltaNet (from 793M to 796M). The computational overhead of computing $\lambda$ is minimal because it involves only a single linear projection per position.

The state update recurrence. The key property that makes decoding efficient is that the Fenwick-tree states can be updated incrementally from one time step to the next without recomputing the entire decomposition. The recurrence is given by:

$S_t^{(\ell)} = \begin{cases} v_t k_t^\top & \text{if } \ell = 0 \\[6pt] 0 & \text{if } 0 < \ell \leq \text{lssb}(t) \\[6pt] \sum_{\ell'=0}^{\ell-1} S_{t-1}^{(\ell')} & \text{if } \ell = \text{lssb}(t) + 1 \\[6pt] S_{t-1}^{(\ell)} & \text{if } \ell > \text{lssb}(t) + 1 \end{cases}$

where $\text{lssb}(t) = \max\{\ell \in \mathbb{N} \mid 2^\ell \text{ divides } t\}$ is the index of the least significant set bit in the binary representation of $t$.

What each case means operationally:

• Level 0 (the sentinel): The new token's own key-value outer product always enters level 0. This is the finest granularity—a bucket of size 1 containing only the current token. Level 0 is "reset" at every time step because it always holds exactly the current token, not an aggregation of multiple tokens.

• Levels $1$ through $\text{lssb}(t)$ (the promotion range): These levels are zeroed out at time $t$. Why? Because the Fenwick-tree structure dictates that at time $t$, buckets at these levels are about to be merged into a coarser bucket. The information that was in these levels at time $t-1$ gets promoted to level $\text{lssb}(t) + 1$. The zeroing-out creates a "blank slate" that will be filled gradually over subsequent time steps as new tokens arrive.

• Level $\text{lssb}(t) + 1$ (the merge target): This level receives the sum of all states from levels 0 through $\text{lssb}(t)$ at the previous time step. This is the promotion operation: multiple fine-grained buckets are merged into a single coarser bucket. After the merge, this level now summarizes a bucket of size $2^{\text{lssb}(t)}$, which is exactly the size prescribed by the Fenwick decomposition.

• Levels $> \text{lssb}(t) + 1$ (unchanged): These coarser levels are unaffected by the addition of a new token. Their bucket compositions do not change, so their states persist from the previous time step.

Example walkthrough for $t = 5, 6, 7$:

• At $t = 5$ (binary 101), $\text{lssb}(5) = 0$. Level 0 gets the new token $v_5 k_5^\top$. Level 1 receives the sum of old level 0 (which held $v_4 k_4^\top$). All higher levels persist. Active levels at this point: 0 (size 1), 1 (size 1, holding position 4), and whatever coarser levels existed from earlier merges.

• At $t = 6$ (binary 110), $\text{lssb}(6) = 1$. Level 0 gets the new token. Levels 1 gets zeroed. Level 2 receives the sum of old levels 0 and 1. Old level 1 held position 4, old level 0 held position 5, so the merged level 2 now holds the sum $v_4 k_4^\top + v_5 k_5^\top$—a bucket of size 2. After the merge, level 0 = $\{v_6 k_6^\top\}$, level 1 = 0 (just reset), level 2 = positions 4–5, and coarser levels persist.

• At $t = 7$ (binary 111), $\text{lssb}(7) = 0$. Level 0 gets the new token. Level 1 receives old level 0 (which held $v_6 k_6^\top$). Level 2 persists (still holds positions 4–5). Active states: level 0 (pos 7), level 1 (pos 6), level 2 (pos 4–5), plus any coarser levels inherited from $t=4$ (e.g., a level 3 holding positions 0–3 from the merge at $t=4$). Total active levels = number of 1-bits in binary representation = $O(\log t)$.

When the hierarchy expands. At powers of two (e.g., $t = 8$), $\text{lssb}(8) = 3$. All lower levels merge into level 3, and a new, previously-nonexistent level is required for the merged result. The total number of levels $L$ grows by one each time $t$ reaches a new power of two, so $L = O(\log T)$ over the full sequence. The paper notes this explicitly: "When $t$ is a power of two the hierarchy expands by one bucket."

Memory and time complexity during decoding. At any time step, exactly $O(\log t)$ states are active (corresponding to the 1-bits in $t$'s binary representation). The update involves (a) writing the new token to level 0 (one outer product, $O(d^2)$), (b) summing at most $O(\log t)$ states for the merge (each sum is a $d \times d$ matrix addition, $O(d^2)$), and (c) reading from all $O(\log t)$ active states (each read is a vector-matrix-vector product, $O(d^2)$). The total memory is $O(\log T \cdot d^2)$ for storing all states, and the per-step time is $O(\log T \cdot d^2)$. This is the central claim: decoding memory and per-step time grow only logarithmically with sequence length, as opposed to constant for linear attention or linear for softmax attention.

---

The Parallel Form and Hierarchical Matrix Decomposition

Reformulating for hardware-efficient training. The recurrent form in Equation 3 is sequential in $t$, which is incompatible with the matmul-centric computation that GPUs and TPUs excel at. To enable parallelization across the sequence length dimension while maintaining the hierarchical structure, the paper rewrites the computation in a parallel matrix form:

$O = \left(Q K^\top \odot M_H\right) V$

where $Q, K, V \in \mathbb{R}^{T \times d}$ are the query, key, and value matrices stacked across all positions, $M_H \in \mathbb{R}^{T \times T}$ is the hierarchical mask defined above, $\odot$ denotes elementwise (Hadamard) product, and $O \in \mathbb{R}^{T \times d}$ is the output for all positions.

What this computes. This is structurally identical to the linear attention parallel form, but with the crucial difference that $M_H$ is not a simple lower-triangular matrix of 1s—it is a hierarchical matrix whose entries depend on the Fenwick-level of each (query, key) pair and the learned $\lambda$ coefficients. For a fixed query row $t$, the non-zero entries of $M_H[t,:]$ are segmented into blocks of sizes 1, 1, 2, 4, 8, ... (the Fenwick bucket sizes), with all entries within each block sharing the same scalar $\lambda_t^{(\ell)}$. The elementwise product $Q K^\top \odot M_H$ scales each attention score $q_t^\top k_s$ by the level-specific weight $\lambda_t^{(\ell(t,s))}$ before aggregating with $V$.

Why this form enables efficient algorithms. The block structure of $M_H$ admits a decomposition that separates intra-chunk interactions (within blocks smaller than the chunk size) from inter-chunk interactions (across chunk boundaries). The key insight (Equation 5) is:

$M_H = D + \sum_{\ell = \ell_C}^{L-1} M^{(\ell)}$

where each term is defined as follows:

• $D \in \mathbb{R}^{T \times T}$ is a block-diagonal matrix with $T/C$ causal blocks of size $C \times C$ along the diagonal. Each block $D^{[k]}$ corresponds to chunk $k$ and captures intra-chunk interactions: $(D^{[k]})_{ts} = \lambda_{kC + t}^{(\ell)} \cdot M_S[kC + t, kC + s]$ for positions within the same chunk (where $M_S$ is the semiseparable mask from the underlying linear attention model—all 1s for vanilla linear attention, or the gated product $\prod \alpha$ for Mamba-2). The level $\ell$ for intra-chunk pairs is whatever level they map to under the Fenwick decomposition.

• $M^{(\ell)} \in \mathbb{R}^{T \times T}$ for $\ell \geq \ell_C$ are inter-chunk matrices, each corresponding to one level of the hierarchy. $\ell_C = \log_2 C + 1$ is the level at which bucket sizes become at least as large as the chunk size. Levels with bucket sizes smaller than $C$ are absorbed into $D$ because their interactions are entirely within individual chunks. Levels $\ell \geq \ell_C$ span multiple chunks and must be handled via cross-chunk state passing.

• Each $M^{(\ell)}$ has block low-rank structure: $M^{(\ell)}[t, s] = \lambda_t^{(\ell)} \cdot M_S[t, s]$ if $s \in B_t^{(\ell)}$ (i.e., if position $s$ belongs to the level-$\ell$ Fenwick bucket for query $t$), and 0 otherwise. Crucially, for a fixed level $\ell$, the non-zero pattern forms a sequentially semiseparable (SSS) structure because within each level, the attention pattern reduces to the same SSS form as the underlying linear attention model, just restricted to the specific bucket boundaries. This means that existing efficient primitives for SSS matrix multiplication (such as those used in Mamba-2 or Gated DeltaNet) can be applied to each $M^{(\ell)}$ independently.

What this decomposition achieves. The original hierarchical matrix $M_H$, which looks complex and irregular, is factored into:

• One block-diagonal matrix $D$ that is trivially parallelizable (each chunk computed independently), costing $O(T C)$ total since each $C \times C$ block takes $O(C^2)$ and there are $T/C$ blocks.
• $L - \ell_C = O(\log(T/C))$ inter-chunk matrices $M^{(\ell)}$, each of which has SSS structure and can be multiplied using the same primitive that the underlying linear attention model uses. Each such multiplication costs $O(T)$, and there are $O(\log T)$ levels, giving $O(T \log T)$ total for the inter-chunk stage.

The total training complexity is $O(T C) + O(T \log T) = O(T \log T)$ (assuming $C$ is a constant, typically 64 or 128). This is the log-linear complexity that gives the framework its name.

Why this is more efficient than naively computing the full $QK^\top \odot M_H$ matrix. The full attention matrix is $T \times T$, which would be $O(T^2)$ to materialize. The decomposition avoids materialization entirely: the intra-chunk blocks are small ($C \times C$) and computed on-the-fly in SRAM; the inter-chunk components are never materialized as dense matrices—they are processed through state-passing primitives that maintain only an $O(d \times d)$ hidden state per chunk per level. This is the same trick that makes linear attention efficient, but applied recursively across hierarchical levels.

Relationship to the quasilinear H-matrix interpretation. Appendix B provides the formal connection: $M_H$ is a quasi-H matrix, meaning it belongs to an intermediate class between general HODLR matrices (which store off-diagonal blocks as arbitrary low-rank factorizations requiring $O(T \log T)$ memory) and HSS matrices (which exploit linear dependencies across levels to compress to $O(T)$ memory). Specifically, in the quasi-H case, only one of the two factor matrices in the low-rank representation satisfies nesting across levels, while the other does not. This asymmetry is what enables $O(\log T)$ recurrence (unlike general HODLR, where no efficient recurrence is known) while still requiring $O(T \log T)$ training (unlike HSS/SSS, which is $O(T)$). The quasi-H structure is not an arbitrary middle ground—it is specifically the property that the $\lambda_t^{(\ell)}$ weights can vary independently across levels (no nesting) while the temporal decay structure ($M_S$) remains nested.

---

The Chunkwise Parallel Training Algorithm

Algorithm overview. The training algorithm (Algorithm 1 in the paper) processes a sequence of length $T$ in three stages, mirroring the decomposition in Equation 5:

Stage 1: Intra-chunk computation (level $\ell < \ell_C$). The sequence is divided into $T/C$ chunks of size $C$. For each chunk $k$, the $C \times C$ intra-chunk attention is computed densely (or using whatever efficient method the underlying model uses for short sequences). In the notation of the algorithm:

$Y^{[k]} = \left(Q^{[k]} (K^{[k]})^\top \odot M_H^{[k]}\right) V^{[k]}$

where $Q^{[k]}, K^{[k]}, V^{[k]} \in \mathbb{R}^{C \times d}$ are the query, key, and value matrices restricted to chunk $k$, and $M_H^{[k]} \in \mathbb{R}^{C \times C}$ is the $k$-th diagonal block of $M_H$, restricted to intra-chunk position pairs.

What happens computationally. This is a dense $C \times C$ attention computation per chunk, costing $O(C^2 d)$ per chunk. Since there are $T/C$ chunks, the total cost is $O(T C d)$. With $C = 64$ (the paper's default chunk size), this is $O(64 T d)$, which is linear in $T$ with a modest constant. The small chunk size means this computation fits in SRAM and is highly parallelizable across chunks. Importantly, $M_H^{[k]}$ is not a uniform matrix—it incorporates the Fenwick-level weights $\lambda_t^{(\ell)}$ for intra-chunk position pairs, which are absorbed into the computation.

Stage 2: Initialize inter-chunk states. For each chunk $k$ and each hierarchical level $\ell \geq \ell_C$, an initial chunk state is computed that summarizes the chunk's key-value pairs, appropriately decayed for the underlying gating mechanism:

$S_k^{(\ell)} = \sum_{s \in \text{chunk } k} \left(\prod_{t = s+1}^{\text{end of chunk}} \alpha_t \right) v_s k_s^\top$

where $\alpha_t$ is the per-position forget gate (from Mamba-2's formulation; for vanilla linear attention, $\alpha_t = 1$) and the product term propagates the decay from each token's position to the chunk boundary. This state captures the chunk's total contribution, weighted by how much it should decay before being passed to subsequent chunks.

What this enables. The inter-chunk state $S_k^{(\ell)}$ is a compact summary of chunk $k$ that can be passed to subsequent chunks without reprocessing the individual tokens. This is the standard chunkwise parallel pattern in linear attention: rather than recurrently processing all $T$ tokens one by one, we process chunks in parallel and exchange only the chunk-level state summaries. The novelty in log-linear attention is that we maintain separate state summaries per hierarchical level, because different levels have different temporal extent and different bucket boundaries.

Stage 3: Inter-chunk computation (levels $\ell \geq \ell_C$). For each hierarchical level $\ell$, a sequential scan is performed across chunks, where each chunk $k$ receives the state accumulated from all prior chunks that fall within the same Fenwick bucket at level $\ell$. The scan is expressed as:

$Y^{[k]} \mathrel{+}= \text{mask}^{(\ell)}_{\text{query}} \left( \Lambda_k^{(\ell)} \odot Q^{[k]} \, \text{State}_{<k}^{(\ell)} \right)$

$\text{State}_{k}^{(\ell)} = \text{mask}^{(\ell)}_{\text{decay}} \left( A_k^{(\ell)} \; \text{State}_{<k}^{(\ell)} \right) + \text{mask}^{(\ell)}_{\text{key}} \left( S_k^{(\ell)} \right)$

where $\text{State}_{<k}^{(\ell)}$ is the accumulated state from chunks before $k$ at level $\ell$, $A_k^{(\ell)}$ is a chunk-level decay factor, $S_k^{(\ell)}$ is the current chunk's initial state, $\Lambda_k^{(\ell)}$ are the per-chunk $\lambda$ weights, and $\text{mask}^{(\ell)}_{\text{query}}$, $\text{mask}^{(\ell)}_{\text{decay}}$, $\text{mask}^{(\ell)}_{\text{key}}$ are level-specific masking patterns that restrict the computation to only those chunk pairs that are actually connected at level $\ell$ in the Fenwick decomposition.

What the masks do. At level $\ell$, not every chunk is connected to every prior chunk. The Fenwick decomposition dictates that each query chunk $k$ can only attend to specific prior chunks as part of its level-$\ell$ bucket. For example, at level $\ell$ corresponding to bucket size $2^{\ell-1}$, a query at chunk $k$ might only include chunks $k - 2^{\ell-1}/C$ through $k - 1$ in its level-$\ell$ bucket—not all prior chunks. The masks enforce these sparsity patterns, ensuring that the scan does not inadvertently aggregate information from chunks that should not be part of the level-$\ell$ summary. The paper states that these inter-chunk dependencies are computed using "only $\text{O}(\log \frac{T}{C})$ primitive calls," where each primitive call is a scan over all $T/C$ chunks, costing $O(T)$ time.

Why this is a parallel scan rather than recurrent. The sequential scan across chunks is implemented using standard parallel prefix-sum (scan) algorithms (e.g., Blelloch scan; Blelloch, 1990). A scan takes an associative binary operator $\oplus$ and a sequence $x_1, \ldots, x_n$, and computes all prefix sums $x_1, x_1 \oplus x_2, x_1 \oplus x_2 \oplus x_3, \ldots$ in $O(\log n)$ parallel steps with $O(n)$ total work. The associative operator here is the state transition: $\text{State}_{i} = A_i \cdot \text{State}_{i-1} + S_i$. Because matrix multiplication and addition are associative, the scan can be parallelized across chunks while maintaining the correct sequential semantics. This is exactly the same technique used in Mamba-2 and Gated DeltaNet for their chunkwise training, but now executed $O(\log T)$ times—once per hierarchical level.

Complexity breakdown. For a sequence of length $T$ with chunk size $C$:

• Intra-chunk: $\frac{T}{C} \times O(C^2 d) = O(T C d)$.
• Inter-chunk: $O(\log \frac{T}{C})$ levels $\times O(\frac{T}{C})$ chunks $\times O(d^2)$ per chunk state = $O(T \log T \cdot d^2)$ (with appropriate constants).
• Total: $O(T \log T \cdot d^2)$, which is log-linear in $T$ as claimed.

Optimizations in the Triton implementation (Section 3.5). A naive implementation that calls the existing Mamba-2 primitive separately for each of the $O(\log T)$ levels would incur significant overhead from redundant memory access (loading the same $Q, K, V$ matrices multiple times) and kernel launch latency. The paper implements several optimizations:

• Level fusion: Multiple hierarchical levels are fused into a single Triton kernel. The paper found that fusing four levels at a time is optimal given SRAM constraints on an H100 GPU, balancing the benefit of reduced kernel launches against the cost of increased register pressure and shared memory usage per thread block.

• Backpropagation optimization: Rather than computing gradients for each level independently (which would require storing intermediate states for all levels, consuming $O(\log T)$ times the memory), the gradients $\nabla K$ and $\nabla V$ are computed by analytically factoring their dependencies across levels. This reduces kernel count and memory usage, achieving "over 3× speedup compared to the naive multi-level version."

• Redundant work elimination: At level $\ell$, the matrix $M^{(\ell)}$ contains $\frac{T}{2^{\ell-1} C}$ chunks of size $2^{\ell-1} C$. The paper notes that "redundant work can be avoided, reducing cost by a constant factor of two," referring to the fact that the state at the boundary of each super-chunk can be computed once and reused.

Figure 3 (right) visualizes this decomposition. The left subfigure shows the decomposition of $M_H$ into block-diagonal (level 0) and block-low-rank (levels 1, 2, 3) components. The right subfigure shows the algorithmic flow: Level 0 handles intra-chunk computation directly (dense within each chunk), while levels 1 and above invoke inter-chunk primitives that propagate states across chunk boundaries, with each level having its own sparsity pattern determined by the Fenwick decomposition.

---

Instantiating Log-Linear Mamba-2 and Log-Linear Gated DeltaNet

The composition principle. The log-linear framework does not replace the underlying linear attention mechanism—it composes with it. Given an existing architecture with semiseparable mask $M_S$ and attention-like matrix $A$, the log-linear variant simply uses the elementwise product of masks:

$M = M_S \odot M_H$

where $M_S$ is the original sequentially semiseparable mask (from Mamba-2's gating or Gated DeltaNet's structured transitions) and $M_H$ is the Fenwick-tree hierarchical mask.

Why elementwise product works. The product of an SSS matrix and an H matrix remains an H matrix (Appendix B notes this property). This means the resulting mask $M$ retains the hierarchical structure needed for efficient training and decoding, while inheriting the gating/transition mechanisms of the base model. The two masks serve complementary roles: $M_S$ controls temporal decay (how quickly past information is forgotten), while $M_H$ controls the granularity at which the past is accessed (whether tokens are accessed individually or in coarsened groups).

Log-Linear Mamba-2. Mamba-2's parallel form is $O = (Q K^\top \odot M_S) V$ where $M_S[t, s] = \prod_{k=s+1}^{t} \alpha_k$ for $s \leq t$ (and 0 otherwise), with $\alpha_k \in (0, 1)$ being data-dependent forget gates. Log-Linear Mamba-2 simply uses:

$O = \left(Q K^\top \odot M_S \odot M_H\right) V$

What changes. The original Mamba-2 computes attention scores as $q_t^\top k_s \cdot \prod_{k=s+1}^t \alpha_k$, where the product of $\alpha$ gates decays the influence of distant tokens. Log-Linear Mamba-2 computes attention scores as $q_t^\top k_s \cdot (\prod_{k=s+1}^t \alpha_k) \cdot \lambda_t^{(\ell(t,s))}$, where the additional $\lambda$ term can upweight or downweight entire temporal buckets. This means the model can learn to override the uniform exponential decay with level-specific adjustments—for example, keeping a coarse summary of very distant tokens accessible even though the per-token $\alpha$ gates would have decayed them to near zero.

Recurrent form of Log-Linear Mamba-2. At inference time, each level-$\ell$ state evolves as:

$S_t^{(\ell)} = \alpha_t S_{t-1}^{(\ell)} + v_t k_t^\top \quad \text{(when the state is active)}$

with the same merge-and-promote logic from the Fenwick recurrence determining which states are active, zeroed, or merged at each step. The $\alpha_t$ gate is shared across all levels—there is a single forget gate per position that applies uniformly to all active states at that position. The level-specific differentiation comes entirely from the readout weights $\lambda_t^{(\ell)}$, not from level-specific gating dynamics.

Log-Linear Gated DeltaNet. Gated DeltaNet has a more complex parallel form:

$O = \left(\left(Q K^\top \odot L\right) \left(I + K K^\top \odot (L - I)\right)^{-1} \odot M_S \odot M_H\right) V$

where $L$ is a lower-triangular matrix of 1s, $I$ is the identity matrix, and the term $(Q K^\top \odot L)(I + K K^\top \odot (L - I))^{-1}$ is the parallel form of the delta-rule computation derived in Yang et al. (2024b). The inverse term captures the Householder-based structured transition: the attention matrix $A$ is not simply $Q K^\top$ but incorporates the Sherman-Morrison-style inversion that gives DeltaNet its ability to "remove" previously stored key-value associations.

What the delta rule adds. In Gated DeltaNet, the recurrent state update is $S_t = \alpha_t S_{t-1}(I - k_t k_t^\top) + v_t k_t^\top$. The $(I - k_t k_t^\top)$ term means that when a new key $k_t$ arrives, the model not only adds the association $v_t k_t^\top$ but also attenuates any previous associations that are aligned with $k_t$. This is a form of memory management: if a new key is similar to an old key, the old association is partially erased to make room for the new one. This mechanism has been shown to improve state-tracking and associative recall compared to simple additive updates (Schlag et al., 2021; Yang et al., 2024b; Merrill et al., 2024).

Log-Linear Gated DeltaNet in recurrent form. At inference time, each level-$\ell$ state evolves as:

$S_t^{(\ell)} = \alpha_t S_{t-1}^{(\ell)}(I - \beta_t k_t k_t^\top) + v_t k_t^\top$

where $\beta_t$ is the data-dependent learning rate of the delta rule (set to 1 in the paper's simplified notation, but typically in $(0, 1)$ or $(0, 2)$ in practice). The merge-and-promote logic is identical to the Mamba-2 case—only the per-level state update differs.

Generality of the framework. The paper emphasizes that these two case studies are not exhaustive. Any linear attention model that admits an efficient chunkwise-parallel primitive can be upgraded to a log-linear variant by composing its temporal mask with $M_H$. The key requirement is that the base model has an SSS or SSS-like structure that can be processed by the chunkwise scan primitives. Models like xLSTM (Beck et al., 2024), MesaNet (Von Oswald et al., 2023), and RWKV (Peng et al., 2024) are explicitly mentioned as candidates (Section 5 and 6). The composition is straightforward: take the model's existing parallel form, and elementwise-multiply its mask by $M_H$. The implementation effort is in adapting the chunkwise training code to handle the additional hierarchical levels, which is the main engineering contribution of the paper's Triton kernels.

Table 5 in the appendix summarizes the structural differences. Mamba-2 uses a "Scaled Identity" hidden-size structure (the state-transition matrix is a scalar times identity), while Gated DeltaNet uses "Identity plus Low-Rank" (the transition includes the $I - \beta k k^\top$ term). Log-Linear variants inherit these hidden-size structures but replace the temporal structure from "Semiseparable" to "Hierarchical." The insight is that temporal structure and hidden-size structure are orthogonal design axes—the hierarchical temporal structure composes cleanly with any hidden-size parameterization.

---

Practical Implementation and Wallclock Performance

Triton kernel design (Section 3.5, Appendix C). The paper provides a reference PyTorch implementation of log-linear attention (Algorithm 1 in Appendix C), which serves as both documentation and a functional reference. The key implementation decisions are:

• Chunk size $C$: Set to 64 for the H100 benchmarks. This balances intra-chunk work (which is quadratic in $C$) against inter-chunk parallelism (more chunks = more parallel scan stages).

• Level fusion: The forward pass fuses four hierarchical levels into a single Triton kernel to reduce kernel launch overhead. The paper states this was empirically optimal on H100 hardware, constrained by SRAM capacity. Fusing more levels would exceed SRAM (requiring spills to HBM, which negates the fusion benefit), while fusing fewer levels leaves kernel launch overhead on the table.

• Backward pass optimization: Gradients for $K$ and $V$ are computed jointly across all levels by analytically factoring the dependencies, rather than computing separate gradients per level and summing. This avoids materializing per-level intermediate states, reducing memory by a factor of $O(\log T)$ in the backward pass. The paper reports a "3× speedup compared to the naive multi-level version."

• Redundancy elimination: Within each level $\ell$, there are symmetric redundancies in the state-passing pattern that allow a factor-of-two reduction in operations. The paper references this briefly (Section 3.3): "Redundant work can be avoided, reducing cost by a constant factor of two."

Throughput benchmarks (Figure 4). The paper benchmarks training throughput on an H100 GPU with batch size 2, 48 heads, head dimension 64, state dimension 128, and chunk size 64. At sequence length 16K:

• Log-Linear Mamba-2 custom kernel achieves approximately 20K tokens/second (from the graph), compared to roughly 22K for standard Mamba-2 and roughly 14K for FlashAttention-2.
• The naive implementation (repeated Mamba-2 primitive calls without fusion) is substantially slower—roughly 7K tokens/second at 16K, highlighting the importance of the fused kernel design.
• At sequence length 131K, all three methods experience a throughput drop due to gradient checkpointing (trading compute for memory). Log-Linear Mamba-2 maintains a competitive throughput relative to the baselines.

Kernel runtime (Figure 4, right). The forward+backward kernel runtime for Log-Linear Mamba-2 (custom) grows roughly linearly with a slight upward curvature, crossing FlashAttention-2 at around 8K sequence length. At 65K, the custom kernel takes roughly 7ms versus roughly 12ms for FlashAttention-2. The naive implementation shows a steeper growth curve, confirming that the fusion optimizations are essential for practical performance.

Model-level throughput. The paper notes that Log-Linear Mamba-2 with MLP layers surpasses Transformer throughput at 32K sequence length, despite having additional layers (depthwise convolutions) that the Transformer lacks. This is an apples-to-oranges comparison (different model architectures), but it demonstrates that the log-linear attention kernel is not a bottleneck relative to other model components at realistic training sequence lengths.

Comparison to other approaches. The paper provides a helpful structural comparison in Table 1 of the main paper: Long-convolution models like Multi-Hyena achieve $O(T \log T)$ training via FFT but have $O(T)$ decoding memory; RetNet/Mamba-2 achieve $O(T)$ training and $O(1)$ decoding but have the fixed-state limitation; Log-Linear models achieve $O(T \log T)$ training and $O(\log T)$ decoding, occupying the previously empty niche. The $2\times$ gap in throughput relative to Mamba-2 at 16K (roughly 20K vs. 22K tokens/sec) is the practical price of this additional expressiveness.

---

Summary of Design Choices and Their Justifications

• Fenwick-tree partition over other hierarchical schemes: chosen because it simultaneously provides (a) logarithmic number of buckets, (b) efficient incremental update from one time step to the next (the recurrence in Section 3.2), and (c) exponentially growing bucket sizes. Alternative dyadic tree partitions lack property (b); arbitrary $k$-ary trees would break the merge-and-promote pattern that keeps per-step decoding $O(\log T)$. The connection to the lssb function makes the recurrence implementable with simple bitwise operations.

• Quasi-H matrix structure over fully general H matrices: chose the asymmetric nesting property (only the temporal decay satisfies nesting across levels, while $\lambda$ weights do not) because general H matrices do not admit a known $O(\log T)$ recurrent formulation. The paper explicitly states that "initial attempts involved using fully Hierarchical matrices, but we were unable to derive a recurrent formulation with O(log T) complexity" (Appendix B.3). The quasi-H restriction is the structural compromise that makes decoding efficient.

• Scalar $\lambda^{(\ell)}$ weights rather than vector-valued or matrix-valued level coefficients: scalar weights ensure that within a Fenwick bucket, the attention pattern reduces to a scaled version of the underlying SSS structure, which is what enables decomposition into per-level SSS components (Equation 5). If $\lambda$ were matrix-valued, the inter-chunk components would no longer be SSS and would require more expensive general hierarchical matrix multiplication. The scalar choice is the minimum expressiveness needed to differentiate levels without breaking the SSS property.

• Chunkwise parallelism over token-level parallelism or fully recurrent execution: the chunkwise approach (chunk size $C = 64$) balances the intra-chunk dense computation (exploiting matmul parallelism) against inter-chunk state passing (avoiding the memory-bandwidth bottleneck of token-level scans). The alternative of a token-level parallel scan (as in Yang et al., 2023) would suffer from limited arithmetic intensity because each step processes only a single token's state update. The alternative of fully recurrent execution would be serial in $T$, wasting GPU parallelism. Chunkwise is the standard approach in the linear attention literature (Sun et al., 2023; Dao & Gu, 2024) and extends naturally to the hierarchical case.

• Level fusion of exactly 4 levels in the Triton kernel: an empirical optimization based on H100 SRAM constraints. Fusing more levels would increase the working set per thread block beyond the 228KB SRAM capacity per SM, causing spills to HBM. Fusing fewer levels increases kernel launch count. The optimal number depends on head dimension, state dimension, and chunk size—the paper's choice of 4 is specific to their benchmark configuration.

• Weak admissibility over strong admissibility in the H-matrix structure (Appendix B.4): weakly admissible H matrices (where off-diagonal blocks are only those at the same level in a perfectly balanced binary tree) have roughly half the active levels of strongly admissible variants (which allow cross-level interactions). The paper found that strong admissibility caused up to 4× slowdown with only marginal accuracy improvements, so they adopted the weakly admissible structure throughout.

• Separate training of the $\lambda$ parameterization rather than deriving $\lambda$ from attention scores: the $\lambda$ coefficients are computed from the hidden state via a linear projection, not from the attention scores $Q K^\top$ themselves. This separation means the level-weighting decision is made based on the input context, not on the specific query-key compatibility. This is a design choice that reflects the inductive bias that temporal granularity preferences should depend on "what am I looking at now" rather than "how well do I match this specific key"—the former is a property of the query's information need, the latter is a property of content-based attention. Computing $\lambda$ from attention scores would conflate these two signals.

4. Key Insights and Innovations

Innovation 1: A Unified Structural Taxonomy of Efficient Attention That Reveals an Unexplored Middle Ground

The paper's most conceptually distinctive contribution is not any single method but rather the unified structured-matrix lens introduced in Section 2 (Equation 1: O = (A ⊙ M) V) and summarized in Table 1. This framing makes visible something that was previously obscured: the computational and memory costs of every efficient attention mechanism are determined entirely by the structure imposed on the masking matrix M, not by the removal of softmax. The field had previously treated linear attention, state-space models, gated RNNs, and long convolutions as fundamentally different architectural families. By showing that they all share the same algebraic form and differ only in whether M is semiseparable, Toeplitz, or hierarchical, the paper creates a common language for discussing what was previously a fragmented design space.

This is significant because it transforms the conversation about efficient attention from "which model family should I use?" to "what structure of M gives the right tradeoff for my deployment constraints?" Before this reframing, the field implicitly assumed that the expressiveness-efficiency tradeoff was binary: you either accepted the fixed-state bottleneck of linear attention (O(T) training, O(1) decoding) or you paid the quadratic cost of full attention. The taxonomy reveals that this is false—there is a rich spectrum of possible M structures between "fully unstructured" (softmax attention) and "maximally structured" (semiseparable). The paper's identification that no existing architecture occupied the O(T log T) training, O(log T) decoding point on this spectrum is a direct consequence of the taxonomy, not an empirical accident. The taxonomy predicted that such a point should be achievable—log-linear attention is the concrete realization.

This reframing parallels the contribution of the Chinchilla scaling laws (Hoffmann et al., 2022) in a different domain: just as Chinchilla didn't invent a new training algorithm but rather provided the conceptual framework that made optimal compute allocation legible, this paper's taxonomy doesn't invent the idea of efficient attention but rather provides the framework that makes the structured-matrix design space legible as a single continuum. The long-term impact is that future work can reason about where a proposed architecture sits on this continuum, what its asymptotic properties are, and what structural ingredient (semiseparable vs. HODLR vs. Toeplitz) it would take to move to a different point.

Innovation 2: The Quasi-H Matrix as the Structural Primitive That Enables Logarithmic Decoding

The paper's key technical insight—and the one that distinguishes it from prior hierarchical attention work—is that logarithmic decoding memory requires a specific matrix structure sitting between general HODLR and semiseparable, which the paper terms a quasi-H matrix (Appendix B.3). This is not a matrix class that was previously studied for sequence modeling, and the paper's identification of its algorithmic properties constitutes a genuine structural advance.

The insight works as follows. General HODLR (Hierarchically Off-Diagonal Low-Rank) matrices store off-diagonal blocks as arbitrary low-rank factorizations at each hierarchical level. This gives them O(T log T) storage and matrix-vector multiplication but no known recurrent formulation with sublinear memory—the factor matrices at each level are independent, so there is no way to incrementally update the representation as new tokens arrive without storing or recomputing the full factorization. The paper's initial attempts to use fully general HODLR matrices for attention "were unable to derive a recurrent formulation with O(log T) complexity" (Appendix B.3). At the other extreme, HSS (Hierarchically Semiseparable) matrices require that the low-rank basis matrices U(ℓ) and V(ℓ) satisfy linear nesting relationships across levels—this constraint is what enables O(T) storage and O(1) recurrence, but it also collapses the hierarchical structure back to something essentially equivalent to semiseparable.

The quasi-H matrix is defined by an asymmetric nesting property: only one of the two basis sequences satisfies nesting across levels, while the other does not. In log-linear attention, the temporal decay structure (the MS mask from the underlying model, which captures per-token forgetting via ∏ α_k) satisfies nesting—the decay from position s to position t is the same regardless of which Fenwick bucket contains s. But the level-weighting coefficients λ(ℓ) explicitly do not satisfy nesting—the model can assign independent weights to each hierarchical level. This asymmetry is what makes logarithmic decoding possible: the nested part (temporal decay) can be maintained incrementally in the standard recurrent form, while the non-nested part (level weights) applies only at readout time and doesn't need to be stored in the recurrent state. The result is that the recurrent state grows as O(log T) (one matrix per active level) rather than O(T) (which would be required to store independent factor matrices at each level).

This is a fundamental structural advance because it identifies the precise algebraic property that enables the sweet spot. Prior work on hierarchical attention (Zhu & Soricut, 2021; Zeng et al., 2022) used general hierarchical matrices and achieved O(T log T) training but O(T) decoding memory—exactly because they lacked this asymmetric nesting insight. The quasi-H structure is not an arbitrary compromise; it is the provably minimal relaxation of semiseparability that enables multi-scale readout while preserving efficient recurrence. This insight is likely to have implications beyond this paper, potentially enabling new hierarchical variants of other recurrent architectures (xLSTM, RWKV, MesaNet) that the paper flags as future work.

Innovation 3: The Fenwick Tree as the Uniquely Suitable Partitioning Scheme for Incremental Hierarchical State Maintenance

While the general idea of hierarchical partitioning for attention is not new (Zhu & Soricut, 2021; Ye et al., 2019; Li et al., 2019), the paper's choice of the Fenwick tree (binary indexed tree) as the specific partitioning scheme is a non-obvious design decision with significant algorithmic consequences. The Fenwick tree is not the same as an arbitrary dyadic tree or a balanced binary partition—it has the specific property that the bucket assignment at time t can be computed from the bucket assignment at time t-1 through a simple set of merge-and-promote operations determined by the least significant set bit of t. This property is what makes the recurrence in Section 3.2 (the four-case state update rule) correct and efficient.

The significance of this choice becomes clear when contrasted with alternatives. A naive hierarchical partition—say, dividing the prefix into fixed chunks of exponentially increasing size regardless of the query position—would require recomputing bucket boundaries at every time step, costing O(log T) work just to determine which tokens belong to which bucket. The Fenwick tree's lssb-based update means that the transition from t-1 to t requires only O(1) bucket boundary changes (the levels ≤ lssb(t) get zeroed, level lssb(t)+1 receives the merge, all others persist). This is what keeps the per-step decoding time genuinely O(log T) rather than O(log^2 T) or worse.

This choice also has a representational consequence: the Fenwick tree induces a specific pattern of bucket sizes (powers of two) and a specific temporal alignment (buckets are aligned to binary boundaries). This means that whether a token ends up in a fine-grained or coarse-grained bucket depends not just on its temporal distance from the query but also on its absolute position modulo powers of two. Two tokens at the same distance from the query could end up in different buckets if they fall on different sides of a binary boundary. This is not obviously an optimal inductive bias—it introduces a positional artifact that the model must learn to compensate for—but it is the price of the efficient recurrence. The paper's empirical results suggest that this artifact does not prevent the model from outperforming linear attention on long-range tasks (as seen in the Needle-in-a-Haystack and per-position loss evaluations), but it remains an underexplored design dimension. Whether alternative partitioning schemes (e.g., based on learnable rather than fixed boundaries) could achieve similar efficiency with better inductive bias is an open question.

Innovation 4: Learnable Level-Weighting as the Mechanism That Prevents Collapse to Linear Attention

The paper makes an observation that is subtle but conceptually critical: log-linear attention with uniform or linearly related λ(ℓ) values collapses algebraically to standard linear attention (Section 3.1). This means that the entire expressiveness gain of the hierarchical structure depends on the model's ability to assign qualitatively different weights to different temporal granularities at different query positions. If all levels were weighted equally, the sum over hierarchical states would be mathematically identical to a single flat state—the hierarchical decomposition would be a no-op.

This is significant because it identifies the λ(ℓ) coefficients not as a minor add-on but as the locus of expressiveness in the framework. The Fenwick-tree structure and the multi-scale states provide the capacity to represent the past at multiple granularities, but the λ weights provide the selectivity that makes that capacity useful. Without learnable, level-varying weights, the model would be strictly equivalent to a linear attention model with a fixed-size state—all the engineering complexity of the hierarchical training and decoding algorithms would yield zero representational benefit.

This insight has implications for how the framework should be extended. The paper parameterizes λ(ℓ) as a linear function of the input (one projection per head, adding <3% parameters), which means the level-weighting is content-dependent—the model can decide, based on the current token, whether it needs fine-grained recent history or coarse-grained distant history. This is a sensible inductive bias: a query that seeks a specific factual detail (e.g., "What was the patient's temperature at admission?") might upweight fine-grained recent buckets where that detail likely resides, while a query that seeks a broad summary (e.g., "What was the overall trend?") might upweight coarser buckets. However, the paper does not ablate whether this content-dependence is actually necessary versus simply assigning fixed learned weights per level (which would have even fewer parameters and no per-token computation). This is a notable gap—if fixed per-level weights were sufficient, the mechanism would be substantially simpler and the contribution would be more about the hierarchical state structure than about adaptive readout.

The λ mechanism also creates an interesting asymmetry with the base model's gating: in Log-Linear Mamba-2, the forget gates α_t apply uniformly to all levels (there is one gate per position shared across all active states), while the λ(ℓ) apply per-level at readout time. This means that information is stored uniformly (same forgetting dynamics for all levels) but retrieved selectively (different emphasis per level). An alternative design could have level-specific gating, where coarse buckets decay differently from fine-grained ones. The paper does not explore this dimension, leaving open the question of whether asymmetric storage and retrieval is the right decomposition or merely a convenient one given the existing chunkwise primitives.

Innovation 5: Empirical Evidence That Logarithmic State Growth Provides Meaningful Gains on Long-Range Tasks Without Sacrificing Short-Range Performance

While the structural innovations above are conceptual, the paper also provides a valuable empirical calibration of what logarithmic state growth actually buys you in practice. The key result is not that log-linear attention beats all alternatives on all metrics—it doesn't, and the paper is transparent about this—but rather that it provides consistent improvements over linear attention specifically on tasks that stress the fixed-state bottleneck, while maintaining competitive performance on short-range tasks.

The most diagnostic evidence comes from the Needle-in-a-Haystack experiments (Table 4). On the single-needle pass-key retrieval task at 8K context (S-NIAH-1), Log-Linear Mamba-2 achieves 99.8% accuracy compared to 56.8% for standard Mamba-2—a 43 percentage point improvement. This is a task that directly probes the fixed-state limitation: a single key-value pair is hidden among thousands of distractor tokens, and the model must retrieve the value when queried with the key. Linear attention's fixed-size state inevitably blends the needle with the haystack, while log-linear attention's fine-grained buckets can preserve the needle's distinct representation. At 16K, the gap narrows (72.4% vs. 21.6%) but remains substantial. On the more challenging multi-key retrieval (MK-NIAH-1), Log-Linear Mamba-2 improves from 18.6% to 39.8% at 8K. These are precisely the tasks where theory predicts logarithmic state growth should help, and the magnitude of improvement is large enough to be operationally meaningful.

Critically, these gains do not come at the cost of degraded short-range performance. On WikiText perplexity (Table 3), Log-Linear Gated DeltaNet improves from 21.73 to 21.45, and on zero-shot commonsense reasoning, the average improves from 45.0 to 45.6. These are short-context benchmarks where the hierarchical structure should provide no benefit, and indeed the improvements are modest—but importantly, they are not negative. The framework does not introduce a short-range inefficiency that must be paid for the long-range gains. This is a non-trivial property: many architectural modifications that improve long-range modeling (e.g., adding more layers, increasing state dimensionality within a fixed-size budget) come with tradeoffs that hurt short-range performance. Log-linear attention appears to be a relatively Pareto-improving change over linear attention, at least at the scales tested (~800M parameters, 50B tokens).

The per-position loss analysis (Figure 5) provides additional nuance. Log-Linear Gated DeltaNet's loss curve tracks the layer-matched Transformer from position 0 through roughly 6K, then maintains a consistent gap of about 0.02 nats thereafter. This suggests that the hierarchical state provides the most benefit at intermediate-to-long ranges (4K–16K tokens), which is exactly where the fixed-state bottleneck starts to bite. The fact that the parameter-matched Transformer (24 layers, 778M vs. Log-Linear Gated DeltaNet's 21 layers, 796M) pulls ahead across all positions suggests that depth still provides benefits that the hierarchical state doesn't fully capture—but the comparison is not fully controlled for architecture (different numbers of layers, different parameter counts in the attention vs. MLP components).

A notable negative result is the MQAR synthetic benchmark (Table 2), where log-linear attention provides only modest improvements over the base models. Log-Linear Mamba-2 improves from 46.9% to 55.9% at dimension 16, but the gains shrink at higher dimensions (75.1% → 76.5% at dim 32, 89.6% → 92.9% at dim 64). Log-Linear Gated DeltaNet shows a similar pattern (38.4 → 40.0 at dim 16, 79.0 → 84.4 at dim 32, and both reach ≥99% at dim 64). This is somewhat surprising given that MQAR is the benchmark most directly motivated by the fixed-state bottleneck, and it suggests that logarithmic state growth is helpful but not sufficient to fully close the gap with softmax attention on pure associative recall. The Transformer achieves ≥99% across all dimensions with only 16 dimensions—the log-linear variants need 64 dimensions to match this, and they still require the Transformer-scale dimension rather than achieving efficiency gains. This result tempers the narrative: while log-linear attention improves recall over linear attention, it does not match the fine-grained access that softmax attention provides, at least at the model sizes and training budgets tested.

Taken together, these empirical results establish log-linear attention as a meaningful but not transformative improvement over linear attention on long-range tasks. The framework's primary contribution remains conceptual—the identification of the quasi-H matrix structural primitive and the demonstration that hierarchical temporal structure can be integrated into existing linear attention architectures without breaking their efficient training and decoding properties—rather than a claim of state-of-the-art performance.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper uses multiple evaluation benchmarks: (1) the MATH benchmark (Hendrycks et al., 2021) for synthetic associative recall experiments (MQAR, Section 4.1); (2) the Long-Data-Collections dataset (50B tokens) for language modeling pretraining with a sequence length of 16K (Section 4.2); (3) WikiText for perplexity evaluation; (4) the RULER benchmark (Hsieh et al., 2024) for Needle-in-a-Haystack (NIAH) experiments spanning three single-needle and three multi-needle tasks at context lengths of 4K, 8K, and 16K (Section 4.2, Table 4); (5) several zero-shot commonsense reasoning benchmarks (LAMBADA, PIQA, HellaSwag, WinoGrande, ARC-easy, ARC-challenge) for short-context evaluation; and (6) LongBench (Bai et al., 2023) and the in-context retrieval benchmark (Arora et al., 2023) for additional long-context assessments (discussed in the appendix). For the MQAR experiments, models are trained and evaluated on 256-token sequences containing 4 to 64 key-value pairs, following the setup of Arora et al. (2024), without length generalization evaluation. For per-position loss analysis, the paper uses 39M tokens from the Book-3 dataset.

• Base model(s). All experiments use custom-trained models rather than existing pretrained checkpoints. For MQAR, small-scale models are trained from scratch with tuned learning rates; Mamba-2 variants use state and head dimensions of 16, while Gated DeltaNet variants use 2 attention heads by default (1 head for dimension 16). For language modeling, the paper trains three families from scratch on 50B tokens: a Transformer baseline with 21 layers, hidden size 1536, 16 attention heads, and a RoPE base of 500K (693M parameters); a modified Mamba-2 with 48 heads and MLP layers (802M parameters); and a Gated DeltaNet with 6 heads (793M parameters). A parameter-matched Transformer variant with 24 layers (778M parameters) is included. Log-linear variants add a linear layer to compute per-head λ(ℓ) values from the hidden state, increasing Mamba-2 to 825M (<3% increase) and Gated DeltaNet to 796M (<0.4% increase). A Hyena model (Poli et al., 2023) with matched parameters is also evaluated but excluded from main comparisons due to substantially worse perplexity (~29 on WikiText versus <23 for other models).

• Metrics. The primary metrics are: (1) Accuracy (%) for MQAR, NIAH, and commonsense reasoning tasks, computed as the fraction of test examples where the model's selected answer matches the ground truth; (2) Perplexity (PPL) for WikiText and LAMBADA, computed as the exponentiated average negative log-likelihood per token; (3) Per-position loss (nats) on Book-3 sequences, computed at each token position and smoothed with a running average of window size 501 to visualize how loss evolves across the sequence; and (4) Training throughput (tokens/second) and kernel runtime (milliseconds) for forward+backward passes on an H100 GPU, measured at varying sequence lengths. For LongBench, task-specific accuracy metrics are used per Bai et al. (2023). For the in-context retrieval benchmark, accuracy is the primary metric.

• Baselines. The paper evaluates against: (1) Standard Transformer (Vaswani et al., 2017) with FlashAttention-2 (Dao, 2024), using 21 layers (693M) and a 24-layer parameter-matched variant (778M); (2) Mamba-2 (Dao & Gu, 2024), the base linear attention model with data-dependent scalar gating and 1-semiseparable temporal structure, using 48 heads and 802M parameters; (3) Gated DeltaNet (Yang et al., 2024a), which extends Mamba-2 with delta-rule-based structured transition matrices, using 6 heads and 793M parameters; and (4) Hyena (Poli et al., 2023), a long-convolution model with O(T log T) training via FFT and O(T) decoding memory, evaluated only on WikiText perplexity due to substantially worse performance (~29 PPL versus <23 for other models). The log-linear variants are compared directly against their corresponding linear-attention base models (Mamba-2 and Gated DeltaNet) at matched parameter counts and training budgets, as well as against the Transformer baselines.

• Generation budget / compute accounting. For language modeling pretraining, all models are trained on exactly 50B tokens with a global batch size of approximately 524K tokens for 95K steps, using sequence length 16K. Training is performed on 8×A100 or 8×H100 GPUs over several days. For MQAR, models are trained until accuracy exceeds 99% (early stopping). For throughput benchmarks (Figure 4), measurements are taken on a single H100 GPU with batch size 2, 48 heads, head dimension 64, state dimension 128, and chunk size 64; Mamba-2-style models use MVA (multi-value attention) while FlashAttention-2 uses GQA (grouped-query attention). The throughput drop at sequence length 131K is attributed to gradient checkpointing to reduce memory usage. For decoding, the paper reports asymptotic complexity rather than wallclock measurements: O(log T) time per step and O(log T) memory for log-linear variants, versus O(1) for linear attention and O(T) for softmax attention.

• Cross-validation / statistical protocol. For the MQAR experiments, each configuration is run with five different random seeds, and results are reported as mean accuracy ± standard deviation (Table 2). For language modeling, due to substantial compute requirements (several GPU-days per run), each model configuration is trained only once; the authors explicitly note this limitation in Section 5: "We were only able to run our 700M-800M parameter language models just once due to compute constraints." Statistical significance is not assessed for the language modeling results, and no confidence intervals are reported. Hyperparameter tuning is limited: learning rates are tuned for MQAR, and the λ parameterization is tuned for log-linear models on MQAR, but no systematic hyperparameter sweep is reported for the language modeling experiments.

---

Main Quantitative Results

MQAR Synthetic Benchmark Results

The MQAR experiments (Table 2) evaluate whether log-linear attention improves in-context associative recall—the task most directly implicated by the fixed-state bottleneck critique of linear attention. Models are tested on 256-token sequences containing 4 to 64 key-value pairs, with model dimension (d) varied across {16, 32, 64}.

The Transformer baseline achieves ≥99% accuracy across all three dimensions, serving as an upper bound. Both Mamba-2 and Gated DeltaNet show dimension-dependent performance that improves with larger state size. At dimension 16, Mamba-2 achieves 46.9% (±2.3) while Log-Linear Mamba-2 reaches 55.9% (±9.1)—a gain of 9.0 percentage points but with substantially higher variance. At dimension 32, the gap narrows: 75.1% (±4.9) for Mamba-2 versus 76.5% (±4.8) for log-linear, a modest 1.4-point improvement. At dimension 64, Mamba-2 achieves 89.6% (±6.1) and Log-Linear Mamba-2 reaches 92.9% (±2.7), a 3.3-point gain.

For Gated DeltaNet, the pattern is similar. At dimension 16, Gated DeltaNet achieves 38.4% (±1.0) and its log-linear variant reaches 40.0% (±1.4)—only a 1.6-point improvement. At dimension 32, Gated DeltaNet achieves 79.0% (±2.1) versus 84.4% (±1.2) for log-linear, a more meaningful 5.4-point gain. At dimension 64, both models reach ≥99% (early stopped).

The headline interpretation from these results is nuanced. Log-linear attention does improve associative recall over linear attention, but the gains are most pronounced at intermediate dimensions (32) and diminish as the base model's fixed-size state becomes large enough to handle the task (dimension 64, where both Mamba-2 and Gated DeltaNet approach ceiling). The high variance in Log-Linear Mamba-2 at dimension 16 (standard deviation 9.1 versus 2.3 for the baseline) suggests sensitivity to initialization or the λ parameterization, which the paper does not ablate. Critically, log-linear variants require dimension 64 to reach ≥99%—the same as their linear counterparts and the Transformer—so the hierarchical structure does not reduce the state dimensionality needed for this task.

Language Modeling Results

WikiText perplexity and zero-shot reasoning (Table 3, Table 6). Log-Linear Mamba-2 achieves WikiText perplexity of 22.11, improving over standard Mamba-2 (22.44) by 0.33 points. On LAMBADA perplexity, the improvement is larger: 21.86 versus 24.14, a reduction of 2.28 points. On zero-shot commonsense reasoning (average across LAMBADA accuracy, PIQA, HellaSwag, WinoGrande, ARC-easy, ARC-challenge), Log-Linear Mamba-2 achieves 44.9% versus 44.8% for standard Mamba-2—essentially tied. The model improves on 3 of 6 individual benchmarks (LAMBADA +0.8, PIQA -0.2, HellaSwag -0.1, WinoGrande +0.1, ARC-easy -0.5, ARC-challenge +0.3), none by a substantial margin.

Log-Linear Gated DeltaNet shows stronger gains. WikiText perplexity improves from 21.73 to 21.44 (0.29 points), and LAMBADA perplexity drops from 19.71 to 18.08 (a 1.63-point reduction). The commonsense reasoning average improves from 45.0 to 45.6, with improvements on 5 of 6 benchmarks: LAMBADA +1.2, PIQA +0.3, HellaSwag +0.5, WinoGrande +1.7, ARC-easy -0.2, ARC-challenge +0.3. Notably, Log-Linear Gated DeltaNet also outperforms the layer-matched Transformer (21 layers, 693M) on WikiText (21.44 vs. 21.56), LAMBADA PPL (18.08 vs. 22.14), and average reasoning (45.6 vs. 44.0). Against the parameter-matched Transformer (24 layers, 778M), it is mixed: better on WikiText (21.44 vs. 21.13) and LAMBADA PPL (18.08 vs. 21.17), but tied on reasoning average (45.6 vs. 45.6).

The Hyena baseline achieves WikiText perplexity of approximately 29—substantially worse than all other models (<23 PPL)—and is excluded from further comparisons.

Per-position loss (Figure 5). This analysis is arguably the most diagnostic for the paper's central claim, as it directly probes whether the hierarchical state improves long-range context utilization. On Book-3 sequences of length 16K, both Log-Linear Mamba-2 and Log-Linear Gated DeltaNet show consistently lower (smoothed) loss than their linear counterparts across all positions, with the gap generally widening in the later tokens (roughly positions 4K–16K). For Mamba-2, the log-linear variant's loss curve sits approximately 0.02–0.04 nats below the baseline throughout, with the gap most visible in the 2K–14K range. For Gated DeltaNet, the improvement is similar in magnitude (roughly 0.02–0.04 nats) and is sustained across the full 16K sequence.

Log-Linear Gated DeltaNet tracks the layer-matched Transformer (21 layers) closely, maintaining a gap of approximately 0.01–0.02 nats across most positions, but falls behind the parameter-matched Transformer (24 layers) by roughly 0.02–0.04 nats—a gap that persists throughout the sequence. This suggests that while the hierarchical state provides meaningful improvements in long-range context utilization over fixed-size linear attention, additional Transformer layers still provide benefits that the log-linear structure does not fully capture.

The paper notes that the loss curves for all models show a generally decreasing trend as position increases, indicating effective use of longer context. The log-linear variants show a steeper or more sustained decline in the later positions compared to their linear counterparts, which is consistent with the hypothesis that multi-scale state representation helps maintain useful information from distant tokens.

Needle-in-a-Haystack Results

Single-needle tasks (Table 4, S-NIAH-1/2/3). These tasks directly test the fixed-state bottleneck by requiring retrieval of a specific key-value pair hidden among distractor tokens. The results are striking for Log-Linear Mamba-2:

• S-NIAH-1 (pass-key retrieval): At 4K context, Log-Linear Mamba-2 achieves 100.0% versus 90.4% for standard Mamba-2 (+9.6 points). At 8K, the gap is dramatic: 99.8% versus 56.8% (+43.0 points). At 16K, 72.4% versus 21.6% (+50.8 points). The log-linear variant maintains high accuracy at 8K where the linear variant has already degraded substantially, and still achieves 72.4% at 16K where the baseline is near chance.

• S-NIAH-2 (number in haystack): At 4K, 89.8% vs. 72.4% (+17.4). At 8K, 68.2% vs. 28.0% (+40.2). At 16K, 12.8% vs. 18.6% (-5.8) — a surprising reversal where the linear variant slightly outperforms the log-linear variant at the longest context.

• S-NIAH-3 (UUID in haystack): At 4K, 33.6% vs. 4.0% (+29.6). At 8K, 22.6% vs. 3.6% (+19.0). At 16K, 2.0% vs. 0.8% (+1.2). Performance is low for both variants on this harder task, but log-linear maintains a consistent advantage.

For Log-Linear Gated DeltaNet, the pattern differs because the baseline is already strong on single-needle tasks: Gated DeltaNet achieves 100.0% across all context lengths on S-NIAH-1, so the log-linear variant maintains 100.0% (no degradation). On S-NIAH-2, Log-Linear Gated DeltaNet slightly underperforms at 4K (95.6% vs. 95.8%) but improves at 8K (59.6% vs. 46.8%, +12.8) and 16K (9.2% vs. 5.0%, +4.2). On S-NIAH-3, it underperforms at 4K (48.8% vs. 66.2%, -17.4) but nearly ties at 8K (13.0% vs. 14.6%) and slightly improves at 16K (8.8% vs. 6.0%).

Multi-needle tasks (Table 4, MK-NIAH-1, MQ-NIAH, MV-NIAH). These tasks are more challenging, requiring retrieval of multiple items or handling multiple queries/values. Log-Linear Mamba-2 shows consistent improvements:

• MK-NIAH-1 (multi-key line retrieval): At 4K, 43.2% vs. 27.2% (+16.0). At 8K, 39.8% vs. 18.6% (+21.2). At 16K, 21.2% vs. 13.6% (+7.6).

• MQ-NIAH (multi-query): At 4K, 26.6% vs. 28.7% (-2.1). At 8K, 22.4% vs. 19.4% (+3.0). At 16K, 6.6% vs. 1.3% (+5.3).

• MV-NIAH (multi-value): At 4K, 28.1% vs. 27.9% (+0.2). At 8K, 22.8% vs. 14.8% (+8.0). At 16K, 8.9% vs. 4.4% (+4.5).

Log-Linear Gated DeltaNet shows more consistent gains on multi-needle tasks, improving on all 9 metrics: MK-NIAH-1 at 4K: 49.4% vs. 23.0% (+26.4), at 8K: 27.8% vs. 21.2% (+6.6), at 16K: 10.2% vs. 5.2% (+5.0); MQ-NIAH at 4K: 34.9% vs. 21.6% (+13.3), at 8K: 22.0% vs. 16.9% (+5.1), at 16K: 9.8% vs. 7.2% (+2.6); MV-NIAH at 4K: 31.4% vs. 16.2% (+15.2), at 8K: 25.0% vs. 14.5% (+10.5), at 16K: 13.3% vs. 7.0% (+6.3).

Comparison to Transformer baselines (Table 4). The Transformer baselines show strong but inconsistent performance. At 4K, the 21-layer Transformer achieves 72.6% on S-NIAH-1, substantially below Log-Linear Mamba-2's 100.0%. The 24-layer Transformer reaches 92.4% at 4K but drops to 78.4% at 8K—still below Log-Linear Mamba-2's 99.8% at 8K. On multi-needle tasks, the Transformer baselines generally outperform the log-linear variants at 4K but show steep degradation at longer contexts, though they remain competitive or superior on some metrics (e.g., 24-layer Transformer achieves 89.8% on S-NIAH-1 at 16K versus Log-Linear Mamba-2's 72.4%).

LongBench and In-Context Retrieval Results

The paper presents additional long-context evaluation results in Table 8 (LongBench) and Table 7 (in-context retrieval) in the appendix, though these are discussed only briefly in the main text (Section 4.2: "Due to space we show the results on the in-context retrieval benchmark and LongBench in the appendix").

On LongBench (Table 8), which includes 14 tasks spanning single-document QA, multi-document QA, summarization, few-shot learning, and code, the results are mixed. Log-Linear Mamba-2 improves over standard Mamba-2 on 8 of 14 tasks but degrades on 6. Log-Linear Gated DeltaNet improves on 9 of 14 tasks and degrades on 5. Neither log-linear variant consistently outperforms the Transformer baselines across the board; the 24-layer Transformer achieves the highest or near-highest accuracy on most tasks. The paper does not provide an aggregate LongBench score, making overall comparison difficult.

On the in-context retrieval benchmark from Arora et al. (2023) (Table 7), models are evaluated on SWDE, SQuAD, FDA, TriviaQA, Drop, and NQ with inputs truncated to varying lengths (512, 1024, 2048, 16K). The pattern is similar: log-linear variants sometimes improve over their linear counterparts (particularly at longer truncation lengths), sometimes underperform, and the Transformer baselines remain strong competitors. For example, on FDA at 16K, Log-Linear Gated DeltaNet achieves 30.5% versus 30.5% for standard Gated DeltaNet—no improvement—while the 24-layer Transformer achieves 73.8%.

Training Efficiency Benchmarks

Throughput (Figure 4, left). On an H100 GPU with batch size 2, 48 heads, head dimension 64, state dimension 128, and chunk size 64:

• At sequence length 8K: FlashAttention-2 achieves approximately 22K tokens/second, Mamba-2 achieves approximately 25K, Log-Linear Mamba-2 (custom fused kernel) achieves approximately 23K, and the naive multi-level implementation achieves approximately 10K.
• At sequence length 16K: FlashAttention-2 drops to approximately 14K, Mamba-2 to roughly 22K, Log-Linear Mamba-2 (custom) to roughly 20K, and naive to roughly 7K.
• At sequence length 32K: Log-Linear Mamba-2 (custom) crosses FlashAttention-2's throughput (both roughly 12–13K by visual estimate), while Mamba-2 maintains approximately 20K.
• At sequence length 65K: FlashAttention-2 reaches roughly 8K, Log-Linear Mamba-2 (custom) roughly 12K, Mamba-2 roughly 18K.
• At sequence length 131K: All methods drop due to gradient checkpointing. Log-Linear Mamba-2 (custom) achieves roughly 5K, Mamba-2 roughly 7K, FlashAttention-2 roughly 3K.

The log-linear variant is consistently slower than standard Mamba-2 (roughly 80–85% of the throughput at 16K-32K) but outperforms FlashAttention-2 at sequence lengths beyond 8K-16K depending on the metric. The naive implementation (without kernel fusion) is 2–3× slower than the custom version, confirming the importance of the fusion optimizations.

Kernel runtime (Figure 4, right). For forward + backward pass at batch size 1:

• At 4K: FlashAttention-2 approximately 0.5ms, Mamba-2 approximately 0.3ms, Log-Linear Mamba-2 (custom) approximately 0.6ms, naive approximately 2ms.
• At 16K: FlashAttention-2 approximately 4ms, Mamba-2 approximately 1.5ms, Log-Linear Mamba-2 (custom) approximately 2.5ms, naive approximately 12ms.
• At 65K: FlashAttention-2 approximately 12ms, Mamba-2 approximately 4ms, Log-Linear Mamba-2 (custom) approximately 7ms, naive approximately 50ms.
• At 131K: FlashAttention-2 approximately 25ms, Mamba-2 approximately 8ms, Log-Linear Mamba-2 (custom) approximately 16ms, naive approximately 100ms.

The custom kernel shows scaling behavior consistent with O(T log T): its runtime grows slightly faster than Mamba-2's O(T) but substantially slower than FlashAttention-2's O(T²). The crossover with FlashAttention-2 occurs around 8K-12K sequence length. The paper notes that the "throughput drop at sequence length 131K is due to gradient checkpointing to reduce memory usage."

---

Ablation Studies and Robustness Checks

The paper is notably light on formal ablation studies. Most design choices (Fenwick tree partitioning, chunk size, level fusion count, scalar λ weights, weak admissibility) are presented as fixed aspects of the framework rather than varied experimentally. The following represent the closest approximations to ablations present in the paper:

• Choice of base architecture (Mamba-2 vs. Gated DeltaNet as log-linear hosts): The paper instantiates the framework on two distinct base models and finds that log-linear variants improve over both, but with different patterns. For Mamba-2, the largest gains appear on single-needle NIAH tasks (e.g., +43 points on S-NIAH-1 at 8K, Table 4) where the baseline is weak. For Gated DeltaNet, the baseline is already strong on single-needle tasks (100% on S-NIAH-1 at all lengths), so the log-linear variant shows more modest gains on multi-needle tasks (e.g., +26.4 points on MK-NIAH-1 at 4K, Table 4) and on language modeling perplexity (Table 3). This provides evidence that the framework's benefits are not specific to one base architecture, though the magnitude and task profile of improvement varies.

• Naive vs. fused kernel implementation: Figure 4 directly compares the naive multi-level implementation (calling existing Mamba-2 primitives once per level) against the custom fused Triton kernel. At sequence length 16K, the fused kernel achieves approximately 2.9× higher training throughput (20K vs. 7K tokens/second) and roughly 4.8× faster forward+backward runtime (2.5ms vs. 12ms). At 65K, the gap widens to roughly 2.4× throughput and 7.1× runtime. This ablation is critical because it demonstrates that the theoretical O(T log T) complexity does not automatically translate to practical efficiency—the engineering optimizations (level fusion, backward pass gradient factoring) are essential to make the framework competitive.

• Parameterization of λ (implicit ablation via existence): The fact that log-linear variants improve over their linear counterparts on several metrics (Tables 2–4, Figure 5) can be viewed as an implicit ablation against the null hypothesis that the hierarchical structure provides no benefit. However, the paper does not compare learnable λ(ℓ) against fixed λ(ℓ) (e.g., all ones, or learned but static per-level weights independent of input), which would directly test whether content-dependent level weighting is necessary. The paper also does not ablate the λ parameterization itself—for instance, whether computing λ from the hidden state (as done) is better than computing it from the query or from the attention scores.

• Chunk size: The paper uses a fixed chunk size of C = 64 for all throughput benchmarks and does not sweep this hyperparameter. Chunk size affects the tradeoff between intra-chunk work (quadratic in C) and the number of inter-chunk levels (log(T/C)), so it could influence both throughput and model quality. This is not ablated.

• Number of fused levels: The paper states that fusing 4 levels was empirically optimal on H100 hardware due to SRAM constraints, but does not present an ablation comparing 1, 2, 4, 8, or all levels fused. The claim that 4 is optimal is stated without supporting data.

• Weak vs. strong admissibility (Appendix B.4): The paper reports that "using strong admissibility in a Triton implementation resulted in up to a 4× slowdown, with only marginal improvements in accuracy." No quantitative accuracy results are provided for this comparison, and "marginal" is not quantified. This is a negative result mentioned in passing rather than a formal ablation.

• Hyena as an alternative log-linear complexity baseline: The paper includes a Hyena model (Poli et al., 2023) with matched parameters trained on the same data. Hyena achieves WikiText perplexity of approximately 29 versus <23 for all other models, making it uncompetitive. This comparison is included only for WikiText and is not extended to other benchmarks. The authors explicitly state that "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." This is more of a sanity check than an ablation—it confirms that not all O(T log T) architectures are equally effective, but doesn't isolate which properties of log-linear attention (hierarchical recurrence, quasi-H structure, Fenwick partitioning) distinguish it from long-convolution alternatives.

• Layer count and parameter matching: The paper includes both a layer-matched Transformer (21 layers, 693M) and a parameter-matched Transformer (24 layers, 778M) to partially control for model capacity. Log-Linear Gated DeltaNet outperforms the layer-matched Transformer on most metrics but is roughly tied with the parameter-matched variant (Table 3, Figure 5), suggesting that the gains from the hierarchical structure are comparable in magnitude to the gains from adding 3 Transformer layers (85M additional parameters). This is a useful calibration but does not isolate the effect of the hierarchical structure from other architectural differences between the Transformer and the SSM families.

---

Critical Assessment

Do the experiments support the central claim that log-linear attention provides a meaningful middle ground between linear attention and softmax attention?

The experiments provide partial but genuine support for this framing, with important caveats about where the benefits materialize. The strongest evidence comes from the Needle-in-a-Haystack results (Table 4), particularly the single-needle pass-key retrieval task (S-NIAH-1) where Log-Linear Mamba-2 achieves 99.8% at 8K context versus 56.8% for standard Mamba-2—a 43 percentage point improvement. This task directly operationalizes the fixed-state bottleneck: a single key-value pair must be distinguished from thousands of distractors, which is precisely the regime where a single matrix-valued state should struggle to preserve individuated representations. The fact that log-linear attention nearly solves this task at 8K while linear attention degrades to near-chance levels at 16K is strong evidence that the hierarchical state is doing the work it was designed to do—maintaining fine-grained access to specific tokens while compressing the irrelevant bulk at coarser granularity.

However, the benefits are task-specific and not uniform. On the multi-query associative recall synthetic benchmark (MQAR, Table 2), which is the canonical diagnostic for the recall limitations of linear attention models, the gains are modest: +9 points for Mamba-2 at dimension 16 (46.9% → 55.9%) but only +1.4 points at dimension 32 (75.1% → 76.5%) and +3.3 at dimension 64 (89.6% → 92.9%). The Transformer achieves ≥99% at all dimensions, meaning the log-linear variants still require dimension 64 to saturate the benchmark—the same as their linear counterparts. The paper's narrative emphasizes that logarithmic state growth addresses the fixed-state bottleneck, but MQAR suggests that the bottleneck is not fully resolved. This is a genuine limitation: the hierarchical structure helps but does not close the gap with softmax attention on the most direct test of associative recall.

On language modeling (Table 3, Figure 5), the gains are real but small in magnitude—0.3–0.4 WikiText perplexity points, 1–2 LAMBADA perplexity points, 0.1–0.6 commonsense reasoning average points. These improvements are consistent across both base architectures (Mamba-2 and Gated DeltaNet) and are large enough to be practically meaningful at the scale tested (if they persist at larger scales, which is untested), but they do not dramatically reshape the competitive landscape. Log-Linear Gated DeltaNet is roughly on par with the 24-layer Transformer on reasoning (45.6 vs. 45.6) and better on WikiText (21.44 vs. 21.13), but it is not clearly superior—it is competitive in a regime where the Transformer remains the dominant architecture.

The per-position loss analysis (Figure 5) arguably provides the cleanest evidence for the paper's core mechanism. The fact that log-linear variants show consistently lower loss than their linear counterparts across all positions, with the gap persisting and sometimes widening at longer ranges (4K–16K), is exactly what one would expect if the hierarchical state is improving long-range context utilization. The gap of 0.02–0.04 nats may seem small, but it is sustained across a 16K-token context window and would compound into meaningful differences in downstream task performance. The fact that the Transformer baselines (particularly the 24-layer variant) still outperform on this metric suggests that depth provides additional benefits beyond what the hierarchical state captures—but this is not a failure of the framework so much as a calibration of where it sits on the expressiveness spectrum.

Are the experiments sufficient to demonstrate that the framework generalizes beyond the tested configurations?

No. All language modeling experiments use a single model scale (~800M parameters), a single training data scale (50B tokens), a single sequence length (16K), and a single training run per configuration. The paper explicitly acknowledges this: "We were only able to run our 700M-800M parameter language models just once due to compute constraints" (Section 5). This is a significant limitation for several reasons:

• Scaling behavior is unknown. Do the relative gains of log-linear over linear attention increase, decrease, or stay constant with model scale? If the fixed-state bottleneck becomes more severe at larger scales (because larger models can exploit longer contexts, making the state capacity the binding constraint), the gains might grow. Alternatively, if larger linear attention models can compensate with higher-dimensional states, the gains might shrink. Without scaling curves, the practical relevance of the framework at production scales (7B, 70B, 100B+ parameters) is speculative.

• Single-run results are noisy. With only one training run per configuration, the reported perplexity differences (e.g., 22.44 → 22.11 for Mamba-2, a 0.33-point gap) could be within the noise of training stochasticity. The MQAR experiments use 5 seeds and report standard deviations (Table 2), revealing substantial variance for some configurations (±9.1 for Log-Linear Mamba-2 at dim 16). The language modeling results have no such quantification.

• Single dataset. All language modeling results are on the Long-Data-Collections dataset. Whether the benefits transfer to other pretraining corpora (C4, The Pile, multilingual data, code) is untested.

• Single sequence length. All models are trained and evaluated at 16K sequence length. Whether log-linear attention provides greater benefits at longer contexts (64K, 128K, 256K)—where the logarithmic state growth should be proportionally more advantageous—is not evaluated. The NIAH experiments (Table 4) test up to 16K and show that some of the largest relative gains are at 8K–16K, but training perplexity at these lengths is not reported.

Are the baselines sufficient to isolate the contribution of the hierarchical structure?

Partially. The primary comparison is between a base linear attention model and its log-linear variant at the same parameter count and training budget. This is the correct comparison for testing whether the hierarchical mask $M_H$ provides benefits over the semiseparable mask $M_S$ alone. The parameter-matched Transformer comparison is useful for calibrating where log-linear attention sits relative to the dominant architecture, but it does not isolate the hierarchical structure because the Transformer differs in many other ways (softmax, per-head key-value caches, no state compression).

Missing baselines:

• A non-Fenwick hierarchical variant. The paper does not compare the Fenwick-tree partition against any alternative hierarchical scheme (e.g., fixed dyadic partitioning, learnable bucket boundaries, or a simple multi-scale RNN with hand-specified exponential bucket sizes). Without such a comparison, it is unclear whether the Fenwick tree's specific alignment to binary boundaries and its lssb-based update recurrence are necessary for the observed gains, or whether any hierarchical decomposition with O(log T) states would perform similarly.

• A fixed-λ variant. As noted above, the paper does not ablate whether learnable, content-dependent level weights are better than fixed learned weights per level. If fixed weights were sufficient, the mechanism would be considerably simpler and the contribution would be primarily about the hierarchical state structure rather than adaptive multi-scale readout.

• A version of linear attention with an enlarged but still fixed-size state. The paper argues that logarithmic growth is the sweet spot, but does not test whether simply increasing the dimension of the fixed-size state in standard Mamba-2 (e.g., doubling the state dimension at the cost of more parameters) would match or exceed the log-linear variant's performance. This is a critical missing ablation because the log-linear variant adds parameters (<3% for Mamba-2) and compute (O(T log T) vs. O(T)). If the same parameter and compute budget allocated to a larger fixed-size state yielded similar gains, the hierarchical structure would be unnecessary. The paper does not report a parameter-matched Mamba-2 with larger state dimension.

• A fully dense attention baseline at the same compute budget. The FlashAttention-2 baseline uses softmax attention with O(T²) cost. At 16K, this costs approximately 256× more than linear attention per attention layer. The paper's throughput benchmarks (Figure 4) show that Log-Linear Mamba-2 is roughly 1.4× faster than FlashAttention-2 at 16K. A fair comparison would give the Transformer additional compute budget (more layers, larger model) to match the total FLOPs—but this is not done.

Do the experiments adequately address the scalability and practicality of the approach?

For training: partially. The throughput benchmarks (Figure 4) demonstrate that the custom Triton kernel achieves practical speeds on H100 GPUs, with throughput within 15–20% of standard Mamba-2 at 16K–32K and outperforming FlashAttention-2 at longer sequences. The 3× improvement from kernel fusion over the naive implementation confirms that the optimizations are necessary and effective. However, these benchmarks are for a single attention layer in isolation, not for end-to-end model training. The paper mentions that Log-Linear Mamba-2 "with MLP layers surpasses Transformer throughput at 32K despite additional layers like depthwise convolutions absent in the Transformer," but does not provide end-to-end training time measurements. Given that attention is only one component of the model (alongside MLP layers, convolutions, normalization), the wallclock advantage of log-linear attention over softmax attention in full training would be smaller than the kernel-level benchmarks suggest.

For decoding: untested empirically. The paper claims O(log T) decoding time and memory based on the recurrence in Section 3.2, but provides no decoding benchmarks whatsoever—no measurements of per-step latency, no memory profiling during generation, no comparison against standard Mamba-2 decoding or Transformer KV-cache inference. The O(log T) claim is purely asymptotic and based on the structural properties of the recurrence. Whether log-linear attention actually achieves faster or more memory-efficient decoding than linear attention in practice depends on constant factors (the cost of managing O(log T) states vs. 1 state, the cost of the merge operations, the memory access patterns) that are not evaluated. This is a notable gap given that efficient decoding is one of the two core promises of the framework.

For the difficulty estimation/λ computation: The λ(ℓ) coefficients are computed via a single linear projection per head from the hidden state. The paper states this adds <3% parameters for Mamba-2 and <0.4% for Gated DeltaNet, which is minimal. The computational cost of this projection is not separately benchmarked but is presumably negligible relative to the attention computation itself. This aspect of the framework is practical and well-justified.

Are there significant weaknesses in the experimental design?

Single training run per configuration. As discussed, this means the reported perplexity and accuracy differences are not accompanied by uncertainty estimates. The language modeling results should be interpreted as suggestive rather than conclusive, particularly for the smaller-magnitude improvements (e.g., Mamba-2 WikiText PPL from 22.44 to 22.11, a 0.33-point difference).

Limited hyperparameter exploration. The paper notes that it was unable to "experiment with different parameterizations of the λ terms (or hyperparameters in general)" due to compute constraints (Section 5) and that "it is possible that optimal parameterization of λ could lead to improved results." This means the reported performance is a lower bound on what the framework can achieve with better tuning, but it also means the comparison against highly-tuned baselines (Mamba-2, Gated DeltaNet) may be unfair—the baselines may have received more tuning attention in their original papers than the log-linear variants received here.

Chunk size is not swept. The chosen chunk size (C=64) affects both training throughput and the decomposition structure (levels below ℓ_C are absorbed into intra-chunk computation). The paper does not explore whether larger chunk sizes (which would shift more of the hierarchy into the intra-chunk dense computation) or smaller chunk sizes (which would increase inter-chunk parallelism) perform differently.

Lack of long-range language modeling benchmarks beyond NIAH and per-position loss. The paper does not evaluate on standard long-range language modeling benchmarks like PG-19 (Rae et al., 2019), SCROLLS (Shaham et al., 2022), or the LRA benchmark (Tay et al., 2021). The LongBench results (Table 8, appendix) are mixed and do not show a consistent advantage for log-linear variants. This limits the evidence that the hierarchical structure provides practical benefits for real-world long-context tasks, as opposed to synthetic diagnostics like NIAH.

The Hyena comparison is underdeveloped. Including Hyena as a baseline is valuable because it also has O(T log T) training complexity (via FFT), providing a point of comparison within the same complexity class. However, the paper only reports Hyena's WikiText perplexity (~29) and excludes it from all other benchmarks. It is unclear whether Hyena's poor performance is due to its architecture, its training recipe, or the specific hyperparameters used. Without a more thorough evaluation, the claim that log-linear attention is superior to other O(T log T) approaches is not well-supported.

Summary of the evidence

The experiments provide convincing evidence that log-linear attention improves over linear attention on tasks that specifically stress the fixed-state bottleneck—most compellingly the Needle-in-a-Haystack pass-key retrieval and the per-position loss analysis. The gains on language modeling perplexity and commonsense reasoning are positive but modest, and the framework does not close the gap with softmax attention on pure associative recall (MQAR). The experiments are limited to a single model scale, single training run, and single sequence length, which restricts the generalizability of the findings. The absence of decoding benchmarks is a significant gap given that O(log T) decoding memory is one of the framework's two headline claims. The results support the paper's positioning of log-linear attention as a "middle ground" that provides meaningful improvements over linear attention without matching softmax attention, but they do not establish that this middle ground is practically transformative at the scales tested.

6. Limitations and Trade-offs

The O(log T) Decoding Memory Claim Is Entirely Unverified Empirically

The assumption. The paper's headline asymptotic claims are that log-linear attention provides O(log T) decoding memory and O(log T) time per step, derived from the recurrence in Section 3.2 where exactly O(log t) independent matrix-valued states are maintained and updated at each time step through the Fenwick-tree merge-and-promote operations. The paper states that this Fenwick-like organization "enables online processing with O(log T) memory" (Section 3.2) and lists "O(log T) Decoding Time and Space" as a key property in Table 1, directly contrasting it with softmax attention's O(T) memory and linear attention's O(1) memory.

The consequence. No decoding benchmarks of any kind are presented. The paper provides no measurements of per-step latency during autoregressive generation, no memory profiling of the recurrent state during decoding, and no comparison against standard Mamba-2 decoding (which uses a single constant-size state) or Transformer decoding (which uses a growing KV-cache). The gap between asymptotic complexity and wallclock performance can be substantial: managing O(log T) individual state matrices with the merge-and-promote recurrence involves non-trivial memory access patterns (reading O(log T) states, zeroing some, merging others, writing back) that could have poor cache locality. The constant factors—the cost of reading and updating O(d² log T) elements per step versus O(d²) for linear attention—are unmeasured. A practitioner deciding whether to deploy log-linear attention for memory-constrained inference (the primary motivation for logarithmic decoding memory) has no empirical evidence that the claimed memory savings actually materialize in practice. The entire decoding story is purely analytic.

What evidence exists in the paper. None. Section 3.5 discusses only training throughput and kernel runtime for forward+backward passes. Figure 4 and accompanying text are exclusively about training throughput on H100 GPUs with batch size 2. The only implementation benchmarks are for the chunkwise parallel training algorithm, not the recurrent decoding algorithm. The O(log T) claim appears in Table 1 and Section 3.2 as a theoretical property, but is never validated empirically.

Mitigation status. Not addressed. The paper does not acknowledge this gap, propose decoding benchmarks, or suggest that decoding efficiency requires empirical validation beyond asymptotic analysis. The Triton implementation described in Section 3.5 and Appendix C is for the training kernel only; there is no mention of a decoding kernel implementation. This is a substantial omission given that memory-efficient inference is explicitly presented as a central motivation for the framework.

---

Single Training Run Per Configuration With No Uncertainty Quantification for Language Modeling Results

The assumption. The paper trains each ~800M parameter language model configuration on 50B tokens exactly once. Section 5 explicitly states: "We were only able to run our 700M-800M parameter language models just once due to compute constraints." The paper implicitly assumes that training stochasticity, initialization variance, and data order effects are small enough that a single run provides a reliable point estimate of model quality.

The consequence. The reported perplexity differences between log-linear variants and their linear baselines are modest in magnitude. Log-Linear Mamba-2 improves WikiText perplexity from 22.44 to 22.11 (a 0.33-point gap) and LAMBADA perplexity from 24.14 to 21.86 (a 2.28-point gap). Log-Linear Gated DeltaNet improves WikiText from 21.73 to 21.44 (0.29 points) and LAMBADA from 19.71 to 18.08 (1.63 points). These differences, while directionally consistent across both base architectures, could plausibly fall within the range of run-to-run variance for models of this scale trained on 50B tokens. The MQAR experiments (Table 2) use 5 seeds and reveal substantial variance: Log-Linear Mamba-2 at dimension 16 has a standard deviation of ±9.1 percentage points, nearly as large as the 9.0-point improvement over the baseline. This serves as a warning that variance can be large at the scales tested, yet the language modeling results—the primary evidence for the framework's practical benefits—have no such quantification. Confidence intervals could reveal that some of the reported improvements are not statistically distinguishable from noise.

What evidence exists in the paper. The MQAR experiments in Table 2 include standard deviations across 5 seeds, confirming that the authors recognize the importance of uncertainty quantification for small-scale experiments. The language modeling results in Tables 3 and 6 are reported as single numbers without error bars, standard deviations, or confidence intervals. Section 5 acknowledges the single-run limitation for the language models but does not discuss its implications for the reliability of the reported improvements. The per-position loss curves (Figure 5) are plotted from a single evaluation run on 39M tokens of Book-3, with a running average smoothing but no indication of variance across model checkpoints or data shards.

Mitigation status. The paper transparently acknowledges the compute constraint that prevented multiple runs but does not attempt any form of uncertainty estimation (e.g., bootstrap resampling of evaluation data, reporting loss variability across the final training steps, or using adjacent checkpoints to estimate training noise). The authors note in Section 5 that "it is possible that optimal parameterization of λ could lead to improved results," implicitly acknowledging that the reported numbers are not necessarily the best achievable, but this does not address the question of whether the observed differences exceed run-to-run variance. Future work at larger scales or with more compute budget could address this, but the current paper's language modeling results should be interpreted as suggestive rather than definitive.

---

The Log-Linear Overhead Relative to Linear Attention Is Not Matched by Parameter-Equivalent Stronger Baselines

The assumption. The paper's central experimental comparison is between a linear attention model and its log-linear variant, controlling for parameter count and training tokens. The implicit assumption is that any improvement from the log-linear variant is attributable to the hierarchical temporal structure rather than to increased effective capacity. However, the log-linear variants add parameters (the λ projection layer, increasing Mamba-2 from 802M to 825M parameters, +2.9%) and increase training compute from O(T) to O(T log T). The paper does not test whether allocating these additional resources differently within the linear attention paradigm would yield similar or larger gains.

The consequence. A practitioner considering adopting log-linear attention needs to know whether the hierarchical structure is genuinely necessary or whether simpler alternatives—such as increasing the state dimension, adding more layers, or using more training tokens—achieve the same effect. The paper does not provide this calibration. For Mamba-2, the 23M additional parameters in the log-linear variant could alternatively fund an enlarged hidden state dimension or additional model depth. For example, doubling the state dimension in standard Mamba-2 (the d dimension of the recurrent state S_t) would increase the state's representational capacity without introducing hierarchical complexity. The paper does not compare against a Mamba-2 with enlarged state dimension matched for total parameter count or total FLOPs. Similarly, the parameter-matched Transformer (24 layers, 778M) generally outperforms or matches Log-Linear Gated DeltaNet (21 layers, 796M) on per-position loss (Figure 5) and several LongBench tasks (Table 8), suggesting that additional Transformer layers provide comparable or better benefits than the hierarchical structure, albeit at higher FLOP cost.

What evidence exists in the paper. The parameter-matched Transformer comparison (Tables 3, 4, 6, 7, 8; Figure 5) provides a partial calibration: on WikiText perplexity, Log-Linear Gated DeltaNet (21.44) slightly edges out the 24-layer Transformer (21.13) but is essentially tied on commonsense reasoning (45.6 vs. 45.6). On per-position loss, the 24-layer Transformer maintains a consistent advantage. On NIAH tasks (Table 4), the Transformer baselines show strong but inconsistent performance—the 24-layer Transformer gets 89.8% on S-NIAH-1 at 16K versus Log-Linear Mamba-2's 72.4%, but only 36.4% on S-NIAH-3 at 16K versus the log-linear variant's 2.0%. These mixed results make it difficult to assess whether the log-linear approach is Pareto-optimal or whether a differently-allocated baseline would dominate it. The key missing comparison is a Mamba-2 variant with increased state dimension matched for parameters and/or compute with Log-Linear Mamba-2.

Mitigation status. Not addressed. The paper does not ablate the effect of increased state dimension in the linear baselines, nor does it provide a FLOPs-matched comparison between log-linear and linear attention (analogous to the training-inference FLOPs comparison in the analyzed example paper). Section 5 acknowledges the limited hyperparameter exploration and the single-run nature of the language modeling experiments, but does not flag the absence of stronger baselines as a limitation. This leaves open the possibility that the reported improvements could be achieved more simply within the linear attention paradigm.

---

Fenwick-Tree Partitioning Introduces Positional Artifacts With Unknown Consequences

The assumption. The Fenwick tree partitions the prefix into buckets aligned to binary boundaries, meaning that whether a token ends up in a fine-grained or coarse-grained bucket depends on its absolute position modulo powers of two, not just on its temporal distance from the query. Two tokens at exactly the same distance from the query but on opposite sides of a binary boundary (say, positions 3 and 4, separated by the 2² boundary) will fall into different buckets and be processed at different granularities. The paper implicitly assumes that the model can learn to compensate for this positional artifact through the λ weights, and that the benefits of efficient recurrence outweigh any degradation from the unnatural boundary alignment.

The consequence. This positional artifact could manifest as a form of positional aliasing: at certain positions, the model has finer-grained access to the past than at adjacent positions, even when the informational need is identical. For example, at position 8 (binary 1000), the Fenwick decomposition creates a merge that affects how positions 0–7 are summarized in the state hierarchy. At position 7 (binary 111), the decomposition is different—the boundary at 2³ has not been reached yet. This means the model's ability to access historical information can change discontinuously as the sequence position changes, even for tokens that are equally distant from the query. This is not a property of any natural task distribution, and it forces the model to learn to read from a state representation whose structure depends on absolute position rather than relative distance. The paper provides no analysis of whether this artifact actually degrades performance at specific positions, whether the λ mechanism successfully compensates, or whether alternative partitioning schemes (e.g., sliding-window hierarchies aligned to relative rather than absolute position) would perform better.

What evidence exists in the paper. None directly. The per-position loss curves (Figure 5) are smoothed with a window size of 501 tokens, which would obscure any position-specific artifacts at the granularity of individual binary boundaries. The paper does not plot unsmoothed per-position loss or analyze loss as a function of position modulo powers of two. The NIAH results (Table 4) test specific retrieval positions but do not analyze whether retrieval accuracy depends on the query position's alignment with the Fenwick boundaries. The paper does not ablate the Fenwick tree against alternative hierarchical partitions (e.g., fixed exponential bucketing independent of absolute position, or learnable bucket boundaries).

Mitigation status. Not addressed. The paper treats the Fenwick tree as a fixed design choice justified by its efficient update properties, without analyzing its potential drawbacks. The authors do not discuss the positional artifact, test for its effects, or propose mitigations. Section 5's discussion of limitations focuses on tasks where log-linear attention did not improve, engineering complexity, and the inductive bias toward "more fine-grained memory" for recent tokens—but does not mention the binary-boundary artifact at all.

---

The Framework Is Evaluated at a Single Model Scale With No Evidence of Scaling Behavior

The assumption. All language modeling experiments use models of ~800M parameters trained on 50B tokens with sequence length 16K. The paper implicitly assumes that the relative benefits of log-linear attention over linear attention will persist—or at least not reverse—at larger scales (7B, 70B, 100B+ parameters), longer contexts (64K, 128K, 256K+), and larger training budgets (hundreds of billions to trillions of tokens). This is a significant assumption because the fixed-state bottleneck that motivates log-linear attention may manifest differently at different scales.

The consequence. A practitioner deciding whether to invest in implementing log-linear attention for large-scale training has no evidence that the benefits observed at 800M/50B/16K will translate. There are plausible arguments in both directions. On one hand, the fixed-state bottleneck should become more severe at longer sequence lengths, and the O(log T) state growth becomes proportionally more advantageous the larger T becomes—suggesting that gains should increase with context length. On the other hand, larger models with higher-dimensional states might compensate for the fixed-state limitation through increased representational capacity, reducing the marginal benefit of hierarchical structure. The paper's own MQAR results (Table 2) show this pattern: at dimension 16, Log-Linear Mamba-2 improves by 9 points (46.9% → 55.9%), but at dimension 64, the improvement shrinks to 3.3 points (89.6% → 92.9%), and both variants are still far from the Transformer's ≥99%. This suggests that as capacity increases, the hierarchical advantage may diminish—but whether this trend continues to production scales is unknown.

What evidence exists in the paper. The MQAR results across dimensions 16, 32, 64 provide a limited form of scaling analysis, but only for a synthetic task on 256-token sequences. The language modeling experiments use a single scale with no variation. The NIAH experiments test three context lengths (4K, 8K, 16K) and show that Log-Linear Mamba-2's relative advantage over standard Mamba-2 on S-NIAH-1 increases with context length (+9.6 at 4K, +43.0 at 8K, +50.8 at 16K), which is encouraging but limited to a diagnostic retrieval task, not end-to-end language modeling. The paper explicitly acknowledges compute constraints as the reason for not running multiple configurations (Section 5), but does not frame the single-scale evaluation as a limitation of the evidence.

Mitigation status. The paper is transparent about the compute limitation that prevented larger-scale experiments, but does not discuss the uncertainty this creates for practitioners or propose what an adequate scaling study would require. Section 5 mentions that "it is possible that optimal parameterization of λ could lead to improved results," hinting that the reported numbers may be underestimates, but this does not address whether the log-linear advantage persists, grows, or shrinks at larger scales. Future work on scaling behavior is implicitly suggested but not explicitly called out as a critical next step.

---

The Engineering Complexity Is Higher, Especially for the Backward Pass and Intra-Chunk Kernels

The assumption. The paper presents log-linear attention as a general framework that can upgrade existing linear attention architectures by composing their temporal mask with the hierarchical mask M_H. The implicit assumption is that this composition is straightforward to implement and maintain, and that the described Triton optimizations (level fusion, backward pass gradient factoring) are sufficient to make the approach practically deployable.

The consequence. The paper acknowledges this limitation explicitly in Section 5: "The engineering complexity of log-linear 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 a 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." This is not a minor practical concern. The fused kernel that achieves the throughput results in Figure 4 required custom Triton implementations with level fusion tuned to H100 SRAM constraints (4 levels). The backward pass required "analytically factoring dependencies across all levels for ∇K and ∇V" and "over 3× speedup compared to the naive multi-level version." A practitioner attempting to port log-linear attention to a different hardware platform (e.g., AMD GPUs, TPUs, Apple Silicon), a different base architecture (e.g., xLSTM, RWKV, MesaNet), or a different precision regime (fp8 training, inference quantization) would need to re-derive and re-implement these optimizations. The λ gradient computation adds a dependency that does not exist in standard linear attention kernels. The intra-chunk computation for the hierarchical mask M_H^{[k]} is denser and more irregular than the uniform semiseparable mask in standard Mamba-2, requiring custom logic rather than reuse of existing optimized primitives. This represents a significant barrier to adoption compared to simply using an off-the-shelf linear attention implementation.

What evidence exists in the paper. Figure 4 directly demonstrates the consequence: the naive implementation (calling existing Mamba-2 primitives once per level) is 2–4× slower than the custom fused kernel, and substantially slower than standard Mamba-2 itself. At sequence length 16K, the naive implementation achieves only ~7K tokens/second versus ~22K for standard Mamba-2—a 3.1× slowdown that would negate any practical benefits for training. Even the custom kernel is 10–15% slower than standard Mamba-2 at most sequence lengths (Figure 4). The paper's own implementation required specific knowledge of H100 SRAM capacity to determine the optimal fusion level count (4), and this parameter would need retuning for different hardware. Section 3.5 and Appendix C describe the implementation in detail, making the complexity transparent.

Mitigation status. The paper partially mitigates this through its open-source code release (linked in the abstract) and the detailed implementation description in Appendix C (including a full PyTorch reference implementation). However, the mitigation is incomplete in two important ways. First, the reference implementation is not production-optimized—it is a PyTorch version that demonstrates correctness but not the performance of the custom Triton kernel. Second, the paper does not provide guidelines for porting to other architectures or hardware platforms. A practitioner wanting to implement, say, Log-Linear xLSTM on an AMD MI300X would need to re-derive the fused backward pass and level fusion strategy from scratch. The paper acknowledges this complexity without proposing systematic mitigations beyond code release and the general suggestion that future work could extend the framework to other architectures (Section 5).

7. Implications and Future Directions

How This Work Changes the Landscape

This paper introduces a new point on the structured-matrix design continuum for efficient attention, establishing that the expressiveness-efficiency tradeoff is not binary (softmax attention vs. linear attention) but rather a spectrum with exploitable intermediate positions. The contribution is primarily a reframing and structural advance rather than a paradigm shift: it does not render existing approaches obsolete, but it makes visible a design space that was previously obscured and provides the algebraic tools to navigate it. The magnitude of the shift is incremental for practitioners (the empirical gains over linear attention are real but modest, ~0.3–0.4 WikiText perplexity points, ~1–2 LAMBADA perplexity points) and more significant for researchers designing new sequence modeling architectures, who now have a principled template for incorporating hierarchical temporal structure without sacrificing the efficient training and decoding properties that make linear attention attractive.

The paper's most enduring contribution is likely the taxonomy of efficient attention through the structured-matrix lens (Equation 1, Table 1). By reducing Mamba-2, Gated DeltaNet, RetNet, long convolutions, and log-linear attention to variants of O = (A ⊙ M)V that differ only in the structure of the masking matrix M, the paper provides a common language for reasoning about what was previously a fragmented design space. This reframing has immediate consequences for how researchers think about architectural innovation: rather than asking "should I use Mamba or a Transformer?", the question becomes "what structure of M gives me the right compute-memory-expressiveness tradeoff for my deployment constraints?" The paper populates one previously empty cell in this taxonomy (O(T log T) training, O(log T) decoding), but the framework itself is more valuable than the specific instantiation—it predicts that other points on this spectrum are achievable and provides the conceptual scaffolding for finding them.

The work also reconciles apparently conflicting properties of hierarchical attention approaches. Prior work on hierarchical matrices for attention (Zhu & Soricut, 2021) achieved O(T log T) training but O(T) decoding memory, creating an impression that hierarchical structure necessarily sacrifices the memory-efficient inference that makes linear attention attractive for deployment. The paper's identification of the quasi-H matrix as the structural primitive that enables logarithmic recurrence (Appendix B.3)—specifically, the asymmetric nesting property where temporal decay satisfies level nesting but readout weights do not—shows that the apparent conflict was an artifact of using fully general HODLR matrices rather than the restricted quasi-H subclass. This is a genuine insight: the prior negative result ("hierarchical attention requires linear decoding memory") is refined to a conditional one ("unless the hierarchy satisfies quasi-H nesting properties"). This opens the door to other hierarchical structures that share this property, potentially including strong-admissibility variants or learnable partitions, that were previously assumed to be incompatible with efficient recurrence.

The paper also provides an empirical calibration of what logarithmic state growth buys you in practice. The 43-percentage-point improvement on single-needle pass-key retrieval at 8K (S-NIAH-1: 56.8% → 99.8%, Table 4) establishes that the fixed-state bottleneck is not merely a theoretical concern but a measurable practical limitation of linear attention that can be substantially mitigated with modest state growth. However, the much smaller gains on MQAR (Table 2) and the mixed LongBench results (Table 8) simultaneously establish that logarithmic growth does not close the gap with softmax attention on all recall-heavy tasks. This nuanced calibration—improvements are large on some tasks, negligible on others—is valuable because it helps the field move beyond binary claims ("RNNs can't do recall") toward a more precise understanding of which types of recall benefit from which types of state expansion.

One subtle but important shift: the paper makes verifier/temporal structure design a first-class research direction for recurrent architectures, analogous to how the RLHF community recognized reward model quality as a bottleneck. Just as the example paper (on compute-optimal test-time scaling) identified verifier over-optimization as the ceiling on inference-time search, this paper identifies the structure of M—and specifically the choice between semiseparable, HODLR, quasi-H, Toeplitz, and other matrix classes—as the primary design lever for balancing efficiency and expressiveness. This reorients research attention away from incremental improvements to the recurrence equation (e.g., different gating mechanisms, different transition matrix parameterizations) and toward the temporal granularity at which information is stored and accessed. The long-term impact may be a generation of architectures that are designed by first choosing an M structure with desired asymptotic properties, then fitting a recurrence to it—the inverse of the historical approach where recurrences were designed first and their matrix structure was analyzed post hoc.

Research directions that become more attractive after this work include: (1) exploring non-Fenwick hierarchical partitions that retain quasi-H properties, (2) applying the log-linear upgrade to other linear attention architectures (xLSTM, RWKV, MesaNet), (3) training verifier models or learned difficulty estimators for adaptive hierarchical depth (analogous to the compute-optimal allocation in the example paper), and (4) developing hardware-optimized kernels for hierarchical matrix multiplication that reduce the engineering complexity barrier. Research directions that become less attractive include: (1) claims that fixed-size recurrent states are sufficient for all practical sequence modeling (the NIAH results directly contradict this), (2) purely parallel hierarchical attention without a recurrent formulation (since decoding memory remains O(T), losing the deployment advantage), and (3) long-convolution approaches that achieve O(T log T) training but cannot be converted to O(log T) recurrence (the Hyena result, with ~29 WikiText PPL versus <23 for other models, suggests that achieving log-linear complexity via FFT is not sufficient for competitive performance without careful architectural design).

Follow-Up Research This Work Enables

Scaling laws for hierarchical state growth: how do the benefits scale with model size and context length? The paper demonstrates improvements at a single scale (~800M parameters, 50B tokens, 16K context), but the fixed-state bottleneck should become more severe at longer sequence lengths (where log T grows relative to 1 for the fixed state) and could either increase or decrease with model scale (larger state dimensions might compensate, or larger models might exploit longer contexts more aggressively, making the bottleneck binding). A scaling study training Log-Linear Mamba-2 at multiple sizes (e.g., 300M, 800M, 1.5B, 3B parameters) on the same data with the same context length, plus a complementary study varying context length (16K, 32K, 64K, 128K) at fixed model size, would reveal whether the log-linear advantage grows, shrinks, or plateaus. The key metric would be the ratio of log-linear to linear attention loss at the maximum context position, plotted against model size and context length. If the advantage grows with both, it would strengthen the case for log-linear attention as a scaling-friendly design; if it plateaus or reverses, it would suggest that hierarchical structure is most valuable in a specific intermediate regime.

Alternative partitioning schemes beyond the Fenwick tree: what happens with learnable bucket boundaries? The Fenwick tree is chosen for its efficient update properties (the lssb-based recurrence), but it imposes a rigid, position-absolute binary alignment that may not match any natural structure in language. An alternative approach would replace the fixed binary partitioning with learnable, data-dependent bucket boundaries—for instance, having the model emit a "merge" signal that dynamically decides when to promote fine-grained states to coarser levels, analogous to the gating mechanism in Mamba-2 but applied to hierarchical structure rather than forgetting. The key challenge is maintaining the quasi-H nesting property that enables O(log T) recurrence while allowing boundaries to vary. A strong follow-up would train such a model on the same 50B-token setup and compare against the Fenwick variant on (a) per-position loss, (b) the NIAH benchmark, and (c) a new diagnostic that specifically probes whether the model can adapt its hierarchical granularity to the input (e.g., alternating segments that require fine-grained vs. coarse-grained access). If learnable boundaries outperform Fenwick, it would establish that the Fenwick tree is a useful starting point but not the final answer; if Fenwick outperforms learnable boundaries, it would suggest that the lssb-based structure has some unanticipated inductive benefit.

Combining log-linear attention with compute-optimal test-time compute allocation. The example paper (on compute-optimal scaling) establishes that different test-time strategies are optimal for different prompt difficulties, with a difficulty-conditioned policy achieving 4× efficiency gains over uniform allocation. A natural synthesis would use log-linear attention as the base architecture and develop an adaptive policy that decides per-query how many hierarchical levels to maintain. On easy short-context queries, the model might collapse to standard linear attention (all λ(ℓ) uniform, effectively a fixed-size state). On hard long-context queries requiring fine-grained recall, it might allocate the full O(log T) states with learnable λ weights. The difficulty signal could come from the λ weight distribution itself—if the model consistently assigns near-zero weights to coarse levels, the query likely doesn't need the hierarchical capacity. A concrete experiment: train a single model that can dynamically switch between 1, 2, 4, or all hierarchical levels based on an input-dependent policy, and measure whether the average FLOPs per query can be reduced while maintaining accuracy on a mixed-difficulty benchmark combining NIAH retrieval (requires hierarchy) with short-context commonsense reasoning (doesn't). This would directly test whether the hierarchical overhead can be made conditional rather than always-on.

Verifier-guided hierarchical attention: can a learned verifier improve which tokens get preserved at which granularity? The current framework uses a fixed structural rule (Fenwick partitioning) to determine which tokens fall into which buckets. An alternative approach would use a learned process reward model (PRM) or importance scorer that evaluates each token's expected future relevance and assigns it to an appropriate granularity level—tokens likely to be queried are retained in fine-grained buckets, while tokens unlikely to matter are aggressively coarsened. This connects to the example paper's use of PRMs for test-time search: just as a PRM can guide which solution beams to expand, an importance scorer could guide which tokens to preserve at high resolution. A concrete experiment: augment Log-Linear Mamba-2 with a lightweight scorer head that predicts, for each key-value pair, whether it will be needed for future retrieval queries (trained on a synthetic task where retrieval targets are known), and use this score to override the Fenwick partition—promoting unimportant tokens to coarser levels early and retaining important tokens at fine granularity. The evaluation would compare standard Log-Linear Mamba-2 against the importance-guided variant on NIAH tasks at 16K–64K context lengths, measuring both accuracy and the effective number of states maintained (a proxy for decoding memory). This would test whether the log-linear framework can be made content-adaptive in its hierarchical structure rather than purely position-based.

Stress-testing the quasi-H assumption: what breaks if the α gating violates nesting? The quasi-H matrix structure that enables O(log T) recurrence depends on the assumption that the temporal decay (the M_S mask from Mamba-2's gating) satisfies level-nesting—meaning the decay from position s to t is the same regardless of which Fenwick bucket contains s. This holds for the standard scalar α_t gating where the product ∏ α_k depends only on the positions, not the bucket assignment. An adversarial stress test would intentionally violate this assumption: create a synthetic variant of Mamba-2 where α_t depends on the bucket level (e.g., fine-grained buckets forget faster, coarse buckets forget slower) and measure whether the log-linear framework's performance degrades or whether the model can still learn to compensate. If performance collapses, it confirms that the quasi-H property is essential and architects must preserve it when designing extensions. If performance is unaffected, it suggests the quasi-H structure is sufficient but not necessary—the O(log T) recurrence might be achievable under weaker conditions than the paper identifies. The experiment would use the MQAR benchmark with controlled key-value pair counts and temporal distances, plus an analysis of the resulting M matrix's singular value spectrum to verify whether the effective rank structure still matches the quasi-H assumptions.

Practical Applications and Downstream Use Cases

Long-context on-device language models with memory-constrained inference. The primary practical promise of log-linear attention over softmax attention is O(log T) decoding memory rather than O(T), which directly enables longer context windows on memory-constrained devices (phones, wearables, edge accelerators) where a growing KV-cache would exhaust available RAM. For a 7B-parameter model with hidden dimension 4096 and 32 heads, the KV-cache for a 128K-token softmax attention context requires approximately 128K × 32 × 2 × 4096 × 2 bytes ≈ 67 GB (for FP16)—far exceeding on-device memory budgets. Standard linear attention would reduce this to O(1) (a single state matrix per layer), but at the cost of the recall degradation documented in Table 4. Log-linear attention with O(log 128K) ≈ 17 hierarchical levels would require roughly 17× the state size of linear attention—still sublinear and proportional to model dimension, not sequence length—while potentially preserving enough fine-grained access for practical retrieval tasks. The NIAH results (99.8% at 8K, 72.4% at 16K on S-NIAH-1) suggest this is viable for at least moderate context lengths, though the absence of decoding benchmarks means the actual memory footprint and latency remain unvalidated. A concrete deployment scenario: an on-device assistant that needs to answer questions about a 50-page document (roughly 30K tokens) that was processed at prefill time; log-linear attention would store a compact hierarchical summary rather than a full KV-cache, enabling the document to fit in the 4–8 GB RAM available on a flagship phone.

Efficient batch inference for retrieval-augmented generation (RAG) with long retrieved contexts. In RAG pipelines, a retriever fetches potentially long documents that are concatenated to the query before being fed to the LLM. With standard softmax attention, the inference cost grows quadratically with the total context length, making it expensive to include many or long retrieved passages. Log-linear attention's O(T log T) prefill cost and O(log T) decoding memory could enable including substantially more retrieved context within the same compute budget. A system processing thousands of RAG queries per hour on a fixed GPU budget could increase the average number of retrieved passages per query without increasing per-query latency or memory pressure. The paper's throughput benchmarks (Figure 4) show Log-Linear Mamba-2 custom kernel achieving approximately 1.4× the throughput of FlashAttention-2 at 16K sequence length and approximately 1.5× at 65K—this advantage would directly translate to higher RAG throughput or reduced GPU-hours per query. However, the practical realization of this benefit depends on whether the recall improvements in Table 4 translate to better downstream RAG accuracy (e.g., correctly answering questions that require synthesizing information from multiple retrieved passages, which stresses the model's ability to recall specific details from within long concatenated contexts). This has not been evaluated.

Training efficiency for long-document language modeling at academic and industrial scales. The O(T log T) training complexity of log-linear attention makes it feasible to train language models on substantially longer sequences than would be practical with quadratic softmax attention, even with FlashAttention. At sequence length 131K, the paper's throughput benchmarks show Log-Linear Mamba-2 achieving approximately 5K tokens/second versus 3K tokens/second for FlashAttention-2 (Figure 4, with batch size 2 and gradient checkpointing)—a 1.7× throughput advantage. For an organization training a model on long-document corpora (legal documents, scientific papers, code repositories) where the natural context unit is 100K+ tokens, this throughput difference could translate to training a model on full documents rather than truncated chunks within the same GPU budget, potentially improving the model's ability to learn document-level coherence and long-range dependencies. The per-position loss results (Figure 5) showing sustained lower loss across all 16K positions for log-linear variants suggest this benefit would compound over full training. The key caveat is the engineering complexity barrier (Section 5): the custom Triton kernels required to achieve these throughputs are non-trivial to implement and maintain, meaning this benefit is currently accessible primarily to organizations with strong systems engineering capabilities or willingness to adopt the authors' open-source implementation.

When to Prefer This Method

The paper explicitly positions log-linear attention as a middle ground between linear attention and softmax attention rather than a universal replacement for either. The decision framework is implicit in the paper's own results and claims:

• Prefer log-linear attention over standard linear attention when your deployment or training scenario involves context lengths beyond ~4K tokens and the task requires fine-grained retrieval of specific information from arbitrary past positions (the S-NIAH-1 result: 99.8% vs. 56.8% at 8K, Table 4). The 3% parameter overhead and modest throughput reduction (~10-15% vs. Mamba-2 at 16K, Figure 4) are likely justified if long-range recall matters. If your task is primarily short-context or requires only gist-level understanding of long contexts (where the fixed-size state suffices), the additional complexity may not be warranted given the similar short-range performance (Table 3: only +0.1 average commonsense reasoning points for Mamba-2).

• Prefer log-linear attention over softmax attention when memory-constrained decoding is essential and you cannot afford the O(T) KV-cache (e.g., on-device deployment, high-throughput serving with many concurrent requests). The O(log T) decoding memory claim is asymptotic and unbenchmarked, but the structural property is sound. If your primary concern is training throughput on sequences under ~8K, FlashAttention-2 is competitive or superior (Figure 4: FlashAttention-2 achieves ~22K vs. Log-Linear's ~23K tokens/sec at 8K, with much simpler implementation).

• Prefer log-linear attention over long-convolution models when you need both O(T log T) training and O(log T) decoding memory—long convolutions achieve the former but remain O(T) for decoding memory (Table 1). The sole Hyena comparison (WikiText PPL ~29 vs. <23, Section 4.2) suggests that achieving competitive performance with pure long-convolution architectures may require additional design work beyond simply matching the complexity class.

• Do not prefer log-linear attention when you have abundant memory for a KV-cache, your context lengths are modest (<4K tokens), and you can afford the O(T²) softmax attention cost—the Transformer baselines remain competitive or superior on most benchmarks (Tables 3, 4, 6, 7, 8; Figure 5), particularly with additional layers, and the engineering simplicity of using an off-the-shelf FlashAttention implementation is a significant practical advantage.