Fathom: Per-Query Read Depth for Sparse Decoding over Offloaded KV Caches

AI summary

Overview

Research area: Efficient large language model inference, specifically top-k sparse attention decoding when the KV cache and its selection index are offloaded to host memory.

Technical level: Advanced. The paper assumes familiarity with grouped-query attention, KV quantization, bit-plane storage, and memory-bandwidth accounting across PCIe.

Scope: The paper proposes Fathom, a method that lets each query choose how many bits of each key channel to read from a bit-plane 4-bit K store, and measures it against fixed-depth sparse scan baselines in offloaded and GPU-resident regimes.

What This Paper Is About

When long agent sessions hold hundreds of thousands to a million tokens and many such sessions are resident at once, the KV cache no longer fits in GPU memory and lives in host memory. Sparse decoding still needs to scan all n keys with a cheap representation to pick the top-k winners, and that scan grows linearly with context while the fetch of the winners does not. Fathom's goal is to shrink the scan by giving every query a per-channel bit budget, so the read depth is decided at query time rather than fixed in advance.

Key Contributions

1. A measured result in the target regime. With the KV cache and its index in host memory on Qwen3-8B at k=512, a decode step is 1.37x faster at 256k tokens and 1.67x faster at 1M tokens in GPU time than the 136-bit scans of Double Sparsity, Loki and SparQ r=32, at equal or better accuracy than Double Sparsity and Loki. Against SparQ's 68-bit read it reads 18% fewer bytes in the same GPU time and is 1.1–5.3x more accurate.

2. A bit-plane key store plus a per-query allocation rule. The 4-bit K cache is stored channel-major as bit planes, so the first t planes of a channel are exactly that channel's t-bit quantizer with the same block scale, and a per-query reverse water-filling rule sets the depth of every channel, with an optional per-layer budget calibrated once.

3. Accuracy and downstream results. Equal-error byte savings of 1.8–2.9x against Double Sparsity's 136-bit scan on 7 settings up to 128k tokens, downstream parity with the exact top-k oracle on RULER-style tasks, and on real coding-agent sessions the step agreement of the most accurate 136-bit scan at 92 bits.

4. A basis rule and a negative analysis. Raw channels are used for models with QK-norm (Qwen3) and planes of the Karhunen–Loève transform of the keys otherwise (Llama-3.1, Qwen2.5); separately, the paper analyses the HBM-resident case, where the method is not faster, and gives an arithmetic-per-byte explanation.

Main Findings

• Target regime (index in host memory, 1M tokens). On an A100 with Qwen3-8B at k=512 and batch 1, Fathom's 56-bit read takes 1.67x less GPU time per decode step than the 32-channel (136-bit) scan, 2.50x less than the block-landmark index and 3.12x less than the 2-bit thumbnail. In wall-clock the ratios are 1.38, 2.07 and 2.59.

• Matched-time comparison with SparQ r=16. SparQ's 68-bit read moves 22% more scan bytes than Fathom's 56-bit read and takes 1.05x its GPU time at 1M. Fathom's mean-40 read, at about 47 bits, is 31% fewer bytes than SparQ r=16 and 1.11x faster; Fathom's mean-64 read (74 bits) costs 1.21x the 56-bit read.

• At 256k and with a real prefill. At 256k the shared row fetch is 167–216 MB per step across methods and GPU time favours the 56-bit read over the 32-channel scan by 1.37x. With a real prefill at 128k the ratio is 1.26x over the 32-channel scan, and SparQ r=16 takes 1.00x Fathom's GPU time. At batch 2 with the synthetic cache the GPU-time ratio over the 32-channel scan is 1.44x at 256k and 1.63x at 512k.

• Where the 1M step goes. Every scan moves bytes at the link rate, about 26 GB/s, so the transfer is where Fathom saves. Its scan kernel costs about twice SparQ's per byte because it extracts bits, and the shared costs of top-k selection, winner-row fetch and weight GEMMs are 33% of Fathom's step and 20% of the 32-channel scan's.

• Equal time, fewer bytes, lower error. Holding GPU time fixed against SparQ r=16, Fathom reads 18% fewer scan bytes and has 1.1–5.3x lower attention-output error on all seven settings with the better of its two plans, and on six with the flat default. The margin is smallest on Qwen3-8B at 32k with the flat budget (close to a tie) and largest at k=2048 on Qwen2.5-7B-1M at 128k (5.3x).

• Equal error, fewer bytes. Double Sparsity's 136-bit error is reached at 46–74 bits on all 7 settings, a 1.8–2.9x saving. SparQ r=32, the strongest fixed-depth scan on six of the seven settings, is reached at 38–92 bits. Loki at 136 bits is matched at 56–75 bits on the 4 settings where it is not rank-limited; on the Qwen3 models Loki collapses.

• Per-layer plans versus flat budget. Per-layer budgets B_l in {24, …, 128} at target means of 48 or 64 bits lower error at mean 48 by about half at 16k and by 8–11% at 32k on the Qwen3 models, but are worse at mean 64 on Qwen3-8B at 32k with k=128, worse on Qwen2.5

Authors’ abstract

When agentic sessions run to a million tokens with many sessions resident at once, the KV cache and the index that ranks it live in host memory, and the scan that ranks all n keys for a top-k step becomes the traffic that bounds decoding. We present Fathom, a key scan in which each query decides how many bits of each key channel to read. The 4-bit K cache is stored channel-major as bit planes, so a prefix of t planes is exactly the channel's t-bit quantizer, and the query spends its bit budget by reverse water-filling over the variance-weighted importance of its channels. At one million tokens on Qwen3-8B a decode step is 1.67x faster in GPU time than with the 136-bit scans of Double Sparsity, Loki and SparQ r=32, and in the same GPU time as SparQ's 68-bit read (r=16) Fathom reads 18% fewer bytes with lower attention error on six of seven model and context settings. On RULER-style tasks every per-token scan matches exact top-k decoding, and on real coding-agent sessions Fathom reaches the step agreement of the most accurate 136-bit scan at 92 bits. The store is the 4-bit K copy a quantized serving stack already holds, and the method is not faster when the index is resident in GPU memory.