Research map / Architectures and efficiency / Attention and transformers
A Training-Free Sub-quadratic Cost Transformer Model Serving Framework with Hierarchically Pruned Attention
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.
Proposes HiP, a training-free hierarchical tree-search top-k attention approximation (O(T log T) time, O(T) space) with block-wise GPU kernels and KV cache offloading, applied to Llama3.1-8B for long-context serving.
Problem
Quadratic time and space cost of attention limits long-context LLM serving; existing sub-quadratic sparse/linear attention methods usually require retraining and degrade quality.
Approach
Exploits "attention locality" (nearby keys have similar attention scores) to find approximate top-k keys per query via a hierarchical, binary-tree-like search over key chunks represented by their center tokens, implemented block-wise on tensor cores, plus GPU/CPU KV cache offloading that keeps only O(log T) hot tokens on GPU.
Key results
- HiP achieves 6.83x end-to-end decoding speedup at 128k context while retaining 96.0% relative LongBench performance.
- On PG19 HiP gives 9.00x prefill-latency and 29.99x decoding-latency speedup vs FlashAttention2 with perplexity rising from 8.1151 to 8.6499.
- With KV cache offloading on an RTX 4090, serving context extends from 16k to 64k at about 93% of no-offload decoding throughput.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HiP attention instead of FlashAttention | Llama3.1-8B · PG19 | Perplexity: 8.1151 → 8.6499 | Hurt |
| Use HiP attention instead of FlashAttention | Llama3.1-8B · PG19 | Prefill latency: 9.00× faster | Helped |
| Use HiP attention instead of FlashAttention | Llama3.1-8B · PG19 | Decode latency: 29.99× faster | Helped |
| Use HiP 2k instead of AVD with an 8K window | Llama3.1-8B-Instruct · BookSum (Normal Window) | ROUGE-1 | Helped |
| Add V 2k and D 1k to HiP 2k (ablation) | Llama3.1-8B-Instruct · BookSum (Normal Window) | ROUGE-1: 38.84% → 39.98% | Helped |
| Add V 2k and D 1k to HiP 2k (ablation) | Llama3.1-8B-Instruct · BookSum (Normal Window) | Decode speedup: 7.75x → 7.05x | Hurt |
| Use a linear probing hash map instead of a vector map for KV cache indexing (ablation) | HiP KV cache offloading · 512k context | GPU memory consumption: 40.8% | Helped |
| Use a linear probing hash map instead of a vector map for KV cache indexing (ablation) | HiP KV cache offloading · KV cache offloading benchmark | Token access latency | Hurt |
Surprising findings
- Hash-map page table lowers GPU memory by 40.8% at 512k but its GPU lookups are slower than naive UVM.
- AVD scores near-perfectly on passkey retrieval yet fails on GovReport and MultiNews, suggesting passkey tests overstate sparse methods.
Limitations
- Theoretical analysis relies on a simplified k=1 setting and an assumed Gaussian, independent attention-score-difference model, which is only approximately supported empirically.
- Perplexity increases by about 0.53 in the latency-optimized setting, and the r_m mask refresh interval trades quality for latency.
- Hash-based page table adds GPU lookup latency, and UVM offloading slows decoding by 5 to 7 times relative to full GPU runtime.
Experimental setup
Datasets: PG19 LongBench RULER BookSum Wikitext2
Benchmarks: PG19 LongBench RULER BookSum passkey retrieval
Metrics: perplexity accuracy ROUGE latency decoding throughput speedup
Baselines: FlashAttention StreamingLLM AVD BigBird HyperAttention H2O
Builds on: FlashAttention StreamingLLM H2O BigBird HyperAttention
Closest papers by meaning
- Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix (ICLR 2025 · similarity 0.92)
- A Little Goes a Long Way: Efficient Long Context Training and Inference with Partial Contexts (ICLR 2025 · similarity 0.91)
- Efficient Low Rank Attention for Long-Context Inference in Large Language Models (NeurIPS 2025 · similarity 0.91)
- MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention (NeurIPS 2024 · similarity 0.90)
- Curse of High Dimensionality Issue in Transformer for Long Context Modeling (ICML 2025 · similarity 0.90)
- RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval (NeurIPS 2025 · similarity 0.90)
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.