# A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Generation and context integration, one of 15 directions in Retrieval-augmented generation.
- Builds on 24 of its 40 references that are in the map.
- First posted on arXiv 14 Jun 2024.

## Placed in

- Retrieval-augmented generation / [Generation and context integration](https://mlsanity.com/rag/generation-and-context-integration/)

## Builds on (most cited first, 24 of 24)

- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Improved Baselines with Visual Instruction Tuning](https://mlsanity.com/paper/2310.03744/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [LLM Maybe LongLM: Self-Extend LLM Context Window Without Tuning](https://mlsanity.com/paper/2401.01325/) (2024)
- [SparQ Attention: Bandwidth-Efficient LLM Inference](https://mlsanity.com/paper/2312.04985/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Transformer Acceleration with Dynamic Sparse Attention](https://mlsanity.com/paper/2110.11299/) (2021)
- [SEA: Sparse Linear Attention with Estimated Attention Mask](https://mlsanity.com/paper/2310.01777/) (2023)

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

- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [Sol-Attn: Accelerating Video Generation Inference via On-the-Fly Attention Sparsification](https://mlsanity.com/paper/2607.24027/) (2026)
- [InfiniteHiP: Extending Language Model Context Up to 3 Million Tokens on a Single GPU](https://mlsanity.com/paper/2502.08910/) (2025)
- [Delta Attention: Fast and Accurate Sparse Attention Inference by Delta Correction](https://mlsanity.com/paper/2505.11254/) (2025)
- [KV Admission: Learning What to Write for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2512.17452/) (2025)
- [SALE : Low-bit Estimation for Efficient Sparse Attention in Long-context LLM Prefilling](https://mlsanity.com/paper/2505.24179/) (2025)
- [Neural Attention Search](https://mlsanity.com/paper/2502.13251/) (2025)
- [Greedy-Gnorm: A Gradient Matrix Norm-Based Alternative to Attention Entropy for Head Pruning](https://mlsanity.com/paper/2602.04491/) (2026)
- [Dynamic Sparse Causal-Attention Temporal Networks for Interpretable Causality Discovery in Multivariate Time Series](https://mlsanity.com/paper/2507.09439/) (2025)
- [BF1: A Causal Dyadic Sparse-Attention Retrofit for Efficient Long-Context Transformers](https://mlsanity.com/paper/2608.20427/) (2026)
- [Block Sparse Attention with Log-Linear Complexity](https://mlsanity.com/paper/2609.31093/) (2026)
- [HHR: Hierarchical Hash Retrieval for Efficient LLM Generation](https://mlsanity.com/paper/2610.01230/) (2026)

## Abstract (arXiv)

In modern large language models (LLMs), increasing the context length is crucial for improving comprehension and coherence in long-context, multi-modal, and retrieval-augmented language generation. While many recent transformer models attempt to extend their context length over a million tokens, they remain impractical due to the quadratic time and space complexities. Although recent works on linear and sparse attention mechanisms can achieve this goal, their real-world applicability is often limited by the need to re-train from scratch and significantly worse performance. In response, we propose a novel approach, Hierarchically Pruned Attention (HiP), which reduces the time complexity of the attention mechanism to O(T log T) and the space complexity to O(T), where T is the sequence length. We notice a pattern in the attention scores of pretrained LLMs where tokens close together tend to have similar scores, which we call ``attention locality''. Based on this observation, we utilize a novel tree-search-like algorithm that estimates the top-k key tokens for a given query on the fly, which is mathematically guaranteed to have better performance than random attention pruning. In addition to improving the time complexity of the attention mechanism, we further optimize GPU memory usage by implementing KV cache offloading, which stores only O(log T) tokens on the GPU while maintaining similar decoding throughput. Experiments on benchmarks show that HiP, with its training-free nature, significantly reduces both prefill and decoding latencies, as well as memory usage, while maintaining high-quality generation with minimal degradation. HiP enables pretrained LLMs to scale up to millions of tokens on commodity GPUs, potentially unlocking long-context LLM applications previously deemed infeasible.