EntmaxKV: Support-Aware Decoding for Entmax Attention

Gonçalo Duarte, Miguel Couceiro, Marcos V. Treviso · 2026

Read EntmaxKV: Support-Aware Decoding for Entmax Attention by Gonçalo Duarte, Miguel Couceiro, Marcos V. Treviso (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21649.txt.

Introduction

Gonçalo Duarte and co-authors introduce EntmaxKV, support-aware decoding. Long context decoding is limited by KV-cache traffic. Existing sparse methods target softmax attention, whose dense tails mean any truncation discards nonzero probability mass. Entmax instead produces exact zeros, turning sparse reading into support recovery: if candidates contain the entmax support, reading stays exact. EntmaxKV exploits sparsity before KV pages load, combining query-aware page scoring and support-aware candidate selection. It matches full-cache entmax on a small fraction of the cache.

Catalog record

CREATORGonçalo Duarte, Miguel Couceiro, Marcos V. Treviso
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54876
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21649

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

EntmaxKV: Support-Aware Decoding for Entmax Attention Gonçalo Duarte, Miguel Couceiro, Marcos V. Treviso Abstract Long-context decoding is increasingly limited by KV-cache memory traffic since each generated token attends over a cache whose size grows linearly with context length. Existing sparse decoding methods reduce this cost by selecting subsets of tokens or pages, but are designed for softmax attention, whose dense tails make any truncation discard nonzero probability mass. In contrast, α \alpha -entmax produces exact zeros, turning sparse decoding from dense-tail approximation into support recovery: if the selected candidates contain the entmax support, sparse decoding remains exact. While recent entmax kernels enable efficient training, they do not address the autoregressive decoding bottleneck, where dense inference still streams the full KV cache before sparsity is known. In this work, we introduce EntmaxKV, an entmax-native sparse decoding framework that exploits sparsity before KV pages are loaded. EntmaxKV combines query-aware page scoring, support-aware candidate selection, and sparse entmax attention. We analyze truncation error through the dropped probability mass δ \delta , showing that output error is controlled by δ \delta and vanishes when the entmax support is recovered. We further introduce a Gaussian-aware entmax selector that estimates the entmax threshold from lightweight page statistics, adapting the selected budget to the score distribution. Empirically, EntmaxKV drops less probability mass, retains more support tokens, and achieves lower output error than softmax-based sparse decoding at matched KV budgets. On long-context and language modeling benchmarks, it closely matches full-cache entmax while using a small fraction of the KV cache, achieving up to 3.36 × 3.36\times (softmax) and 5.43 × 5.43\times (entmax) speedup over full attention baselines at 1M context length. 1 1 1 Code available at: https://github.com/deep-spin/entmaxkv . 1 Introduction Recent large language models (LLMs) support increasingly long context windows, with some systems extending to hundreds of thousands or even millions of tokens [ 13 , 20 ] . This capability enables applications that require reasoning over long documents, code repositories, conversation histories, and retrieval-augmented inputs. However, long contexts come at substantial computational cost, especially during autoregressive decoding: at each generation step, the model must attend over the key-value (KV) cache containing all previous tokens. As a result, long-context decoding is often memory-bound, and KV-cache reads can account for over half of the per-token latency [ 19 ] . A natural way to reduce this cost is to avoid reading the entire cache. Existing sparse decoding methods select only a subset of tokens, blocks, or pages for attention. Some approaches permanently discard tokens from the KV cache using positional, learned, or attention-based heuristics [ 23 , 22 , 15 , 10 ] . Others keep the full cache available but select a query-dependent subset at each decoding step, using page-level bounds, clustering, or adaptive thresholds to identify the tokens that matter for the current query [ 19 , 11 , 18 , 14 , 24 ] . These methods exploit the empirical observation that attention is often concentrated on a small subset of the context. However, most sparse decoding methods are designed around softmax attention. Since softmax assigns strictly positive probability to every token, any truncation of the KV cache necessarily discards nonzero probability mass. Thus, sparse decoding under softmax attention is inherently a dense-tail approximation problem. In this work, we revisit sparse decoding through the lens of \alpha -entmax attention [ 16 , 1 ] . Unlike softmax, \alpha -entmax produces input-dependent sparse probability distributions with exact zeros. This changes the goal of sparse decoding: rather than approximating a dense distribution with a truncated one, an entmax decoder only needs to recover the nonzero support. As shown in Figure 1 , if the selected KV pages contain all tokens in the entmax support, sparse decoding is exactly equal to full-cache entmax attention while avoiding the memory traffic associated with irrelevant pages. Softmax weights k Dropped ( \delta^{\text{sm}}>0 ) Sorted tokens \alpha -entmax weights k Dropped ( \delta^{\text{ent}}=0 ) Support \mathcal{S} Sorted tokens Figure 1: Softmax assigns non-zero probability mass to all tokens, so truncation always discards some mass ( \delta^{\text{sm}}>0 ). In contrast, \alpha -entmax concentrates probability on a sparse support \mathcal{S} ; when \mathcal{S} falls within the budget, \delta^{\text{ent}}=0 . As budget increases, the \alpha -entmax error drops to zero once k\geq|\mathcal{S}| , while the softmax error remains positive for any k . Recent work has shown that entmax is both useful for long-context modeling and practical to train at scale [ 21 , 7 , 6 ] . However, these advances do not address the autoregressive decoding bottleneck: full entmax decoding still reads the full KV cache before discovering which tokens receive zero attention weight. We introduce EntmaxKV, an entmax-native sparse decoding framework that exploits sparsity before KV pages are loaded. Concretely, EntmaxKV is a paged selective decoding method for \alpha -entmax attention: it scores KV pages using lightweight metadata, selects candidate pages, and computes entmax attention only over the selected KV entries. Overall, our main contributions are: • We formulate entmax-native sparse decoding as support recovery: unlike softmax truncation, which always drops nonzero mass, entmax sparse decoding is exact whenever the selected candidates contain the true support. • We analyze sparse decoding error through the dropped probability mass \delta , showing that the output error is bounded by 2B\delta and vanishes once the entmax support is recovered. • We introduce EntmaxKV, a paged sparse decoding method that uses query-aware metadata to avoid loading KV pages unlikely to contain entmax support tokens. • We propose a Gaussian-aware entmax selector that estimates the entmax threshold from lightweight page statistics and adapts the candidate budget to the score distribution. • We show empirically that EntmaxKV retains more support tokens, drops less probability mass, and achieves lower output error than softmax-based sparse decoding, while speeding up full-cache softmax and full-cache entmax decoding baselines on long sequences. 2 Background 2.1 Softmax Attention Let \bm{q}\in\mathbb{R}^{d} be the query vector, and let \{\bm{k}_{j},\bm{v}_{j}\}_{j=1}^{n} denote the keys and values stored in the KV cache for the n previous tokens. The single-head attention output is computed as follows: \displaystyle s_{j}(\bm{q})=\frac{\bm{q}^{\top}\bm{k}_{j}}{\sqrt{d}},\qquad\bm{p}=\pi(\bm{s}(\bm{q})),\qquad\bm{o}=\sum_{j=1}^{n}p_{j}\bm{v}_{j}, (1) where \pi:\mathbb{R}^{n}\to\triangle_{n} is a probability transformation, such as softmax. During autoregressive decoding, each new token attends to all previously generated tokens. For a context of length n , computing full attention therefore requires loading O(n) keys and values from GPU high-bandwidth memory into on-chip SRAM at every decoding step. This memory movement becomes a dominant cost for long contexts, even when the attention computation itself is highly optimized. A defining property of softmax is that it is dense. That is, for any finite score vector \bm{s} , every output component satisfies p_{j}>0 . Thus, no matter how irrelevant a token is, softmax assigns it some probability mass. Empirically, however, only a small fraction of tokens often receives significant attention mass [ 23 , 10 ] . This mismatch between dense probability assignments and sparse effective usage motivates decoding schemes that read and process only a subset of tokens for each query. 2.2 The \alpha -entmax Transformation \alpha -entmax [ 16 , 1 ] is a differentiable transformation that generalizes softmax while allowing exactly sparse probability distributions. For an input score vector \bm{s}\in\mathbb{R}^{n} and \alpha>1 , \alpha -entmax has the form \displaystyle\alpha\text{-entmax}(\bm{s})_{i}

Read the complete text