The Autoregressive Bottleneck & Inference Phases

The Autoregressive Nature of LLMs

Large Language Models generate text autoregressively. This means each new token is predicted based on the entire sequence of tokens that came before it.

While this process creates coherent language, it creates a massive computational bottleneck as the sequence grows longer.

Welcome to the mechanics of LLM optimization. To understand KV caching, we first must look at the autoregressive process. Notice how the model predicts one token, then uses that token as input for the next step, and so on. As the sequence grows, the model has to look back at an ever-increasing history.

The Quadratic Complexity Trap

In a standard Transformer, the self-attention mechanism calculates pairwise interactions between all tokens. This results in an O(N²) time complexity.

Without optimization, generating the 1,000th token is significantly more expensive than generating the 10th token.

In a naive implementation, the attention matrix grows quadratically. For a short prompt, the computation is manageable. But as the context length L increases, the matrix area—and the work required—expands by the square of L. This quadratic growth means that for long-form generation, the process becomes catastrophically slow.

Motivation: Speed Comparison

Compare the performance of a 8B parameter model with and without KV caching. Observe how the 'Tokens Per Second' metric changes as the sequence length grows.

Let's see the impact of caching in real-time. Click 'Run Simulation' to compare a naive implementation against one using KV caching. Notice the 'Naive' line. As more tokens are generated, the speed per token drops because it's re-calculating everything. The 'Cached' version, however, stays relatively flat because it only processes the new token.

Phase 1: The Prefill Phase

The Prefill Phase (or Prompt Processing) is the first step of inference. The model ingests the entire prompt in parallel.

This phase is compute-bound, meaning it is limited by the raw mathematical speed (TFLOPS) of your GPU cores.

During Prefill, the GPU is in its element. Since all prompt tokens are known, it processes them all at once using parallel matrix-matrix multiplications. The bottleneck here is simply how fast your GPU cores can crunch numbers. If your Time-to-First-Token is too high, you need more TFLOPS.

Phase 2: The Decode Phase

The Decode Phase generates tokens one-by-one. Unlike Prefill, this phase is memory-bandwidth bound.

The GPU spends most of its time waiting for data to move from VRAM to the cores, rather than performing calculations.

Now look at the Decode phase. We are only generating one token at a time. Because the workload is small, the GPU cores sit idle while waiting for weights and past data to be loaded from memory. This is memory-bandwidth bound. To speed this up, you don't need faster cores—you need faster VRAM throughput.

Diagnosing the Bottleneck

A user reports that their LLM application is slow. Analyze the performance data below and provide a diagnosis. Is the issue in the Prefill or Decode phase, and what hardware upgrade would help?

Take a look at these metrics: Time-to-First-Token is 50ms, which is great, but the generation throughput is only 2 tokens per second. Type your diagnosis in the box. Which phase is struggling, and why?