feat: best-of-N parallel worker — tournament-select candidates against the frozen ladder

[krimvp]

Problem / motivation

Today goaly runs exactly one worker per iteration, retried strictly in series. step() advances one canonical LoopCtx; the Driver emits exactly one RUN_AGENT command, gets one AGENT_RAN back (src/orchestrator/step.ts startIteration → stepRunningAgent), scores it on the frozen ladder, and only then does iteration N+1 begin (src/driver/driver.ts enforces commands.length === 1 per non-terminal state). The whole iteration N+1 is gated on N's verdict via decide() (src/orchestrator/decide.ts).

That serial retry leaves a lot of value on the table. goaly already owns the two hard pieces needed to do better:

1. A frozen, ungameable scorer — the verifier Ladder (src/verify/ladder.ts) runs the rungs cheapest-first with short-circuit and is fail-closed. It is a perfect tournament referee: "most rungs passed" is a total, deterministic order over candidates, computed by the identical frozen contract for every one of them.
2. A private tree-snapshot / baseline machinery — GitWorkspace.checkpoint() / #snapshotTree() write a content-addressed git tree with a throwaway GIT_INDEX_FILE and no commit / no HEAD or branch move (src/workspace/git-workspace.ts), plus setBaseline()/currentBaseline()/--baseline and the Baseline module (src/driver/baseline.ts).

A worker that produces a wrong-but-plausible edit costs a full iteration to discover and unwind. Running K independent attempts per iteration and keeping the best-scoring one trades wall-clock-serial latency and tokens for a materially higher chance that an iteration ends green — without weakening the bar, because every candidate is judged by the same frozen ladder.

Proposed capability

A new flag --candidates N (alias --best-of N; default 1 = today's behavior, byte-for-byte). When N > 1, each loop iteration fans out K independent worker attempts into isolated git worktrees, scores each against the same frozen verifier ladder, and keeps the single best-scoring candidate's tree as the iteration's result.

goaly run --goal "..." --verify-cmd "npm test" --candidates 4
goaly run --goal-file ./BIG.md --generate --phased --candidates 3 --sandbox

From the user's point of view nothing else changes: still one frozen contract, still one canonical iteration count, still two keys for DONE, still --resume-able. goaly runs show gains a per-iteration "K candidates, winner = #j (3/4 rungs)" line.

Selection order (the tournament). Most rungs passed on the frozen ladder wins. Because Ladder.verify() short-circuits at the first failing rung, a partial scorer is needed for ranking; see Open questions for exactly how rung-depth is derived without re-authoring the bar. Tie-break, in order: (a) a passing ladder + non-veto Sign-off beats a passing ladder alone; (b) lower cost (tokens/wall-clock from the per-candidate BudgetSnapshot); (c) lowest candidate index (stable, deterministic).

Worktree lifecycle (Driver-only). For an iteration the Driver: (1) creates K linked worktrees off the current baseline tree (git worktree add pointed at the snapshot SHA checkpoint() already produces); (2) runs the worker + scores the ladder in each, concurrently; (3) selects the winner purely from the recorded per-candidate results; (4) promotes the winning tree into the canonical workspace and advances the one baseline; (5) tears down all K worktrees. All of this is effect code — none of it touches the reducer.

Why it belongs in goaly

It is the natural payoff of goaly's central thesis: a success criterion the worker can't weaken. A frozen, ungameable contract is exactly what makes best-of-N safe — selection is anti-reward-hacking by construction, because the thing choosing the winner is the same frozen ladder + veto-only approver that gates DONE, not a softer proxy. It is harness-agnostic (any HarnessAdapter works; K attempts are K harness.run() calls), reuses the existing snapshot/baseline machinery, and composes with --phased, --delta-verify, and --sandbox. It strengthens the loop's core promise (reach green, verifiably) without adding a new trust seam.

Invariant impact

This is the crux; each of the eight is addressed concretely.

• Zero-LLM pure reducer (preserved). All fan-out, parallelism, scoring, and selection live in the Driver. The reducer still advances one LoopCtx per iteration and receives exactly one winning Event. Concretely: a new Command RUN_AGENT_BEST_OF { prompt; sessionId; candidates: N } replaces RUN_AGENT when N > 1 (chosen purely in the reducer from ctx.config.candidates; still one command per non-terminal state, so the commands.length === 1 Driver invariant holds). The Driver performs the whole fan-out/score/select tournament and folds it into the existing AGENT_RAN event for the winner — same shape (run, prevDiffHash, diffHash, budget), so stepRunningAgent is unchanged and step() stays synchronous with no Promise/IO. The reducer never learns K existed.
• Compile once, then freeze (preserved). Every candidate is scored by the identical frozen ladder built once from the frozen contract (makeLadder(contract), reused as the Driver does today). Nothing is authored or rewritten per candidate; contractHash is logged unchanged every iteration. No per-candidate bar.
• Two keys for DONE (preserved). Selection picks the best candidate; it does not declare done. The winner still flows through RUN_VERIFIER → VERIFIED and, only on a passing ladder, REQUEST_SIGNOFF, exactly as today — so DONE still requires the frozen ladder to pass and the approver not to veto. A crashing/timing-out candidate is just a non-winning candidate, never a green. If all K fail, the winner is the least-bad red and the iteration is a normal red that loops back through decide().
• Fail-closed everywhere (preserved). A candidate whose worker throws, times out, crashes, or whose worktree/ladder errors scores as a hard red (pass:false, the ladder's own fail-closed path) and simply can't win on merit. The Driver's per-candidate scoring is wrapped like runVerifierFailClosed; drive() still never rejects. An empty/degenerate candidate set degrades to "all red" — never a green, never a throw.
• --autonomous moves Seal only (untouched). Best-of-N is post-Seal loop behavior; it never touches contract authoring or the freeze.
• Parse at every seam, Zod (preserved). The winner's AGENT_RAN is the existing Zod-validated event. New per-candidate records written to the log (see below) get their own Zod schema and parse on read; the new Command needs no schema (Commands are never persisted). --candidates parses as a positive int in args.ts.
• Write-ahead + resume (the sharp risk — see below). Resolved by logging each candidate's completion as a non-reducer marker event, then logging the winner selection, with the winning tree promoted via the existing CHECKPOINTED/baseline path so resume is a deterministic replay-fold that re-runs no completed candidate and double-applies no tree.
• Stuck detection stays pure (preserved, with one honest subtlety). The canonical LoopCtx still records exactly one diffHash per iteration — the winner's post-tree hash — so no-diff / oscillation / repeat-failure keep their meaning over the canonical timeline. The working-tree hash still means "what the iteration committed to," now "best of K" instead of "the one." See Open questions for the one genuine wrinkle (a tie repeatedly selecting an identical loser tree).

Alternatives considered

• Reducer-level fan-out (reducer emits K RUN_AGENTs, collects K events) — rejected: breaks the commands.length === 1 invariant and forces the reducer to hold parallelism/selection state, eroding purity. Selection is an effect; it belongs in the Driver.
• Best-of-N as an outer wrapper running K whole drive()s and diffing outcomes — rejected: K full runs don't share a frozen contract instance or a single run log, can't promote a partial winning tree mid-loop, and lose per-iteration tournament selection (the whole point).
• Sequential "try, score, retry if red" (today) — the status quo; strictly weaker per wall-clock because a good attempt is never raced against alternatives.
• Commit each candidate to a branch — rejected: violates the "no commit / no HEAD movement" guarantee checkpoint() is built to preserve; the worktree-off-a-tree-SHA approach keeps that intact.

Acceptance criteria / definition of done

• --candidates N / --best-of N parses (positive int, default 1) in src/cli/args.ts; RunConfig gains candidates in the loop-policy view so a --phased sub-goal inherits it via pickLoopPolicy (src/orchestrator/step.ts phaseConfigFor).
• N === 1 is byte-for-byte the current path: the reducer emits RUN_AGENT, not the new command, and no candidate markers are written (existing logs and tests unchanged).
• Reducer purity proven: step()/decide()/stuck.ts import no adapter, take no Promise, and stepRunningAgent is unchanged; a test asserts the reducer sees exactly one winning AGENT_RAN regardless of N.
• Tournament selection is a pure, table-tested function over recorded per-candidate { verdict, budget } results (rung-depth, then Sign-off, then cost, then index), with the frozen ladder as the only scorer.
• Driver fan-out into isolated worktrees off the current baseline tree; winner promoted via the existing baseline/CHECKPOINTED path; all worktrees torn down on every exit path (including throw/timeout). Fakeable: K attempts run through the fake harness with zero real subprocesses.
• Fail-closed coverage: all-K-fail → normal red iteration; a crashing/timeout candidate never wins on merit; drive() never rejects.
• Resume determinism: a test crashes mid-fan-out (some candidates logged, winner not yet selected) and asserts replay reconstructs the same state without re-running completed candidates or double-applying a tree.
• --sandbox composition: each of the K concurrent worker execs is independently jailed via the existing RunExecWrapper/launcher seam; an unavailable launcher refuses to start (fail-closed). --phased composition tested end-to-end.
• New behavior covered by tests
• Docs synced (README.md + docs/index.html) if applicable — new flag in the flags table + how-it-works, the state-machine/loop diagram noting the Driver-side tournament, and the support/composition notes for --phased/--delta-verify/--sandbox. (docs/adding-a-harness.md only if the HarnessAdapter shape changes — it should not.)

Out of scope

• Changing the HarnessAdapter interface — K attempts are K ordinary harness.run() calls; the seam is untouched.
• Cross-candidate "merge the best parts of several diffs" — selection picks one whole winning tree, never synthesizes.
• Parallelizing the verifier/approver LLM steps themselves, or speculative multi-iteration look-ahead.
• A new sandbox mechanism — best-of-N only reuses the existing launcher seam K times.

Open questions

1. Partial ladder scoring without re-authoring the bar. Ladder.verify() short-circuits at the first red and returns a single boolean Verdict, so it can't natively rank "2 of 4 rungs" vs "1 of 4". Options, all of which keep the frozen contract identical: (a) add a Driver-side scoring pass that runs the same frozen rungs without short-circuit purely to compute rung-depth for ranking (the real gating VERIFIED still uses the canonical short-circuit ladder on the winner); (b) rank only by the boolean ladder pass + Sign-off + cost, treating all reds as equal and using cost/index to break ties. (a) is more discriminating but doubles rung execution for losers; (b) is cheaper but blunter. Which is the right default? This must not introduce a second scorer that could disagree with the frozen ladder — both must be derived from the one frozen rung set.
2. Exact write-ahead schema + ordering for resume. Proposed: for each candidate, append a Zod-validated CANDIDATE_RAN { index; tree; run; budget; verdictDigest } marker (a baseline/scoring marker, skipped by step() in replay.ts exactly like CHECKPOINTED) as it completes; then append a CANDIDATE_SELECTED { winner; tree } marker that promotes the winner's tree (re-pointing the baseline, as CHECKPOINTED does on resume); then append the existing AGENT_RAN for the winner — the only event the reducer folds. A crash before CANDIDATE_SELECTED resumes by re-running just the not-yet-logged candidates (completed ones are read back from their markers, never re-run) and re-selecting deterministically; a crash after it but before AGENT_RAN re-points the baseline from the marker and re-emits the single winning AGENT_RAN. Open: is re-running the unfinished candidates on resume acceptable (at-least-once, matching today's "one repeated effect" stance in driver.ts), or should an incomplete fan-out collapse to the best already-logged candidate to re-run nothing at all? The latter is more deterministic but can pick a worse winner than a completed fan-out would have.
3. Stuck-detection wrinkle under ties. With the canonical timeline recording only the winner's diffHash, could a persistent tie that keeps selecting the same loser tree across iterations make no-diff/repeat fire later or earlier than intended? Likely fine (the winner's hash is still a real post-iteration tree), but it needs an explicit table-test before we commit to the tie-break order.
4. Defaults & resource ceiling. What is a sane default cap for K, and should there be a token-budget interaction (best-of-N multiplies per-iteration spend by up to K)? Lean: default 1, document the multiplier, and let the existing --budget-tokens cap govern total spend (it already meters every harness call).
5. Worktree support floor. git worktree needs a real repo with a resolvable HEAD; the current snapshot path tolerates an unborn branch (it diffs the empty tree). Does best-of-N require a committed HEAD, and if so should --candidates > 1 refuse to start (fail-closed) on an unborn-branch repo with a clear message?