RL for LLM10 / 13

Module 10. Search, verification, and test-time compute

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Use the author’s worked answers to review open questions and code tasks yourself. Code does not run on this site.

Checked: 0 / 4 · Correct: 0

Question P01 · Three metrics for one candidate pool

A system generates 32 completions. At least one correct completion exists in 96% of runs, plurality voting is correct in 71%, and a reward-model selector is correct in 83%. Match the numbers to pass@32, self-consistency accuracy, and Best-of-32 accuracy. Why is reporting only the largest number misleading?

Your answer or notes

Answer and explanation

0.96 is pass@32 coverage, 0.71 is the accuracy of plurality voting, and 0.83 is the deployed accuracy of the reward-model selector. Coverage says a solution exists, not that the system returns it. A useful report therefore includes coverage, selected-answer accuracy, and cost.

Question P02 · Repeated attempts and conditional independence

Single-attempt empirical accuracy is 0.2, so independence predicts pass@8 = 1-0.8^8. In a real run, all eight answers often repeat the same error. Is that observation enough to establish dependence or the direction of error in the calculation? Give an independent-sampling counterexample and propose a protocol check.

Your answer or notes

Answer and explanation

No. An independent generator can return one correct answer with probability 0.2 and the same wrong answer with probability 0.8. All eight attempts then repeat that error with probability $0.8^8$ , while the coverage formula remains exact. Repetition alone establishes neither dependence nor the sign of a discrepancy. Check for shared prefixes, randomness, or search branches; measure coverage across repeated groups for fixed prompts, its uncertainty, and distinct answers. Prompt heterogeneity also prevents replacing each conditional $p$ with an overall average accuracy.

Question P03 · Ties and positional bias

Four votes produce counts (2,2,0). The correct category has index 1. What is its success probability under uniform random tie-breaking? What does np.argmax return?

Probability of a correct choiceAbsolute tolerance: ±0.000001np.argmax indexAbsolute tolerance: ±0

Only your selection or numeric part is checked automatically. Compare your reasoning with the author’s worked answer.

Answer and explanation

Uniform tie-breaking gives probability 1/2. np.argmax returns index 0 and is always wrong here. If the correct category were stored at index 0, it would always win the tie. The result therefore depends on array order rather than the intended voting protocol.

Question P04 · A verifier with anti-signal

Let $p=0.3$ , $\alpha=0.2$ , and $\beta=0.6$ . Does selecting uniformly among accepted candidates improve on the 0.3 base rate at large $N$ ?

Your answer or notes

Answer and explanation

No. Accepted-candidate precision is

\rho=\frac{0.3\cdot0.2}{0.3\cdot0.2+0.7\cdot0.6}=0.125.

With positive acceptance probability, large $N$ drives this protocol toward 0.125. The verifier is anti-informative because $\alpha<\beta$ ; inverting its decision might help, but that requires separate validation.

Question P05 · Uncertainty in a prefix label

Eight independent continuations are sampled from one prefix and six succeed. The Wilson 95% interval is approximately (0.4093, 0.9285). What does its width tell you?

Success estimateAbsolute tolerance: ±0.000001Wilson lower boundAbsolute tolerance: ±0.0001Wilson upper boundAbsolute tolerance: ±0.0001

Only your selection or numeric part is checked automatically. Compare your reasoning with the author’s worked answer.

Answer and explanation

The point estimate is $0.8^8$ , but the interval is wide. Eight rollouts provide a noisy process target even when the mean looks high. A PRM trained on such labels may need more rollouts, uncertainty-aware weighting, or shrinkage.

Question P06 · A hidden length penalty

Two paths have identical per-step scores 0.9 but lengths 2 and 10. Compare product and mean aggregation. What preference does the product introduce?

Product, 2 stepsAbsolute tolerance: ±0.000001Product, 10 stepsAbsolute tolerance: ±0.0001Mean for either pathAbsolute tolerance: ±0.000001

Only your selection or numeric part is checked automatically. Compare your reasoning with the author’s worked answer.

Answer and explanation

Both means equal 0.9. The products are $0.8^8$ and $0.9^{10}\approx0.3487$ . Product aggregation strongly prefers the shorter path. That is meaningful only under an appropriate joint-probability interpretation; otherwise it is an implicit length penalty.

Question P07 · One UCT index

A child has mean value 0.6 and 10 visits; its parent has 100 visits; $c=\sqrt2$ . Compute $0.6+c\sqrt{\ln100/10}$ .

UCT indexAbsolute tolerance: ±0.0001

Answer and explanation

The score is approximately $0.8^8$ . It is an optimistic selection index, not a success probability. Its scale depends on the value range and exploration coefficient.

Question P08 · A good tree with a bad scorer

Why can a wider beam hurt under a biased process score even when the correct branch exists in the tree?

Your answer or notes

Answer and explanation

A wider search exposes more prefixes that exploit the scorer's bias. Inflated dead ends can occupy the beam and prune the correct route. Existence of the route is coverage; retaining and selecting it is a separate property of the search controller.

Question P09 · The Pareto frontier

Modes have (cost, quality): A (1,0.70), B (2,0.80), C (3,0.75), D (4,0.85). Which points are non-dominated?

Your answer or notes

Answer and explanation

A, B, and D are non-dominated. C is dominated by B because B is cheaper and better. Choosing among frontier points requires a product-level trade-off over quality, latency, money, and risk.

Question P10 · Early stopping in a vote

The maximum budget is 11 votes. After 8 votes, the leader has 6 and the runner-up 2. Can the procedure stop if all three remaining votes could go to the runner-up?

Your answer or notes

Answer and explanation

Yes. The runner-up can reach at most 5, below the leader's 6. Stopping preserves the result of the full 11-vote protocol, but it does not establish that the leader is correct.

Question P11 · The price of a minimum quota

Why can “at least one completion for every prompt” reduce expected total coverage while still being a defensible product constraint?

Your answer or notes

Answer and explanation

The mathematical optimum may allocate zero attempts to nearly hopeless prompts and spend them where marginal gain is larger. A minimum quota lowers modelled average coverage but preserves basic availability, fairness, and an opportunity to detect a miscalibrated difficulty predictor. It is an external constraint, not a consequence of pass@N.

Question P12 · A release passport

Give two required fields for each layer: generator, selection/search, cost, and independent quality.

Your answer or notes

Answer and explanation

One valid answer is:

generator: model version and decoding parameters;
selection/search: verifier version and search hyperparameters;
cost: generated tokens/nodes and latency quantiles;
independent quality: selected-answer accuracy and held-out results.

Useful additions include seeds, rejection reasons, GPU-seconds, API price, calibration, and audits of proxy–goal disagreement.