Allocate Width, Depth, or a Search Tree
Paper version: “Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters,” v1 — https://arxiv.org/abs/2408.03314v1 • Source: Stanford CS329A, “Test-Time Compute Scaling,” 00:22:00–00:43:20 — https://www.youtube.com/watch?v=-Ggc37xLj_Y&t=1320s
Stop giving every request the same budget
Day 03 produced selector-calibration.json; Day 02 produced difficulty-profile.json. Today’s one capability is choosing an allocation policy among parallel samples, sequential revision, and tree search from those supplied measurements. The result is allocation-policy.json, tied to task difficulty, selector error, and remaining budget.
Snell et al. study process-verifier search and adaptive changes to the response distribution, finding that the best inference strategy depends on prompt difficulty; that is the paper’s experimental result, not a universal production guarantee (v1 paper). In that study, off-the-shelf prompted revision was ineffective; reported MATH gains for sequential strategies used fine-tuned revision and verifier models. Do not generalize them to an arbitrary chat model.
Conceptual reconstruction; not a source-figure transcription:
Read outcome and process reward correctly
Without feedback, a controller cannot decide where another unit of compute helps. An outcome reward scores the final answer: ShipRight’s full test suite returns pass or fail. A process reward scores an intermediate step: input validation is correct, integer units are preserved, or a proposed formula matches the written rounding policy.
Outcome reward is cheap and decisive when an oracle exists, but it says little about where a failed trajectory went wrong. Process reward offers denser guidance, but a mistaken intermediate scorer can steer search away from a valid unconventional solution. Reward-model training was introduced in How LLMs Actually Work, Day 05; this course consumes that concept and focuses on allocating inference, not retraining a reward model.
For ShipRight, score a reasoning state with three deterministic checks:
state score = validation_check + integer_units_check + boundary_example_check
Each check is 0 or 1. This is a hand-built process verifier, not a learned model. It lets the controller compare unfinished repair paths without claiming the highest-scored path is already correct.
Route easy, uncertain, and stuck work differently
An allocation policy turns evidence into the next action:
| Observed state | Next allocation | Why |
|---|---|---|
| Candidate passes all tests | Stop | More compute adds cost, not evidence |
| Several diverse near-passes | Add depth | Repair known local failures |
| Candidates fail in unrelated ways | Add width | Explore another basin |
| Intermediate steps have useful scores | Branch top states | Preserve promising partial work |
| No trustworthy verifier | Stop and escalate | Search cannot certify its output |
For the pricing bug, start with width 2. Candidate 0 keeps floats and fails the half-cent hidden test. Candidate 1 uses integer basis points but rejects valid discount_bps=0. Both are near-passes. Spend one depth step revising candidate 1’s boundary condition, then rerun all tests. Do not generate six unrelated candidates when feedback already localizes the fault.
For a latency-sensitive quote preview, cap at one candidate and one outcome check. For an overnight SQL migration proposal, permit a wider tree because dry-run invariants are cheap and no query is applied automatically. Compute-optimal means best allocation under a stated budget and task distribution, not “maximum possible thinking.”
Challenge the controller and recover safely
Difficulty estimation itself costs calls or calibration data. Easy tasks can invite verifier exploitation because many candidates optimize visible checks. Hardest tasks can show no progress as budget grows because generation assigns negligible probability to a valid path or the verifier supplies no useful gradient. A controller can amplify a bad reward. Imagine process score rewards “uses integer arithmetic” but omits negative-price behavior. A candidate can score 3/3 and still allow a refund to become a charge. Final protected tests must remain authoritative; process reward guides search, never bypasses outcome checks.
Normal path: depth repair passes public and hidden suites, search stops early, receipt records unused budget. Failure: three branches repeat the same invalid formula, triggering a diversity or retry cap. Recovery: return no_selection, preserve prior target, and hand the clustered failure traces to an operator. Positive control: an unrelated shipping-fee test continues passing. Cleanup: cancel queued branches, wait for running subprocess exits, then delete branch directories.
Scored check, with one unknown: two candidates fail different assertions and no intermediate state is better. Add one unit of width or depth? Expected: width. Choosing depth assumes a promising trajectory that evidence has not identified.
Save the decision:
{"schema":"allocation-policy/v1","easy":"parallel_2","medium":"tree_width_2_depth_2","hard":"abstain_after_no_progress","max_calls":8}
Assessment receipt: given one unknown—width or depth when two candidates fail different assertions and no path has a better intermediate score—the accepted answer is width; evidence is the unrelated failure traces, misconception is assuming a promising revision path exists, and remediation is checking whether feedback localizes one candidate’s fault.
Day 04 hands allocation-policy.json to Day 05, which composes one fixed inference architecture. Architecture search waits until Day 06.