PQ-HSA: Reusing Product-Quantized Scores for Hybrid Sparse-Approximate Attention

At each decoding step a language model attends over the key-value (KV) cache of every earlier token, so at long context the attention call is bounded by memory bandwidth. Sparse attention reads only a subset of keys chosen by a cheap score estimate, and most methods give the unread tokens zero weight, so accuracy drops at small budgets, most on tasks that aggregate information across the context.

PQ-HSA (hybrid sparse-approximate attention) builds an inverted-file product-quantization (IVF-PQ) index over the cached keys. It attends the selected tokens with their original keys and values, while the unselected tokens enter the same softmax through their PQ scores, summed per inverted list and multiplied by the list’s mean value. At 128K and a 1-2% retrieval budget, PQ-HSA is more accurate than Quest and SnapKV on Llama-3.1-8B and Qwen3-30B-A3B and stays close to full attention; inside vLLM on one NVIDIA H20, the decode attention call runs 1.6x faster than the FlashAttention-3 kernel. A vLLM plugin runs PQ-HSA without changes to the engine source.