Articles
Rejection Sampling for LLMs: Interview Questions on Quality, Diversity, and Cost
Practice LLM rejection sampling interview questions with best-of-N distribution traces, reward-model checks, diversity measures, and compute-cost trade-offs.
Generating more answers and keeping the highest-scoring one can improve an LLM's selected output. It also changes the output distribution, spends compute on discarded candidates, and gives a flawed judge more chances to select a convincing mistake.
A clear rejection-sampling interview answer separates the selection rule, training update, and evaluation metric. This guide gives you a three-outcome distribution trace and a compute ledger for explaining quality, diversity, and cost without treating reward score as ground truth.
Evidence boundary: Primary papers establish the methods their authors actually studied. Classical sampling theory comes from the linked textbook chapter. Numerical cases are original exercises, and proposed evaluation designs are engineering inference. No candidate reports are used, and no employer's interview format is implied.
For targeted practice, use the reward-model versus DPO comparison to explain where generation, selection, and parameter updates enter the pipeline.
Which meaning of rejection sampling does the interviewer intend?
Ask whether the goal is to sample from a specified target distribution or to select useful responses from a candidate pool. The algorithms need different correctness claims.
Primary research fact: The Llama 2 paper describes rejection-sampling fine-tuning as generating multiple outputs, selecting the highest-reward response for each prompt, and training on the selected responses. That is an account of the paper's procedure, not a universal definition of all LLM post-training.
Best-of-N at inference ends with serving the winner. Rejection-sampling fine-tuning adds an update using the selected dataset. Threshold filtering instead accepts candidates satisfying a condition. These can share a generator and scorer while producing different output distributions and training data.
Classical source: Art Owen's acceptance-rejection chapter describes an envelope-based method. With normalized target p, proposal q, and a valid constant M satisfying p(y) ≤ Mq(y) everywhere, accept a proposal y with probability p(y)/(Mq(y)).
Under those assumptions, its accepted samples have distribution p. The proposal must cover the target's support, and the envelope condition must hold globally. Clipping an invalid acceptance ratio to one generally changes the result; it does not repair the proof.
An interview answer should name the method before naming its benefits. “It removes bad samples” cannot establish whether the resulting samples follow p, a conditional distribution, or a maximum-score distribution.
Trace three outcomes through three selection rules
Original discrete exercise: Suppose the proposal produces responses A, B, and C with probabilities 0.5, 0.3, and 0.2. A judge assigns increasing scores: A lowest, B middle, C highest. This ordering is assumed perfect only for this calculation.
The desired target is instead p = (0.2, 0.3, 0.5). The largest p/q ratio is 2.5, so choose M equal to 2.5.
| Outcome | Proposal q | Target p | Envelope acceptance p/(2.5q) | Best-of-two output |
|---|---|---|---|---|
| A | 0.50 | 0.20 | 0.16 | 0.25 |
| B | 0.30 | 0.30 | 0.40 | 0.39 |
| C | 0.20 | 0.50 | 1.00 | 0.36 |
The envelope method accepts total mass 0.5×0.16 + 0.3×0.4 + 0.2×1 = 0.4. Dividing accepted mass by 0.4 recovers the target (0.2, 0.3, 0.5). The expected number of independent proposals per accepted output is 1/0.4 = 2.5.
For best-of-two, A wins only when both proposals are A: probability 0.5² = 0.25. C wins whenever at least one proposal is C: 1 - 0.8² = 0.36. B gets the remaining mass, 0.39.
The winner distribution differs from both p and q. If a threshold simply removes A and accepts B or C, the accepted distribution is (0, 0.6, 0.4). Three sensible-looking selection procedures therefore answer three different probability questions.
For a general ordered discrete score, the probability of selecting outcome i as the maximum is F(i)^N - F(i-1)^N, where F is the proposal's cumulative mass in score order. Ties between distinct responses need an explicit rule; the simple expression describes ordered outcome categories here.
This trace is more useful than claiming best-of-N “approximates the target.” There is no target-distribution guarantee without defining a target and proving the selection rule matches it.
How much quality can additional samples buy?
Original idealized calculation: If an independently drawn candidate is correct with probability 0.2, the probability that at least one of N candidates is correct is 1 - 0.8^N. It is 0.2 for one candidate, 0.5904 for four, and approximately 0.8322 for eight.
This is candidate availability, not selected-answer accuracy. To convert it into winner accuracy, the selector must reliably identify a correct answer whenever one exists. A judge that prefers a fluent wrong answer breaks that implication.
Correlated candidates also weaken the simple independence calculation. Repeating nearly identical reasoning under slightly changed random seeds can spend eight generations without creating eight independent opportunities. Temperature, prompts, and model choice affect the proposal pool, but none guarantees useful independence.
Primary research fact: The test-time compute paper studies how inference compute is allocated and finds that the useful strategy depends on factors including problem difficulty. It does not justify choosing one universal N for every production request.
Engineering inference: Measure the marginal independent quality gain per added unit of compute. Compare N values on the same held-out prompts, record errors by category, and keep a single-sample baseline. An adaptive budget can be appropriate when a reliable signal identifies hard requests; validate that signal rather than assuming confidence equals correctness.
Why can a higher reward score hide worse answers?
The judge defines what selection optimizes. A model-based reward can be a useful proxy without being the task objective itself. More aggressive selection can amplify a weakness in that proxy.
Primary research fact: Scaling Laws for Reward Model Overoptimization studies the divergence between proxy reward and a separate reward signal under optimization, including best-of-N. Its experimental setup supports a caution about proxy optimization, rather than a claim that every reward model fails at a particular N.
Original diagnostic case: Candidate A is short and correct; B is longer and cites nonexistent evidence; C is polished but ignores a constraint. If the judge mostly rewards detailed presentation, B or C may outrank A. Increasing N supplies more opportunities for that failure.
Engineering inference: Evaluate winners with evidence that was not used to select them. For executable tasks, use held-out tests with a clear specification. For factual responses, inspect source support. For subjective tasks, use blinded human comparisons and disagreement analysis. Each evaluator has limits; independence from selection is valuable but does not make it infallible.
Freeze the judge version for a comparison, log its prompt and scoring rubric, and separate candidate-generation changes from judge changes. Otherwise, a reported gain may combine several interventions that cannot be attributed.
Do not train a model on the selected outputs and then evaluate it only with the same judge. That creates a feedback loop in which the model can improve at pleasing the selector while independently measured quality stalls.
What diversity should survive selection?
Diversity is not merely a high count of unique strings. Eight differently worded copies of the same reasoning path may offer little coverage. Conversely, a task with one precise answer should not reward arbitrary contradictions as diversity.
Engineering inference: Define diversity at the level that matters: valid solution strategy, supported viewpoint, language, response style, or user subgroup. Measure it in the proposal pool, after selection, and after any fine-tuning update. Those are different stages.
In the three-outcome exercise, increasing N makes the highest-scoring category C increasingly dominant. As N grows, 1 - 0.8^N approaches one. A selected dataset can therefore become concentrated even when the generator still has substantial probability on A and B.
For a training dataset, inspect prompt coverage as well as response coverage. A fixed score threshold may reject most responses for difficult prompts while accepting many easy ones. The resulting dataset can overweight easy requests without anyone explicitly choosing that policy.
Potential controls include per-prompt quotas, stratified auditing, deduplication, and preserving multiple valid approaches. Each changes the selection rule or training mixture. Explain what distribution you want to preserve and what quality trade-off you are willing to make.
Never retain unsafe or invalid outputs simply to improve a diversity statistic. Treat validity requirements separately from diversity among valid responses, and report the rejected population rather than silently forgetting it.
Build a cost ledger before comparing methods
Original hypothetical budget: Let generation cost three compute units per candidate and judging cost one unit per candidate. One independent comparison uses P prompts and N candidates per prompt.
collection cost = P × N × (generation + judging)
= P × N × 4
For P = 1,000 and N = 8, collection costs 32,000 units. If training on the selected responses costs another 6,000 units, the experiment totals 38,000 before evaluation. These units are invented for reasoning; they are neither GPU measurements nor provider prices.
Best-of-N inference pays the generation and selection costs at request time. Fine-tuning on selected outputs pays collection and training up front, potentially serving one response later. It does not guarantee that the trained model reproduces the selector's quality, so the cheaper serving path must be evaluated independently.
An amortization comparison needs traffic volume, refresh frequency, evaluation costs, and the quality difference between the alternatives. A one-time training expense can be inexpensive across many requests and wasteful for a small, rapidly changing workload.
Latency is another column. Parallel generation can reduce wall-clock time without reducing total compute. Memory capacity, queueing, variable sequence length, and judge scheduling constrain that parallelism. Report both total resource consumption and latency percentiles rather than calling parallel candidates free.
For threshold rejection, a constant independent acceptance rate a gives expected proposals 1/a. A retry cap changes the behavior: some requests fail to produce an accepted output. Define fallback or abstention explicitly, and do not count only successful requests when estimating cost.
How would you test the complete selection pipeline?
Engineering inference: Use a deterministic fixture before a model benchmark. Give the selector candidate IDs, known scores, ties, missing scores, and judge errors. Verify that it returns the intended ID, keeps text attached to that ID, and applies the documented fallback.
Then run a held-out prompt experiment. Save all candidates, selection scores, independent outcome labels, token counts, and timing. Compare selected quality and diversity against both the one-sample baseline and the best available candidate under independent labels. The gap between that available candidate and the selected winner reveals selector failures.
If selection data trains the next model, preserve dataset provenance and evaluate the resulting checkpoint separately. Check difficult prompts, underrepresented groups, and behavior that earlier checkpoints handled well. Selected-data quality is a hypothesis about the next model, not proof of its behavior.