Skip to content

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

Sep 2026 · 0 citations · 46 references
Computer Science

TL;DR

PQ-HSA (hybrid sparse-approximate attention) attends the selected tokens with their original keys and values, and the unselected tokens, the background, enter the same softmax through those scores, summed per inverted list and multiplied by the list's mean value.

Abstract

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. The output then draws on only a small fraction of the KV cache, and accuracy drops at small budgets, most on tasks that aggregate information across the context. An inverted-file product-quantization (IVF-PQ) index over the cached keys computes an approximate score for every indexed token in order to rank them; after ranking, those scores approximate the attention logits of the tokens left out. PQ-HSA (hybrid sparse-approximate attention) attends the selected tokens with their original keys and values, and the unselected tokens, the background, enter the same softmax through those 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 in macro accuracy; with the same selector, the background term raises macro accuracy on the 8B model from 0.71 to 0.83. In the same 128K setting, inside vLLM on one NVIDIA H20, the decode attention call runs 1.6x faster than the FlashAttention-3 kernel; the speedup grows with context length, and a cost model fitted on 8B to 30B models gives the context length at which it begins. A vLLM plugin runs PQ-HSA on two engine versions without changes to the engine source; code is available at https://github.com/KunmingSHAO/pqhsa_release.

View source

Similar papers

#machine learning Preprint Sep 2026

SANTA++: Sampling Attention through Representative Keys

Attention often concentrates on a small subset of tokens in the context, but which subset matters changes from one query to the next. To exploit this changing structure, we introduce SANTA++, a training-free stochastic attention method that uses representative keys for memory-efficient selection without scanning the en...

Kyle Lee, Christian Z. Pratt, Ruo-Yu Fang et al. · 0 citations
#natural language process... Preprint Sep 2026

SAS: Simple Attention Sparsification via End-to-End Optimization of Context Ranking

Across reasoning, long-context understanding, and agentic tasks, SAS consistently outperforms trainable sparse attention baselines across attention budgets, with especially large gains under tight budgets, demonstrating more effective context ranking for downstream tasks.

Zhi-Wei Li, Lei Zhu, Hao Gu et al. · 1 citation
#artificial intelligence Preprint Sep 2026

From Attention Sensitivity to Layer Role: Revisiting Mixed-Precision Quantization of Transformers

This work defines one scalar loss over the joint Q, K, V weights of a block, evaluated against the block's real causally-masked attention output, and uses it twice: to fit the quantized weights, and to score the block for a multiple-choice knapsack allocation.

Nafiseh HosseinpourFardi, Negar Alihadi, Mahmoudreza Babaei et al. · 0 citations
Preprint Aug 2026

Beyond Sparse Weights: When Is Attention Compressible?

Results motivate CertKV, a training-free compressor that reserves one tail-summary slot per head and allocates the rest by value dispersion, which is top-two in seven of nine LongBench-v2 settings, remains in the leading compressed tier on 128K RULER, and realizes a ten-fold cache budget in a packed Llama prototype.

Chi-Wun Yang, Xiaoyu Li · 0 citations
#artificial intelligence Preprint Sep 2026

MassAlloc Attention: Let Attention Allocate Its Own Compute

MALA, a fused attention primitive that preserves score access to every legal causal interaction and uses normalized contribution to allocate post-score computation, indicates that allocating post-score computation according to normalized attention contributions can retain the evaluated capabilities of FullAttn while re...

Jing-Ze Shi, Zhang-Yang Peng, Xian-Duo Li et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

MIT News · Artificial Intelligence Oct 23, 2026

Q&A: How AI came to model the “messy” human mind

Assistant Professor Benjamin Lindquist studies how engineers deliberately injected randomness into early AI, giving rise to deep-learning models that sometimes hallucinate.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.