Each node is a partial "program" — a short sequence of DSL tokens. A deterministic verifier assigns every (parent, next-token) edge a fixed score derived from a seeded hash, so re-running the same seed always reproduces the same scored tree — this stands in for a real synthesis verifier scoring how well a candidate token continues to satisfy a hidden spec.
beam[0] = { "" : score 0 }
for depth d = 1..N:
children = { parent+token : parent.score + edge(parent,token)
for parent in beam[d-1], token in vocabulary }
beam[d] = top-k children by score // the rest are PRUNED
greedy = beam search run with k = 1
Because pruning only keeps the top-k candidates at each level, a token that looks locally weak can still be sitting on the path to the true best full-length program — greedy (k=1) commits early and cannot recover if its single choice was wrong, while a wider beam keeps enough alternatives alive to find it. A brute-force search over every possible token sequence (small enough here to enumerate exactly) gives the true optimum to check both against.
- Left pane — the beam-search tree, generation by generation. Filled circles are kept in the beam; faded circles were generated, scored, and pruned.
- Top-right pane — the same tree explored with beam width forced to 1 (pure greedy), for direct comparison.
- Bottom-right pane — best score in beam vs. greedy vs. the brute-force optimum, level by level.
- On every reseed, the search re-tries hash seeds until it finds one where greedy provably lands in a local optimum (below brute-force) — so the gap you see is a real, checked property of that tree, not a coincidence.