SANTA++ uses 16–22% of dense KV reads — Inverse-probability sampled attention — What does it mean?

The news. On September 28, 2026, a team from UC Santa Barbara and Flucta posted SANTA++, a training-free attention method for decoding. With Qwen2.5-7B-Instruct at 32K context and 32 or 64 sampled teams, the paper reports 16–22% of dense attention's KV reads while keeping 94–99% of the dense baseline's scores on LongBench v2 and HELMET's RAG subset, and 85–91% on RULER. Its Triton kernel reports a 1.69× attention speedup over FlashAttention on one 32K decode workload. Read the paper →

Picture a city council that needs the average opinion of a million households by tonight. Knocking on every door is the honest answer and takes all week; that is dense attention, where each new token's query is scored against every cached key and every value is read. A lazy council could instead survey only the few loudest neighbourhoods and report their view as the city's view. That is top-k sparse attention: fast, but the quiet majority is simply missing from the total.

SANTA++ runs the survey the way a statistician would. Once, right after the prompt is processed, it groups the cached keys into teams of similar keys and picks one real key per team as the representative, like phoning one household to get a feel for each neighbourhood. On every decoding step the query scores only those representatives, scales each score by the team's size to guess the team's share of attention, and then samples teams at random in proportion to those guesses. Surveyors then walk every door in a sampled neighbourhood: the method reads the actual keys and values of every member of each sampled team and computes their exact attention scores.

The last move is the one that makes it a survey and not a shortcut. A team that had a 1-in-4 chance of being sampled has its contribution counted four times, and a team that was almost certain to be picked is counted once. That inverse-probability weight is applied to both halves of the softmax, the value-weighted sum and the normalizing total, and the paper shows that both sums are unbiased estimates of the full-cache sums. Their ratio, the actual attention output, is generally slightly biased, and selecting every team recovers dense attention exactly.

Why bother with representatives at all? Because the expensive part is not the arithmetic. During decode, every step re-reads the whole cache from HBM; the paper puts that at about 64 MiB per layer for every generated token for Qwen2.5-7B at 32K context in bf16. An earlier version, SANTA, sampled from the exact attention distribution, but to know that distribution it first had to score every key, which the paper's counter puts at 50% of dense reads before any value is touched. Representatives are what let SANTA++ decide where to look without first reading every key.

The paper also explains why the representative is a real key and not the group's average key. Scoring a group's mean key can badly underestimate its attention mass, because of Jensen's inequality (the two agree only when every key in the group scores the same): the exponential of an average is smaller than the average of exponentials. Take four keys with scores 0, 0, 0 and 8 (illustrative). The exact mass is 1 + 1 + 1 + e⁸ ≈ 2,984; the mean score is 2, and four copies of e² give only ≈ 30. A single sharp match, which is exactly what attention looks for, vanishes inside the average. Starting each team from the key nearest the mean and then adding the keys farthest from the existing representatives keeps such outliers visible.

Here is where the correction earns its keep (illustrative numbers). Say the cache splits into 61 teams: one heavy team with attention mass 40 and sixty light teams with mass 1 each, so the true total is 100. Top-1 selection reads the heavy team and reports a total of 40, handing it 100% of the attention instead of its true 40%. Now sample instead, always reading exactly 7 teams, as SANTA++ does with a fixed budget. Suppose the heavy team is picked with probability 0.7; when it is, six light teams join it, and when it is not, seven light teams are read. Each light team then has an inclusion probability of (0.7 × 6 + 0.3 × 7) / 60 = 0.105. Each sampled team is divided by its own inclusion probability. A draw that contains the heavy team estimates 40 / 0.7 + 6 / 0.105 ≈ 114.3; a draw without it estimates 7 / 0.105 ≈ 66.7. Averaged over draws, 0.7 × 114.3 + 0.3 × 66.7 = 100, from 7 of 61 teams read every time. That is noise around the right answer, not a lean toward the wrong one, and a larger budget generally shrinks it.

Two limits keep the headline honest. The 16–22% is a count of logical key and value reads, not measured memory traffic, and the 1.69× speedup is one attention operator on one layer (63.52 µs against 107.33 µs for FlashAttention, 32K tokens, batch size one, an RTX 5090 Laptop GPU) with the one-time team building excluded. The paper notes that end-to-end gains depend on that preparation cost and on how many tokens are generated. It also frames the method as complementary to cache compression such as multi-head latent attention or GQA: those shrink each cached entry, while sampling reduces how many entries each query reads. The kernel itself follows the FlashAttention playbook of fusing selection, reads and a split softmax into a few launches; the code is published on GitHub.

Goes deeper in: LLM Internals → Self-Attention → From Scores to Output

Related explainers

• CompKV — Compensation-aware KV block selection — the deterministic alternative: choose blocks exactly and patch the rest with a summary.
• FlashMemory — Lookahead sparse attention — a trained indexer that predicts which chunks to read.
• AVQ-Attention — Adaptive vector-quantized attention — approximate every key with shared codewords instead of skipping any.