Repeated Sampling Finds Rare Successes
Source: Stanford CS329A, “Test-Time Compute Scaling,” 00:05:29–00:11:18 — https://www.youtube.com/watch?v=-Ggc37xLj_Y&t=329s • Paper: “How Do Large Language Monkeys Get Their Power (Laws)?” — https://proceedings.mlr.press/v267/schaeffer25a.html
Spend width on independent attempts
Day 01 produced task-outcomes.json. Today you will allocate width: multiple samples for each task, run in parallel, then emit candidate-corpus.json and difficulty-profile.json. Sampling temperature and top-p were already taught in How LLMs Actually Work, Day 03; use that exact back-route if “sample” is unfamiliar.
The Stanford lecture defines coverage as the share of problems solved by at least one sample and discusses its scaling with sample count at 00:05:29–00:06:03. Width changes search coverage, not model weights.
Conceptual reconstruction; not a source-figure transcription:
Derive the per-task exponential law
If one independent attempt solves a fixed task with probability p, it fails with probability 1-p. All k attempts fail with (1-p)^k; therefore the probability that at least one succeeds is:
P(success by k) = 1 - (1 - p)^k
For a ShipRight repair with hypothetical single-sample success p=0.25:
Samples k | All fail (0.75)^k | At least one succeeds |
|---|---|---|
| 1 | 0.7500 | 0.2500 |
| 2 | 0.5625 | 0.4375 |
| 4 | 0.3164 | 0.6836 |
| 8 | 0.1001 | 0.8999 |
This conceptual simulation is not a fit to ShipRight data. Its exponential saturation law assumes independent and identically distributed (IID) attempts, constant p, and an analysis oracle that labels success after the fact. It is the same probability behind pass@k, already taught in How LLMs Actually Work, Day 08; today’s advance is building a difficulty profile for allocation.
Aggregate difficulty creates a heavy tail
A service handles many tasks, each with its own p_i. Easy tasks have large p_i and saturate quickly. Rarely solved tasks have tiny p_i; they keep contributing new successes at large k. Mixing those per-task exponentials can create aggregate power-law scaling when single-attempt success probabilities are heavy-tailed, as the authors derive and test (PMLR paper). The lecture connects this effect to a long tail of hard problems at 00:10:14–00:11:18.
A light-tail counterexample is a task set where every task has p_i >= 0.5: almost all gains arrive in the first few samples. A correlated-sample falsifier is eight candidates with the same reasoning trace and same wrong answer. Call count increased, but effective diversity did not; the IID equation no longer describes that pool.
Consider four real workflows with illustrative, measured-on-your-own-system probabilities rather than universal claims:
| Task | Hypothetical p_i | P(success by 8) | Verifier available? |
|---|---|---|---|
| Integer arithmetic | 0.80 | nearly 1 | Exact answer |
| ShipRight code repair | 0.25 | 0.8999 | Tests, introduced Day 03 |
| SQL order aggregation | 0.10 | 0.5695 | Query result invariants |
| Customer-support apology | 0.04 | 0.2786 | No complete oracle |
The last row exposes a boundary: sampling can generate many empathetic replies, but “good support” depends on policy, facts, tone, and customer context. Width cannot manufacture a trustworthy verifier.
Compare latency and cost before scaling out
Parallel samples reduce elapsed time only when capacity exists. Eight 2-second calls may finish near 2 seconds while consuming roughly eight calls of compute; under a two-worker cap they arrive in four waves and approach 8 seconds. Use observed provider billing and queueing data, not sample count alone.
ShipRight’s decision table:
| Signal | Allocation |
|---|---|
| Low-value quote preview | k=1; return quickly |
| Checkout total with deterministic tests | k=4; verify all |
| Incident repair with 15-minute operator window | k=8; parallel cap 4 |
| No reliable verifier | k=1; request human review |
Normal path: four candidates finish within byte/time limits. Failure: two time out, each receives an explicit status. Recovery: remaining workers continue; timeouts do not cancel healthy siblings. Cleanup: all sample directories disappear after outputs and correlations are recorded.
candidate-corpus.json stores task ID, sample ID, prompt/config fingerprint, output hash, cost fields, and analysis-only correctness label. difficulty-profile.json stores observed success frequency, pairwise answer duplication, timeout rate, and an explicit iid_supported flag. Neither file is a deployed selector.
Scored check, with one unknown: p=0.25, k=4. Compute probability at least one attempt succeeds. Expected: 1 - 0.75^4 = 0.68359375. Answering 1.0 assumes diversity guarantees correctness.
Assessment receipt: given one unknown—p=0.25 with k=4—the accepted result is 0.68359375; evidence is 1 - 0.75^4, misconception is treating four attempts as guaranteed success, and remediation is recomputing the all-fail complement. Identical hashes remain a separate falsifier for the IID assumption, not a second scored item.
Day 02 hands candidate-corpus.json and difficulty-profile.json to Day 03. No candidate is selected because analysis labels are unavailable to deployment.