# Derivations

## 1. KV bytes per token

Each decoder layer caches one K and one V vector per KV head:

```
kv_bytes/token = 2 · L · H_kv · d_head · bytes_per_el
```

- **MHA**: `H_kv = H_q`
- **GQA**: `H_kv = H_q / g` (Llama 3: 64 query heads, 8 KV heads → 8× smaller)
- **MQA**: `H_kv = 1`
- **MLA** (DeepSeek V2/V3): the cache is not K/V at all but a compressed
  latent `c_KV ∈ R^{d_c}` plus a decoupled RoPE key `k_R ∈ R^{d_r}`, shared
  across all heads and carrying both K and V information:

```
kv_bytes/token = L · (d_c + d_r) · bytes_per_el          (no factor 2)
```

DeepSeek-V3: `61 · (512 + 64) · 2 B = 68.6 KiB/token` vs. a hypothetical MHA
cache at its dims `2 · 61 · 128 · 128 · 2 B = 3.8 MiB/token` — ~57×.

### Quantization

`bytes_per_el`: FP16/BF16 = 2, FP8 = 1. Integer formats add per-group scale
overhead; with group size 128 and an FP16 scale: INT8 = `1 + 2/128`,
INT4 = `0.5 + 2/128`.

## 2. Budget and walls

```
kv_budget = M_gpu − P · bytes_per_param − f_overhead · M_gpu
max_batch(S)  = ⌊ kv_budget / (S · kv_bytes/token) ⌋
max_seq(B)    = ⌊ kv_budget / (B · kv_bytes/token) ⌋
```

`f_overhead` (default 0.10) absorbs activations, CUDA context and workspace —
the same knob as vLLM's `gpu_memory_utilization` complement.

Worked example — Llama 3 8B FP16 on A100 80GB:
weights 16 GB, overhead 8 GB → 56 GB ≈ 52.2 GiB budget.
KV = 128 KiB/token → at 4k context, `max_batch = ⌊52.2 GiB / 512 MiB⌋ = 104`.

## 3. Decode roofline (the part calculators skip)

Each decode step must read all weights once and all live KV once, and do
`2·P` FLOPs per token in the batch:

```
t_mem     = (W + B·S·kv_bytes/token) / (BW · MBU)
t_compute = (2 · P · B) / (FLOPS · MFU)
t_step    = max(t_mem, t_compute)

inter-token latency = t_step        throughput = B / t_step
```

Defaults MBU = 0.7, MFU = 0.5 (typical achieved fractions of peak).

**Regimes:**

1. **Small B** — `t_mem ≈ W/BW` dominates: batching is nearly free
   (throughput ∝ B, latency ~flat). This is why serving without batching
   wastes the GPU.
2. **Growing B** — the `B·S·kv` term takes over: latency climbs linearly with
   batch, throughput saturates toward `BW·MBU / (S·kv_bytes/token)`.
3. **Compute knee** — setting `t_mem = t_compute`:

```
B* = (W / (BW·MBU)) / ( 2P/(FLOPS·MFU) − S·kv_bytes/token/(BW·MBU) )
```

   If the denominator ≤ 0 (long context, fat KV), decode is memory-bound at
   **every** batch size — the knee is at infinity and only smaller KV or more
   bandwidth raises throughput.

4. **OOM wall** — the budget truncates the sweep at `max_batch(S)`,
   frequently *before* the knee.

**The Pareto frontier** is the swept `(latency, throughput)` curve: both are
non-decreasing in B, so no point dominates another; you pick a point per your
SLO. KV quantization / GQA / MLA don't move the small-B part of the curve
(weights dominate) — they move the **endpoint**, letting you ride the curve to
batches FP16 can't reach. That is the actual mechanism by which "KV
compression increases throughput".

## 4. PagedAttention

Pre-paging servers allocate contiguous KV per sequence and must reserve
`max_seq_len` slots up front (final length unknown). Waste per sequence
`= (max_seq − actual) · kv_bytes/token` — with mixed workloads, utilization
of 20–40% was typical (vLLM paper reports similar).

Paged allocation grabs `block_size`-token blocks on demand:

```
allocated = ⌈S / block⌉ · block · kv_bytes/token
waste     < block · kv_bytes/token   per sequence  (last-block internal frag)
```

Admission capacity at a fixed budget:

```
naive : ⌊ budget / (max_seq · kv_bytes/token) ⌋      (length-independent!)
paged : fill by actual footprint of the request mix
```

The gain is the ratio — for a mix averaging ~35% of `max_seq`, roughly
2–3×. The simulator uses a deterministic right-skewed length distribution so
the numbers are reproducible.

## 5. What is deliberately not modeled

Prefill (compute-bound, amortized), chunked prefill interference, tensor
parallel sharding of KV, prefix caching / sharing, attention kernel
efficiency differences between paged and contiguous layouts, CPU offload.
The byte accounting is exact; everything time-domain is first-order.