Mitigating the Prefill Latency Bottleneck in LLM Inference

49 concepts44 papers1 proposal

Large Language Model (LLM) inference is traditionally characterized as a memory-bound problem. When an LLM generates text token by token during the decoding phase, the hardware must repeatedly load billions of model parameters and an ever-growing Key-Value (KV) cache from high-bandwidth memory to the processor's SRAM just to produce a single token.

However, as context windows expand to hundreds of thousands or millions of tokens—driven by applications like Retrieval-Augmented Generation (RAG), long-document analysis, and multi-turn agents—a different bottleneck emerges. Before generation can even begin, the model must ingest the initial prompt. This is the prefill phase, and it is fundamentally compute-bound. Because every token in the prompt must attend to every other token, the computational complexity scales quadratically ($O(N^2)$) with the prompt length. For massive inputs, this creates a severe latency wall, causing users to wait seconds or even minutes for the Time-to-First-Token (TTFT).

To make long-context LLMs practical, a major research direction has emerged to optimize, bypass, or parallelize this prefill bottleneck. The core insight driving this field is that we do not need to compute full, dense attention across the entire prompt to build a high-quality initial representation.


Strategy 1: Dynamic Sparsification and Token Pruning

The most direct way to accelerate the prefill phase is to reduce the number of tokens or attention operations the model has to process. If we can identify which tokens are mathematically critical to the output before running the full transformer stack, we can skip the quadratic cost of the rest.

Exploiting Intrinsic Attention Structures

Attention matrices in long-context models are rarely uniform. As discovered by Abdi et al. in MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention, long-context attention naturally concentrates into specific geometric patterns: an "A-shape" (focusing on the beginning of the prompt and recent tokens), a "Vertical-Slash" (focusing on specific anchor tokens), and "Block-Sparse" clusters. By dynamically assigning sparse attention kernels to match these patterns at runtime, the authors reduced prefill computation by up to 95% without requiring model retraining.

Predictive Filtering and Clustering

Rather than computing sparse attention patterns layer-by-layer, some approaches prune the prompt tokens entirely at the entrance of the network.


Strategy 2: Exploiting Structural Asymmetry

Another major insight is that the workload within a Transformer is highly asymmetric: not every attention head or every layer needs to perform full-context retrieval during the prefill phase.

Head Specialization

In DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads, Xiao et al. observed that attention heads naturally specialize. A small fraction act as "Retrieval Heads," which must look back across the entire long history to find specific facts. The vast majority act as "Streaming Heads," which only require local context to maintain grammatical fluency. By restricting the streaming heads to a constant-length local cache during the prefill phase, the authors bypassed the quadratic scaling bottleneck for the majority of the model's width.

Standard Attention:  [All Tokens] <====== Quadratic Attention ======> [All Tokens] (Slow)

DuoAttention:        [Retrieval Heads] ===> Full Context Attention ===> [All Tokens]
                     [Streaming Heads] ===> Fixed Local Window Only ===> [Recent Tokens] (Fast)

Layer Skipping and Architectural Redesign

We can also exploit asymmetry across the depth of the network. Qiao et al. proposed SwiftKV: Fast Prefill-Optimized Inference with Knowledge-Preserving Model Transformation, a method where prompt tokens skip later transformer layers entirely. The model still populates a high-quality KV cache in the early layers, but avoids the heavy computational stack of the deeper layers during the initial ingestion, cutting prefill latency by up to 50%.

Taking this further, Sun et al. introduced a structural paradigm shift in You Only Cache Once: Decoder-Decoder Architectures for Language Models. By splitting the model into a self-decoder that generates a single global KV cache and a cross-decoder that reuses it, they fundamentally altered the prefill scaling laws, achieving orders-of-magnitude faster prompt processing.


Strategy 3: Parallel Encoding and Cache Fusion for RAG

In applications like Retrieval-Augmented Generation (RAG), the prompt is often composed of a user query appended to several long, independent reference documents. Standard LLM engines process this entire sequence as one contiguous block. This means that if a user asks two different questions about the same document, the system must re-run the quadratic prefill computation over that document both times.

To solve this, researchers have developed techniques to precompute, modularize, and "stitch together" KV caches for independent text chunks.

Parallel Chunk Encoding

Because retrieved documents do not inherently depend on each other until the final generation step, they can be processed in parallel. In APE: Faster and Longer Context-Augmented Generation via Adaptive Parallel Encoding, Yang et al. developed a method to encode context chunks completely in parallel. They then mathematically align the resulting KV states with the model's expected sequential distribution, bypassing the sequential prefill bottleneck.

Cache Fusion and Re-encoding

When combining precomputed KV caches from different documents, the primary challenge is that the attention weights between the documents are missing.

  • Selective Recomputation: In CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion, Yao et al. showed that you do not need to recompute everything to fix this. By selectively recomputing only a small fraction (~15%) of the KV cache, they restored the vital cross-attention between distinct retrieved text chunks while accelerating TTFT by up to 3.3×.
  • Independent Block Attention: Similarly, Ma et al. introduced Block-Attention for Efficient Prefilling, which treats documents as isolated blocks. By utilizing a position re-encoding trick, their mechanism allows engines to instantly reuse precomputed document caches across entirely different queries, dropping the prefilling overhead for RAG systems by up to 98.7%.

Overlapping Compute and I/O

Even when caches are precomputed, loading massive KV caches from disk or CPU memory into the GPU introduces an I/O bottleneck that can rival compute latency.

To address this, Jin et al. proposed a bidirectional scheduling strategy in Compute or Load KV Cache? Why Not Both?. Their system, Cake, concurrently computes the KV cache from the beginning of the prompt on the GPU while streaming the precomputed cache from storage starting from the end of the prompt. By meeting in the middle, it perfectly hides I/O latency behind computation, ensuring that hardware is never left idling.


Summary

The shift toward long-context LLMs has forced a re-evaluation of inference optimization. By recognizing that the prefill phase is a distinct, compute-bound bottleneck governed by quadratic scaling, recent architectures and systems have moved away from uniform dense processing. Whether through pruning uninformative tokens, restricting attention to specialized retrieval heads, or fusing precomputed chunk caches, these techniques ensure that the time to first token remains interactive, even when processing millions of words of context.

Key Foundational Work

RAPID: Long-Context Inference with Retrieval-Augmented Speculative Decoding (2025) — contributed 2 concept elements to this direction.
Fast On-device LLM Inference with NPUs (2024) — contributed 2 concept elements to this direction.
KV Prediction for Improved Time to First Token (2024) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_prefill_latency_bottleneck_eb797e10,
  title = {prefill latency bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/prefill-latency-bottleneck/rdr_eb797e10019e43aebe7c9dbac2f28400},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_prefill_latency_bottleneck_eb797e10_v1,
  title = {prefill latency bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/prefill-latency-bottleneck/rdr_eb797e10019e43aebe7c9dbac2f28400/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake