Linear and Sparse Attention

Featuring Kimi and DeepSeek

Attention is at the heart of LLMs and (similar to our own human attention spans) we are always trying to find ways to become more efficient with it.

Linear and sparse attention are two approaches to improving the efficiency of LLMs that have recently been implemented by two leading open source model labs, Kimi and DeepSeek. Kimi focuses on linear attention with Kimi Delta Attention (KDA), whereas DeepSeek has introduced an improved sparse-attention mechanism with DeepSeek Sparse Attention (DSA).

Kimi Delta Attention

Kimi K3 has recently taken the spotlight as a frontier-approaching open source model scaled to 2.8T parameters, with Kimi Delta Attention at its heart.

Kimi Delta Attention builds on a lineage of linear-attention variants that the authors map out in their previous paper, Kimi Linear. The progression runs from linear attention to DeltaNet, then Gated DeltaNet, and finally Kimi Delta Attention. Below, we go through the updates one rule change at a time, highlighting the changes each contributes in red.

First, linear attention accumulates key-value pairs in a matrix-valued recurrent state; the query reads an output from that state.

\mathbf{S}_t = \mathbf{S}_{t-1} + \mathbf{k}_t\mathbf{v}_t^\top,\qquad \mathbf{o}_t = \mathbf{S}_t^\top\mathbf{q}_t.

DeltaNet changes the additive write into an error-correcting delta rule, taking an online gradient step with learning rate $\beta_t$ on the reconstruction loss:

\mathcal{L}_t(\mathbf{S}) = \tfrac12\|\mathbf{S}^\top\mathbf{k}_t - \mathbf{v}_t\|^2.

\begin{aligned} \mathbf{S}_t &= \mathbf{S}_{t-1} - {\color{#b52622}\beta_t\nabla_{\mathbf{S}}\mathcal{L}_t(\mathbf{S}_{t-1})} \\ &= (\mathbf{I} - {\color{#b52622}\beta_t\mathbf{k}_t\mathbf{k}_t^\top})\mathbf{S}_{t-1} + {\color{#b52622}\beta_t}\mathbf{k}_t\mathbf{v}_t^\top. \end{aligned}

Gated DeltaNet adds the scalar forget gate $\color{#b52622}\alpha_t$ , which decays the previous memory uniformly before the delta-rule update.

\mathbf{S}_t = {\color{#b52622}\alpha_t}(\mathbf{I} - \beta_t\mathbf{k}_t\mathbf{k}_t^\top)\mathbf{S}_{t-1} + \beta_t\mathbf{k}_t\mathbf{v}_t^\top.

Finally, Kimi Delta Attention replaces that scalar gate with the diagonal gate $\color{#b52622}\operatorname{Diag}(\boldsymbol{\alpha}_t)$ , giving each key channel its own forgetting rate before the same delta-rule update.

\begin{aligned} \mathbf{S}_t &= (\mathbf{I} - \beta_t\mathbf{k}_t\mathbf{k}_t^\top){\color{#b52622}\operatorname{Diag}(\boldsymbol{\alpha}_t)}\mathbf{S}_{t-1} + \beta_t\mathbf{k}_t\mathbf{v}_t^\top \in \mathbb{R}^{d_k\times d_v}; \\ \mathbf{o}_t &= \mathbf{S}_t^\top\mathbf{q}_t \in \mathbb{R}^{d_v}. \end{aligned}

TL;DR: starting from linear attention, we make 3 changes to get to KDA:

Replace additive writes with error-correcting updates.
Add a scalar forget gate.
Give each key channel its own forgetting rate.

Table comparing recurrent and parallel forms of attention, from softmax and linear attention through DeltaNet and gated variants, with KDA highlighted in the final row. — The history of attention mechanisms, from the Kimi Linear paper.

DeepSeek Sparse Attention

Sparse attention is another approach to solving the quadratic attention problem. In its simplest form, sparse attention can be thought of as a sliding window or filter on the global attention mechanism.

DeepSeek Sparse Attention (DSA), introduced with DeepSeek-V3.2, uses a two-stage pipeline:

Lightning indexer: score all tokens for relevance.
Top-k selection: compute attention using only the highest-scoring tokens.

The increased complexity of sparse selection allows the model to learn more context-aware filtering procedures while retaining quality.

DeepSeek-V3.2 attention architecture with DSA under MLA. The green path shows the lightning indexer scoring tokens and the top-k selector choosing key-value entries for core attention. — DSA architecture from the DeepSeek-V3.2 paper.

DeepSeek has since built on DSA in DeepSeek V4, combining it with several key upgrades, including token-wise compression, to make long-context attention more efficient.

DSA in Other Contexts: GLM 5.2

GLM 5.2 is another open-source model that leverages DSA alongside an optimization called IndexCache.

Whereas vanilla DSA has an indexer and top-k selection at each layer, IndexCache reuses the indexer’s top-k indices across layers.

Specifically, in GLM-5.2, every 4 transformer layers share a lightweight indexer. Top-k indices are reused for 4 layers, significantly reducing the number of indexer dot product and top-k operations that need be performed.

How Might We Learn?

For both linear and sparse attention, the goal is the same: make longer contexts more useful and less expensive. The approaches raise a shared question: what is worth retaining, and what is worth revisiting?

I find there are interesting parallels to research on how humans learn how to learn and the ideas of the trade-off between retention and repetition. For humans, too, learning involves a balance between what we commit to immediate memory and what we trust we can reconstruct.