Program Synthesis Search Tree

Search Setup

Beam width 4

DSL branching factor 3

Search depth 6

Spec strictness 0.80

Result

Status

–

Depth reached

–

Candidates explored

–

Nodes pruned

–

Best test score

–

Verifier calls

–

How it works

Each node in the tree is a partial program built from a small domain-specific grammar. At every depth the search expands every surviving candidate into branching factor children — one per production rule — and a verifier runs the DSL's test suite against each new candidate, returning a pass fraction. Only the top beam width candidates by score survive to the next depth; everyone else is pruned (shown dim, falling away). This is exactly the beam-search-plus-verifier loop DSL-based synthesis uses to keep the search space small enough for an LLM to explore.

score(node) = verifier.testsPassed(node) / totalTests
survivors  = topK(children, beamWidth, by: score)
solved     = any(score >= strictness)

Beam width — how many candidates stay alive each round; wider beams explore more of the grammar but cost more verifier calls.
Branching factor — grammar productions available at each node; a bigger DSL means more expressive programs but a much larger search space.
Spec strictness — the pass-fraction a candidate needs to count as a verified solution; stricter specs reject more near-misses.
Repair loop — when on, a failed candidate's counterexample nudges its children's scores upward, modelling how feeding a failing test back into the LLM helps it converge faster than blind resampling.

Real-world relevance: this is the inner loop of LLM-based program synthesis over a DSL — the same shape used for spreadsheet formula synthesis, ETL pipeline generation and SQL-from-text tools, where a small, well-typed language plus an executable spec makes automatic search tractable.

Verified (passes spec) Kept in beam Pruned this round Never expanded

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.