MOIRA: training-free sparse decoding in vLLM, 2.5x faster at 128k with dense-level accuracy

MOIRA: Mass-Oriented Indexing with Ragged Attention for Long-Context Decoding

Dich Nhat Minh Nguyen, Tran Dang Duong Nguyen

cs.AI

2026-10-03

A training-free sparse decode path for vLLM: per-head page selection by attention-mass coverage reads ~30% of the KV cache at 128k, cuts TPOT 2.2-2.7x, and matches dense accuracy.

What problem this solves

Long-context decoding is bound by memory bandwidth: every output token reads the full KV cache of every layer. Sparse decoding reads only part of it, and methods split on how the budget is set. Fixed budgets (Quest, the trained sparse attention in production models) are sized for the hardest head, so most heads over-read and the number needs retuning per workload. Adaptive budgets (Twilight, FFD) follow the query, but pay in host-side planning, a low-bit scan of every key at every step, or training.

The paper's oracle analysis makes the waste concrete. To give 90% of rows 95% of the attention mass, one global budget reads 2.38× the tokens actually needed; even a budget profiled offline per (layer, KV head) reads 1.73×. Demand varies at exactly that granularity: on Llama-3.1-8B the first layer needs 68% of the context on average, several layers need 9%, and the coefficient of variation across KV heads within a layer is 0.74.

A second wall sits in the kernels. FA3 and FlashInfer assume rows of similar length. Give each KV head its own page list and things break: padding reads unselected pages too (measured 492 µs against 489 µs dense, so sparsity buys nothing), FA3's varlen mode reads exactly but slows 23–32% as row lengths spread, and FlashInfer's host-side plan() cannot enter a CUDA graph. Across 32 layers that plan costs 9–22 ms, longer than an entire Moira decode step.

Method

Moira is a training-free sparse decode path for vLLM 0.30: Triton kernels loaded as a Python module via an import hook, no changes to model code or KV layout. Each decode layer runs four kernels, all captured in the CUDA graph.

The granularity is backed by data. Selecting per query head makes several heads demand the same page, 1.51× the reads at equal error; one list shared by all KV heads of a layer needs the union, 78–87% of pages on real data against 33–41% for per-head lists.

Results

One H200, bf16, 64-token pages.

ComparisonResult
RULER-13 128k, Llama-3.1-8B: Moira γ=0.99 vs dense FA371.83 vs 71.51, TPOT 7.7 vs 19.0 ms (2.46×)
Same, γ=0.9819.6% of pages read, TPOT 7.1 ms (2.69×), score 69.60 within benchmark noise
Same, Twilight-36k / FFD67.94 / 64.85, significantly below dense; Quest-36k holds accuracy but its attention step costs 24.1 ms vs dense 15.6
AIME, Qwen3-4B-Thinking, 480 solutions: γ=0.98 vs dense75.2% vs 75.2% at 39.4% of pages, 1.86× faster wall clock; at equal reads proportional top-k gets 41.0%, fixed K=75 gets 69.8%
Online serving, LongBench, concurrency 16output throughput +45% (Llama), +51% (Qwen3-4B); AIME output +88% at concurrency 64

AIME is where the adaptive budget proves itself. RULER answers are a few tokens long, so any generous budget works; AIME generates up to 32k reasoning tokens and small per-step errors compound over thousands of steps. Fixed K=75 loses everything to truncation (131 vs 94 solutions hit the length limit): a short budget does not make the model answer wrongly, it makes it reason longer until it hits the wall. A budget profiled per (layer, KV head) reaches 74.6% but needs 288 fitted counts; the coverage rule gets 75.2% with one γ.

The counterexample is stated plainly: with a single short request, GEMMs dominate the step and Moira runs slower than dense below 32k tokens, passing it only at 64k with 1.05×.

Why it matters

This drops into a production stack: no training, 0.06% KV-capacity loss, and at γ=1 it matches FA3 within one bf16 ulp. A 2–2.7× TPOT cut converts directly into serving throughput under load. The longer-lived idea is making the budget an output of the selection rule instead of a hyperparameter: real per-head demand differs by a median 4.0× (up to 16.6×), so any single number is wrong for most heads.

Limitations

The authors' own list: 4B/8B models from two families, bf16 KV cache, one H200, vLLM 0.30; larger models shift the step toward GEMMs and shrink the speedup; quantized KV, tensor parallelism, latent attention and open-loop serving are untested; Moira saves bandwidth, not capacity, so the full KV cache stays resident. Three more caveats from a close read: γ=0.98 loses 1.9 points on Llama's RULER score, covered by the claim that benchmark noise runs 1.3–2.7 points; Quest and Twilight do not run in vLLM, so they are compared on attention time rather than end to end, and FFD's TPOT comes from its own runtime; at 128k there are only 32 rows, so the kernel's balancing advantage has not paid off yet and the speedup there comes mostly from reading less. The KL error also concentrates on variable-tracking tokens: 43 tokens carry a third of the KL on Llama.

Terms

Source

What people are saying

Related papers

All paper explainers