Log-linear attention, and what a logarithm buys

This paper reads Log-Linear Attention by Han Guo, Songlin Yang, Tarushii Goel and Yoon Kim at MIT, Eric P. Xing at Carnegie Mellon, and Tri Dao at Princeton. The work and every figure, table and number below are theirs. What is ours is the reading: which result matters, what the complexity claim does and does not buy, and where the mechanism should be expected to fail. We have not trained or reproduced any of it.

Linear attention gave up something specific to get its speed. It compresses the whole prefix into one fixed-size state, so the cost of a step does not grow with the length of the history. That is the entire win, and it is also the entire limitation: a state of fixed size cannot hold an arbitrarily long context at arbitrary resolution.

This paper asks what happens if the number of states grows, but slowly. The answer is O(T log T) compute and O(log T) memory for training, and O(log T) time and memory per step at decode, against O(T) and O(1) for linear attention and quadratic compute with linear memory for softmax.

1. The framing that makes the mechanism obvious

Section 2 of the paper puts a wide class of attention variants into one form: P = A ⊙ M, O = PV, where A carries the query-key interaction and M is a causal masking matrix. The authors are explicit that the structure of M is what decides complexity, not the removal of softmax:

Using an unstructured M (e.g., a random lower-triangular matrix) degrades both compute and memory complexity to softmax attention-levels, despite the absence of softmax.

Linear attention is M lower-triangular all-ones. Mamba-2 is M 1-semiseparable, every lower-triangular submatrix of rank at most one. Gated DeltaNet differs in how it structures A, not M. Softmax is M with no exploitable structure at all.

Seen from decode time, each choice of M is a way of cutting the prefix into buckets. Softmax keeps t buckets of size one, which is the KV cache. Linear attention keeps one bucket of size t. Both store a fixed-size state per bucket, so the bucket count is the memory.

2. What structure buys the middle

Log-linear attention cuts the prefix with a Fenwick tree: greedily subtract the largest power of two that fits in what remains. The cut is driven by lssb(t) = max{ℓ | 2^ℓ divides t}, the least significant set bit of t. The result is at most L = ⌈log₂ t + 1⌉ + 1 disjoint buckets, where bucket ℓ has size 2^(ℓ-1) for ℓ ≥ 1 plus a sentinel bucket of size one.

Each bucket gets its own recurrent memory S_t^(ℓ) ∈ ℝ^(d×d). The output sums over levels, weighted by a learned nonnegative coefficient per level:

o_t = Σ_ℓ λ_t^(ℓ) q_tᵀ S_t^(ℓ)

The λ_t^(ℓ) are a linear function of the current input x_t, computed per head by a linear layer on top of the hidden states. That is the whole addition. It costs under 3 per cent extra parameters for Mamba-2 and under 0.4 per cent for Gated DeltaNet.

The decode recurrence is the Fenwick update, written out. The outer product v_t k_tᵀ enters level zero. Every level up to lssb(t) is merged and promoted one level coarser. When t crosses a power of two the hierarchy grows a bucket. Nothing is recomputed, and the live state is O(log T).

The authors then name the object: M is a lower-triangular HODLR matrix, hierarchically off-diagonal low-rank, and attention here is structured matrix multiplication against a hierarchical matrix. They call their restricted version a quasi-H matrix, a class between general hierarchical and semiseparable matrices, chosen to admit an O(log T)-space recurrence. This is worth borrowing even if you never use the architecture. It places sequence models on a lattice by the structure of one matrix, which organises the field better than a list of architecture names.

3. Where the log-linear cost is actually earned

A hierarchical mask is useless if it cannot be trained with matmuls. Section 3.3 is the answer and it is the strongest engineering in the paper.

For chunk size C, the mask decomposes as M = D + Σ_{ℓ ≥ ℓ_C} M^(ℓ). D is block diagonal with T/C causal blocks of size C × C, absorbing every level finer than the chunk. Each block costs O(C²), so the intra-chunk stage is O(TC). The remaining levels reduce to scaled sequentially semiseparable matrices, which means each one is a call to the state-passing primitive the base model already has. There are O(log(T/C)) such calls, each O(T) in time and memory, so the inter-chunk stage is O(T log(T/C)).

The authors describe this as extending the parallel prefix scan to a hierarchy: O(log T) independent scans, one per memory level, each implementable with a standard Blelloch scan. The consequence is the reason the paper generalises at all. Any linear attention layer with structured memory and a chunkwise primitive can be lifted by composing its temporal mask with M, because the elementwise product of a semiseparable matrix and a hierarchical matrix is still hierarchical.

In Triton on an H100, batch size 2, 48 heads, head dimension 64, state dimension 128, chunk size 64, the custom log-linear Mamba-2 kernel beats FlashAttention-2 on forward plus backward beyond 8K tokens, and full-model training throughput passes the Transformer at 32K. Those two crossover points are the honest version of the efficiency claim, and they are later than the asymptotics suggest.

4. The numbers

Pretraining: 50B tokens of Long-Data-Collections at 16K sequence length, 21 layers, hidden size 1536. Transformer 693M parameters, Mamba-2 802M, Gated DeltaNet 793M, with log-linear variants at 825M and 796M and a parameter-matched 24-layer Transformer at 778M.

Perplexity improves in both lifts, by 0.33 and 0.28 on WikiText. The commonsense average moves 0.1 for Mamba-2 and 0.5 for Gated DeltaNet. The authors say plainly why they do not expect more: these are short-context tasks and therefore largely insensitive to state size.

The long-context results are where the state size should matter, and they do. On RULER single-needle passkey retrieval, Mamba-2 at 8K goes from 56.8 to 99.8 and at 16K from 21.6 to 72.4. On multi-key line retrieval at 4K, 27.2 to 43.2. Log-linear Mamba-2 improves on 8 of 9 single-needle metrics and 8 of 9 multi-needle metrics; log-linear Gated DeltaNet improves on all 9 multi-needle metrics.

On MQAR over five seeds, Mamba-2 at dimension 16 goes from 46.9 to 55.9. The standard deviations are 2.3 and 9.1. That interval overlaps, and the paper prints both numbers, which is the right thing to do.

5. Where it beats neither end

The appendix carries the result we think is most informative, and it is a regression.

On the in-context retrieval tasks of Table 7, at 16K input, log-linear Mamba-2 is worse than Mamba-2 on SWDE (30.6 down to 28.5) and markedly worse on FDA (21.3 down to 16.6). Gated DeltaNet improves on SWDE at 16K, 27.8 to 35.1, and is flat on FDA at 30.5, so it does not regress where Mamba-2 does.

Our reading, which the authors do not state. The Fenwick partition is not a neutral compression. It is a prior that distant tokens matter at lower resolution, and the tasks where log-linear loses are exactly the tasks where that prior is false. FDA and SWDE are extraction: find one exact old string. Coarse buckets are the wrong representation for that, because thousands of distant tokens share a single d × d state. NIAH rewards knowing roughly where to look; extraction rewards precision about an arbitrary position. The paper frames the inductive bias as a limitation that "may not be optimal for all applications". We would put it more strongly: the sign of the gain is predictable from whether the task's answer is recent, and a log-linear model is therefore not a drop-in upgrade over a linear one.

Our second position. The phrase "balances linear attention's efficiency and the expressiveness of softmax attention" oversells the geometry. There is a setting that collapses to linear attention, when all λ_t^(ℓ) are equal or linearly related across time. There is no setting that recovers softmax, and the paper does not claim one. Log-linear attention is not a dial between the two ends. It is linear attention with a multi-resolution recency prior and one extra scalar per level per head. That is a real contribution. It is not an interpolation.

Our third position, about deployment. O(log T) memory is an asymptotic win over softmax and a constant-factor loss against linear attention, and the constant is the part you pay. At 128K context the bucket count from the paper's own formula is 19, so the recurrent state is roughly 19 times a linear model's. That is still far under a softmax KV cache at the same length, but a team choosing a serving architecture is usually comparing cheap against cheap. The arithmetic there is ours and approximate; the paper reports no inference memory table, which is a gap given that O(log T) decode memory is one of its two headline claims.

6. What the paper does not establish

The authors are unusually direct about this, and it is worth repeating rather than softening.

• The 700M to 800M models were run once each. No seeds, no error bars at scale. The perplexity gains of 0.33 and 0.28 are single-run differences.
• The λ parameterization was never tuned at scale, by their own statement, for lack of compute. They tuned it on MQAR only. So the headline architecture is being judged at its untuned default.
• There is no ablation isolating the components. The extra parameters, the per-level states and the Fenwick structure arrive together. Nothing separates the gain from O(log T) states from the gain from a slightly wider model.
• The gap to the Transformer remains. Their words: a significant performance gap across all benchmarks. Log-linear Gated DeltaNet beats the layer-matched Transformer on every metric in Table 6 and the parameter-matched one on half, but the Transformer wins the retrieval tables outright, often by 20 points or more.
• Two architectures, both chosen for a reason. Mamba-2 and Gated DeltaNet both have mature chunkwise primitives to reuse. xLSTM and MesaNet are named as untested.
• The engineering cost is real and unquantified. Intra-chunk operations need bespoke kernels, the backward pass needs hand-derived gradients for the λ terms, and the paper says these intra-chunk mechanisms are the primary factor behind the speed differences without putting a number on them.

One small thing a careful reader will notice: Table 3 reports 21.45 and 18.09 for log-linear Gated DeltaNet where Table 6 reports 21.44 and 18.08. A rounding difference, not a result, but we would rather flag it than quietly pick one.

7. Why this matters outside a lab

The transferable idea is not the architecture. It is that the cost of a sequence model is a property of one matrix's structure, and that you can move along a spectrum of costs by changing that structure rather than the model family. We have made the adjacent argument about where capacity goes in Kimi K3: where the compute went and about conditional compute in Mixture of experts: what actually changed. The attention operator this is all still a variation of is covered in Attention Is All You Need, nine years on.

The second idea is about memory. Log-linear attention is a hierarchy of summaries at different resolutions, recent context sharp and old context compressed. That is the same shape as the systems argument in Memory leaves the model: when a fixed state cannot hold the history, the fix is tiered storage, not a bigger state. The architectural answer and the systems answer converge.

And the methodological note we made in ViT-5, and what vision should not borrow from language applies here. The components arrive as a bundle and are measured as a bundle. The result is believable and the mechanism is clean. Nobody yet knows which part of it is doing the work.

8. Sources

1. Han Guo, Songlin Yang, Tarushii Goel, Eric P. Xing, Tri Dao and Yoon Kim, Log-Linear Attention. Every figure, table, quotation and number above is from this paper.
2. Tri Dao and Albert Gu, Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality, the Mamba-2 paper and the source of the semiseparable framing.
3. Songlin Yang, Jan Kautz and Ali Hatamizadeh, Gated Delta Networks: Improving Mamba2 with Delta Rule, the second architecture lifted here.
4. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas and François Fleuret, Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, the linear attention formulation being generalised.
5. Tri Dao, FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning, the kernel baseline in the throughput comparison.
6. Cheng-Ping Hsieh et al., RULER: What's the Real Context Size of Your Long-Context Language Models?, the source of the NIAH tasks in Table 4.
7. Simran Arora et al., Zoology: Measuring and Improving Recall in Efficient Language Models, where MQAR and the recall limitation of fixed-state models come from.
8. Ashish Vaswani et al., Attention Is All You Need, the softmax attention at the expressive end of the spectrum.

We have not trained, reproduced or benchmarked log-linear attention, and we have not run the authors' Triton kernel. We read the arXiv HTML of version 3 and worked from its tables; we did not inspect the released code, so we cannot speak to whether the kernel behaves as described. The crossover points at 8K and 32K are read from the text, not from the figure, because we did not extract values from the plot. Every number is the authors'. The three positions in section 5 and the whole of section 7 are ours, and they are arguments rather than findings, so argue with them.

This note sits in our Research track, alongside the foundation models and GPU acceleration threads. The full library is at Research.