Attention: Undivided & Uncompressed

Transformers spend too much compute on tokens that barely affect the output. This post looks at attention from a systems angle: identifying which keys actually change the result, then auditing kernels and memory traffic to see why exact tiled I/O beats low-rank approximations.

Softmax attention is one formula and three objects. Tsai, Bai, Yamada, Morency, and Salakhutdinov¹ write it as a Nadaraya–Watson kernel smoother²³: a query is a location, a key is a sample point, a value is a label, and the output is a locally weighted mean. Katharopoulos, Vyas, Pappas, and Fleuret⁴, then Choromanski and coauthors⁵, keep that smoother and change the kernel so the weighted mean factors through a feature map. Sequence length $n$ then sits outside a product of size independent of $n$. Dao, Fu, Ermon, Rudra, and Ré⁶ keep the original kernel and change the traffic. Sequence length $n$ is no longer a FLOP count. It is the number of words that cross from HBM into SRAM.

Those papers all say they make attention cheaper. They stop agreeing as soon as you fix what $n$ is. A tighter approximation of the softmax kernel can still lose, on the wall clock, to a worse kernel that never writes the $n \times n$ score matrix, and it can lose to the exact kernel once that kernel is tiled. Paging, radix prefix trees, multi-head latent attention, and quantization arrive later and cut four other units. They are not substitutes. Paging is an allocator, not a compressor.

The rest of this post counts those units the way each paper counted them, then writes the bookkeeping that flips the advice.

Notation

Sequence length is $n$. Dao writes $N$, Katharopoulos writes $N$, Tsai writes $T$. One letter here. Head width is $d$. Query-head count is $h$. Key/value-head count is $g$, with $1 \le g \le h$. Layer count is $L$. Element width is $b$ bytes. On-chip SRAM holds $M$ scalars.

A query, key, and value at position $i$ are $q_i, k_i, v_i \in \mathbb{R}^{d}$. Stacked over the sequence they are $Q, K, V \in \mathbb{R}^{n \times d}$. The score matrix is $S = QK^{\top} / \sqrt{d}$. Row-wise softmax of $S$ is $P$. The head output is $O = PV$.

A kernel on the joint feature space is $k(\cdot,\cdot)$. A feature map is $\phi: \mathbb{R}^{d} \to \mathbb{R}^{r}$. Tsai’s mask, the set of keys visible to a query, is $M(x_q, S_k)$. SRAM block rows and columns are $B_r$ and $B_c$. A KV page holds $B$ tokens.

Cached width per token per layer is $w$. For multi-head attention $w = 2hd$. For grouped-query attention $w = 2gd$. For DeepSeek’s multi-head latent attention $w = d_c + d_{h}^{R}$, where $d_c$ is the joint KV latent and $d_{h}^{R}$ is the decoupled RoPE key.

Prefix overlap of a batch is $\rho = p / n$ when every request shares a prefix of $p$ tokens. Unique cached tokens in a batch of $R$ requests are then $p + R(n-p)$ if the tree hits, and $Rn$ if it misses.

Bytes, not parameters, are the serving currency. FLOPs stay in the training argument where Dao put them.

Smoother

Nadaraya and Watson, separately in 1964, estimated a regression function by a locally weighted average of observed labels. For a kernel $K_h$ at bandwidth $h$ the estimator is

Replace the location $x$ by a query, the sample point $x_i$ by a key, the label $y_i$ by a value, and $K_h$ by a positive similarity. The same fraction is attention. Tsai et al. write that fact as a definition, not a metaphor. Given a nonnegative kernel $k$, a set filter $M$, and a value map $v$,

Vaswani et al.⁷ sit inside that class with the asymmetric exponential kernel

The softmax is not an extra ingredient. It is the normalization that turns a positive kernel into a probability. If the kernel can be negative, the weights stop being a probability and the smoother is no longer a smoother. Tsai’s linear kernel failed to converge on both IWSLT’14 and WikiText-103 for that reason.

Two consequences fall out before anyone mentions GPUs.

The support of the smoother is the set $M(x_q, S_k)$. Encoder self-attention takes the whole set. Decoder self-attention takes a prefix. Sparse attention takes a subset of that prefix. Transformer-XL adds a memory set. Every later “efficient attention” paper is, in this language, a choice of kernel or a choice of support. Changing the support changes which labels enter the mean. Changing the kernel changes the weights. Neither change is a statement about memory traffic.

The kernel Tsai actually recommends is not the one serving stacks run. On IWSLT’14 an RBF kernel beat the exponential. A symmetric exponential, $W_q = W_k$, matched the asymmetric one while deleting a projection. Product kernels over content and position beat adding a positional vector into the same space. None of that is what FlashAttention implements. FlashAttention implements Vaswani’s kernel exactly. Already the objects have split: the statistician is choosing $k$, the systems paper is transporting a fixed $k$.

Bahdanau attention⁸ was already this smoother, with an additive score in place of a scaled dot product. The Transformer did not invent the weighted mean. It made the mean dense, multi-headed, and stacked, which is what turned the support size $n$ into the thing everyone later tried to delete.

Feature map

Katharopoulos et al. keep Tsai’s fraction and impose a finite feature map,

The associative rewrite is one line. The numerator $\bigl(\phi(Q)\phi(K)^{\top}\bigr)V$ is also $\phi(Q)\bigl(\phi(K)^{\top} V\bigr)$. Written per query,

Let $S = \sum_j \phi(k_j) v_j^{\top} \in \mathbb{R}^{r \times d}$ and $z = \sum_j \phi(k_j) \in \mathbb{R}^{r}$. Both sums are independent of the query. Softmax attention spends $\Theta(n^{2} d)$ arithmetic building $P$ and applying it. The feature-map form spends $\Theta(n r d)$ building $S$ and $z$, then $\Theta(n r d)$ applying them. If you count $n$ as arithmetic, and if $r \ll n$, you have won.

Causal masking does not restore the quadratic. The running sums

update in constant time. Autoregressive inference stores an $r \times d$ state and a normalizer, not a growing list of keys. Katharopoulos et al. write the layer as an RNN for that reason. On CIFAR-10 pixel generation they report 4,460 generated images per image from a cached-softmax baseline, at matched bits per dimension. That number is a decode-time constant-state number. It is not a prefill number, and it is not an HBM number.

The failure mode sits in $\phi$. The softmax kernel $\mathrm{SM}(x,y) = \exp(x^{\top} y)$ does not admit a finite-dimensional feature map. Katharopoulos et al. say so. They pick $\mathrm{elu}+1$ because it is positive, cheap, and trained stably on their tasks. It is a different kernel. Tsai already saw that kernel form moves BLEU and perplexity. Substituting $\mathrm{elu}+1$ for $\exp(\langle q, k \rangle / \sqrt{d})$ is not an approximation error you can drive to zero with more features. It is a model change.

Choromanski et al. try to stay with softmax. FAVOR+ draws positive orthogonal random features so that

The estimator is unbiased for the softmax kernel. Trigonometric random features are also unbiased and are the ones kernel papers used for years. They are the wrong ones here. Choromanski et al., Lemma 2, compute the mean squared errors. As $\mathrm{SM}(x,y) \to 0$, the trigonometric MSE diverges and the positive-feature MSE goes to zero. Attention matrices are full of near-zero entries. A feature map that misfires on those entries produces negative normalizers and broken rows. Positivity is not a nicety. It is what keeps the smoother a smoother under approximation.

Orthogonality of the features cuts variance further, for every $d > 0$, by an explicit gap in their Theorem 2. Uniform convergence of the approximated attention matrix, their Theorem 4, needs $m = \Theta\bigl(d\,\delta^{-2}\log(d^{3/4} R / \delta)\bigr)$ features on a ball of radius $R$. The feature count depends on $d$ and on how large queries and keys are, not on $n$. That is the sense in which Performer claims linear attention without assuming sparsity or low rank of $P$.

Linformer⁹ is the other low-rank story, and it is not this one. Wang, Li, Khabsa, Fang, and Ma project $K$ and $V$ along the sequence axis from $n$ down to a fixed $k$. They assume $P$ is approximately low rank. Performer assumes a kernel that is an expectation of rank-$1$ feature products. Katharopoulos assumes a kernel that is exactly a feature product and is not softmax. Three low-rank maps. Three different matrices being compressed. Calling all of them “linear attention” hides the matrix.

Qin et al.¹⁰, in The Devil in Linear Transformer, later showed that the accumulated state $S_i$ is poorly conditioned and that the attention distribution of $\mathrm{elu}+1$ is flatter than softmax. The algebraic win, $\Theta(nrd)$ instead of $\Theta(n^{2}d)$, survives. The smoother does not.

def linear_attn(phi_q, phi_k, v):
    # phi_q, phi_k: (n, r), v: (n, d)
    S = phi_k.T @ v          # (r, d), independent of each query
    z = phi_k.sum(axis=0)    # (r,)
    num = phi_q @ S          # (n, d)
    den = phi_q @ z          # (n,)
    return num / den[:, None]

That snippet is the entire arithmetic claim. It does not tile, it does not fuse, and it does not know what HBM is. Those absences are the next paper.

Traffic

Standard attention materializes $S$ and $P$ in HBM. For one head that is $\Theta(n^{2})$ extra memory, and it is also $\Theta(n^{2})$ extra traffic, because softmax is memory-bound and because the backward pass wants $P$. Dao et al. write the standard implementation’s HBM accesses as $\Omega(nd + n^{2})$. On an A100, HBM moves at 1.5–2.0 TB/s and SRAM, 192 KB per SM, moves at roughly 19 TB/s. Once arithmetic outruns HBM, the $n \times n$ matrix is not a FLOP problem. It is a bus problem.

FlashAttention keeps Vaswani’s kernel. The algorithm never writes $S$ or $P$ to HBM. Inputs are tiled into blocks that fit in SRAM. Softmax is computed online, following Milakov and Gimelshein, in the block-decomposed form Rabe and Staats used to get $O(n)$ working memory. For two consecutive score blocks $S^{(1)}, S^{(2)}$,

The running max $m$ and the running sum $\ell$ are $O(B_r)$ statistics. Rescaling by $\exp(m^{(1)} - m^{(2)})$ puts two partial softmaxes on a common footing. The output after the last block equals the full-row softmax, exactly. FlashAttention-2 delays the final division by $\ell$ until the end of the loop and stores only the log-sum-exp $L = m + \log \ell$, which cuts non-matmul FLOPs. The algebra is the same object.

IO complexity is not. With SRAM of size $M$ and $d \le M \le nd$, Dao et al., Theorem 2, give FlashAttention $O(n^{2} d^{2} M^{-1})$ HBM accesses. The proof is a pass count. A block of $Q$ of size $\Theta(M/d)$ rows stays on-chip while the kernel streams all of $K$ and $V$. Each such pass reads $\Theta(nd)$ scalars. The number of $Q$ blocks is $\Theta(nd / M)$. Multiply. Standard attention is stuck with $\Omega(n^{2})$ because it writes $S$.

For the $d$ and $M$ of an A100 head, $d^{2}/M$ is much smaller than 1, so the quadratic term shrinks by a large constant. Their microbenchmark on that GPU: 66.6 GFLOPs standard versus 75.2 GFLOPs FlashAttention, 40.3 GB HBM read/write versus 4.4 GB, 41.7 ms versus 7.3 ms. More FLOPs, less time. The extra FLOPs are the backward recomputation of $P$ from stored $O$ and $L$. Recomputation is cheaper than rereading an $n \times n$ matrix from HBM. That sentence is the paper. Gradient checkpointing in the Chen et al. sense trades time for memory. FlashAttention’s recomputation buys time because the scarce resource is the bus.

Proposition 3 is the limit. No exact-attention algorithm has $o(n^{2} d^{2} M^{-1})$ HBM accesses for every SRAM size in a nonempty range. Approximate attention can beat the bound by computing a different map. Exact attention cannot asymptotically beat FlashAttention over that range of $M$. Aggarwal and Vitter’s IO model is the parent of that style of lower bound.

Block-sparse FlashAttention multiplies the leading term by the nonzero block fraction $s$. Longformer, Sparse Transformer, and Reformer change Tsai’s set $M$. Once the kernel is fused, sparsity is an IO win in proportion to $s$. Without fusion, a sparse mask still writes enough intermediates to lose the bus.

FlashAttention-2¹¹ does not change the IO class. It parallelizes the sequence axis across thread blocks when batch $\times$ heads is too small to fill the SMs, and it splits $Q$ rather than $K,V$ across warps so the warps do not reduce through shared memory. On A100 the forward pass reaches 50–73% of peak FLOPs/s, against 30–50% for FlashAttention. Same smoother. Same exactness. Different occupancy.

Disagreement

Hold the kernel fixed and count $n$ two ways.

Tsai, Katharopoulos, and Choromanski count $n$ as the support of a smoother, or as the inner dimension of a product. Advice: replace $k$ by a factorizing kernel, or estimate $k$ with $r$ features, and arithmetic drops from $\Theta(n^{2}d)$ to $\Theta(nrd)$. At decode, store $S \in \mathbb{R}^{r \times d}$ instead of $K,V \in \mathbb{R}^{n \times d}$. The win is real in that accounting. It is also a different function unless the feature map is an exact finite factorization of softmax, which it is not.

Dao counts $n$ as HBM words moved by the exact function. Advice: do not write $S$. Tile, fuse, recompute. Arithmetic may go up. Wall-clock goes down while the function stays put.

Those cannot be the same advice. A better kernel approximation can still lose to a worse one that is IO-aware, and it can lose to the exact kernel once the exact kernel stops touching HBM.

Dao et al. already ran the comparison. On Long-Range Arena, sequence lengths 1K–4K, against a tuned Transformer baseline:

• FlashAttention, exact softmax: 2.4$\times$ speedup, average score 59.8 against the baseline 59.3.
• Katharopoulos linear attention: 2.3$\times$, 59.6.
• Performer: 1.8$\times$, 58.9.
• Linformer: 2.5$\times$, 54.9.

Linformer is the only one in that list that is faster, and it pays for the speed in score. Performer is the better softmax approximation. It is slower than the ELU linear map and slower than exact FlashAttention. The usual story, “approximate the quadratic and you will go faster,” fails on the number the hardware actually bills.

The crossover they plot is the other half of the disagreement. Up to length 512, FlashAttention is faster than the approximate methods they tested. Past about 1K, some approximations, Linformer in particular, overtake it on runtime. That is allowed. FlashAttention’s remaining traffic is still $\Theta(n^{2} d^{2} / M)$. Linear arithmetic is $\Theta(nrd)$. For large enough $n$, any method that never forms an $n \times n$ object wins the asymptotic, including a bad kernel. The LRA lengths were not large enough for Performer to collect that win, and they were large enough for Linformer to collect it at a quality cost.

If you counted $n$ as FLOPs, you would have shipped Performer, or $\mathrm{elu}+1$, and expected the ranking to follow approximation quality. If you counted $n$ as HBM words of the exact map, you would have shipped FlashAttention and treated kernel change as a last resort for lengths where $n^{2} d^{2}/M$ still dominates. The papers do not disagree about algebra. They disagree about which $n$ is on the invoice.

Scatterbrain later multiplied a sparse term by a low-rank term and called the product a better approximation of softmax than either factor. That is a kernel paper. It does not restore IO-awareness. A fused Scatterbrain would be a different object again.

I am going to count serving cost as a product of four factors that the 2023–2026 systems papers keep separate. That is a choice. Almost no paper writes the product. The product is what makes paging, radix trees, latent heads, and quantization refuse to substitute for one another.

Units

Decode does not rebuild $S$. Decode loads every cached key and value for every new query. Pope, Shazeer, and the later serving papers all say the same thing: the step is memory-bound in the cache, not in the matmul. Williams, Waterman, and Patterson’s roofline¹² is the right picture. Arithmetic intensity of a decode step against the cache is $O(d / (w b))$ FLOPs per byte, which for realistic $w$ sits under the ridge point of an A100 or H800.

Four papers then cut four different factors of the same bill.

Kwon et al., PagedAttention.¹³ Prior engines reserved a contiguous $n_{\max}$ slab per request. On their traces, 20.4% to 38.2% of that slab held live tokens. The rest was reserved future slots, internal fragmentation from $n \ll n_{\max}$, and external fragmentation from variable slab sizes. PagedAttention breaks the cache into pages of $B$ tokens, maps logical pages to physical pages through a block table, and allocates on demand. Internal waste is at most one partial page per sequence. External waste is zero because every page is the same size. Copy-on-write lets beam candidates and parallel samples share a page until a write. Throughput against FasterTransformer and Orca: 2–4$\times$ at matched latency, larger on long sequences and on beams.

Paging does not change $w$. It does not change $b$. It does not change how many unique tokens exist. It changes how many slots you pay for per live token. That ratio goes from something like 3–5 down to just over 1. The algorithm in the kernel is still softmax attention, walked page by page instead of along a contiguous pointer.

Zheng et al., RadixAttention.¹⁴ After a request finishes, vLLM’s original default frees its pages. SGLang keeps the pages in a radix tree keyed by the token sequence. A node owns the pages for its edge label. A new request walks the tree, reuses the longest matching prefix, and branches at the first mismatch. Eviction is LRU on leaves, with a reference count so in-flight nodes stay pinned. The paper’s point is automatic reuse across chained calls, few-shot prefixes, tree-of-thought forks, and multi-turn chat, without the user marking the prefix. They report up to 6.4$\times$ end-to-end on those workloads against systems that drop the cache at request end.

RadixAttention does not change $w$ or $b$. It changes the number of unique tokens stored from $Rn$ to $p + R(n-p)$ when a prefix of length $p$ is shared. The tree is an index over pages. SGLang runs paged kernels underneath the tree. The two papers are stacked, not paired as alternatives.

DeepSeek-AI, MLA.¹⁵ Multi-head latent attention trains a down-projection $W^{DKV} \in \mathbb{R}^{d_c \times d}$ so that a token’s keys and values are functions of one latent $c_t^{KV} \in \mathbb{R}^{d_c}$. At inference the cache is $c_t^{KV}$ plus a shared RoPE key $k_t^{R} \in \mathbb{R}^{d_h^{R}}$. RoPE cannot sit inside the latent. A rotary matrix that depends on the current query position would fall between $W^{Q}$ and $W^{UK}$ and would block absorption, forcing a recompute of every prefix key. Decoupled RoPE is the workaround. DeepSeek-V2’s cache per token is $(d_c + d_h^{R})L$ elements, against $2hdL$ for MHA. Their Table 1 states that this width equals GQA with 2.25 groups, while quality matches or beats MHA. Against DeepSeek 67B they report a 93.3% KV-cache cut and a 5.76$\times$ generation-throughput lift on the deployed H800 node, after FP8 weights and a 6-bit-average cache quant.

MLA changes $w$. It does not allocate pages and it does not find shared prefixes. It is a trained compressor of hidden width. You cannot uptrain it with Ainslie et al.’s 5% recipe¹⁶. GQA mean-pools existing heads. MLA needs the latent and the decoupled RoPE trained in.

Bit-width. KIVI¹⁷, KVQuant¹⁸, and the DeepSeek-V2 serving stack change $b$. Two-bit keys with a per-channel codebook, four-bit fused kernels, six bits on average: all of these keep the token set and the hidden width and spend fewer bits per element. Quantization is near-lossless in the sense of Colaco and Lahjouji: the map is reversible up to a bounded perturbation, not up to a dropped token.

Colaco and Lahjouji (2026)¹⁹ write the serving stack into a rate–distortion problem. History $H$ is compacted to $Z$ at rate at most $B$, then used to answer $Q$. Lossless reuse (PagedAttention, RadixAttention, prefix caches) is the zero-distortion corner. Their sentence is the one that matters here: those methods do not spend fewer bits, they amortize bits already spent, and the gains collapse without prefix overlap.

One table, one units convention. $n$ is tokens in the sequence. $R$ is batch requests. Waste $\omega$ is allocated slots per live token.

The product that serving actually pays, per live unique token, is $\omega \cdot w \cdot b$. Prefill additionally pays FlashAttention traffic on whatever tokens are not already in the tree. No factor in that product is a synonym for another factor.

Bytes

Write the cache of one request, one model, $n$ tokens already seen.

The factor of two on the first two lines is key and value. MLA’s latent already jointly encodes both, so the two disappears and a small RoPE key remains.

Ainslie et al., GQA¹⁶ put GQA between MHA ($g = h$) and MQA ($g = 1$). Going from MHA to MQA cuts the cache by $h$. They picked $g = 8$ on T5-XXL as the knee: quality near MHA, speed near MQA. Shazeer’s MQA paper²⁰ is the bandwidth argument those numbers sit on. Loading $K,V$ each decode step is a memory-bandwidth tax. Fewer KV heads, less tax. Quality is the residual.

DeepSeek-V2 publishes the MLA constants: $h = 128$, $d = 128$, $d_c = 512$, $d_h^{R} = 64$, $L = 60$. Then

Per token in bf16, $b = 2$,

Table 1 of DeepSeek-V2 equates 576 elements with GQA at 2.25 groups, because $2 \cdot 2.25 \cdot 128 = 576$. That is a width match, not a quality match. GQA-2 would store 512 elements and would not carry decoupled RoPE. The 2.25 is what you get if you insist on describing MLA as “GQA with a fractional group.” It is a conversion, not an identity of architectures.

Llama 2 70B, from Touvron et al.²¹, is the GQA example people actually deploy: $L = 80$, $h = 64$, $g = 8$, $d = 128$. In bf16,

An 8$\times$ cut, exactly $h/g$. No kernel was approximated. No page was allocated. The projection matrices for $K$ and $V$ shrank, and the cache shrank with them.

Put a page size $B$ on top. Kwon et al. allocate $\lceil n / B \rceil$ pages. Bytes charged become

$\omega - 1 < B/n$. For $B = 16$ and $n = 2048$, $\omega - 1 < 0.008$. For a reserved slab of $n_{\max} = 2048$ wrapping a true length of 200, $\omega = 10.24$. That is the fragmentation PagedAttention deletes. It is not a 10$\times$ compressor. It is a 10$\times$ less wasteful allocator on that request.

Quantization multiplies by $b'/b$. A 2-bit cache against bf16 is a factor of 8 on $b$, times whatever residual window you keep in 16-bit. KIVI keeps such a window. The factor is not 8 on the whole cache unless the window is empty.

The four factors compose. A paged, radix-indexed, MLA, 4-bit cache of unique tokens $u$ costs $u \cdot L \cdot (d_c + d_h^{R}) \cdot b_{4}\cdot \omega$. Drop any one factor and the product grows by that factor. There is no identity that turns a page table into a latent, or a latent into a prefix hit.

Collapse

Let $R$ requests share a prefix of length $p$ and then diverge. A flat cache stores $RnLwb$ bytes. A radix tree stores

The fractional saving is $(1 - 1/R)\rho$. Three ways it is zero.

If $\rho = 0$, the tree is a forest of $R$ disjoint paths. Indexing them does not delete a byte. Zheng et al. already see this in their zero-shot GSM-8K setting: the shareable prefix is short, and the throughput gap over vLLM shrinks relative to the five-shot case.

If $R = 1$, there is no second request to share with. Multi-turn helps only after turn two, and only for the prefix that actually repeats.

If the scheduler thrashes, $\rho$ on paper is not $\rho$ in SRAM. Zheng et al. add a cache-aware sort by matched prefix length because FCFS interleaves unrelated prompts and evicts the trunk. Colaco and Lahjouji’s collapse statement is this math plus that operational clause. Paging still wins in all three cases, because $\omega$ does not depend on $\rho$. The allocator keeps working when the compressor-by-amortization has nothing to amortize.

A worked miss. $R = 32$, $n = 2048$, $p = 0$, Llama 2 70B GQA bf16. Cache is $32 \cdot 2048 \cdot 327680 \approx 21.5$ GB either way. Radix adds a walk and a lock. Paging still avoids the $n_{\max}$ slab.

A worked hit. Same batch, $p = 1536$ (a long system prompt). $\rho = 0.75$. Unique tokens drop by $(1 - 1/32)\cdot 0.75 = 0.727$. Cache falls from 21.5 GB to about 5.9 GB. Prefill arithmetic on the 1536-token trunk runs once. That is the SGLang workload: few-shot, agents that append observations, forks that share a stem.

vLLM’s later prefix-caching hash table hits the same $\rho$ term without a tree. The radix tree is the better index when prefixes nest and branch, which is Zheng et al.’s tree-of-thought and beam case. A flat hash still saves $(1-1/R)\rho$ on a single global prefix. Neither structure compresses a token. Both refuse to store it twice.

H2O, StreamingLLM, and SnapKV look adjacent and are not. They drop tokens. Colaco and Lahjouji call that irreversible, query-agnostic compaction. The rate–distortion bound they write,

applies to eviction and does not apply to paging. Paging’s $B$ in their notation is not smaller than the original cache’s information. The pages still hold the same keys and values. Quest keeps every page and reads a query-conditioned subset. That cuts bandwidth, not capacity, and keeps reversibility. Mixing Quest’s hit rate with PagedAttention’s $\omega$ is another units error.

Open

Five problems sit on the disagreement, not on the architecture catalog.

When does a worse kernel beat exact tiled softmax? Dao et al. saw Linformer overtake FlashAttention past about 1K on their A100 benchmark, at a quality cost. The crossover as a function of $M$, $d$, $r$, and the kernel gap $\|P_{\phi} - P_{\mathrm{SM}}\|$ is not written down. Hardware with more SRAM moves the crossover to the right. A fused Performer with orthogonal features and a Flash-style online normalizer is a different point again. Nobody has published that kernel’s IO in Dao’s accounting. Until someone does, “linear attention is faster at long $n$” is an arithmetic claim pretending to be a wall-clock claim.

What is the parameterized IO lower bound? Proposition 3 rules out beating $n^{2}d^{2}/M$ for every $M$ in a range. A bound that keeps $M$ as a parameter, in the Flum–Grohe sense Dao points at, is open. FlashAttention-2’s occupancy tricks do not touch it. Multi-GPU attention adds a third memory, the network, that neither paper prices.

Do the four serving factors compose cleanly? Width, bits, pages, and unique tokens multiply in the byte formula. Errors do not. A 2-bit MLA latent, paged, with a 90% prefix hit, has no published joint distortion. Palu and GEAR compose rank and bits post hoc on MHA caches. TransMLA tries to convert GQA checkpoints into latents. Colaco and Lahjouji flag composition as uncharted and treat preprint numbers as provisional. A clean falsifier: a published, rerunnable grid on one model where the product of single-axis quality drops does not predict the joint drop.

Where is the $\rho$ threshold? Radix pays a walk, a lock, and CPU-side tree memory. Against a paged baseline with no prefix cache, the byte win is $(1-1/R)\rho$. The compute win is the avoided prefill on $p$ tokens, once per distinct trunk. At small $\rho$ the bookkeeping can exceed the hit. SGLang’s own zero-shot versus few-shot gap is evidence that the threshold is workload-visible, not a constant. A serving paper that plots throughput against measured $\rho$ on a single engine, rather than against named apps, still is not the default.

Is decode-time linear attention a fifth factor or a different model? Katharopoulos’s $S_i \in \mathbb{R}^{r \times d}$ replaces the cache instead of shrinking it. That is architectural compaction in Colaco and Lahjouji’s taxonomy, uniformly lossy, fixed size, trained. The 2026 bound says a state of $s$ bits cannot answer a query that needs more than $s$ bits, so multi-key retrieval should cliff. Exact paged softmax should degrade more slowly. That prediction is testable on existing linear-attention checkpoints. It is not settled by CIFAR-10 image generation.

A dialogue between two engineers shipping this stack, late:

— “Ship Performer. The kernel MSE goes to zero with $r$.”

— “On LRA it lost to the exact kernel, and the exact kernel was the one that did not write $S$. Count HBM.”

— “Then page the cache and stop thinking about kernels.”

— “Page what? If $\rho = 0$ you allocated well and you compressed nothing. MLA is the width cut. Four bits is the bit cut. The tree is an index. Mixing them is how we ended up with a 2-bit page table as a research idea.”

— “So we just multiply the four factors.”

— “Multiply the bytes. Do not multiply the papers.”

Fit

FlashAttention remains the right default wherever the function has to stay Vaswani’s kernel and $n$ is in the range where $n^{2}d^{2}/M$ still dominates the bus. That includes training, prefill, and any decode kernel that still attends to an explicit cache. The LRA table is the evidence. The A100 microbenchmark is the mechanism. FlashAttention-2 is the same claim with occupancy repaired. Both are falsified on a device whose SRAM is large enough that exact attention becomes compute-bound and a cheaper kernel wins on arithmetic, or on lengths where even $n^{2}d^{2}/M$ loses to $\Theta(nrd)$ at a quality budget you can tolerate. Path-X at 16K and Path-256 at 64K, solved first by FlashAttention and block-sparse FlashAttention, are the opposite falsifier for “we had to approximate to go long.”

GQA remains the right width cut when you cannot retrain. Ainslie et al. gave the uptraining recipe and the $g = 8$ knee on T5. Llama 2 70B shipped it. MQA is the $g = 1$ end and is the quality risk they documented, including fine-tune instability on long inputs. MLA is the right width cut when you can train the latent and the decoupled RoPE, and when you are willing to live with absorption tricks in the inference kernel. DeepSeek-V2’s 576-versus-32768 width ratio is the number. The 93.3% figure is against their 67B MHA model, not against a matched-width GQA trained from scratch on the same 8.1T tokens. That comparison is still missing in public.

Paging remains the right allocator for every cache shape above. The 20.4%–38.2% utilization number is the reason. It does not take a position on kernels. RadixAttention remains the right index when measured $\rho$ is high and nested. Colaco and Lahjouji already wrote the collapse: lossless reuse wins only when prefixes overlap. A day’s traffic of unique prompts is a complete empirical falsifier. Quantization remains the bit cut, reversible in their sense, and it stacks with the others until someone publishes the joint distortion that says it does not.

The kernel line is the one that did not become the serving stack. Tsai’s product kernels, Katharopoulos’s ELU map, Choromanski’s positive features, Qin’s diagnosis of the linear-attention state, and every later state-space model are still the right tools when you want a different function of the past: constant decode state, a non-exponential kernel, a smoother whose support is not the full prefix. They are the wrong tools for “make softmax faster” once Dao has counted the bus. The disagreement was never about whether feature maps are legal. It was about whether the object you sped up is the object you claimed to keep.

If you need a single measurement that would force a rewrite of this post, run one engine, one model, three axes. Axis one: exact Flash-style softmax versus a fused FAVOR+ kernel at equal $r$, report HBM words and wall-clock against $n$, not FLOPs. Axis two: paged cache with the radix tree forced off, sweep fragmentation by varying $n / n_{\max}$, confirm that throughput tracks $\omega$ and does not track $\rho$. Axis three: the same paged engine with the tree on, sweep $\rho$ at fixed $\omega$, confirm that the extra win is $(1-1/R)\rho$ until the tree’s own overhead eats it. If axis one ranks Performer above Flash at moderate $n$ on current SRAM, Dao’s invoice is stale. If axis two shows a paging win at $\omega = 1$, paging is doing something other than allocation. If axis three shows a radix win at $\rho = 0$, the tree is not an index. Until one of those happens, the papers stop agreeing exactly where the units change.

References