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

Long agent sessions push the KV cache out of GPU memory and into host RAM. Once that happens, the thing a decode step waits on is not the model weights or the selected KV rows. It is the index scan that ranks all n keys to pick the top-k, and that scan grows with context while the fetch of the winners does not. For Qwen3-8B the 136-bit-per-token index that Double Sparsity, Loki and SparQ read is 5.1 GB per step at one million tokens against about 200 MB of winner rows.

Fathom lets each query decide how many bits of each key channel to read. Store the 4-bit K cache channel-major as bit planes and the first t planes of a channel are exactly its t-bit quantizer, so a prefix read is exact and contiguous. Each query then spends a bit budget by reverse water-filling over its channel importances, which has a closed form and runs as one Triton kernel.

Measured on an A100 at one million tokens with the cache and index in host memory: a decode step is 1.67x faster in GPU time than the 136-bit scans. Fathom reaches Double Sparsity's attention error at 46 to 74 bits per token on seven model and context settings up to 128k, and on real OpenHands coding-agent sessions it matches the most accurate 136-bit scan at 92 bits.

Two things it does not do. With the index resident in GPU memory it is not faster, because the scan is arithmetic-bound there and reading fewer bits does not remove multiply-adds. And the calibration domain barely matters, which was worth testing and worth reporting.

Code, every result file and the run chains are public, and each table and figure in the paper regenerates from those files.