vLLM Solved the Wrong Bottleneck… and That’s Why It Won

Imagine spending thousands of dollars every month on GPUs, only to discover they’re sitting idle for a significant portion of the time.

Strange, right?

Surely the first thought would be:

The transformers architecture is the bottleneck?

Surprisingly, no.

The real bottleneck wasn’t the transformer itself. It was how we managed memory and served hundreds of unpredictable user requests efficiently.

That’s the realization that changed LLM serving forever.

Before understanding vLLM and why it became the industry standard for LLM serving, we first need to understand the world before it existed.

P.S. This blog is fairly technical and assumes basic familiarity with LLMs and transformers. If you’re completely new to AI infrastructure learning, I’ve also written a beginner-friendly version here for AI learners and non-technical folks: Coming Soon.

In the era of 2022–2023, when ChatGPT and open-source models had just launched, imagine hosting a model on a rented GPU and asking it tonnes of random questions from a number of users like:

User A: “Tell me about AI and its future.”

User B: “Write a blog for me on …”

User C: “Translate this sentence to English …”

User: D: “What’s the solution for this maths problem? …”

Each request has

Different arrival time

Different prompt length

Different output length

Now think like an inference engineer.

Your GPU costs $2–$5/hour (or much more for H100s). You want it busy all the time.

But the GPU wasn’t busy, and you couldn’t squeeze as much infra as you wanted to.

And here’s the frustrating part: companies weren’t paying for idle GPUs because the hardware was slow; they were simply paying because the software couldn’t utilize that hardware efficiently.

But behind that frustration were five core problems preventing GPUs from staying busy.

Problem 1: The KV cache was eating all the GPU memory.

When the LLM begins to generate output, each token needs the context of all previous tokens.

For example: If the prompt is 1000 tokens and the output sequence is 100 tokens in length.

For generating the 1001st token, the LLM needs to calculate Keys and Values (KV) for all previous 1000 tokens.

For the 1002nd token, the LLM needs to calculate KV for all previous 1000 tokens + the 1001st token.

For the 1003rd token, the LLM needs to calculate KV for all previous 1000 tokens + 1001st token + 1002nd token and so on… Till the last output token

This obviously creates an enormous slowdown due to matrix multiplication of all the tensors every time. Without any optimization, every newly generated token would require recomputing the Key and Value tensors for every previous token in the conversation.

As the conversation grows longer, that quickly becomes computationally infeasible.

Note: The optimization of storing KV Cache leads to another bottleneck, a memory bottleneck, because the KV cache is a better way to handle the computation, but it consumes the memory of the GPU, and as the context length (input + output length) increases, the memory requirement of the KV cache increases.

Problem 2: Memory Fragmentation (Contiguous Memory)

This is the second biggest bottleneck faced while hosting/serving the LLMs. When KV cache was stored, it was stored in contiguous memory blocks.

For example: Imagine 4 units of 500 memory blocks are storing KV cache.

| A | B | C | D |

Now A and C are no longer needed and evicted.

| 500 | B | 500 | D |

Now we have to store a new KV cache unit which requires 700 memory blocks. We have 1000 memory blocks free in total, but they’re split into two separate 500-unit gaps, and neither gap alone is big enough to hold it as one contiguous block. So even with enough memory on paper, the request still can’t be placed.

In technical terms this is called external fragmentation. It becomes worse after thousands of requests. This was solved using the PagedAttention algorithm, which is the heart of vLLM (I’ll explain more in further sections).

Problem 3: Static batching wastes enormous computation.

The GPU still waits because batch execution is synchronized.

Now imagine a batch size of 4.

Let’s imagine our old friends A, B, C, and D are 4 requests that are synchronized and being executed in parallel in a single batch.

Now A and C were small requests which got finished early, but still they have to wait till B and D completed their tasks, causing idle time and wasting precious and very, very expensive GPU resources.

To solve this batching and GPU idle time issue, vLLM started Continuous Batching (don’t worry, nothing fancy; will explain soon in the next section, I promise!).

Problem 4: Variable-length outputs

As the name seems self-explanatory enough, the requests that come in, they will be random in nature, will mostly have variable-length outputs.

This problem is actually a direct causality of Problem 3 as well; let’s understand with an example:

Our old friends are back again. Imagine: A, B, C, and D are four requests out of which B and C are summary requests (different friend groups this time) and will generate output of length 40 and 50 only.

Meanwhile, A and D are requests to explain some topics in detail; they’ll take 300 and 500 output tokens.

Now traditionally these were just batched together, hence causing Problem 3, where B and C sit idly finishing their summarization task while A and D keep generating their detailed explanation of their requests.

Problem 5: Throughput was terrible.

Now, obviously the companies wanted more users; what really mattered to them was not “lower latency for one user”.

As serving one request at a time isn’t economically viable.

If your GPU handles 5 users instead of 50 users.

Your infrastructure costs increase dramatically. Hence, the companies weren’t satisfied with the performance they were getting vs the cost they were paying at the time.

Wow, that has been a long list of problems; imagine the guys who were scratching their heads day and night over these problems daily for months. Well, they’re bald now maybe, but thanks to vLLM now they are more relieved. Let’s look at how vLLM solved their problems.

How did vLLM solve their problems?

The vLLM team realized they had been asking the wrong question all along.

So what did the vLLM team ask?

Not

“How do we make attention faster?”

Instead

“How do we keep the GPU busy almost all the time?”

That shift in thinking shaped the entire project.

Their key observation?

The expensive part wasn’t the transformer architecture itself.

It’s managing memory for many concurrent requests.

The bottleneck was Memory management.

Not matrix multiplication.

Their inspiration came from an unexpected place:

Operating systems.

Modern operating systems solved a very similar problem decades ago using virtual memory.

Instead of treating memory as one giant contiguous block, they divide it into fixed-size pages that can be allocated independently.

vLLM applied the same philosophy to KV cache management.

This became PagedAttention.

So what is PagedAttention? I’ve mentioned it maybe 50 times by now; let’s unravel the mystery.

PagedAttention

So as we know pagedattention, the concept itself, isn’t a novel or unique concept that nobody knew before.

It has been very smartly borrowed directly from virtual memory and paging in operating systems like Unix and Windows.

Where instead of treating memory as one large block, the OS divides it into page frames and only keeps the active parts in fast memory.

As we already know, the KV cache has unique characteristics: it dynamically grows and shrinks over time as the model generates new tokens, and its lifetime and length are not known beforehand.

PagedAttention allows storing continuous keys and values in non-contiguous memory space.

PagedAttention partitions the KV cache of each sequence into KV blocks. Each block contains the key and value vectors for a fixed number of tokens, also denoted as KV Block Size.

Let’s go back to our fragmentation example. That 700-unit request that couldn’t fit into either 500-unit gap? With PagedAttention, it doesn’t need to. It gets split into smaller fixed-size blocks, and those blocks get scattered across both gaps, wherever there’s room. A block table then keeps track of which blocks belong to which request, the same way a page table in an OS keeps track of scattered memory pages belonging to a process.

The result: external fragmentation basically disappears. There’s still a little internal fragmentation left, since we don’t know the exact output length ahead of time, but it’s now capped at wasting at most one block’s worth of space per request, instead of wasting the whole reserved allocation.

And the numbers back this up: prior systems were only using 20.4%–38.2% of their KV cache memory for actual token states ; meaning roughly 62–80% was wasted on reservation, internal fragmentation, and external fragmentation.

With PagedAttention, vLLM pushes effective usage up to 96.3%, or under 4% waste. That’s the difference between most of your GPU memory sitting reserved and unused versus almost all of it actually doing work. vLLM’s own benchmarks show 2–4x higher throughput at the same latency compared to serving systems before it, and the gap gets even bigger with longer sequences, larger models, and more complex decoding algorithms.

Well, that explains how KV cache is stored efficiently. What about the problems 3 and 4 you mentioned, MK? Did you forget about it? Of course not; let’s understand the world of continuous batching now (both promises kept).

Continuous Batching

Well, here’s the solution to Problems 3 and 4. Now with PagedAttention in place, the scenario changes, and we can say bye-bye to static batching.

Now if 4 requests, W, X, Y, Z (plot twist), come, of varied output lengths, and W finishes up earlier, it doesn’t have to wait for X, Y, Z to complete; it can move on, and the next request, A (here it comes), can directly start processing and generating tokens.

With continuous batching, the GPU doesn’t care which request a token belongs to. It only cares about having enough work to stay busy.

Now, again, continuous batching wasn’t some novel thing that vLLM invented; the idea was much older. Companies such as NVIDIA, Google, and Microsoft also implemented internal dynamic schedulers for inference systems years before vLLM.

So the scheduling algorithm wasn’t new, so why didn’t they do it already?

The hard part was transformers.

Why transformers made it difficult

Autoregressive transformers, as we know, kept a KV cache.

Because the memory is fragmented and contiguous, even if W finishes up early and the next request comes, there are no non-contiguous memory blocks where it could store its KV cache tokens.

For example: GPU memory already is serving 3 requests

AAA

BBBBBBBBBB

CCCCC

A and C will finish early and form empty slots for next requests in continuous batching.

___

BBBBBBBBBB

_____

Need space for D

DDDDDDDD

But even if we tried to fit the new requests, no contiguous space exists.

Traditional allocators had to:

• Move memory
  
• Copy KV cache
  
• Reserve worst-case memory or
  
• Rebuild batches

These operations are expensive, which answers your question:

Why nobody widely deployed continuous batching?

The bottleneck wasn’t scheduling.

It was KV cache management.

Eventually, the scheduling overhead outweighs the gains.

This is why many people consider PagedAttention to be the foundation that unlocked almost every optimization that followed.

Impact

The combination of continuous batching and PagedAttention substantially increased GPU utilization and throughput for LLM serving, especially under workloads with many concurrent requests of varying lengths. These ideas influenced later inference engines, and concepts similar to paged KV caches and dynamic scheduling have since appeared in systems from organizations such as NVIDIA, Hugging Face, Google, and OpenAI.

That subtle shift in thinking by vLLM engineers led to innovations like paged attention and continuous batching, two ideas that continue to influence modern inference engines today.

Sometimes the biggest breakthroughs aren’t about inventing something entirely new. They’re about applying an old idea, in this case, virtual memory, to a completely new problem.

If you enjoyed this deep dive, stay tuned. In the next blog, we’ll explore SGLang, another modern inference engine that builds on many of these ideas while taking a different path towards even lower latency.