Research map / Architectures and efficiency / Attention and transformers
QUEST: Query-Aware Sparsity for Efficient Long-Context LLM Inference
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Quest proposes a training-free, query-aware KV cache page selection method that uses per-page min/max key metadata to estimate page criticality and attends only to the top-K pages, speeding up long-context decoding.
Problem
Long-context LLM decoding is slowed by loading the full KV cache during self-attention, and existing KV cache eviction methods discard tokens based on history or current state, losing tokens that become critical for later queries.
Approach
Keep the full KV cache but, per page of keys, store channel-wise min and max key vectors; for each new query compute an upper bound on page attention scores from these and attend only to the top-K pages, so critical tokens are chosen dynamically per query.
Key results
- Quest achieves up to 7.03x self-attention speedup at 32K context with a 2048 token budget versus FlashInfer.
- End-to-end decode latency is reduced 2.23x at 32K context with 2048 budget and 4-bit weight quantization (1.74x with FP16 weights).
- On 10K and 100K passkey retrieval, Quest reaches near-perfect accuracy with a 64 (10K) or 1024 (100K) token budget, where H2O, TOVA and StreamingLLM fail.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use query-aware page selection instead of historical-attention KV eviction | LongChat-7b-v1.5-32k · Passkey retrieval, 10k tokens, budget 64 | accuracy: 1% -> 99% (H2O); 1% -> 99% (TOVA); 1% -> 99% (StreamingLLM) | Helped |
| Use query-aware page selection instead of historical-attention KV eviction | Yarn-Llama-2-7b-128k · Passkey retrieval, 100k tokens, budget 1024 | accuracy: 2% -> 96% (H2O); 2% -> 96% (TOVA); 1% -> 96% (StreamingLLM) | Helped |
| Use query-aware page selection instead of historical-attention KV eviction | LongChat-7b-v1.5-32k · Passkey retrieval, 10k tokens, budget 512 | accuracy: 8% -> 100% (TOVA); 5% -> 100% (StreamingLLM); 3% -> 100% (H2O) | Helped |
| Use query-aware page selection instead of historical-attention KV eviction | Yarn-Llama-2-7b-128k · Passkey retrieval, 100k tokens, budget 2048 | accuracy: 2% -> 100% (H2O); 2% -> 100% (TOVA); 2% -> 100% (StreamingLLM) | Helped |
| Use Quest with token budget 2048 and FP16 weights instead of full-cache FlashInfer | Llama2-7B · Decode, 32K sequence length | inference speedup: 1.74× | Helped |
| Use Quest with token budget 2048 and 4-bit weight quantization instead of full-cache FlashInfer | Llama2-7B · Decode, 32K sequence length | inference speedup: 2.23× | Helped |
| Use Quest attention instead of FlashInfer full attention | Llama2-7B · Self-attention, 32K sequence length, token budget 2048 | self-attention speedup: 7.03× | Helped |
| Use Quest instead of TOVA at the same accuracy target | LongBench GovReport · Lossless accuracy comparison | inference speedup: 3.82× | Helped |
| Use Quest instead of TOVA at the same accuracy target | LongBench TriviaQA · Lossless accuracy comparison | inference speedup: 4.54× | Helped |
| Use a 1K-token Quest budget instead of full KV cache | LongChat-7b-v1.5-32k · LongBench | accuracy | No clear effect |
| Use Quest instead of H2O, TOVA, or StreamingLLM | LongChat-7b-v1.5-32k · LongBench, six datasets and various KV cache budgets | accuracy | Helped |
| Use Quest with a 4096-token budget instead of full KV cache | LongChat-7b-v1.5-32k · PG19 test | perplexity | No clear effect |
Surprising findings
- The first two layers of the model have low attention sparsity, so Quest and baselines are applied only to later layers to preserve accuracy.
Limitations
- Evaluation is limited to a few 7B long-context models.
- Baselines lack kernel implementations, so their latency is only qualitatively estimated using FlashInfer timings.
- The first two layers are left at full attention because of low sparsity.
Experimental setup
Datasets: PG19 passkey retrieval LongBench
Benchmarks: PG19 passkey retrieval LongBench NarrativeQA LongBench HotpotQA LongBench Qasper LongBench TriviaQA LongBench GovReport LongBench MultiFieldQA
Metrics: perplexity accuracy recall rate latency speedup
Baselines: H2O TOVA StreamingLLM FlashInfer SparQ
Builds on: FlashInfer PagedAttention H2O StreamingLLM
Closest papers by meaning
- SCBench: A KV Cache-Centric Analysis of Long-Context Methods (ICLR 2025 · similarity 0.93)
- SparQ Attention: Bandwidth-Efficient LLM Inference (ICML 2024 · similarity 0.92)
- ThinK: Thinner Key Cache by Query-Driven Pruning (ICLR 2025 · similarity 0.92)
- CateKV: On Sequential Consistency for Long-Context LLM Inference Acceleration (ICML 2025 · similarity 0.92)
- ArkVale: Efficient Generative LLM Inference with Recallable Key-Value Eviction (NeurIPS 2024 · similarity 0.92)
- Efficient Low Rank Attention for Long-Context Inference in Large Language Models (NeurIPS 2025 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.