hardNewvLLMTogether AI

Implement the block allocator behind a paged KV cache, including prefix sharing and copy-on-write.

A free list, a per-sequence block table, and a reference count are the whole structure. What forking costs, why the first write after a fork must copy, and the measured waste that this design accepts in exchange for eliminating the far larger waste of pre-allocation.

Updated Sep 2026 · Grounded in real AI infrastructure interview loops and written to a senior-engineer editorial bar, with every number worked and every diagram hand-built.

more free answers with an account · no card

The concepts behind this question

Ranked by how closely each one overlaps this question's topic, so the first card is the thing to read if the answer above moved too fast.

Foundational

🚀 Inference & Serving

The KV CacheThe KV cache stores each token's attention keys and values so decode never recomputes them, turning a quadratic cost into a linear one at the price of memory that grows with every token in every concurrent sequence. Its size, 128 KB per token for Llama 3.1 8B and 320 KB for 70B in bf16, is what caps concurrency and context on a given GPU, so it decides batch size, replica count and whether a model fits at all.

Advanced

🧮 Napkin Math & Capacity🔒 Premium

Bandwidth-Bound Decode ThroughputBecause decode reads every weight once per step, its speed is a division: memory bandwidth over bytes per step. That one formula gives single-stream tokens per second for any model on any card, the batch curve that flattens at the ridge point, the effect of quantization, and the point where the KV cache rather than the weights becomes the thing being read. This page derives it, works it for a 70B model on four accelerators, and shows how to read a vendor throughput claim against it.

Foundational

🧮 Napkin Math & Capacity

KV Cache SizingThe KV cache is the memory that decides how many users a serving replica can hold and how long their context can be. Its size per token comes from four numbers in the model's config file (layers, KV heads, head dimension, bytes per element) and one formula; multiplied by context and concurrency it is the number every capacity plan is built on. This page derives it, works it for four models including an MLA one, and shows the two places candidates get it wrong by a factor of eight.

Advanced

💻 Coding for Infra🔒 Premium

Batching Queues and BackpressureWrite a request batcher is the coding round's version of the serving engine's scheduler: requests arrive one at a time, the GPU wants them in groups, and the batcher decides when a group is full enough to send without holding anyone too long or accepting more than it can hold. The two knobs are the maximum batch size and the maximum wait, the invariant is a bounded queue, and the follow-ups (priorities, cost-aware batching, cancellation, bounded in-flight batches) are the ideas the real engines carry. This page implements the batcher in asyncio, derives what each knob buys, and walks the follow-ups.

Explore the full curriculum →

UP NEXT ON YOUR JOURNEY

Next in this trackImplement the scheduler loop of a continuous-batching engine: admit, step, preempt. Where does it livelock?Next in this trackIn Go, download many model shards concurrently with a concurrency limit, a timeout and clean cancellation. Write it.Next in this trackRoute requests to replicas by prefix using a consistent hash ring. Why virtual nodes, and how many?

FEDITOR'S NOTE

Scored on reference counting for shared prefixes, on copy-on-write at the first append after a fork, and on quantifying the internal fragmentation the block size costs.

DISCUSSION · 0

No comments yet — be the first to share your approach.