Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference
Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, Song Han
ICML 2024
cs.CL, cs.LG
2024-06-16
Quest ranks KV pages by a query upper bound on key min/max, loading only top pages. At 32K and 2048-token budget, attention is 7.03× faster than FlashInfer; 4-bit decode is 2.23×.
Long-context decode is slow because it moves too much memory. Each new token has to read the whole history of Keys and Values before attention can run. On Llama-7B at 32K context in FP16, that KV cache is about 16GB. Reading it once with FlashInfer on an RTX 4090 takes at least 11ms and about 53% of decode time. With a 16K prompt and a 512-token answer, decode is more than 86% of the step's wall time.
Attention is sparse, and the sparse set moves. On LongChat-7B, every layer after the first two can drop more than 90% of tokens before PG19 perplexity rises by 0.01. Which tokens matter depends on the current query. In the prompt A is B. C is D. A is, one head gives token B almost no weight when the query is D, then attends to B strongly on the final is. Eviction that keeps tokens by summed past attention (H2O), or that keeps only attention sinks plus a recent window (StreamingLLM), deletes text a later query still needs.
Quest keeps the full KV cache and only chooses which pages to read on this step. Pages follow PageAttention, the same unit vLLM uses. When a token is appended, its page updates two vectors with the same width as the Key: a per-channel minimum and a per-channel maximum.
The page score is an upper bound on the attention dot product. If dimension i of the query is Qi and every Key in the page lies in [mi, Mi] on that channel, Qi times any of those Key values is at most max(Qi·mi, Qi·Mi), whatever the sign of Qi. Summing those per-channel bounds is the largest Q·K the page could contain. No real token in the page can score higher, so a page that holds a critical token is hard to skip. A loose bound also pulls in ordinary pages.
Quest then runs standard attention on the Top-K pages only. The token count inside those pages is the token budget. Experiments use budgets from a few dozen tokens up to 4096. The first two layers are under 10% sparse, so Quest and every baseline leave them dense. That choice is separate from how pages are ranked.
Bytes moved are about 1/page size plus selected pages over total pages. Metadata is two vectors per page; attention touches only the budget. With page size 16, a 64K sequence, and a 4K-token budget, the load is about 1/8 of the full KV cache. Top-K itself costs 5 to 10 microseconds under 128K tokens.
Accuracy is measured on LongChat-7B-v1.5-32k and Yarn-Llama-2-7B-128k against H2O, TOVA, and StreamingLLM. The source text is prefilled with a full cache. The question is then fed one token at a time, so the answer can sit far from the query that needs it.
Passkey retrieval asks the model to recover a short secret buried in long filler.
| Setting | Budget | Quest | H2O | TOVA | StreamingLLM |
| 10K / LongChat-7B | 32 | 65% | 0% | 0% | 1% |
| 10K / LongChat-7B | 64 | 99% | 1% | 1% | 1% |
| 100K / Yarn-Llama-2-7B | 1024 | 96% | 2% | 2% | 1% |
| 100K / Yarn-Llama-2-7B | 2048 | 100% | 2% | 2% | 2% |
64 tokens is about 0.6% of a 10K sequence. 1024 tokens is about 1% of 100K. At a budget of 512 on 10K, and 4096 on 100K, Quest hits 100%. The three eviction methods stay at or below 10%. The secret has already been deleted by the time the question arrives. StreamingLLM never sees a secret outside its recent window.
On PG19 language modeling, LongChat-7B with inputs out to 32K and a budget of 4096 (about 1/8 of the sequence) tracks full-cache perplexity. The paper does not give the exact gap.
Six LongBench tasks are reported: NarrativeQA, Qasper, and MultiFieldQA for single-document QA, HotpotQA for multi-document QA, GovReport for summarization, and TriviaQA for few-shot learning. Quest beats the three baselines at every budget, and a budget near 1K tokens is already close to the full cache. Counting the two dense early layers, Quest stays lossless at a sparsity of 1/6 on Qasper, HotpotQA, and MultiFieldQA, 1/5 on NarrativeQA and GovReport, and 1/10 on TriviaQA.
Kernel time is on an RTX 4090, CUDA 12.2, Llama-2-7B. End-to-end time is single-request decode on an Ada 6000: average latency per generated token, sampling left out.
| Comparison | Setting | Speedup |
| Self-attention vs FlashInfer | 32K, budget 2048 | 7.03× |
| End-to-end vs FlashInfer | 32K, budget 2048, FP16 weights | 1.74× |
| End-to-end vs FlashInfer | 32K, budget 2048, 4-bit AWQ | 2.23× |
Under a lossless-accuracy target, NarrativeQA averages about 24K of context. TOVA needs 14K tokens there; Quest needs 5K. On that same target, Quest is 3.82× faster than TOVA on GovReport and 4.54× faster on TriviaQA. Those two ratios are converted, not run on one kernel. The baselines have no kernels, so the latency is FlashInfer at the token count each method needs, and TOVA's history-score cost is omitted. Quest's timing includes scoring, Top-K, and sparse attention.
The saving is bandwidth. Capacity does not shrink, so concurrent caches still fill GPU memory. For one long request whose time is mostly decode, each step stops reading the whole KV. It reads a min vector and a max vector per page, then a fixed budget of pages. The budget does not grow linearly with length, so latency rises more slowly than FlashInfer as context stretches to 32K.
Eviction buys capacity by deleting tokens. H2O, TOVA, and StreamingLLM can throw away text a later query still needs. Quest leaves the KV resident and picks pages for the query in hand. That trade holds when the needle is buried and the question comes last.
There is no training and no weight change, and the method stacks with weight quantization. Page size and budget are serving knobs. The kernels sit on FlashInfer.
The 7.03× stops at self-attention. The first two layers stay dense, and the FFN is untouched. End-to-end speedup is 1.74× in FP16. With 4-bit weights, attention is a larger share of the step, and end-to-end speedup reaches 2.23×.
The paper has no limitations section. The setup draws the boundary.
Accuracy covers two 7B long-context models and six LongBench tasks. There is no 13B or 70B run, no continuous batching, and no multi-request throughput. End-to-end numbers are single-batch decode with sampling removed.
The page score sums per-channel extremes. If Keys in a page span a wide range, a page with no critical token can still enter the Top-K. The curve in Figure 3 matches an oracle defined by how many tokens can be dropped before PG19 perplexity rises by 0.01. That is not step-by-step recall of the top-10 attention tokens. Figure 4 only reports that Quest's top-10 recall stays near full attention and well above H2O. Recall by budget is not tabulated.
The 3.82× and 4.54× figures were not measured in one kernel. Baselines have no implementation, so latency is FlashInfer at the budget required for lossless accuracy. Quest's own 7.03× and 2.23× are the runs that include every operator.
On the 100K passkey task, H2O's historical scores start only at decode, because prefill uses FlashAttention and never builds the full attention map. That handicap pushes H2O down further. Part of the gap is the protocol.
Each page also stores a min Key and a max Key. Quantization or a larger page can shrink that extra memory, but no byte count is given. A larger page makes estimation cheaper and the bound looser. Page size is not swept in the accuracy tables.