Program synthesis searches a domain-specific language's grammar for a program that satisfies a specification. A verifier scores every candidate against tests and type constraints; beam search keeps only the top-k at each generation so the search space stays tractable.
beam(g+1) = top_k( { expand(c, branch) : c in beam(g) }, k = beam_width )
score(c) = verify(c, spec) // tests passed, types check
- Beam width — how many surviving candidates (green nodes) are carried into the next generation.
- Branch factor — how many child programs the DSL grammar can expand each survivor into.
- DSL constraint tightness — a tighter grammar shrinks the search space and biases the verifier's scores upward.
- Search speed — how quickly generations advance.
This mirrors how tools like sketch-based synthesizers and LLM-guided program search prune an exponential space of candidate programs down to a handful of verified solutions.