Fathom: Per-Query Read Depth for Sparse Decoding over Offloaded KV Caches
Vivek Kalyanarangan
cs.LG, cs.CL, cs.DC
2026-09-16
Fathom allocates per-channel key-scan depth per query. At 1M tokens it is 1.67x faster in GPU time than 136-bit scans, and at SparQ r=16's GPU time it reads 18% fewer bytes.
When agent sessions run to hundreds of thousands or a million tokens, and many sessions sit in memory at once, the KV cache and the index that ranks it live in host memory. Sparse attention fetches only the top-k keys and values, but the scores are unknown before the read, so every method first scans a cheap view of all n keys.
On Qwen3-8B at 32k tokens, dense attention reads 4.8 GB per step. The winner rows at k=512 stay near 200 MB regardless of context. A 136-bit scan of the Loki, Double Sparsity, or SparQ r=32 kind is 160 MB at 32k and 5.1 GB at one million tokens. That term becomes the decode traffic. Existing scans either freeze the channel set or read every touched channel to the same depth.
Two pieces share one store.
Keys as bit planes. Each channel is quantized to 4 uniform bits with an fp16 scale per 64-token block. The four bits of a channel become four planes, stored channel-major. The first t planes are exactly the t-bit quantizer under the same scale. No extra low-precision copy is required.
Per-query reverse water-filling. Channel j's contribution to score variance is the query energy on that channel times a calibration variance of the key. One extra bit cuts that channel's remaining error by about four. Under a budget B, each channel gets 0 to 4 bits by how far its importance sits above a water line. A mean-48-bit read touches 30 to 34 of 128 channels. Query heads that share a KV head share the plan.
Models with QK-norm (Qwen3) keep raw channels. Models without it (Llama-3.1, Qwen2.5) store planes of a calibration KLT. A flat per-layer budget is the default. A greedy per-layer plan has to be calibrated at the deployment context length; a 16k plan evaluated at 32k is worse than flat.
On the host, a plane prefix of an active channel is one contiguous run. A gather copies those runs into HBM at link rate, then the scan runs on the GPU.
A100, Qwen3-8B, k=512, rows and scan index in pinned host memory.
At one million tokens, a 56-bit read is 1.67x faster in GPU time than the 136-bit scans and 2.50x faster than an 8-token block-mean landmark index. SparQ r=16 (68 bits) takes 1.05x the GPU time of the 56-bit read; Fathom moves 18% fewer scan bytes and has lower attention error on six of seven settings, up to about 5.3x. The 47-bit read is 1.11x faster than SparQ r=16. With a real prefill at 128k the GPU-time ratio over the 136-bit scan is 1.26x.
Keep the index in HBM and only offload the rows, and every per-token scan lands at 45-48 ms. Fathom is not faster there.
At Double Sparsity's 136-bit error, Fathom needs 46-74 bits, a 1.8-2.9x byte cut.
On RULER-style tasks, every per-token scan sits with exact top-k (Fathom 56-bit 0.881 vs exact 0.874 vs dense 0.884 at 32k). Coding-agent sessions separate them. Forty OpenHands traces of about 95k tokens, scored by word-level step agreement with exact top-k:
| Method | bits | k=512 agreement | k=2048 agreement |
| Fathom 56-bit | 56 | 0.53 | 0.67 |
| SparQ r=16 | 68 | 0.49 | 0.49 |
| SparQ r=32 | 136 | 0.60 | n/a |
| Fathom 92-bit | 92 | 0.60 | n/a |
At k=512, 92 bits match the most accurate 136-bit scan. End-to-end task success with test execution is not measured.
The method is built for one regime: long context, many sessions, KV and index in host memory or slower. A serving stack that already holds a 4-bit K cache can treat the planes as that cache. That path is not built; winner keys still come from bf16 rows.
If the index fits in GPU memory, skip it. On HBM the scan is arithmetic-bound: fewer bits remove bytes, not multiply-adds, and bit extraction is more expensive per byte than a nibble scan. The abstract states this limit up front.
Timing past 128k used synthetic KV contents. The Triton kernels are prototypes and the harness pays Python issue cost, which is why GPU time is the headline metric. In wall-clock, SparQ r=16 is 7% faster at 1M. The agent study was planned at 100 sessions and stopped at 40. The many-session case is argued from index size, not measured. CPU-side retrieval of the MagicPIG or RetroInfer kind is not compared. RULER standard errors are about 0.014 to 0.034, so small gaps among per-token scans are not established. The 128k instruct model was prompted without its chat template, which lowers absolute scores without changing the scan ranking.