Loading codebase...
Complete Source Code
Every single line of code behind Build Atlas, organized across all 9 parts. From tensor math, autograd, and byte-level BPE to TinyGPT training, LoRA chat tuning, hybrid RAG, autonomous agents, and continuous-batch serving.
Continuous batching serving scheduler: iteration-level scheduling, KV-cache slot allocation, and streaming token output.
"""Part 9 · Serve it fast: a KV cache, batching, and cost per token.
Generation has two phases. Prefill processes the whole prompt at once (compute-bound, parallel). Decode makes one
token at a time; without a cache, every step recomputes attention keys and values for the entire sequence so far,
which is quadratic waste. The KV cache stores each layer's keys and values, so a decode step only computes the new
token's. Batching then shares each weight read across many sequences, and continuous batching keeps the batch full
by admitting new requests the moment others finish. Cost per token falls out of measured throughput.
"""
from __future__ import annotations
import random
import time
import torch
from torch.nn import functional as F
def _split_heads(t, n_head):
B, T, C = t.shape
return t.view(B, T, n_head, C // n_head).transpose(1, 2) # (B, H, T, hd)
@torch.no_grad()
def prefill(model, idx):
"""Run the prompt through the model once, returning last-position logits and per-layer (K, V) caches."""
model.eval()
B, T = idx.shape
x = model.tok(idx) + model.pos(torch.arange(T))
cache = []
for blk in model.blocks:
a = blk.attn
q, k, v = a.qkv(blk.ln1(x)).split(x.size(-1), dim=2)
q, k, v = (_split_heads(t, a.n_head) for t in (q, k, v))
y = F.scaled_dot_product_attention(q, k, v, is_causal=True)
x = x + a.proj(y.transpose(1, 2).contiguous().view(B, T, -1))
x = x + blk.mlp(blk.ln2(x))
cache.append((k, v))
return model.head(model.ln_f(x))[:, -1, :], cache
@torch.no_grad()
def decode_step(model, token, pos, cache):
"""One new token per sequence: compute its q, k, v, append k, v to the cache, attend over the whole cache."""
B = token.shape[0]
x = model.tok(token) + model.pos(torch.full((1,), pos, dtype=torch.long))
new_cache = []
for blk, (K, V) in zip(model.blocks, cache):
a = blk.attn
q, k, v = a.qkv(blk.ln1(x)).split(x.size(-1), dim=2)
q, k, v = (_split_heads(t, a.n_head) for t in (q, k, v))
K, V = torch.cat([K, k], dim=2), torch.cat([V, v], dim=2)
y = F.scaled_dot_product_attention(q, K, V) # one query attends to every cached position: no mask needed
x = x + a.proj(y.transpose(1, 2).contiguous().view(B, 1, -1))
x = x + blk.mlp(blk.ln2(x))
new_cache.append((K, V))
return model.head(model.ln_f(x))[:, -1, :], new_cache
@torch.no_grad()
def generate_cached(model, idx, max_new_tokens: int):
"""Greedy decoding with a KV cache. Stops at the model's context length (no sliding window here)."""
logits, cache = prefill(model, idx)
out = idx
for _ in range(max_new_tokens):
if out.size(1) >= model.config.block_size:
break
nxt = logits.argmax(-1, keepdim=True)
out = torch.cat([out, nxt], dim=1)
logits, cache = decode_step(model, nxt, out.size(1) - 1, cache)
return out
@torch.no_grad()
def generate_naive(model, idx, max_new_tokens: int):
"""Greedy decoding that recomputes the whole sequence every step (what Part 4's generate does)."""
model.eval()
out = idx
for _ in range(max_new_tokens):
if out.size(1) >= model.config.block_size:
break
logits, _ = model(out)
out = torch.cat([out, logits[:, -1, :].argmax(-1, keepdim=True)], dim=1)
return out
def time_decode_step(model, batch: int, prompt_len: int = 16, steps: int = 20) -> float:
"""Measured seconds per decode step at a given batch size (warm, CPU)."""
idx = torch.randint(0, model.config.vocab_size, (batch, prompt_len))
logits, cache = prefill(model, idx)
tok = logits.argmax(-1, keepdim=True)
decode_step(model, tok, prompt_len, cache) # warm-up
t = time.perf_counter()
pos = prompt_len
for _ in range(steps):
logits, cache = decode_step(model, tok, pos, cache)
pos += 1
return (time.perf_counter() - t) / steps
def simulate(requests: list, step_time, max_batch: int, continuous: bool) -> dict:
"""requests: (arrival_time_s, output_tokens). step_time(b): seconds for one decode step of batch b.
Static batching starts a batch only when the previous one has fully finished; continuous batching refills
free slots at every step. Returns throughput and latency statistics."""
pending = sorted(requests)
t, i, active, done = 0.0, 0, [], []
while i < len(pending) or active:
free = max_batch - len(active)
can_admit = continuous or not active
while can_admit and free > 0 and i < len(pending) and pending[i][0] <= t:
arrival, n = pending[i]; active.append([arrival, n]); i += 1; free -= 1
if not active:
t = pending[i][0]
continue
t += step_time(len(active))
for r in active:
r[1] -= 1
done += [t - r[0] for r in active if r[1] == 0]
active = [r for r in active if r[1] > 0]
total_tokens = sum(n for _, n in requests)
lat = sorted(done)
return {"throughput": total_tokens / t, "p50": lat[len(lat) // 2], "p95": lat[int(0.95 * len(lat))], "makespan": t}
def request_trace(n: int = 200, rate_per_s: float = 40.0, seed: int = 0) -> list:
rng = random.Random(seed)
t, reqs = 0.0, []
for _ in range(n):
t += rng.expovariate(rate_per_s)
reqs.append((t, rng.randint(10, 100))) # output lengths vary widely, as in real traffic
return reqs