# H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models

**Authors:** Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, Beidi Chen  
**arXiv:** [2306.14048](https://arxiv.org/abs/2306.14048)  
**Date:** 2023-06-24  
**Summary page:** https://www.summarizepaper.com/en/paper/2306.14048v1/

## Key points

- The paper addresses the cost-prohibitive nature of deploying Large Language Models (LLMs) for long-content generation applications.
- Storing a large amount of transient state information known as the KV cache in GPU memory alongside model parameters significantly increases memory usage.
- The authors propose a novel approach to reduce the memory footprint of the KV cache by identifying and removing "Heavy Hitters" (H$_2$), which are tokens that contribute most to the value when computing attention scores.
- They introduce Heavy Hitter Oracle (H$_2$O), a KV cache eviction policy designed to retain a balance between recent tokens and H$_2$ tokens.
- The authors provide theoretical guarantees for their novel eviction algorithm, which is formulated as a dynamic submodular problem.
- The accuracy of their algorithm is validated across various tasks using OPT, LLaMA, and GPT-NeoX models.
- Implementing H$_2$O with 20% heavy hitters improves throughput by up to 29x compared to leading inference systems DeepSpeed Zero-Inference, Hugging Face Accelerate, and FlexGen on OPT-6.7B and OPT-30B models.
- H$_2$O also reduces latency by up to 1.9x with the same batch size.
- Code for implementing H$_2$O is available at https://github.com/FMInference/H2O.

## Summary

In their paper titled "H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models," Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen address the cost-prohibitive nature of deploying Large Language Models (LLMs) for applications involving long-content generation such as dialogue systems and story writing. The authors highlight that storing a large amount of transient state information known as the KV cache in GPU memory alongside model parameters can significantly increase memory usage. This cache scales linearly with the sequence length and batch size. To tackle this issue and reduce the memory footprint of the KV cache, the authors propose a novel approach based on their observation that only a small portion of tokens contributes most to the value when computing attention scores. They refer to these tokens as Heavy Hitters (H$_2$). Through extensive investigation they find that H$_2$ naturally emerges and strongly correlates with frequent token co-occurrence in text. Removing these heavy hitters leads to significant performance degradation. Based on their insights, the authors introduce Heavy Hitter Oracle (H$_2$O), a KV cache eviction policy designed to dynamically retain a balance between recent tokens and H$_2$ tokens. They formulate the KV cache eviction as a dynamic submodular problem and provide theoretical guarantees for their novel eviction algorithm. The accuracy of their algorithm is validated across various tasks using OPT, LLaMA, and GPT-NeoX models. The implementation of H$_2$O with 20% heavy hitters improves throughput by up to 29x , 29x , and 3x compared to leading inference systems DeepSpeed Zero-Inference , Hugging Face Accelerate , and FlexGen on OPT-6 .7B and OPT -30B . Furthermore , H $ _ 2 $ O reduces latency by up to 1 .9 x with the same batch size . The authors provide code for their implementation of H $ _ 2 $ O at https://github .com/FMInference/H2O .