08.06 · Concept
Parallel Sampling
Spend the budget sideways instead of deep, on best-of-n and self-consistency, and price it properly: n branches share one prompt prefix but each own their divergent KV, so the cost is sublinear in memory and linear in decode.
Parallel sampling spends extra inference budget on multiple independent continuations from one prompt, then picks or aggregates the results. The shared prompt prefix is paid once, but every branch still pays for its own generated tokens and divergent KV cache, so memory grows sublinearly while decode cost grows linearly.
What this lesson answers
- how does parallel sampling reduce inference cost
- best of n versus self consistency inference
- why prefix sharing does not save decode
Notes
Parallel sampling means running independent continuations from the same prompt state, usually with nonzero temperature, then selecting or aggregating them: best-of- chooses under a reward, verifier, logprob, or task metric, while self-consistency estimates after mapping each rationale to an answer .
Common questions
- What is parallel sampling in model inference?
- Parallel sampling runs multiple continuations from the same prompt state, usually with randomness enabled. The outputs are then selected by a verifier, reward model, task score, or combined by answer-level voting. It is a way to spend compute on breadth: several attempts from one context rather than one longer or more deterministic attempt.
- Why is parallel sampling cheaper than separate retries?
- Separate retries repeat the prompt processing and usually duplicate the prompt KV cache. A serving system with prefix sharing can process the prompt once, keep one shared prefix, and attach separate branch tails as generations diverge. That saves prefill work and prefix memory, but not the cost of producing each branch token.
- When is best-of-n not worth the extra inference cost?
- Best-of-n becomes unattractive when generated answers are long, the prompt is short, or decode already dominates latency and cost. The shared prefix then represents only a small part of the request. More branches may also consume batch capacity that could have served other users, especially if the runtime cannot share prefix KV correctly.
Short definition: what is Parallel Sampling?