Part 10 of 12 · 2 min read
Quick notes
- Three questions look alike but need different tools: how many attempts at one task (repeated sampling), which task next (prioritisation), and which strategy next (exploration against exploitation).
- Repeated sampling is test-time compute with diminishing returns, and how you choose among attempts matters more than how many you make.
- Best-of-N with a verifier kept improving; majority vote flattened, because wrong answers can agree. A verifier is only as good as its false-approval rate.
- Under a budget, order by value per cost, but when value estimates are noisy, ranking by value hurts and cheapest-first can win.
- A policy that never tries alternatives has regret that grows linearly; adaptive policies (epsilon-greedy, Thompson sampling, UCB) grow far more slowly and survive a mid-run change in the best strategy.
The detail The full notes
- Three questions look alike but need different tools: how many attempts at one task (repeated sampling), which task or branch next (prioritisation), and which strategy to run next (exploration against exploitation).
- Repeated sampling (best-of-N, majority vote, self-consistency) is test-time compute: more attempts, more cost, diminishing returns. Two outputs cost about twice as much as one, and diversity in the candidates raises the chance that one is good. Self-consistency draws several reasoning paths and takes a majority vote; external verifiers and iterative generation with verifier feedback are the other common forms.
- How you choose among attempts matters more than how many you make:
- best-of-N with a verifier rose from 0.55 (one sample) to 0.73 at N=3, 0.78 at 5, 0.82 at 15, at twice the calls because every candidate is checked;
- majority vote rose only to 0.63 at N=5 and then flattened at 0.65, because wrong answers can agree: when half the wrong answers were the same attractor, N=15 gave 0.65; when 90 percent were, 0.58; when they scattered, 0.72.
- A verifier is only as good as its false-approval rate: best-of-5 fell from 0.83 (never approves a wrong answer) to 0.77, 0.69, 0.63 and 0.54 (approves everything, no better than one sample).
- Prioritisation under a budget: ordering by value per cost reached 99 percent of the best possible value; arrival order reached 58 percent; highest value first 86 percent. But when the agent's value estimates are noisy, ranking by value hurts: at 100 percent estimate error value-per-cost fell to 0.84, below the 0.88 of simply taking the cheapest first.
- Exploration: a policy that never tries alternatives has regret that grows linearly (32 at 100 runs, 160 at 500); adaptive policies (epsilon-greedy, Thompson sampling, explore-then-commit) grow far more slowly (8 at 100, 24 to 27 at 500). If the best strategy changes mid-run, committing forever is fragile (regret 114 against 83 to 102 for UCB, Thompson and epsilon-greedy over 1,000 runs).