PopKV: Popcount-Based Query–Key Scoring for Efficient Long-Context KV Retrieval

Autoregressive decoding for long-context large language models repeatedly reads the accumulated keys and values whenever a new token is generated. As the context length grows, both the KV-cache footprint and memory traffic increase, causing per-token latency to rise sharply under constraints imposed by HBM bandwidth and data-movement energy. Existing query-aware sparse-attention methods select only a subset of KV entries relevant to the current query; however, projection-based token retrieval may require precomputed bases and additional floating-point operations, whereas page-level pruning may fetch irrelevant KV entries within selected pages. FIER provides fine-grained token-level retrieval with compact 1-bit keys, but its scale-aware, full-dimensional scoring over all tokens can make candidate selection a substantial cost in its own right. We treat the cost of candidate-key selection before exact attention as an independent bottleneck and propose PopKV, a training-free 2-bit token-level retrieval method. PopKV assigns one sign bit and one magnitude bit to each token dimension and approximates query–key scores primarily through bitwise logical operations and population-count operations that count the number of one-bits in each 32-dimensional group. Token-axis statistics determine the relative magnitude bits of keys, while dimension-axis statistics construct low/high representative values. This design preserves ranking information while converting continuous FP16 inner products into a small number of packed-integer operations and scalar accumulations. Exact attention is then performed using the original-precision KV entries only for the selected Top-k tokens, enabling fine-grained KV retrieval without a separate projection basis or explicit key dequantization.