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.
- Speculative Estimation: Liu et al. developed Speculative Prefill: Turbocharging TTFT with Lightweight and Training-Free Token Importance Estimation, which uses a tiny, fast "speculator" model to run a draft pass over the prompt. It ranks token importance and discards up to 90% of the input tokens for the heavy base model, drastically slashing TTFT.
- Clustering and Proxies: Other methods look at how tokens group together. In ClusterAttn: KV Cache Compression under Intrinsic Attention Clustering, Zhang et al. utilize density-based clustering to retain only the most representative prompt tokens. Similarly, Wang et al. demonstrate in ProxyAttn: Guided Sparse Attention via Representative Heads that a few "representative heads" can accurately predict the sparse attention patterns of an entire layer, allowing the system to bypass full attention calculations for the remaining heads.
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.