# CritiPrefill: A Segment-wise Criticality-based Approach for Prefilling Acceleration in LLMs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 42 references that are in the map.
- First posted on arXiv 19 Sep 2024.

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

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Yi: Open Foundation Models by 01.AI](https://mlsanity.com/paper/2403.04652/) (2024)
- [The NarrativeQA Reading Comprehension Challenge](https://mlsanity.com/paper/1712.07040/) (2017)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers](https://mlsanity.com/paper/2105.03011/) (2021)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding](https://mlsanity.com/paper/2404.16710/) (2024)
- [Effective Long-Context Scaling of Foundation Models](https://mlsanity.com/paper/2309.16039/) (2023)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving](https://mlsanity.com/paper/2407.00079/) (2024)
- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)

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

- [CriticalKV: Optimizing KV Cache Eviction from an Output Perturbation Perspective](https://mlsanity.com/paper/2502.03805/) (2025)
- [Locret: Enhancing Eviction in Long-Context LLM Inference with Trained Retaining Heads on Consumer-Grade Devices](https://mlsanity.com/paper/2410.01805/) (2024)
- [Speculative Prefill: Turbocharging TTFT with Lightweight and Training-Free Token Importance Estimation](https://mlsanity.com/paper/2502.02789/) (2025)
- [Efficient Prompt Compression with Evaluator Heads for Long-Context Transformer Inference](https://mlsanity.com/paper/2501.12959/) (2025)
- [KV Prediction for Improved Time to First Token](https://mlsanity.com/paper/2410.08391/) (2024)
- [LoopServe: An Adaptive Dual-phase LLM Inference Acceleration System for Multi-Turn Dialogues](https://mlsanity.com/paper/2507.13681/) (2025)
- [From Rigid to Dynamic: Entropy-Guided Adaptive Inference for Long-Context LLMs](https://mlsanity.com/paper/2606.09508/) (2026)

## Abstract (arXiv)

Large language models have achieved notable success across various domains, yet efficient inference is still limited by the quadratic computation complexity of the attention mechanism. The inference consists of prefilling and decoding phases. Although several attempts have been made to accelerate decoding, the inefficiency of the prefilling phase, especially for long-context tasks, remains a challenge. In this paper, we observe a locality in query criticality during the prefilling phase of long-context processing: adjacent query tokens tend to focus on similar subsets of the past Key-Value (KV) cache. Based on this observation, we propose CritiPrefill, a criticality-based segment-wise prefilling method. This method partitions the input sequence's queries and KV cache into segments and blocks, utilizing a segment-wise algorithm to estimate the query criticality. By pruning non-critical computations between query segments and cache blocks in the self-attention mechanism, the prefilling process can be significantly accelerated. Extensive evaluations on multiple long-context datasets show up to 2.7x speedup on Llama3-8B and 3.0x speedup on Yi-9B for 128K context length on a single A100 GPU, with minimal quality degradation.