Maintain a fixed-width beam of promising programs; expand one per step, prune by fitness+diversity.
Beam Search keeps a fixed-width beam of the most promising programs. Every admitted program joins the beam, and whenever the beam grows past its width it is pruned back to `beam_width` by fitness — optionally diversity-aware, so the beam does not collapse onto a single lineage. Each step one parent is drawn from the beam by one of four strategies (best, stochastic, round_robin, or diversity_weighted), and the program is expanded into a single child; inspirations passed as context are the global top programs.
This scaffold is a faithful port of SkyDiscover's `BeamSearchDatabase` (UC Berkeley Sky Computing Lab). In Galapagos its two beam-specific axes map cleanly onto two components: the beam structure, diversity-aware admission, and search-tree depth tracking live in a `BeamPopulation`, while the parent choice lives in a `BeamSelectionPolicy`. Both share one fitness notion — `combined_score` with an optional exponential depth penalty — and one cheap, embedding-free diversity metric (character n-gram Jaccard distance between programs), keeping pruning and selection mutually consistent.
The result is a search that is greedier than a flat population sampler but cheaper and more parallel-friendly than a full evolutionary loop. A keep-all store underneath the beam means every program is retained, so inspirations can always be sourced from the global best even after a candidate has been pruned out of the active beam.
The six components this scaffold snaps together. Each block names its concrete implementation.
The set of candidate solutions in play — the gene pool the search evolves over.
Decides which genomes survive and reproduce — tournament, elitism, novelty, or your own policy.
Assembles the context handed to the model — parents, feedback, instructions, examples.
The LLM-driven variation operator — proposes new candidates by mutation and crossover.
Scores each candidate against the task — the fitness signal that drives selection.
SkyDiscover (UC Berkeley Sky Computing Lab) — beam_search search strategy
galapagos run --scaffold beam_search --task circle_packing \
--proposer.model_name openai/gpt-4o-mini \
--proposer.api_base openrouter