Question 1

Implement a paged KV-cache block manager with copy-on-write forking, then a scheduler step that preempts when blocks run out.

Accepted Answer

Forty lines of Python, and graders run property tests against them. The answer gets the three invariants right first, then the one copy-on-write case most implementations get backwards.

Question 2

Implement grouped-query attention over a preallocated KV cache, with no torch.cat, for both prefill chunks and decode.

Accepted Answer

The attention math is ten lines. The grade comes from where the new keys land, which query head reads which KV head, and the causal mask when a chunk of queries sits at the end of a longer cache.

Question 3

Implement batched top-p sampling with temperature. It must handle ties at the cutoff, p = 1, temperature 0 and masked tokens.

Accepted Answer

Everyone can sort and cumsum. The grader feeds you tied logits, p = 1 on a 128K vocabulary and a temperature of zero, and checks whether your kept set depends on the order of the sort.

Question 4

Implement a continuous batching scheduler with a token budget and chunked prefill, so decodes never wait behind a long prompt.

Accepted Answer

A scheduler is a loop over three queues and a budget. The answer gets the order of those loops right, shows what the budget costs in milliseconds of TPOT, and tests the invariants a grader will check.

Question 5

Implement the lossless speculative sampling verifier for a batch with ragged draft lengths, and prove it matches the target.

Accepted Answer

The accept rule is one line. The residual distribution, the bonus token, rows that drafted fewer tokens and a test that can tell a lossless verifier from a subtly biased one are the rest of the grade.

Question 6

Implement a radix tree prefix cache: match, insert with edge splitting, request locks and LRU eviction of unlocked leaves.

Accepted Answer

Matching a prefix is a trie walk. The grade is in the edge split, which cached tokens a running request pins, and an eviction loop that turns parents into leaves without ever freeing a slot twice.

Question 7

Implement RoPE for a batched decode step where every row sits at a different position, and verify it against the full-sequence version.

Accepted Answer

RoPE is a rotation per pair of dimensions. The bugs live in which dimensions pair up, which position each row of a ragged batch is at, what left padding does to position ids, and the precision of the angle at position 100,000.

Question 8

Implement INT4 packing with group scales and a dequantizing matmul, and test it against FP32 with odd K and a partial group.

Accepted Answer

Two nibbles per byte and a scale per 128 weights sounds like bookkeeping. The grader checks the sign extension, the nibble order, what happens when K is odd or not a multiple of the group, and whether your error test has a bound or just a vibe.

Question 9

Write a row-wise softmax kernel in Triton that stays correct when a row is longer than the block size, and test it.

Accepted Answer

The tutorial kernel loads a whole row into one block and breaks the moment the row is a 128,256-entry vocabulary. The answer writes the looped version, keeps it free of NaNs when a whole tile is masked, and tests it the way a grader will.

Question 10

Implement a ring all-reduce as a simulation over p ranks, verify it against a direct sum, and count the bytes each rank sends.

Accepted Answer

Two loops and an index formula, and most attempts get the index wrong by one. The answer writes reduce-scatter and all-gather over a simulated ring, proves the result matches a direct sum when p does not divide the length, and turns the byte count into the reason small messages avoid the ring.

Question 11

Implement beam search over a paged KV cache, forking beams by sharing blocks and copying only the tail on write.

Accepted Answer

Beam search reshuffles which hypotheses survive every step, and a naive cache copies every survivor's history. The answer forks block tables instead, gets the release order right so the last sharer writes in place, and proves it against a beam search that never pages.

Question 12

Implement a per-tenant rate limiter for an LLM API that limits tokens, not requests, using a token bucket.

Accepted Answer

A request costs anything from ten tokens to a hundred thousand, and you only learn the real cost when it finishes. The answer reserves at admission, refunds at completion, fails fast on requests that can never fit, and tests the bound the bucket is supposed to guarantee.

Question 13

Implement a KV block allocator that shares prefix blocks across requests by chained hashes, with LRU eviction of cached free blocks.

Accepted Answer

Two prompts with the same 16 tokens in block 3 must not share block 3 unless blocks 0 to 2 match too. The answer chains the hashes, keeps freed blocks hittable until memory is needed, evicts tails before heads, and proves a colliding hash cannot hand a request the wrong KV.

Question 14

Implement a minimal autoregressive generate loop that streams text and honors stop sequences, including ones split across tokens.

Accepted Answer

The stop string arrives as three tokens, the euro sign arrives as two, and the client has already been sent half of both. The answer holds back exactly the text that could still become a stop, decodes bytes incrementally, and tests the stream against a reference that sees the whole output at once.

Question 15

Implement split-KV decoding attention and the merge of the partial results, and prove it matches attention over the whole sequence.

Accepted Answer

At batch 1 a decode attention kernel gives each KV head one thread block and leaves most of the GPU idle. The answer splits the sequence, carries a log-sum-exp with every partial output, merges them exactly, and survives the split that has no keys at all.

Question 16

This KV allocator passes ordinary append tests but corrupts forked requests. Find two bugs and prove the repair.

Accepted Answer

A runnable allocator hides an exception-safety defect and a payload-aliasing defect. Reduce each failure to a short operation sequence, then test ownership and content against separate oracles.

Question 17

Implement cancellation for an inference request without reusing KV pages while GPU work still references them.

Accepted Answer

A disconnect arrives after launch, then the request ID is reused. Implement deferred reclamation and prove that late or duplicate completions cannot emit stale output or free another request's pages.

Question 18

A continuous batch changes order while a forward pass runs. How do you return each token to its owner?

Accepted Answer

The tensor has the right shape and every token ID is valid, yet one request receives another request's continuation. Reproduce the routing error and repair the launch-to-completion contract.

Question 19

A speculative verifier returns correct tokens, but the next step diverges. Debug its cache commit boundary.

Accepted Answer

Accepted, emitted and computed tokens are different counts. Trace rejection, full acceptance, EOS and an output cap to find the state that the next forward pass is allowed to read.

Question 20

Logits are identical, but a seeded request changes output after batch reordering. Repair the sampler's RNG contract.

Accepted Answer

A fixed global seed reproduces a launch order, not a request. Build a random-draw address that survives compaction, extra draft work and continuation, then state what it cannot guarantee.

Question 21

A streaming client stops reading. Keep its output bounded without blocking the inference batch.

Accepted Answer

One slow connection can stall unrelated generations or retain an unbounded output queue. Implement a byte budget that includes the pending write, then connect overflow and disconnects to engine cancellation.

Implement-from-Scratch Coding

Inference Coding Interview Questions