Your 128K Context Is 6x Slower Than It Needs to Be

A paper landed this morning with a number you should tape to your monitor. Same model, same GPU, same 128K prompt, first token arriving 5.97 times faster. Not a new checkpoint. Not new silicon. A different answer to one question: which parts of your prompt does the model actually need to look at?

That question has been open for two years, and most answers have disappointed in production. Sparse attention promises to skip work and then quietly costs you accuracy on the one task you shipped for. This paper names the failure mode behind that, and once you can name a failure mode, you can design against it.

PhantomByte already showed you that prefill and decode are two different machines, and we priced the KV cache before that. Both notes ended on the same bottleneck. This is the sequel. The last two told you where your latency budget dies. This one tells you how to cut the bill.

THE PREFILL TAX, EXPLAINED

Prefill is the model reading your entire prompt before it writes a single token. Dense attention means every token in that prompt looks at every other token. That is the whole mechanism, and it is why your first token takes as long as it does.

The cost scales quadratically with prompt length. Double your context and you quadruple the attention work, before anything else in the stack gets a vote. At 128K tokens, context is not long. Context is a bill, and it arrives before your model has said one word.

Call it the prefill tax. You pay it on every call, not once at setup. Every chat product pays it when a user pastes a document. Every agent harness pays it when it reloads a repository into the window. Every retry pays it again from scratch, because prefill does not care that you already read the same 90,000 tokens on the previous turn. Three retries on a 128K prompt is not one expensive call. It is three, and the second and third buy you nothing new.

Time-to-first-token is the number a user actually feels, which is why it matters more than a throughput chart. Your tokens per second mean nothing to somebody staring at a blank box for eight seconds.

The architecture split is what makes this fixable. Prefill is compute-bound and decode is memory-bound, so the two phases respond to completely different optimizations. That work already exists in our notes on the KV cache and on prefill and decode as separate machines. This is the third leg. How to stop paying full price for the first one.

WHY BLOCK-SPARSE ATTENTION UNDERPERFORMS: THE MEAN-DILUTION TRAP

Block-sparse attention is the obvious fix. Instead of every token attending to every other token, you group keys into blocks, score the blocks, and attend only to the winners. You skip the losers entirely. Cheaper by construction, and the kernel underneath it is already fast.

The failure mode is subtle enough that most teams never see it. Score a block by its centroid, which is the average of the keys inside it, and one highly relevant token sitting among two hundred irrelevant ones gets averaged into mediocrity. The selector reads the block as mediocre, skips it, and your answer was inside that block. Once the block is pruned, nothing in it can contribute to the output.

The paper, published September 17 by Chuxu Song, Jiuqi Wei, and Zhencan Peng, calls this mean dilution. Their diagnostic found the geometry underneath it. Centroid rank underestimation increases as keys scatter farther from their block centroid, and the highest-radius quintile of blocks contains 39.5 percent of the top-5 percent attention blocks in their measurement. The blocks a selector most needs to keep are exactly the blocks its average score most misleads it about.

This is why block-sparse attention has a reputation problem in production. The damage is silent. Aggregate benchmark accuracy slides a point or two, the team blames the model, swaps checkpoints, and never touches the selector. Name the framework and it becomes citable: the mean-dilution trap. A block's average can be wrong about a block's best token.

THE RESCUE BRANCH: TWO SELECTION PATHS, ONE MASK

The fix is not a smarter average. It is a second selection path.

The centroid branch stays exactly as you know it. It scores every block on average relevance and keeps the ones that score high. That is every sparse method you have already seen.

The rescue branch asks a different question. How far is the farthest key from its own block centroid, and does that radius look unusual for this prompt, this layer, this head? Blocks with a wide radius are the blocks where a single token may be carrying the evidence, and those get rescued into the mask even when their average score says otherwise.

Read the mechanics and you can see how little machinery this actually requires. Partition your queries, keys, and values into blocks. For each key block, compute the centroid, then compute the maximum distance from any key in that block to that centroid. That single radius number is the entire second signal. The paper derives a radius-adaptive coefficient from the distribution of those radii, using the median and the 90th percentile as the reference points, then scores rescue candidates against the base path with that coefficient applied.

None of that pre-computation cancels the savings, and the reason is the shape of the two costs. Building block centroids, computing radii, and deriving the median and 90th percentile reference points all scale linearly with sequence length, because each token is read a fixed number of times. The dense attention you are replacing scales quadratically, because every token pair gets compared. At 32K the two are closer than you would like. At 128K the mask build is a rounding error against the quadratic work it removes, which is exactly where the speedup shows up.

Grouped-Query Attention makes that cheaper still, and the model in this benchmark is a clear example. Qwen3-30B-A3B-Instruct-2507-FP8 carries 32 attention heads against only 4 key-value heads, so the centroids and radii run over an eighth of the projections a multi-head baseline would require. The paper computes its radius quantiles separately for each layer and each key-value head, which is the granularity that makes the rescue signal adaptive without making it expensive.

The radius threshold is not a constant. The paper characterizes its prompt-dependent, layer-dependent, and head-dependent distribution, so the rescue budget adapts to what the model is doing at that depth instead of being fixed once for the whole network. The two branches are then thresholded independently and their masks are combined. That independence is the design decision worth stealing. You can hold base selection steady and dial rescue up or down without re-tuning the other path, and the paper makes the case for separate thresholds explicitly rather than folding both signals into one score.

Block size is the second knob, and the paper sweeps it. It also examines whether thresholds tuned on one model transfer to another, which is the question you will care about the moment you try this on a checkpoint nobody calibrated.

One more property makes this practical. The combined mask still runs as regular block-sparse FlashAttention. No custom kernel, no retraining, no new checkpoint. Training-free means you can evaluate it against the model you already serve, this week, with no fine-tune in the loop.

THE NUMBERS, STATED HONESTLY

• 20.65x at the kernel. The headline is 20.65x, and that is the number to distrust first. It measures standalone prefill-attention speedup on H100 GPUs, which is the kernel in isolation with nothing else in the stack around it.
• 11.92x inside vLLM. Move up one level and the same method gives 11.92x prefill-attention speedup inside vLLM. Everything around the attention call, the scheduler, the sampling, the KV management, stays exactly where it was.
• 5.97x end to end. Move up to the number a user feels and you get 5.97x end-to-end time-to-first-token at 128K context, on Qwen3-30B-A3B-Instruct-2507-FP8. That is the honest figure and the one you can defend in a review, because every other component in the stack is unchanged. Six times faster to first token is still a different product.

The setup behind it is specific enough to reproduce. H100 GPUs, vLLM 0.10.0, FlashAttention 2.8.3, with each speedup normalized against dense execution on the same model, the same hardware, and the same context length. Supplementary system measurements on A100s cover retention under the original quality configurations and prompt throughput.

Accuracy is where the claim gets tested, and this is the reason the paper is worth your afternoon. On dense Qwen3-32B, 88.65 overall RULER accuracy against 89.52 for full dense attention. A little under a point, measured rather than asserted. LongBench-v2 lands at 0.376 against 0.394 for dense, and the paper adds InfiniteBench and Video-MME results plus matched-density comparisons against MInference and FlashPrefill. At a matched 5.34 percent density, the reported advantage is 3.41 accuracy points over MInference and 5.55 over FlashPrefill. A multimodal Qwen3-VL-30B-A3B-Thinking-FP8 model is in the quality sweep as well, which tells you the selection policy is not tuned to one architecture.

That matched-density gap is not a tuning artifact, it is a difference in mechanism. MInference determines the optimal sparse pattern for each attention head offline and then builds sparse indices at inference time against that fixed assignment (arXiv 2407.02490). FlashPrefill also uses block-sparse prefill with mean-based block scoring. Static structure is the bet in both, and it pays until a prompt stops looking like the prompts the pattern was fitted on. Rescue does not make that bet. It reads the radius distribution of the prompt in front of it, per layer and per head, and pulls dispersed blocks back in at runtime. That is the mechanical reason the gap is largest in exactly the regime this article is about, and the paper's own counterexample is worth noting because it keeps the claim honest. A wide radius signals risk of mean dilution, not proof that the block holds evidence for this particular query.

One more thing the numbers tell you, and it is the part most people would not expect. The rescue signal survives at FP8 precision. Quantizing keys to eight bits is a reasonable place to expect distance metrics to fall apart, because both the centroid and the radius are computed from key vectors and small representation errors compound in a maximum-distance statistic. The benchmark model is an FP8 checkpoint, and the accuracy still holds within a point of dense attention on the quality sweep. Treat that as measured on this model rather than guaranteed on yours, because the paper reports block size and threshold sensitivity rather than a dedicated quantization study, and thresholds tuned on one checkpoint may not transfer. But the signal was not washed out by eight-bit keys, which was the real question.

Two caveats the authors state themselves, and both belong in your notes. Accuracy is not claimed to match dense attention, because the method works by omitting blocks and the output is an approximation by construction. And summary size is not peak memory. Materializing every token-to-centroid comparison costs space that grows with prompt length times block count, block scores and masks cost space that grows with the square of block count, and tiled reductions only shrink the first of those. If you were hoping a smaller block summary was automatically a smaller footprint, the supplemental measurements are where that assumption gets tested. The rule of thumb for when that flips from a footnote into your bottleneck is sequence length. At 128K the quadratic attention term still dominates and memory stays a rounding error. Push toward 256K and beyond and the intermediate token-to-centroid distance tensors, plus the block score and mask materialization, start competing for VRAM against the KV cache you already need. Compute scales up with the square of your context, and so does the workspace you need before the kernel fires. At some length the selector becomes the binding constraint, and that is the length at which you want to have already measured peak memory instead of reasoning about summary size.

Keep one more caveat in view. RULER is not your workload. A benchmark can hold its average while the specific behavior you shipped for quietly disappears.

WHAT TO DO TODAY

• Measure your time-to-first-token at 32K and 128K with your real prompts before you change anything. You cannot claim a speedup you never measured, and most teams have never measured this number at all.
• Pull your serving stack's attention configuration and check whether it already exposes block-sparse selection. vLLM 0.10.0 was current in the paper's setup, and runtimes in this area are moving fast. Verify against your installed version instead of assuming either way.
• Reproduce the paper's setup on one model you actually serve. Same checkpoint, sparse selection on, TTFT at both context lengths, then compare. One model, one afternoon, one honest number.
• Re-run at a matched density if you compare against another sparse method. Retained block percentage, not block count, is the honest basis for a comparison, and the paper's own matched-density table is the reason to do it.
• Check peak memory, not summary size. Sweep block size on your own workload and watch both accuracy and footprint, because the two do not move together.
• Run your own evaluation suite, not RULER. Aggregate accuracy can survive a regression that your product's specific task does not.
• Watch the rescue threshold as your tuning knob. Too aggressive and you are back to dense cost. Too loose and you re-inherit mean dilution with extra steps.

THE UNCOMFORTABLE QUESTION

Your serving bill assumes every token in the prompt deserves attention. The paper says most of them do not, and your users cannot tell the difference except that the first token shows up six times sooner. So why is your runtime still configured to read everything?

The prefill tax is a default, not a law of physics. You stop paying it the day you measure what you actually need to read.