Fathom Makes KV-Cache Scans Query-Adaptive for Long-Context Decoding

Long-context inference can become a memory-traffic problem rather than a pure compute problem. When agent sessions approach a million tokens and many sessions are active at once, the KV cache and the index used to rank it may reside in host RAM. Every decoding step must then scan a large number of keys to identify the top-k candidates. The scan can cost more than fetching the relatively small set of KV rows that ultimately wins.

Fathom changes the usual assumption that every query should use the same scan precision. Its method allows each query to decide how many bits to read from every key channel. The underlying 4-bit K cache is stored in channel-major bit planes. Reading the first t planes of a channel is equivalent to using that channel’s t-bit quantized value, so partial reads remain contiguous and provide progressively finer approximations.

Given a total bit budget, Fathom uses a reverse water-filling rule to assign more bits to channels that matter more for the current query. The allocation has a closed-form solution and is implemented in a single Triton kernel, keeping the control path lightweight.

The reported findings are notable:

• On Qwen3-8B with a one-million-token context on an A100, Fathom is 1.67 times faster in GPU time than 136-bit scans used by Double Sparsity, Loki, and SparQ configurations.
• At the same GPU time as SparQ’s 68-bit read configuration, Fathom reads 18% fewer bytes and produces lower attention error in six of seven model and context settings.
• On RULER-style tasks, its per-token scan agrees with exact top-k decoding. On real OpenHands coding-agent sessions, a 92-bit read reaches the step agreement of the most accurate 136-bit scan.

The broader implication is a shift from uniformly compressing or scanning an index toward assigning a read budget per query. In systems where KV data truly lives in host memory, eliminating unnecessary transfers can be more valuable than reducing arithmetic alone. Fathom is not a universal speedup, however. When the index is already in GPU memory, the scan is arithmetic-bound, so reading fewer bits does not remove the corresponding multiply-add work. The authors also report that the calibration domain has little effect on results and provide code, result files, and run chains for reproduction.

Source: Hugging Face Daily Papers