Inside vLLM and TGI: Paging, Versioned Schedulers and Operations

The memory manager is part of the serving algorithm

A decoder needs growing per-request K/V state. Reserving maximum context for every request wastes unused tails; repeated contiguous growth can copy state and create allocation pressure. PagedAttention separates logical token order from physical fixed-size blocks, allowing kernels to read a sequence through a block table. This can increase feasible concurrency, which may improve throughput when weight reuse was the bottleneck. It does not guarantee a particular speedup,95% utilization or infinite capacity.

The hotel analogy is rooms rather than reserved wings: each request has a list of room IDs, and unused rooms are available to others. The list preserves logical order even when rooms are scattered. The PagedAttention paper explicitly draws on virtual-memory ideas to explain this approach.

Prerequisites: ordinary KV byte accounting, continuous batching, and numerical representation. Outcomes: trace block tables and reference counts, test copy-on-write, inspect a versioned scheduler/config, diagnose preemption, and prepare local-only launch/load-test recipes. The executable program is a CPU allocator model; all vLLM/TGI/GPU service commands are references only.

Block addresses and fragmentation arithmetic

For block width b, logical token position t maps to logical_block=t//b, offset=t%b, and physical block table[logical_block]. At b=16, a50-token request uses four blocks, e.g. [7,3,12,5], with14 unused slots. Its51st token is zero-based position50, offset2 of physical block5. Token65 needs a fifth block. A20-token request uses32 slots, leaving12. External fragmentation from unequal allocation sizes is removed within this uniform pool, but last-block internal waste remains.

For live lengths T_i, allocated slots are sum(b*ceil(T_i/b)). Waste is each (-T_i) mod b, between0 and b-1; total is less than b*number_of_nonempty_requests. A max-reservation allocator instead uses N*T_max. Different layer groups/block types, metadata, retained prefixes and allocator reserves add further terms in a real engine.

For a capacity exercise, lengths uniformly distributed over integers200…2000 have mean1100. A2000-slot reservation has expected used fraction55%. With16-token blocks the mean rounding waste is about7.5slots, hence payload utilization around99.3% for the ratio of mean used to mean allocated. State whether this is a ratio of expectations, sample aggregate or mean of per-request ratios; they are not generally identical. With a4096-slot reservation the baseline would instead be about26.86%. The chosen baseline matters more than the word “contiguous”.

Paging requires a compatible kernel to follow the table. Physical layout is backend-specific and need not place all layers' K/V in one contiguous object. Indirection and coalescing have costs; blocks allow amortization but do not prove every lookup is negligible or that the optimal block-size curve is always flat.16 is a common example, not a universal default across devices/releases.

Exact CPU block manager and copy-on-write

This model stores token IDs rather than K/V tensors. It demonstrates ownership, shared-prefix reference counts, atomic admission failure, growth and free. It intentionally supports a shared partial last block and copies it before mutation. That is a general paging mechanism, not a claim that vLLM0.11.0 automatic prefix caching uses this exact partial-block policy.

import math
from collections import Counter
class Blocks:
    def __init__(self,count,width):
        if type(count) is not int or type(width) is not int or count<1 or width<1:
            raise ValueError('positive integer pool size and block width required')
        self.width=width; self.data=[[] for _ in range(count)]
        self.refs=[0]*count; self.free_ids=list(range(count)); self.tables={}
    def _take(self):
        block=self.free_ids.pop(); assert self.refs[block]==0
        self.refs[block]=1; self.data[block]=[]; return block
    def _drop(self,block):
        self.refs[block]-=1
        if self.refs[block]==0: self.data[block]=[]; self.free_ids.append(block)
    def create(self,name,tokens):
        if name in self.tables or not tokens: raise ValueError('name/tokens')
        needed=math.ceil(len(tokens)/self.width)
        if needed>len(self.free_ids): raise MemoryError('pool full')
        table=[]
        for start in range(0,len(tokens),self.width):
            block=self._take(); self.data[block]=list(tokens[start:start+self.width]); table.append(block)
        self.tables[name]=table; self.check()
    def fork(self,source,name):
        if name in self.tables: raise ValueError('duplicate')
        table=self.tables[source].copy()
        for block in table: self.refs[block]+=1
        self.tables[name]=table; self.check()
    def append(self,name,token):
        table=self.tables[name]; last=table[-1]
        full=len(self.data[last])==self.width
        copy=not full and self.refs[last]>1
        if (full or copy) and not self.free_ids: raise MemoryError('no growth slot')
        if full: table.append(self._take())
        elif copy:
            new=self._take(); self.data[new]=self.data[last].copy()
            self._drop(last); table[-1]=new
        self.data[table[-1]].append(token); self.check()
    def read(self,name):
        return [x for block in self.tables[name] for x in self.data[block]]
    def release(self,name):
        for block in self.tables.pop(name): self._drop(block)
        self.check()
    def check(self):
        counts=Counter(b for table in self.tables.values() for b in table)
        assert self.refs==[counts[i] for i in range(len(self.refs))]
        assert len(set(self.free_ids))==len(self.free_ids)
        assert set(self.free_ids)=={i for i,r in enumerate(self.refs) if r==0}
        for table in self.tables.values():
            assert all(len(self.data[b])==self.width for b in table[:-1])
            assert 1<=len(self.data[table[-1]])<=self.width
 
pool=Blocks(6,4)
pool.create('A',[1,2,3,4,5]); pool.fork('A','C')
assert pool.tables['A']==pool.tables['C']
pool.append('C',9)
assert pool.read('A')==[1,2,3,4,5] and pool.read('C')==[1,2,3,4,5,9]
assert pool.tables['A'][0]==pool.tables['C'][0]
assert pool.tables['A'][-1]!=pool.tables['C'][-1]
pool.release('A'); assert pool.read('C')==[1,2,3,4,5,9]
pool.release('C'); assert len(pool.free_ids)==6
small=Blocks(1,4); small.create('A',[1,2]); small.fork('A','B')
before=(small.read('A'),small.read('B'),small.refs.copy())
try: small.append('B',3)
except MemoryError: pass
else: raise AssertionError('COW without space')
assert before==(small.read('A'),small.read('B'),small.refs.copy())
# Negative control demonstrates why mutating a shared tail without COW is wrong.
small.data[small.tables['B'][-1]].append(99)
assert small.read('A')==[1,2,99]
lengths=list(range(200,2001))
used=sum(lengths); allocated=sum(16*math.ceil(n/16) for n in lengths)
assert allocated-used < 16*len(lengths)
print('mean length',used/len(lengths),'mean waste',(allocated-used)/len(lengths),
      'paged utilization',used/allocated,'max2000 utilization',used/(2000*len(lengths)))

The allocator above is synchronous, single-owner and uses trusted nonempty Python token lists. check() validates structure, not tensor values, tenant authorization, or concurrent kernel completion. A request table reference and an in-flight worker lease are different ownership obligations: releasing the former must not invalidate the latter.

Here is a minimal synchronous event model of that handoff. Cancel stops new dispatches, retires the request and defers recycling until its outstanding epoch is acknowledged. A request epoch rejects results for a reused name, and a unique dispatch ticket rejects a delayed duplicate from an earlier step of the same live request. This is a teaching contract layered over Blocks, not a reproduction of vLLM's asynchronous internals.

class LeasedBlocks:
    def __init__(self, pool):
        self.pool = pool
        self.live = {}
        self.next_epoch = 0
        self.next_dispatch = 0
    def create(self, name, tokens):
        self.pool.create(name, tokens)
        self.next_epoch += 1
        self.live[name] = {"epoch": self.next_epoch, "busy": False, "retired": False}
        return self.next_epoch
    def dispatch(self, name):
        state = self.live[name]
        if state["busy"] or state["retired"]:
            raise ValueError("one live dispatch at a time")
        self.next_dispatch += 1
        state["dispatch"] = self.next_dispatch
        state["busy"] = True
        return name, state["epoch"], state["dispatch"]
    def cancel(self, name):
        state = self.live[name]
        state["retired"] = True
        if not state["busy"]:
            self.pool.release(name)
            del self.live[name]
    def complete(self, ticket):
        name, epoch, dispatch = ticket
        state = self.live.get(name)
        if (state is None or state["epoch"] != epoch or not state["busy"]
                or state["dispatch"] != dispatch):
            raise ValueError("stale or duplicate completion")
        state["busy"] = False
        if state["retired"]:
            self.pool.release(name)
            del self.live[name]
 
leased = LeasedBlocks(Blocks(1,4))
epoch = leased.create("request", [11,12])
ticket = leased.dispatch("request")
leased.cancel("request")
assert leased.pool.free_ids == []  # Worker still owns a lease.
try: leased.create("other", [99])
except MemoryError: pass
else: raise AssertionError("recycled before worker acknowledgement")
leased.complete(ticket)
assert len(leased.pool.free_ids) == 1
assert leased.create("request", [99]) > epoch
assert leased.pool.read("request") == [99]
try: leased.complete(ticket)
except ValueError: pass
else: raise AssertionError("old epoch accepted")
new_ticket = leased.dispatch("request")
leased.complete(new_ticket)
try: leased.complete(new_ticket)
except ValueError: pass
else: raise AssertionError("duplicate completion accepted")
next_ticket = leased.dispatch("request")
try: leased.complete(new_ticket)
except ValueError: pass
else: raise AssertionError("old dispatch completed a newer step")
leased.complete(next_ticket)
leased.cancel("request")
assert len(leased.pool.free_ids) == 1

A real asynchronous implementation must fence all device/transfer operations that hold a lease, not just receive an arbitrary control-plane message. This model assumes a trusted completion acknowledges finished work; it cannot certify GPU stream synchronization, distributed failure recovery or secure erasure. Immediate reuse after cancellation is the negative control: with one block it would admit other while the old dispatch can still write that same physical block.

Before a real kernel consumes a table, validate ownership, bounds, cache dtype and logical length. After cancellation/free, no active request may retain an uncounted reference. A reuse test must also show that request B cannot read stale tenant A tokens from a recycled block; clearing storage is one defense, but correct logical bounds and isolation are indispensable.

Prefix reuse versus general branch sharing

The vLLM0.11.0 design document says automatic prefix caching caches full blocks. The key chains parent-prefix hash, block token IDs and extra identity such as LoRA IDs, multimodal hashes and cache salts. A textually identical system prompt may tokenize differently under a changed template or model; matching text alone is insufficient. Per-request cache_salt allows a trust-group isolation boundary in V1. The server, not an untrusted client, should decide the tenant's salt/namespace.

A general branch-sharing allocator can use reference counts and partial-block COW as above. Full-block prefix reuse need not copy a shared immutable block when a new suffix starts in a fresh block. Do not claim every divergence performs exactly one copy. Prefix lookup/retention/eviction has CPU/memory cost, and only matched prefill work is saved; uncached suffixes and decoding still execute. Under pressure, cached reusable blocks with no active owners may be evicted. Cold-after-burst latency can therefore be a cache miss rather than a correctness failure.

SGLang's RadixAttention uses a radix-tree cache for reusable prefixes in structured generation programs. That algorithmic distinction motivates measurement on branch-heavy workloads, not a timeless3–6× advantage over any vLLM release or free tree-search branches.

Read the vLLM0.11.0 scheduler, not a timeless pseudocode loop

The source under vllm/v1/core/sched/scheduler.py tracks how many tokens each request requires versus has computed. It budgets pending work, considers running requests and allocates cache slots before dispatch. Waiting admissions may reuse computed prefixes. Returned model outputs update the request and completion releases state.

On allocation failure, this release's path chooses a victim by configured priority/arrival ordering, or pops the end of the running list under the nonpriority path; it frees cache, marks the request PREEMPTED, resets computed-token count to zero and prepends it to waiting. That is a recompute path. The presence of a swap_space configuration field elsewhere does not prove this V1 path swaps KV to CPU. V0 “sequence group preempted” logs and current V1 request structures are not interchangeable APIs. “Evict shortest remaining sequence” is particularly misleading because the eventual output length is unknown.

Recompute cost grows with prefix length and available prefill capacity. Host swap, when supported by a selected engine, costs cache bytes in both directions plus synchronization and host memory; it is not independent of the amount of accumulated state. Compare t_recompute against 2*cache_bytes/effective_link_bandwidth + overhead. Conservative admission avoids this work but can reduce utilization and cannot by itself guarantee zero queueing latency. Near-zero preemption is not evidence of undertuning.

Launch a pinned engine from already reviewed local artifacts

These unexecuted operational references assume a pre-provisioned environment, drivers and local model/config/tokenizer files whose hashes and licenses were reviewed. They do not install dependencies, download models or expose a public listener. Run them only in an environment where you are authorized to operate the service.

# Resource reference: vLLM 0.11.0, local compatible unquantized checkpoint.
HF_HUB_OFFLINE=1 TRANSFORMERS_OFFLINE=1 \
  vllm serve /srv/models/chat-model --served-model-name local-chat \
  --host 127.0.0.1 --port 8000 --dtype auto \
  --max-model-len 8192 --gpu-memory-utilization 0.85 \
  --max-num-seqs 16 --max-num-batched-tokens 2048 \
  --enable-prefix-caching --enable-chunked-prefill --tensor-parallel-size 1

gpu_memory_utilization is the fraction of device memory for the model executor, not “90% of memory left after weights”. It is a per-instance setting, not a global arbitration mechanism with other processes. Startup profiling and later memory use both matter. max_model_len constrains total context; token work budget and active sequence cap constrain different scheduler dimensions. These example values are a starting hypothesis, not a capacity promise. FP8 cache support depends on device/backend/scales and is not solely an H100 feature.

To combine quantization with prefix/chunked prefill, substitute a real local AWQ checkpoint with compatible quantization metadata and add --quantization awq to the same release-compatible command. That flag does not transform an ordinary BF16 model into an AWQ artifact. Validate numerical quality and backend support first. Speculative configuration has changed across versions; do not paste legacy --speculative-model flags into an unrelated release without its help/source contract.

TGI3.3.5 is a separate pinned alternative with Rust/Python/gRPC components and continuous batching. The tagged README documents its container and Messages API. With an already present image and model, a loopback-only reference is:

# Resource reference: image/model already provisioned; not executed.
docker run --rm --pull never --gpus all --shm-size 1g \
  -p 127.0.0.1:8080:80 -v /srv/models/chat-model:/model:ro \
  -e HF_HUB_OFFLINE=1 -e TRANSFORMERS_OFFLINE=1 \
  ghcr.io/huggingface/text-generation-inference:3.3.5 --model-id /model

Pin the image digest as well as tag in an actual deployment manifest. Private backend networking and authentication are still needed if anything can reach it. The vLLM OpenAI-compatible API and TGI Messages API support a documented subset, not every OpenAI feature/SDK behavior verbatim. A test client must accept role-only deltas, empty choices for usage where applicable, finish reasons, cancellation, errors and tool fragments. A successful /health is not a throughput benchmark.

Engines, kernels and workload-specific choices

Choose by required model/quantization/hardware/API support and measured SLOs, not a universal ranking. vLLM is a general serving engine with versioned backends; TGI offers Hugging Face ecosystem integration and a Rust router; TensorRT-LLM has NVIDIA-focused execution paths whose build/runtime requirements depend on version; SGLang emphasizes structured execution/prefix reuse; llama.cpp targets broad local/edge CPU/GPU backends and GGUF; Ollama supplies convenient local model management; MLC targets compiled deployment on supported devices. Managed platforms trade operational control against lifecycle/cost constraints. These descriptions are selection questions, not claims that one can never serve production or always wins by15%.

The V1 announcement describes a unified scheduler, prefix-cache changes and compilation-related work. Compilation/CUDA graph capture, warmup and shape handling are release/config dependent; not every new prompt length triggers a fresh3–10-second compile. Use startup logs, warm representative shapes and compare cold/warm runs. An upgrade is a controlled migration: preserve the old manifest, run golden outputs and load tests, inspect unsupported flags and rollback on measured regression. Do not delete every tuning flag blindly.

Observability and debugging runbook

For vLLM0.11.0 V1, verify emitted metrics against vllm/v1/metrics/loggers.py: vllm:num_requests_running, vllm:num_requests_waiting, vllm:kv_cache_usage_perc, vllm:time_to_first_token_seconds, and vllm:inter_token_latency_seconds. The older gpu_cache_usage_perc is deprecated/hidden under version controls, and time_per_output_token_seconds is deprecated in favor of ITL. Do not build dashboards around invented num_running names. Histograms require appropriate aggregation before quantiles; average p99 values from replicas are not a fleet p99.

If admission fails, inspect total context cap, token budget, chunking setting and cache slot availability separately. A long prompt can exceed a per-step budget and still be processed in chunks; raising every budget to longest prompt is not always required. If OOM occurs, compare weights, peak workspace, graph buffers, other processes, per-rank cache and startup reserves; do not label all OOMs fragmentation. If waiting grows, compare arrival load with measured capacity and investigate stalled workers, oversized prompts, authentication abuse or preemption before adding replicas.

For a later throughput reproduction, capture exact checkpoint/tokenizer hashes, engine commit, driver/device count, precision, TP, prompt/output distributions, request arrival process, cache hit policy, warmup, sampling and SLO definition from the cited benchmark. Run a bounded independent load trace, retain errors/rejections and raw latency events, then compare like-for-like. A CPU block simulation cannot reproduce a paper's tok/s. Abort on unsafe memory/error thresholds and keep the backend private.

Worked recall and acceptance criteria

1. What is PagedAttention? Logical-to-physical block addressing for attention cache, with a compatible kernel and allocator. It reduces specific allocation waste but leaves bounded tails/metadata and finite capacity.
2. What changed in V1? Unified token-work scheduling and revised cache/execution architecture, verified at a named release rather than a universal1.5× promise.
3. Why prefix caching for chat? Compatible common prefixes reuse prefill and physical state; correctness requires full identity and tenant isolation. New suffixes still cost work.
4. Why preempt? Requested slots cannot fit under the selected policy; the pinned V1 path frees/recomputes state. Diagnose actual workload and allocation, not an assumed shortest-job algorithm.
5. How to choose SGLang/TRT-LLM/TGI/vLLM? Build a support matrix and measure the actual workload; branch reuse, hardware-specific kernels and router integration are hypotheses to test, not guarantees.
6. Allocator stretch? The exact loop over integer lengths200…2000 computes expected waste and aggregate utilization; compare the same max reservation and record tail/metadata limitations. COW failure must leave both branches unchanged.
7. Serve7B and reproduce a number? Follow the benchmark contract above only with separate authorization and local provisioned artifacts. Acceptance requires actual raw results and SLOs; it remains unexecuted here.

Primary sources

PagedAttention, vLLM0.11.0 cache config, V1 scheduler, prefix-cache design, V1 metrics, TGI3.3.5, V1 announcement, and SGLang. Source-backed API semantics, exact CPU allocator checks and unexecuted GPU service procedures are separate evidence categories.

Course navigation

Series: Deep Learning & LLMs From Scratch — 80 sessions · Session 71 / 80 · Module M11 · ~2 hours

Previous: ← DL S070 · Next: DL S072 →

Optional reading

Use these links for additional background. Version-specific behavior is documented in the primary references above.

• Optional resource 1
• Optional resource 2
• Optional resource 3
• Optional resource 4