Senior interview question
Your chat app's replies range from 8 to 256 tokens. Which batching strategy would you pick, and what did the simulation show?
Model answer
Continuous batching. Static batching waits for a full batch and dynamic caps the wait, but both finish a batch together, so a short reply waits for its longest neighbour. Continuous batching, Orca's iteration-level scheduling, returns each reply when done and refills its seat.
Scroll sideways to see the whole diagram
Two requests are decoded together: A needs 8 more tokens, B needs 64.
Text version
- Two requests are decoded together: A needs 8 more tokens, B needs 64.
- In request-level batching the batch finishes together. A's reply is ready after 8 steps but waits 56 more for B.
- In continuous batching A is returned as soon as its last token is generated.
- Its seat is filled by a waiting request at the very next step, so the batch stays full.
- Orca calls this iteration-level scheduling: the batch is decided again before every step.
After AI Engineering, Ch. 9, "Batching", and Orca (Yu et al., OSDI 2022). Illustrative lengths.
Simulated from our measured Apple GPU steps (200 requests, at most 8 at once), continuous gave 343 tokens/s and a 22 ms median first token; static batches gave 299 tokens/s and a 5.3 s median wait.
Practise the rest
10 Where the time goes questions, 492 in all, each with a model answer. Free.
More Where the time goes interview questions
- What's the difference between compute-bound and memory bandwidth-bound work, and which one is decode?
- How would you show, on a given machine, that decode is bandwidth-bound and prefill compute-bound?
- Why does decoding a batch of 8 cost far less than 8 separate decode steps, and why can't the batch grow forever?
- You're sizing an 80 GB accelerator for Llama 2 13B in 16-bit with 2,048-token conversations. How many fit, and what would you change if that's not enough?
- Estimate an FFN layer's FLOPs, parameter and activation bytes, and the communication from sharding it. Which limit binds: compute, HBM or network?
- Explain the optimisations an ML compiler makes, such as kernel fusion, and how they map to the hardware.