# HiRE: High Recall Approximate Top-k Estimation for Efficient LLM Inference

arXiv: https://arxiv.org/abs/2402.09360 · HTML: https://mlsanity.com/paper/2402.09360/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 43 of its 59 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 30 of 43)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [BoolQ: Exploring the Surprising Difficulty of Natural Yes/No Questions](https://mlsanity.com/paper/1905.10044/) (2019)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [SuperGLUE: A Stickier Benchmark for General-Purpose Language Understanding Systems](https://mlsanity.com/paper/1905.00537/) (2019)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [GLaM: Efficient Scaling of Language Models with Mixture-of-Experts](https://mlsanity.com/paper/2112.06905/) (2021)
- [RACE: Large-scale ReAding Comprehension Dataset From Examinations](https://mlsanity.com/paper/1704.04683/) (2017)
- [Adversarial NLI: A New Benchmark for Natural Language Understanding](https://mlsanity.com/paper/1910.14599/) (2019)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [TyDi QA: A Benchmark for Information-Seeking Question Answering in Typologically Diverse Languages](https://mlsanity.com/paper/2003.05002/) (2020)
- [DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale](https://mlsanity.com/paper/2207.00032/) (2022)
- [WiC: the Word-in-Context Dataset for Evaluating Context-Sensitive Meaning Representations](https://mlsanity.com/paper/1808.09121/) (2018)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [Atom: Low-bit Quantization for Efficient and Accurate LLM Serving](https://mlsanity.com/paper/2310.19102/) (2023)
- [SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning](https://mlsanity.com/paper/2012.09852/) (2020)
- [PowerInfer: Fast Large Language Model Serving with a Consumer-grade GPU](https://mlsanity.com/paper/2312.12456/) (2023)
- [ReCoRD: Bridging the Gap between Human and Machine Commonsense Reading Comprehension](https://mlsanity.com/paper/1810.12885/) (2018)
- [LLM in a flash: Efficient Large Language Model Inference with Limited Memory](https://mlsanity.com/paper/2312.11514/) (2023)
- [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023)
- [Sparse GPU Kernels for Deep Learning](https://mlsanity.com/paper/2006.10901/) (2020)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers](https://mlsanity.com/paper/2210.06313/) (2022)

## Built on by (most cited first, 7 of 7)

- [Prompt-prompted Adaptive Structured Pruning for Efficient LLM Generation](https://mlsanity.com/paper/2404.01365/) (2024)
- [Read-ME: Refactorizing LLMs as Router-Decoupled Mixture of Experts with System Co-Design](https://mlsanity.com/paper/2410.19123/) (2024)
- [MemoryFormer: Minimize Transformer Computation by Removing Fully-Connected Layers](https://mlsanity.com/paper/2411.12992/) (2024)
- [Spark Transformer: Reactivating Sparsity in FFN and Attention](https://mlsanity.com/paper/2506.06644/) (2025)
- [Scaling the Vocabulary of Non-autoregressive Models for Efficient Generative Retrieval](https://mlsanity.com/paper/2406.06739/) (2024)
- [Stochastic Sparse Attention for Memory-Bound Inference](https://mlsanity.com/paper/2605.01910/) (2026)
- [A Faster Generalized Two-Stage Approximate Top-K](https://mlsanity.com/paper/2506.04165/) (2025)

## Abstract (arXiv)

Autoregressive decoding with generative Large Language Models (LLMs) on accelerators (GPUs/TPUs) is often memory-bound where most of the time is spent on transferring model parameters from high bandwidth memory (HBM) to cache. On the other hand, recent works show that LLMs can maintain quality with significant sparsity/redundancy in the feedforward (FFN) layers by appropriately training the model to operate on a top-k fraction of rows/columns (where k ≈ 0.05), there by suggesting a way to reduce the transfer of model parameters, and hence latency. However, exploiting this sparsity for improving latency is hindered by the fact that identifying top rows/columns is data-dependent and is usually performed using full matrix operations, severely limiting potential gains. To address these issues, we introduce HiRE (High Recall Approximate Top-k Estimation). HiRE comprises of two novel components: (i) a compression scheme to cheaply predict top-k rows/columns with high recall, followed by full computation restricted to the predicted subset, and (ii) DA-TOP-k: an efficient multi-device approximate top-k operator. We demonstrate that on a one billion parameter model, HiRE applied to both the softmax as well as feedforward layers, achieves almost matching pretraining and downstream accuracy, and speeds up inference latency by 1.47× on a single TPUv5e device.