Preempt by recompute or by swapping KV to host memory? Derive the break-even from PCIe bandwidth and prefill speed.

TL;DR: Compare per-token costs: a swap round trip moves $2 \times$ KV bytes over PCIe, a recompute redoes $2N$ FLOPs plus attention. For Llama 3.1 8B on an H100 that is 5.2 µs per token at 50 GB/s against 34.7 µs at 50% MFU (4K context), so a well-batched swap wins; the break-even effective bandwidth is only 7.6 GB/s. Per-block copies of 32 KiB fall to 3 to 6 GB/s, where recompute wins up to roughly 62K to 104K tokens.

How to approach it

Name the two resources first: swap spends PCIe bandwidth and host memory, recompute spends GPU FLOPs that other requests also want. Then ask what the model's KV bytes per token are relative to its parameter count, because that ratio decides the comparison. Ask how the engine copies blocks (one batched kernel or one transfer per block per layer), and whether prefix caching is on.

A strong answer

Set up the per-token costs. Swapping out and back in moves each token's KV twice over PCIe. Recomputing re-runs prefill: $2N$ FLOPs per token for the weights, plus attention, which for a prompt of length $L$ adds an average of $4 \cdot n_{\text{layers}} \cdot n_{\text{heads}} \cdot d_{\text{head}} \cdot L/2$ FLOPs per token.

$$t_{\text{swap}} = \frac{2 \cdot b_{\text{kv}}}{B_{\text{pcie}}}, \qquad t_{\text{rec}}(L) = \frac{2N + a L / 2}{F_{\text{eff}}}$$

Llama 3.1 8B, BF16, H100 SXM (989 TFLOP/s dense BF16), 50% MFU -> F_eff = 494.5 TFLOP/s
b_kv   = 2 x 32 x 8 x 128 x 2 B                = 131,072 B (128 KiB)
a      = 4 x 32 layers x 32 heads x 128        = 524,288 FLOP per token-pair
recompute, L = 4,096: (16.06e9 + 524,288 x 2,048) / 494.5e12 = 34.7 us/token
swap round trip at 50 GB/s achieved:  2 x 131,072 / 50e9      = 5.2 us/token
break-even bandwidth at L = 4,096:    2 x 131,072 x 494.5e12 / 17.13e9 = 7.6 GB/s

PCIe Gen5 x16 is 64 GB/s per direction on paper, and a pinned-memory copy gets most of it, so with one large transfer swap is about 6.6x cheaper per token than recompute. The ratio holds for big models too: a 70B on TP=4 is 3.3 µs per token to swap against 71 µs to recompute per GPU. GQA made KV small relative to FLOPs, and that moved the comparison toward swapping.

So why would anyone recompute? Because effective PCIe bandwidth depends on copy size. Paged KV lives in blocks, typically 16 tokens, and many engines keep K and V for each layer in separate tensors. A naive swap issues one copy per block, per layer, per K or V:

one copy   = 16 tokens x 8 kv_heads x 128 x 2 B   = 32 KiB
at 5 us fixed cost per copy:   32,768 / (5e-6 + 32,768/50e9)  = 5.8 GB/s
at 10 us fixed cost per copy:  32,768 / (10e-6 + 32,768/50e9) = 3.1 GB/s
break-even length at 4 GB/s:   (2 x 131,072 x 494.5e12 / 4e9 - 16.06e9) / 262,144
                             = 62,000 tokens  (104,000 at 3 GB/s)

Below the break-even bandwidth, recompute is cheaper for every sequence shorter than that length. The attention term grows with length, so very long sequences eventually favor swapping anyway. The vLLM paper (Kwon et al., SOSP 2023) measured the same shape: swap overhead high at small block sizes, recompute flat across them.

Three more facts move the decision toward recompute in practice:

1. Spare compute. A decode step at batch 64 and 2,048-token contexts runs 9.92 ms, memory-bound. Compute equals that time at 9.92 ms x 989 TFLOP/s / 16.06 GFLOP = 611 tokens, so about 547 recomputed tokens ride in each step at peak for close to zero added latency.
2. Prefix caching. Freed blocks keep their hashes until reallocated, so a recomputed request often hits its own blocks and skips most of the prefill.
3. Simplicity. No host pool, no swap-in latency on the critical path, no copy stream to order against compute.

That is the design vLLM chose: in v0.31 the scheduler preempts the last running request under FCFS (or the lowest-priority one under the priority policy), frees its blocks, sets its computed-token count to zero and puts it back at the front of the waiting queue. Host offload exists, but as a KV connector (OffloadingConnector) rather than as a preemption mode.

The reversal: swap wins when the model has large KV per token relative to its FLOPs (MHA models, long contexts), the copy path is a single batched gather kernel at tens of GB/s, the GPU is compute-bound so recompute steals real throughput, and the host pool is large. Long-context agents with 100K-token histories meet all four.

What interviewers probe next

"The model is MHA, not GQA." KV per token rises 4x for the same architecture otherwise, so the break-even bandwidth rises 4x to about 30 GB/s at 4K context, and only a well-batched copy path still wins.

"Preemption happens every few steps at peak. What do you change?" Not the preemption mode. Admit less: a KV watermark, a lower concurrency cap or FP8 KV, because frequent preemption means admission is overcommitting the pool.

"Which request do you preempt?" The newest, because it has the least sunk prefill and the least KV to rebuild; preempting the oldest throws away the most work.

How it's scored

Weak: asserts recompute is "faster on GPUs" or swap is "always better" with no per-token numbers.

Hire: writes both per-token costs, plugs in KV bytes, PCIe bandwidth and prefill FLOPs, and gets a break-even.

Strong Hire: shows that small per-block copies destroy effective bandwidth, adds the spare-compute and prefix-cache arguments, states what vLLM does today, and names the workloads that reverse it.

Common mistakes

• Counting the swap one way only. A preempted request must come back, so the KV crosses PCIe twice.
• Using the 128 GB/s bidirectional figure as if one direction could use it.
• Ignoring the attention term in recompute, which at 32K tokens makes up about a third of prefill FLOPs for an 8B model.
• Treating recompute as wasted work when the prefix cache still holds most of the request's blocks.