TL;DR

The previous article “Kimi K3's KDA (1): How KDA Works with Gated MLA and AttnRes” analyzed in detail how K3's hybrid attention mechanism resolves “A Detailed Analysis of Attention, Sparse or Linear?”, the 9 defects of Linear Attention raised there.

But one problem remains: the state matrix in KDA is fixed during processing — if a piece of information is already lost to collision or Delta overwrite when it is written into a KDA layer's state matrix, no later stage can recover it. This is why the first article discussed KDA's algebraic structure as an affine contractive semigroup — six words that compress a great deal of information:

• Semigroup: in essence, why it is not a group — this answers the irreversibility of forgetting. It also states the closure of composition and the failure of commutativity, which constrains parallelization strategies along one dimension.
• Affine: in the affine structure, governs “how fast to forget” (stability), while governs “what to remember” (expressivity); the affine structure cleanly separates the two, but information written earlier is bound to keep being forgotten by later transitions — it is both the source of expressivity and the root cause why inter-segment reduction must preserve order.
• Contractive: the older the token, the smaller its weight, decaying geometrically; pointwise contraction without a uniform gap unfolds into many derivations, such as the numerical-precision requirements on the state at long context.

But the first article still lacked a detailed comparison with Sparse Attention schemes. There is considerable controversy in both academia and industry; my consistent view is that an unsettled question is often a great research opportunity, and since it is a controversy, each side naturally has strengths and weaknesses — so let us peel it apart layer by layer. This article analyzes it from several angles:

1. Split the Attn data path into the KV write stage, the KV store stage, and finally the Query read stage, then analyze the different compression and addressing mechanisms along the data path.
2. From an architecture perspective, the State of Linear Attn is more like a Register File, while the KV of traditional Full Attn / Sparse Attn resembles a Cache hierarchy. So from a model-architecture / chip-system co-design perspective, we are essentially designing a memory subsystem — and “Memory” here is a pun: it means both the memory of an LLM and the physical memory hierarchy of a real chip.
3. One more question worth considering is Memory in Agent Harness and RSI scenarios, so the discussion should also cover spatiotemporal composability under Test-Time Training and Harness settings.

That was the demand side. On the supply side, given the Memory Wall of chips, the competition among algorithms / model architectures essentially becomes a difference in memory access at equal intelligence — and this is the real focus of the Sparse vs Linear debate... Of course, viewing LLM memory algorithms from an architecture perspective may deserve its own article later.

Contents of this article:

1. What is the Linear vs Sparse debate?
1.1 Starting from standard Full Attention
1.2 Linear's essence: query-awareness traded for associativity
1.3 Sparse Attention compression is learned pooling
1.4 A unified compression-granularity scale

2. The hard part of compression
2.1 What does the KV compression lower bound say?
2.2 The ineliminable O(T)?
2.3 The Linear vs Sparse debate revisited
2.4 The Linear Attn perspective
2.4.1 A history of patches
2.4.2 KDA's unavoidable walls
2.5 The Sparse Attn perspective

3. Compression as Intelligence
3.1 A Linear Attn that supports O(T)?
3.1.1 Constraints on block size
3.1.2 Snapshots from Prefix Cache
3.1.3 Block overlap and fast/slow state updates
3.1.4 Query-Aware block selection
3.2 Hidden-dim compression via the Grassmann Manifold?
3.2.1 From the JL lemma to the Grassmann Manifold
3.2.2 From global latents to block-local subspaces
3.2.3 Sparse Attention inside local coordinates
3.2.4 How much can it actually save?
3.2.5 Only let “compressible” blocks enter the low-dimensional space
3.3 Harness? Compression on the timeline?
3.3.1 The timeline is actually three clocks
3.3.2 Compaction! Compression of the timeline
3.3.3 Algebraically, who is invertible and who commutes?

4. Summary

1. What is the Linear vs Sparse debate?

1.1 Starting from standard Full Attention

From a computer architecture perspective, standard Full Attention comprises a complete write / store / read process. A token goes through three stages from arrival to consumption:

The Softmax Full Attention baseline does not compress at any of the three stages, so storage is and reads are . But notice an asymmetry:

• The write stage runs once per token
• The read stage runs once per query, and future queries do not even exist yet when the write stage runs.

From this perspective, the Linear Attn vs Sparse Attn debate is really about how Memory is handled: “into which stage compression is inserted” can yield higher efficiency with as little output degradation as possible. Jie Tang's recent survey “Memory for Large Language Models” is a good read, and we will expand the analysis from this perspective later.

The real choices are where compression is inserted and along which axis it acts. A KV pair has two compressible axes — the token axis and the channel axis — and compressing them has drastically different consequences, giving 4 schemes:

Plan A: compression inserted at the write stage, along the token axis. The moment a token arrives, it is folded into a fixed-size object; writing is compressing — history entries are compressed into 1 state. Storage drops to , the most thorough saving possible. But with the token axis compressed down to a single object, the read side has nothing left for the Query to “pick”. Linear Attention and KDA take this path.

Plan A': compression inserted at the write stage, but only along the channel axis. Compressing at the write side by down-projecting the KV, represented by MLA: it runs once per token, independent of any query, with compression ratio x. But it does not merge a single token: the entry count is still ; each token keeps its own independent entry. At read time the 576 dims are projected back up to full K and V, so the number of candidates is exactly the same as the baseline — the query's power of choice is fully intact, and the only loss is that each candidate gets blurrier.

The difference between the two is really a trade-off over whether compression strips the read side of its power of choice. Compressing the token axis changes “how many things there are to pick”; compressing the channel axis changes “how clearly each thing is seen”.

Plan B: compression inserted at the read stage. Every time a query arrives, compress the history specifically for that query. Query-awareness is maxed out, because the compression function may freely depend on the query. But storage is not saved at all — you must keep the full history to have anything to compress; and the compression cost goes from “once per token” to “once per query”, making compute even more expensive. So nobody takes this path in engineering.

Plan C: compression inserted at the store stage, compressing both axes, with selection inserted at the read stage. First reshape the KV storage form: on the token axis, pool entries into entries; on the channel axis each slot is 512-dim. This step is still query-independent; but what remains after compression is still a set of addressable KV entries — just fewer of them. So the read stage can still pick a subset per query as usual. DSA takes this path.

Put the four schemes side by side with the baseline, and the evolutionary logic becomes clear:

In essence, compression is lossy, and the compression loss must be balanced against compute/storage. When K3 uses Plan A to compress the token axis to the limit in exchange for state, it has to insert a series of Plan A' in between to preserve the token axis and regain addressability.

Plan C is the midpoint between A and B, and it exists thanks to the same inconspicuous property as Plan A′: the compressed object remains addressable. A′ keeps it by merging no tokens at all; C keeps it by leaving independent entries after merging. Only A loses it.

1.2 Linear's essence: query-awareness traded for associativity

KDA's write stage is

where and — all parameters of , , , are generated solely from the current token's input . Unrolling into the general solution:

There is no in this formula. How large a share of history a token occupies is determined by its own at write time and the of all later tokens, multiplied together — and all these quantities are fixed before any query arrives. Once the write stage is done, who matters and who does not is already hard-coded into .

So what can the query still do? Expand the readout into implicit-kernel form:

In essence, the query can adjust the angle between and ; but the query cannot adjust the envelope — by the compatibility of with the operator norm,

Not a single appears on the right-hand side. Hence a crisp verdict: in KDA, the query can only pick a direction under an already-painted ceiling; the ceiling itself is out of its reach. And this ceiling decreases monotonically with distance — the older the token, the lower its cap. So a piece of information judged “unimportant” at write time and given a tiny , or one repeatedly decayed by later tokens, can never be retrieved no matter how relevant a later query is.

This turns the problem into a bet. The write stage must decide two things in the present: decides how long to remember it, decides how strongly to write it. The optimal values of both depend on what queries will come in the future. For two sequences with identical prefixes but different subsequent queries, KDA necessarily produces exactly the same .

A more direct comparison:

The left formula achieves per step for one reason only: the summation is moved ahead of the query. Once the sum is done, history becomes a query-independent object, and any number of later queries each cost just one read. It is an efficiency trade: you sell the right to “look at what to read before reading” in exchange for a constant-size state. The query becomes direction selection within the state matrix, rather than object selection as in Sparse Attention.

The flip side of O(1) is the fixed state matrix: taking the current K3 as an example, each layer can hold at most elements; with context length , each token keeps only about 1.5 elements per layer at 1M context — and to cope with Linear Attention's own defects (e.g. the 9 listed above), Hybrid Attention must be introduced.

1.3 Sparse Attention compression is learned pooling

Take DeepSeek-V4 as an example: the compression step deserves a close look, because it loses information in a completely different way from KDA's “decay-overwrite”. HCA has the simplest form: let , , and every entries are compressed into one via

Here is a learnable within-window positional bias. Through this compression, HCA reduces the sequence length to x. Note that is the Hadamard product, so the weights are channel-wise; in other words, different channels within the same window can pick different tokens as their main source. This point is often overlooked, and it makes the compression far more expressive than scalar weighted averaging.

CSA's compression ratio is only 4, but it adds an overlap mechanism: it computes two sets of projections and two sets of weights , and each compressed slot is produced from entries:

The slot's index overlaps with the slot's index, so the sequence length is still compressed to , but adjacent slots share boundary tokens. Note that overlap is not merely a smoothing trick — it has deeper uses. After obtaining the compressed slots, CSA can run another query-based top-k indexer selection, whereas HCA, with compression ratio , attends densely over all compressed slots.

1.4 A unified compression-granularity scale

Let be the number of tokens merged into one indivisible unit; then is the number of history segments a query can distinguish. The four layer types on one scale:

By compression ratio: at 1M, KDA keeps only 1.5 elements per token per layer, while DSv4's HCA layers keep 4 — KDA compresses harder, but the two are of the same order of magnitude. Actually I have a question here: from the eventual ablation results, HCA at such a high compression ratio is probably of little use anyway — can we compute some lower bound on the compression ratio? But weighted over the whole model, K3 is , DSv4 is ; K3's average kept elements per layer per token is instead 2.30x that of DSv4. A counter-question: does Linear Attn actually save anything?

Another revealing difference is the number of addressable units: KDA has 1, DSv4 CSA has 262,144. In bits, that is “how many selection decisions a query can make in one read”: CSA picks 1024 out of 262,144 units, a decision content of

While KDA has 1 unit, so the combinatorial selection content is exactly bit. So “query-awareness” gets a computable scale:

• KDA's query dependence is purely continuous direction selection; its discrete addressing information is zero
• HCA and MLA make no discrete choice, but their continuous weights act on 8,192 and 1,048,576 distinguishable units
• Only CSA uses both discrete selection and continuous weighting

For KDA and DSA compression, there is another angle for analyzing compression interference:

Finally, a summary of the differences:

The two routes diverge on “whether to resolve uncertainty at write time or at read time”: K3 bets across 69 layers, hedging with 24 MLA layers and 8 AttnRes archives; DSv4 defers everything to the read stage.

2. The hard part of compression

This chapter starts from lower-bound calculations of KV compression, then discusses the respective strengths and weaknesses of Sparse and Linear.

2.1 What does the KV compression lower bound say?

Although KDA can be said to reduce complexity from to , that claim holds only at the KDA layer level; for the whole model, K3 keeps 24 full MLA layers to fix a series of pure-Linear-Attn defects. Hence a conjecture: the lower bound of KV compression at the model level must take the form and cannot be eliminated; the practical difference is only a trade-off in how the constant factor of gets reduced. K3 does it by reducing the number of layers, from 93 to 24; DSv4 does it by lowering the per-layer price of the term, compressing 4x (CSA) or 128x (HCA).

So does this lower bound really exist? As the previous chapter explained, we essentially face the data-compression lower bound under query-blindness.

2.2 The ineliminable O(T)?

On this conjecture, I later searched the literature and found that the paper 《Compression Barriers in Autoregressive Transformers》^[1] already treats it in detail. Specifically:

Some readers complain that too much math is “inhumane”, so here is the proof sketch in plain language: the problem is reduced to a communication index problem — that is, we view Attn itself as a memory-access problem.

• Alice holds a bit string ;
• Bob holds an index , and Alice does not know ;
• Alice may send Bob a single message (one-way communication, no interaction);
• Bob must, with probability at least , output .

The one-way randomized communication complexity of this problem is.

By analogy with Attn: Alice's input here is a 0/1 matrix , totaling bits; Bob needs to query its -th bit. Here is the token sequence length and is the hidden-dim. Attention is then used as an address-based read operation. We focus on Alice's KV encoding:

1. Values carry the information to be encoded: the most direct step — take 's -th row as the -th value vector:

2. Keys serve as mutually independent addresses: we need mutually non-interfering address vectors. In this is trivial: the standard orthonormal basis has pairwise inner products . But we want to compress the key space, e.g. keys live in a -dim space with , which cannot hold strictly orthogonal vectors.

This is where the Johnson–Lindenstrauss (JL) random projection comes in; it answers a beautiful question:Can we compress many high-dimensional vectors into low dimensions while approximately preserving all pairwise Euclidean distances? The answer is yes.

After Alice has fed in triples, she sends the -bit memory state to Bob. Bob then only needs to feed the algorithm one more triple , where

— i.e. take the direction of the -th address vector, scaled by a factor (this scaling trick is from Keles et al., 2022). The score vector then satisfies

This is exactly what the paper calls softmax's malleability: increasing makes and the remaining arbitrarily far apart, and the exponential amplifies the gap further, degenerating softmax from a smooth weighted average into an approximate argmax — a Dirac-like spike on the discrete support.

Let be the softmax weights. The -th component of the output vector is

(The row Bob fed in satisfies and contributes nothing to the numerator; only adds one term to the denominator, without changing its magnitude.)

Two cases follow. Denote the main term and the upper bound on the sum of interference terms :

Case 1: . the numerator keeps only interference terms, each , so

Case 2: . the numerator contains at least the main term itself, so

For the protocol to work, Bob must be able to distinguish these two intervals, i.e. . And

Any works. The paper takes , , which gives

That is, the outputs in the two cases differ by a factor of . At this point the construction is complete, and the range of is fixed. But only guarantees that Bob can answer correctly; between that and “ must be large” there is still the entire finishing stretch of the reduction. The crux is that the protocol's success rate meets the requirement; there are two failure sources: the JL projection failing the inner-product condition (probability ), and the algorithm itself erring (probability ). Taking a union bound, Bob's success probability is at least

which meets the success-rate requirement of the index problem. At this point we hold a complete, valid protocol for the index problem:

• Input size: , i.e. bits;
• One-way, randomized, success rate ;
• Communication: .

The JL theorem asserts: any protocol satisfying the above conditions has communication . We can thus sandwich out the lower bound

The paper also discusses the following:

1. The boundary in low dimensions: When the embedding dimension is small (), the paper proves a space-complexity lower bound of , and points out that the SubGen algorithm proposed by Zandieh et al. achieves this theoretical lower bound in this specific scenario. But typical LLMs today
2. The role of structural assumptions: The paper explicitly states that unstructured sparsity alone is not enough to break the linear space barrier. In other words, merely knowing that the attention matrix is sparse, without knowing where the sparsity lies, still cannot achieve sublinear space. This provides a theoretical basis for many practical algorithms that rely on specific sparse patterns (e.g. sliding windows).
3. Extension to sliding-window attention: The paper analyzes a more general sliding-window attention mechanism in which Value vectors outside the window are not completely ignored. For this scenario, the authors propose a novel sublinear-space algorithm based on reservoir sampling, and prove its space complexity is nearly optimal.
4. Time-complexity lower bound: The paper also studies the time complexity of token generation, proving that any non-adaptive streaming algorithm (i.e. one with the data-access pattern fixed in advance) requires, in the worst case, at least .

2.3 The Linear vs Sparse debate revisited

In fact, a common rebuttal immediately arises here:

1. Linear attention's state is fixed at , independent of , so it necessarily loses information and cannot reproduce the output of softmax attention;
2. so it is a lossy approximation without any guarantees;
3. so it is pointless — since cannot be dodged anyway, better to honestly store the full KV and then compress the KV dimension via the JL lemma — like MLA/DSA/CSA?

A fixed state is Linear Attn's biggest weakness: linear attention's state is times smaller than (taking , , about 2000x), so it sits completely outside the lower bound — supporters of Linear Attn have nothing to deny here; the first article already discussed the 9 defects of pure Linear Attn...

Of course such a conclusion is somewhat one-sided, because the Linear Attention path has already evolved into Hybrid Attention — e.g. should Kimi K3's block of 3 KDA layers + 1 Gated MLA layer be viewed as a whole?

For example, the hard problem used in the reduction is an index communication problem: Alice hides a bit and Bob later specifies a position to retrieve. This is essentially needle-in-a-haystack: exact retrieval of a single point from unstructured long context. So the theorem does not just say “sublinear must be lossy” — it pinpoints on which tasks the loss occurs. And this matches empirical observations: Kimi K3 may drop points on long-context exact-recall tasks, while losing very little on highly redundant tasks like language modeling, summarization, and commonsense reasoning. So is the whole K3 block (3x KDA + 1x MLA) itself a decent Attention structure? Hence a head-on opposing view: “My favorite kind of approximation is allowed to be lossy, yours is not” — and I don't need “guaranteed losslessness” either; being a bit blurry and appending a Full Attn afterwards is perfectly fine?

On the other hand, the paper also shows that without data-awareness, merely knowing the attention matrix is sparse — without knowing where — still cannot achieve sublinear space, which seals off a family of Sparse Attn algorithms without an indexer. For Hybrid Attn, Linear Attn supporters might also argue: the state matrix is a data-driven compression, the interleaved MLA restores long-range memory, and it adds many layers of inductive-bias capability over Sparse Attn, which could improve generalization?

So the Linear Attn vs Sparse Attn debate has shifted to Hybrid Attn vs indexer-carrying Sparse Attn schemes like DSA/CSA.

2.4 The Linear Attn perspective

2.4.1 A history of patches

The previous article “Kimi K3's KDA (1): How KDA Works with Gated MLA and AttnRes” also discussed in detail: various issues of Linear Attention mean must be repaired with a conv; then got added, had to be added too, and after that a nonlinear SiLU — the exponential computation one hoped to save crept back in; even so, the state still accumulates and collides.

Then Linear Attention could only keep writing into the state matrix with no way to forget. So Mamba-2 introduced — an input-dependent memory lifetime — but the forgetting was too coarse-grained and writing was still additive. Then came DeltaNet, i.e. , which can directionally rewrite along the current key, but lacks a mechanism to quickly clear stale global state. So Gated DeltaNet was built, i.e. , combining global forgetting with directional rewriting, but each head has only one decay. Then KDA appeared, , introducing an independent decay per key channel — but a fixed state still does not equal full token-addressable memory.

We then continue examining the transition . It has eigenvalues equal to , and the eigenvalue along the direction is Without constraining , even if , one can still get , causing that direction to be amplified or overshoot backward in the recursion. Then more patches: Q/K need L2Norm; the output gate also needs a full-rank projection, and MLA needs to be added as well — activated parameters grow by another 8B.

This is at the KDA operator level; further, from its algebraic structure, it is an affine contractive semigroup. The contractive property determines its limited ability to remember long-range retrieval, so Hybrid Attn must be used, with Full-Attn MLA as the supplement. This is how Linear Attn gradually evolved into KDA — a history of patches.

2.4.2 KDA's unavoidable walls

If we consider a future Linear Attn that can avoid full-Attention layers like MLA with O(T) KV and still gain sublinear benefits — equivalently, if we connect token-to-token attention into a topology, the question to answer is: can the “edge” between two tokens at distance survive in the KDA state until it is read out?, KDA's weights decay along time as , so the strength of this edge drops exponentially with distance. Set a “still alive” threshold (below 1% counts as dead), giving

The key is that making large has only one way: push toward 1. And triggers three bad things at once:

Wall 1: the requirement itself is extreme (the decay wall) : means grows 10x, must shrink 10x. can only support 458 tokens; to support 1M you need . , accurate to the 7th decimal place.This demands pinning a number at an extremely narrow spot in the neighborhood of 1.

Wall 2: the gradient at that spot is almost zero (the trainability wall): ; differentiating gives . To have you need — the far-left end of the sigmoid, approaches zero, a gradient four orders of magnitude smaller — effectively telling the optimizer “don't go this way”.

Wall 3: even if learned, it cannot be computed accurately (the numerical wall): §2.3.8 of the previous article also covered this — FP32 at has only 7 significant digits left, i.e. the long-range Attn topology loop at 1M distance is already unreliable in FP32.

The crux of the three walls is “mutually independent, tightening in the same direction”

All three are stuck on the same knob, and all worsen in the same direction; no setting of can satisfy all three at once. On the other hand:

• decay's lower bound is sealed (, cannot forget fully in one step) — this buys numerical safety, and the lost “fast forgetting” ability is compensated by the delta term;
• decay's upper bound is open (, long memory) — this buys expressivity, at the price of losing the uniform contraction gap.

But each delta step can only erase one direction (Rank=1). So: selectively clearing a -dim conceptual subspace needs at least steps. Decay can clear fast but has no within-channel selectivity. Forgetting that is “both fast and selective” is unreachable in a single layer at a single step — it can only be relayed over multiple tokens or layers.Does this also imply that several consecutive KDA layers must cooperate, and that the whole model needs a deeper network? In fact the depth axis's efficiency is also affected. This produces a dialectical contradiction:

• To preserve ultra-long dependencies, the model needs to push some channels toward .
• To keep learning the timescales of these channels, the decay gate must stay out of the saturation region.
• To preserve ultra-long dependencies, the model cannot use low precision to improve compute efficiency.
• To balance the decay contradiction, the model potentially needs more layers, which also hurts compute efficiency.

Next comes an efficiency question — or let me phrase it differently: why is FlashKDA's chunksize = 16? In the formula, the division by is the Achilles' heel of the chunkwise form: is the cumulative product of 's retention factors, and its reciprocal grows unboundedly with intra-chunk distance. Under negative-Softplus parameterization, 16 steps of accumulated decay can get arbitrarily close to , and overflow is inevitable at finite precision.

Kimi Linear's countermeasure is to subdivide the chunk into 16-token sub-tiles: off-diagonal tiles can use Tensor Cores after computing relative decay in log space, but diagonal tiles must still be computed explicitly position by position, becoming the main bottleneck of intra-chunk computation. Kimi K3's solution is to eliminate the numerical problem at the source: once is floored,

the reciprocal renormalization factor is representable throughout, diagonal and off-diagonal tiles unify into dense Tensor Core GEMMs, and the slow path is deleted entirely. This also explains the three reasons FlashKDA chose :

1. Numerical range: lands exactly within bf16's dynamic range, needing no intra-chunk rescaling tricks;
2. Cheap inversion: 's inverse expands directly with a Neumann series, no further factorization needed;
3. Instruction mapping: all math maps cleanly onto SM80 MMA (m16n8k16) instructions, keeping the kernel simple and portable.

A nice way to put it is that it happens to match the common GPGPU TensorCore 16x8x16 shape — but consider another question: for DSA-architecture accelerators like TPUs, whose systolic arrays are usually 128x128 / 256x256, what should we do? The rough problem is shown below:

It looks like just changing CHUNK to 128 solves everything. But K3's numerical constraints bite back: single-level renormalization requires (both bf16 and fp32 have exponent ceiling ), so one cannot buy MXU-friendliness by raising — that changes the model, not the kernel. and CHUNK = 16 are a jointly calibrated pair.

The deeper obstacle lies in channel-wise decay: the dangerous factor appears inside the inner product

is a per-channel vector that cannot be pulled out of the dot product. With scalar decay like GDN / Mamba-2, is a pure scalar, free to re-anchor by block in log space, so enlarging the chunk is almost painless. KDA chose channel-wise for expressivity; the price is that the re-anchoring window is pinned by the numerical range to 16 token.

Of course we could also consider a 2-level loop tiling strategy: the outer CHUNK = 128 computes the GEMMs unaffected by at 128x128, and the inner uses concatenated matrices to improve TensorCore utilization. But overall the MFU would not be great either.

2.5 The Sparse Attn perspective

The Sparse Attn perspective is actually very straightforward: first, from the EOT viewpoint SDPA is the optimal solution, so softmax is worth keeping however slow. The remaining items: from the channel axis standpoint: acknowledge the sparsity of KV and compress the hidden-dim via the JL lemma — that is what MLA does. From the the token-sequence axis dimension: perceive the content to a certain degree and select through a lower-dimensional, lower-precision (FP4) evaluator (the indexer) — that is DSA. Another issue is that softmax peaks flatten as sequences grow: on one hand, attn-sink handling can be introduced; on the other, top-k selection also increases long-context kurtosis.

Then further blocking constructs the compression; and for the block-boundary jumping problem that top-k may have, overlap on the KV handles it — that is CSA. You can see DeepSeek's whole evolution here.

Of course, Sparse directly taking a constant topK may have problems: how to ensure that the blocks selected by this hard truncation can approximate Full Attn? A quick derivation:

For keys, sorted scores , softmax probabilities , where . Top-k truncation keeps the top and renormalizes: (), . Denote the tail mass .

: each head term gains (the denominator shrank); each tail term loses . The total “extra” of the head is , and the total “lost” of the tail is also . Hence

For , the likelihood ratio is a constant independent of . The expectation of a constant's logarithm is itself:

is a structure unique to Top-k renormalization. Now analyze the score distribution: each head term has , totaling terms; each tail term has , totaling terms. Substituting into :

that is, grows by 1, the error bound shrinks by about x. For example, at , , , which guarantees . This bound needs only two numbers.

So to guarantee , from we directly get the single requirement:

Hence a simple bucketing algorithm:

1. Bucket: while computing the score , also compute the bucket index , and increment the integer counter . Each key costs one subtraction, one rounding, and one increment.
2. Table lookup: the keys in bucket are worth at most ; this table is data-independent and can be computed at compile time. “How many are in the bucket” times “how much each is worth at most” gives the bucket's mass upper bound.
3. Accumulate: accumulate right-to-left starting from the rightmost (lowest-score) bucket, stopping as soon as the budget is exceeded. Whichever bucket it stops at, its boundary is the threshold ; keep keys.

There is another potential issue related to the HCA implementation: no matter how Sparse picks topK, how to further raise the compression ratio of a single block is also worth considering. HCA's pooling map is

Let us construct a minimal model: the gates are approximately uniform, i.e. ; within the window exactly one token carries the signal the query needs, , with scale ; the remaining tokens are mutually independent, zero-mean, same scale. The pooled slot is

The signal amplitude is , and the interference amplitude, by independent superposition, is . The of the two cancel, so the SNR takes an extremely simple form:

On the other hand, decompose the loss of the attention distribution via KL: