---
title: "Quest: Query-Aware Sparsity for Efficient — Tang 2024"
description: "Generating text with very long contexts is slow because every new token requires reading the full KV cache from memory."
authors: ["Jiaming Tang", "Yilong Zhao", "Kan Zhu", "Guangxuan Xiao", "Baris Kasikci", "Song Han"]
year: 2024
venue: "arXiv:2406.10774"
source: "https://arxiv.org/abs/2406.10774"
doi: "10.48550/arxiv.2406.10774"
arxiv: "2406.10774"
licence: "arXiv — non-exclusive license to distribute"
licence_url: "http://arxiv.org/licenses/nonexclusive-distrib/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/tang-2024-quest-query-aware-sparsity-efficient/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/tang-2024-quest-query-aware-sparsity-efficient/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2024](https://md.research.elamur.ai/free/en/papers/2024/page/4/) / Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference

# Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference

**Authors:** [Jiaming Tang](https://md.research.elamur.ai/free/en/authors/jiaming-tang/), Yilong Zhao, Kan Zhu, [Guangxuan Xiao](https://md.research.elamur.ai/free/en/authors/guangxuan-xiao/), Baris Kasikci, [Song Han](https://md.research.elamur.ai/free/en/authors/song-han/) · **Year:** 2024 · **Venue:** arXiv:2406.10774 · **Licence:** [arXiv — non-exclusive license to distribute](http://arxiv.org/licenses/nonexclusive-distrib/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2406.10774) · [PDF](https://arxiv.org/pdf/2406.10774) · [DOI 10.48550/arxiv.2406.10774](https://doi.org/10.48550/arxiv.2406.10774) · [arXiv 2406.10774](https://arxiv.org/abs/2406.10774) · [OpenAlex](https://openalex.org/W4399794499)

**Citations:** 1 citations (openalex-snapshot · 2026-10-14) · [196](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
Generating text with very long contexts is slow because every new token requires reading the full KV cache from memory. For Llama 7B at 32K tokens, that cache reaches about 16GB. Earlier eviction methods such as H2O, TOVA and StreamingLLM permanently drop tokens judged unimportant from past attention. The authors show that which tokens matter shifts with each new query, so a dropped token may be needed later.

Quest keeps the whole cache but reads only the relevant parts. The cache is split into pages, and each page stores the per-dimension minimum and maximum of its Key vectors. At every decoding step, the current Query is combined with these bounds to estimate an upper limit on attention for each page. Exact attention is then computed only over the Top-K highest-scoring pages.

Tests on PG19, passkey retrieval and LongBench show better accuracy than baselines at equal token budgets, along with large latency gains. This makes long-context serving cheaper without retraining.

## Key points
- At 32K context with a 2048-token budget, self-attention runs up to 7.03× faster than FlashInfer. End-to-end decoding is 1.74× faster with FP16 weights and 2.23× faster with 4-bit AWQ weights.
- Evaluations used LongChat-7b-v1.5-32k and Llama-2-7B, with token budgets from 256 to 4K. Outside the first two layers, more than 90% of KV tokens could be skipped with almost no change in PG19 perplexity.
- In passkey retrieval, Quest's recall of the top-attended tokens stays close to full attention, while H2O's recall drops noticeably.
- Under a lossless-accuracy target on LongBench, NarrativeQA needed about 5K tokens with Quest versus 14K with TOVA. Attention ran 3.82× faster on GovReport and 4.54× faster on TriviaQA.
- The paper appeared at ICML 2024, and the code is published at github.com/mit-han-lab/Quest.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Other](https://md.research.elamur.ai/free/en/shelves/other/)

## Cited by

Cited by

196 papers of our library cite it (of the 140673 whose bibliographies we read); 3 of them have a page here, 193 not yet.

- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://md.research.elamur.ai/free/en/papers/jiang-2024-minference-1-0-accelerating-pre/)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://md.research.elamur.ai/free/en/papers/xiao-2024-duoattention-efficient-long-context-llm/)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://md.research.elamur.ai/free/en/papers/yuan-2025-native-sparse-attention-hardware/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{tang2024quest,
  title = {{Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference}},
  author = {Tang, Jiaming and Zhao, Yilong and Zhu, Kan and Xiao, Guangxuan and Kasikci, Baris and Han, Song},
  year = {2024},
  doi = {10.48550/arxiv.2406.10774},
  eprint = {2406.10774},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2406.10774}
}
```

- [← previous QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs](https://md.research.elamur.ai/free/en/papers/ashkboos-2024-quarot-outlier-free-4-bit/)
- [next → Question-Answering (QA) Model for a Personalized Learning Assistant for Arabic Language](https://md.research.elamur.ai/free/en/papers/sammoudi-2024-question-answering-qa-model-personalized/)
- [↑ back to papers of 2024](https://md.research.elamur.ai/free/en/papers/2024/page/4/)

## References

29 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Anthropic. Introducing the next generation of Claude. [https://www.anthropic.com/news/claude-3-family](https://www.anthropic.com/news/claude-3-family), 2024. [Accessed 28-05-2024]. [↗](https://www.anthropic.com/news/claude-3-family)
2. Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou, L., Dong, Y., Tang, J., and Li, J. Longbench: A bilingual, multitask benchmark for long context understanding, 2023. [find](https://scholar.google.com/scholar?q=Bai%2C+Y%2E%2C+Lv%2C+X%2E%2C+Zhang%2C+J%2E%2C+Lyu%2C+H%2E%2C+Tang%2C+J%2E%2C+Huang%2C+Z%2E%2C+Du%2C+Z%2E%2C+Liu%2C+X%2E%2C+Zeng%2C+A%2E%2C+Hou%2C+L%2E%2C+Dong%2C+Y%2E%2C+Tang%2C+J%2E%2C+and+Li%2C+J%2E+Longbench%3A+A+bilingual%2C+multitask+benchmark+for+long+context+understanding%2C) [our card](https://md.research.elamur.ai/free/en/papers/bai-2023-longbench-bilingual-multitask-benchmark/)
3. Dao, T., Fu, D. Y., Ermon, S., Rudra, A., and Ré, C. Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022. [find](https://scholar.google.com/scholar?q=Dao%2C+T%2E%2C+Fu%2C+D%2E+Y%2E%2C+Ermon%2C+S%2E%2C+Rudra%2C+A%2E%2C+and+Re%CC%81%2C+C%2E+Flashattention%3A+Fast+and+memory%2Defficient+exact+attention+with+io%2Dawareness%2C+2022%2E)
4. Dasigi, P., Lo, K., Beltagy, I., Cohan, A., Smith, N. A., and Gardner, M. A dataset of information-seeking questions and answers anchored in research papers, 2021. [find](https://scholar.google.com/scholar?q=Dasigi%2C+P%2E%2C+Lo%2C+K%2E%2C+Beltagy%2C+I%2E%2C+Cohan%2C+A%2E%2C+Smith%2C+N%2E+A%2E%2C+and+Gardner%2C+M%2E+A+dataset+of+information%2Dseeking+questions+and+answers+anchored+in+research+papers%2C+2021%2E) [our card](https://md.research.elamur.ai/free/en/papers/dasigi-2021-dataset-information-seeking-questions-answers/)
5. Ge, S., Zhang, Y., Liu, L., Zhang, M., Han, J., and Gao, J. Model tells you what to discard: Adaptive kv cache compression for llms, 2024. [find](https://scholar.google.com/scholar?q=Ge%2C+S%2E%2C+Zhang%2C+Y%2E%2C+Liu%2C+L%2E%2C+Zhang%2C+M%2E%2C+Han%2C+J%2E%2C+and+Gao%2C+J%2E+Model+tells+you+what+to+discard%3A+Adaptive+kv+cache+compression+for+llms%2C+2024%2E) [our card](https://md.research.elamur.ai/free/en/papers/ge-2023-model-tells-discard-adaptive-kv/)
6. Huang, L., Cao, S., Parulian, N., Ji, H., and Wang, L. Efficient attentions for long document summarization. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1419– 1436, Online, June 2021. Associati… [find](https://scholar.google.com/scholar?q=Huang%2C+L%2E%2C+Cao%2C+S%2E%2C+Parulian%2C+N%2E%2C+Ji%2C+H%2E%2C+and+Wang%2C+L%2E+Efficient+attentions+for+long+document+summarization%2E+In+Proceedings+of+the+2021+Conference+of+the+North+American+Chapter+of+the+Association+for+) [our card](https://md.research.elamur.ai/free/en/papers/huang-2021-efficient-attentions-long-document-summarization/)
7. Joshi, M., Choi, E., Weld, D., and Zettlemoyer, L. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Barzilay, R. and Kan, M.-Y. (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 160… [find](https://scholar.google.com/scholar?q=Joshi%2C+M%2E%2C+Choi%2C+E%2E%2C+Weld%2C+D%2E%2C+and+Zettlemoyer%2C+L%2E+TriviaQA%3A+A+large+scale+distantly+supervised+challenge+dataset+for+reading+comprehension%2E+In+Barzilay%2C+R%2E+and+Kan%2C+M%2E%2DY%2E+%28eds%2E%29%2C+Proceedings+of+the+5) [our card](https://md.research.elamur.ai/free/en/papers/joshi-2017-triviaqa-large-scale-distantly-supervised/)
8. Kočiský, T., Schwarz, J., Blunsom, P., Dyer, C., Hermann, K. M., Melis, G., and Grefenstette, E. The NarrativeQA reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:317–328, 2018. doi: 10.1162/tacl a 00023. URL https://aclanthology.org/Q18-1023. [↗](https://aclanthology.org/Q18-1023) [our card](https://md.research.elamur.ai/free/en/papers/kocisky-2018-narrativeqa-reading-comprehension-challenge/)
9. Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J. E., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023. [find](https://scholar.google.com/scholar?q=Kwon%2C+W%2E%2C+Li%2C+Z%2E%2C+Zhuang%2C+S%2E%2C+Sheng%2C+Y%2E%2C+Zheng%2C+L%2E%2C+Yu%2C+C%2E+H%2E%2C+Gonzalez%2C+J%2E+E%2E%2C+Zhang%2C+H%2E%2C+and+Stoica%2C+I%2E+Efficient+memory+management+for+large+language+model+serving+with+pagedattention%2E+In+Proceedin)
10. Li, D., Shao, R., Xie, A., Sheng, Y., Zheng, L., Gonzalez, J. E., Stoica, I., Ma, X., and Zhang, H. How long can open-source llms truly promise on context length?, June 2023. URL [https://lmsys.org/blog/2023-06-29-longchat](https://lmsys.org/blog/2023-06-29-longchat). [↗](https://lmsys.org/blog/2023-06-29-longchat)
11. Liu, H., Yan, W., Zaharia, M., and Abbeel, P. World model on million-length video and language with blockwise ringattention, 2024a. [find](https://scholar.google.com/scholar?q=Liu%2C+H%2E%2C+Yan%2C+W%2E%2C+Zaharia%2C+M%2E%2C+and+Abbeel%2C+P%2E+World+model+on+million%2Dlength+video+and+language+with+blockwise+ringattention%2C+2024a%2E)
12. Liu, X., Yan, H., Zhang, S., An, C., Qiu, X., and Lin, D. Scaling laws of rope-based extrapolation, 2024b. [find](https://scholar.google.com/scholar?q=Liu%2C+X%2E%2C+Yan%2C+H%2E%2C+Zhang%2C+S%2E%2C+An%2C+C%2E%2C+Qiu%2C+X%2E%2C+and+Lin%2C+D%2E+Scaling+laws+of+rope%2Dbased+extrapolation%2C+2024b%2E)
13. NVIDIA. Nvidia ada lovelace professional gpu architecture. [https://images.nvidia.com/aem-dam/en-zz/Solutions/technologies/NVIDIA-ADA-GPU-PROVIZ-Architecture-Whitepaper_1.1.pdf](https://images.nvidia.com/aem-dam/en-zz/Solutions/technologies/NVIDIA-ADA-GPU-PROVIZ-Architecture-Whitepaper_1.1.pdf), 2023. [Accessed 28-05-2024]. [↗](https://images.nvidia.com/aem-dam/en-zz/Solutions/technologies/NVIDIA-ADA-GPU-PROVIZ-Architecture-Whitepaper_1.1.pdf)
14. NVIDIA. Nvbench: Nvidia’s benchmarking tool for gpus, 2024. Available online: [https://github.com/NVIDIA/nvbench](https://github.com/NVIDIA/nvbench). [↗](https://github.com/NVIDIA/nvbench)
15. OpenAI. New models and developer products announced at devday. [https://openai.com/blog/new-models-and-developer-products-announced-at-de](https://openai.com/blog/new-models-and-developer-products-announced-at-de) OpenAI, November 2023. Accessed: 2024-01-31. [↗](https://openai.com/blog/new-models-and-developer-products-announced-at-de)
16. OpenAI. Introducing gpt-4o: our fastest and most affordable flagship model. [https://platform.openai.com/docs/models](https://platform.openai.com/docs/models), 2024. [Accessed 28-05-2024]. [↗](https://platform.openai.com/docs/models)
17. Oren, M., Hassid, M., Adi, Y., and Schwartz, R. Transformers are multi-state RNNs, 2024. URL https://arxiv.org/abs/2401.06104. arXiv:2401.06104. [↗](https://arxiv.org/abs/2401.06104)
18. Peng, B., Quesnelle, J., Fan, H., and Shippole, E. Yarn: Efficient context window extension of large language models, 2023. [find](https://scholar.google.com/scholar?q=Peng%2C+B%2E%2C+Quesnelle%2C+J%2E%2C+Fan%2C+H%2E%2C+and+Shippole%2C+E%2E+Yarn%3A+Efficient+context+window+extension+of+large+language+models%2C+2023%2E)
19. Rae, J. W., Potapenko, A., Jayakumar, S. M., Hillier, C., and Lillicrap, T. P. Compressive transformers for long-range sequence modelling. arXiv preprint, 2019. URL https://arxiv.org/abs/1911.05507. [↗](https://arxiv.org/abs/1911.05507) [our card](https://md.research.elamur.ai/free/en/papers/rae-2019-compressive-transformers-long-range-sequence/)
20. Ribar, L., Chelombiev, I., Hudlass-Galley, L., Blake, C., Luschi, C., and Orr, D. Sparq attention: Bandwidth-efficient llm inference, 2023. [find](https://scholar.google.com/scholar?q=Ribar%2C+L%2E%2C+Chelombiev%2C+I%2E%2C+Hudlass%2DGalley%2C+L%2E%2C+Blake%2C+C%2E%2C+Luschi%2C+C%2E%2C+and+Orr%2C+D%2E+Sparq+attention%3A+Bandwidth%2Defficient+llm+inference%2C+2023%2E)
21. Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., and Liu, Y. Roformer: Enhanced transformer with rotary position embedding, 2023. [find](https://scholar.google.com/scholar?q=Su%2C+J%2E%2C+Lu%2C+Y%2E%2C+Pan%2C+S%2E%2C+Murtadha%2C+A%2E%2C+Wen%2C+B%2E%2C+and+Liu%2C+Y%2E+Roformer%3A+Enhanced+transformer+with+rotary+position+embedding%2C+2023%2E)
22. Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lample, G. Llama: Open and efficient foundation language models, 2023. [find](https://scholar.google.com/scholar?q=Touvron%2C+H%2E%2C+Lavril%2C+T%2E%2C+Izacard%2C+G%2E%2C+Martinet%2C+X%2E%2C+Lachaux%2C+M%2E%2DA%2E%2C+Lacroix%2C+T%2E%2C+Rozie%CC%80re%2C+B%2E%2C+Goyal%2C+N%2E%2C+Hambro%2C+E%2E%2C+Azhar%2C+F%2E%2C+Rodriguez%2C+A%2E%2C+Joulin%2C+A%2E%2C+Grave%2C+E%2E%2C+and+Lample%2C+G%2E+Llama%3A+Open+and+ef)
23. Tworkowski, S., Staniszewski, K., Pacek, M., Wu, Y., Michalewski, H., and Miłoś, P. Focused transformer: Contrastive training for context scaling, 2023. [find](https://scholar.google.com/scholar?q=Tworkowski%2C+S%2E%2C+Staniszewski%2C+K%2E%2C+Pacek%2C+M%2E%2C+Wu%2C+Y%2E%2C+Michalewski%2C+H%2E%2C+and+Mi%C5%82os%CC%81%2C+P%2E+Focused+transformer%3A+Contrastive+training+for+context+scaling%2C+2023%2E)
24. Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Efficient streaming language models with attention sinks. arXiv, 2023. [find](https://scholar.google.com/scholar?q=Xiao%2C+G%2E%2C+Tian%2C+Y%2E%2C+Chen%2C+B%2E%2C+Han%2C+S%2E%2C+and+Lewis%2C+M%2E+Efficient+streaming+language+models+with+attention+sinks%2E+arXiv%2C+2023%2E)
25. Yang, Z., Qi, P., Zhang, S., Bengio, Y., Cohen, W. W., Salakhutdinov, R., and Manning, C. D. Hotpotqa: A dataset for diverse, explainable multi-hop question answering, 2018. [find](https://scholar.google.com/scholar?q=Yang%2C+Z%2E%2C+Qi%2C+P%2E%2C+Zhang%2C+S%2E%2C+Bengio%2C+Y%2E%2C+Cohen%2C+W%2E+W%2E%2C+Salakhutdinov%2C+R%2E%2C+and+Manning%2C+C%2E+D%2E+Hotpotqa%3A+A+dataset+for+diverse%2C+explainable+multi%2Dhop+question+answering%2C+2018%2E) [our card](https://md.research.elamur.ai/free/en/papers/yang-2018-hotpotqa-dataset-diverse-explainable-multi/)
26. Ye, Z., Lai, R., Lu, R., Lin, C.-Y., Zheng, S., Chen, L., Chen, T., and Ceze, L. Cascade inference: Memory bandwidth efficient shared prefix batch decoding. [https://flashinfer.ai/2024/01/08/cascade-inference.html](https://flashinfer.ai/2024/01/08/cascade-inference.html), Jan 2024. URL https://flashinfer.ai/2024/01/08/cascade-inference.html. Accessed on 202… [↗](https://flashinfer.ai/2024/01/08/cascade-inference.html)
27. Zhang, J., Naruse, A., Li, X., and Wang, Y. Parallel topk algorithms on gpu: A comprehensive study and new methods. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’23, New York, NY, USA, 2023a. Association for Computing Machinery.… — [doi:10.1145/3581784.3607062](https://doi.org/10.1145/3581784.3607062) [find](https://scholar.google.com/scholar?q=Zhang%2C+J%2E%2C+Naruse%2C+A%2E%2C+Li%2C+X%2E%2C+and+Wang%2C+Y%2E+Parallel+topk+algorithms+on+gpu%3A+A+comprehensive+study+and+new+methods%2E+In+Proceedings+of+the+International+Conference+for+High+Performance+Computing%2C+Netwo)
28. Zhang, Z., Sheng, Y., Zhou, T., Chen, T., Zheng, L., Cai, R., Song, Z., Tian, Y., Ré, C., Barrett, C., Wang, Z., and Chen, B. H 2 o: Heavy-hitter oracle for efficient generative inference of large language models, 2023b. [find](https://scholar.google.com/scholar?q=Zhang%2C+Z%2E%2C+Sheng%2C+Y%2E%2C+Zhou%2C+T%2E%2C+Chen%2C+T%2E%2C+Zheng%2C+L%2E%2C+Cai%2C+R%2E%2C+Song%2C+Z%2E%2C+Tian%2C+Y%2E%2C+Re%CC%81%2C+C%2E%2C+Barrett%2C+C%2E%2C+Wang%2C+Z%2E%2C+and+Chen%2C+B%2E+H+2+o%3A+Heavy%2Dhitter+oracle+for+efficient+generative+inference+of+large+la)
29. Zhao, Y., Lin, C.-Y., Zhu, K., Ye, Z., Chen, L., Zheng, S., Ceze, L., Krishnamurthy, A., Chen, T., and Kasikci, B. Atom: Low-bit quantization for efficient and accurate llm serving, 2024. [find](https://scholar.google.com/scholar?q=Zhao%2C+Y%2E%2C+Lin%2C+C%2E%2DY%2E%2C+Zhu%2C+K%2E%2C+Ye%2C+Z%2E%2C+Chen%2C+L%2E%2C+Zheng%2C+S%2E%2C+Ceze%2C+L%2E%2C+Krishnamurthy%2C+A%2E%2C+Chen%2C+T%2E%2C+and+Kasikci%2C+B%2E+Atom%3A+Low%2Dbit+quantization+for+efficient+and+accurate+llm+serving%2C+2024%2E)