Top-K
Always expand the single best program, with the next K as context. Pure greedy elitism.
# Top-K (`topk`)
> Always expand the single best program, with the next K as context. Pure greedy elitism.
## Overview
Top-K is the simplest SkyDiscover search strategy: at every step it selects the single best program as the parent and the next K programs (ranks 2 through K+1) as inspirations, drawn from an uncapped keep-all archive sorted by combined score. There is no topology, no migration, and no adaptive selection — just deterministic greedy elitism applied to the full history of everything ever generated.
The method is a faithful port of SkyDiscover's `TopKDatabase` (UC Berkeley Sky Computing Lab). In Galapagos it decomposes into an `InMemoryPopulation` acting as the flat fitness-sorted leaderboard plus a fixed-rule `TopKPolicy` that does the rank-1-parent / rank-2-to-K+1-context selection. The reference store enforces no population cap, so Top-K effectively keeps all candidates and re-ranks them on every selection.
Because the selection rule is fixed and stateless, Top-K is a reliable, reproducible baseline. It is the natural first thing to run when you want to sanity-check a new task or evaluator before committing budget to an adaptive search strategy, and it makes a clean reference point for measuring whether more elaborate selection actually helps.
## Algorithm
Each iteration the scaffold re-ranks the keep-all population by combined score, takes the top program as the parent and the following K as read-only context, asks the proposer for a SEARCH/REPLACE diff against the parent, evaluates the child, and admits it back into the archive. The selection policy holds no state, so nothing is updated between iterations beyond the population itself — the only thing that changes the next parent is whether a newly admitted child outscores the incumbent best.
The distinctive mechanism is the fixed `num_inspirations + 1` slice: rank 1 is always the parent and ranks 2..K+1 are always the inspirations. On the lone-seed first step the seed is used as its own single inspiration (matching SkyDiscover), so the inspiration set is never empty.
```
seed -> evaluate -> population.add(seed)
repeat until max_iterations:
top = population.query(top = K + 1) # fitness-sorted slice
parent = top[0] # rank 1 (the single best)
inspiration = top[1 : K+1] or [parent] # ranks 2..K+1 (the seed itself on the lone-seed step)
prompt = build(parent, inspiration, memory) # task -> metrics -> feedback -> inspirations -> current
child = propose(parent, prompt) # one LLM call -> diff or full rewrite
score = evaluate(child) # task-supplied evaluator (retried up to inner_retry_times)
population.add(child) # keep-all; re-ranked next iteration
```
## Components
A Galapagos scaffold composes six components. Top-K wires up the SkyDiscover defaults: a keep-all leaderboard, the fixed greedy selection rule, the canonical multi-section prompt, and the diff proposer, with no memory.
| Slot | Implementation | Role |
|---|---|---|
| Population | `TopKPopulation` (InMemoryPopulation, keep-all) | Uncapped fitness-sorted leaderboard over the full history. |
| SelectionPolicy | `TopKPolicy` (topk_greedy) | Parent = rank 1, inspirations = ranks 2..K+1; stateless. |
| PromptBuilder | `TopKPromptBuilder` (DefaultPromptBuilder) | Canonical task → metrics → feedback → inspirations → current template. |
| Proposer | `TopKProposer` (DiffProposer) | One LLM call → SEARCH/REPLACE diff or full-rewrite fallback, with no-op detection. |
| Evaluator | task-supplied | Scores each child; provides the combined score used for ranking. |
| Memory | `TopKMemory` (NullMemory, none) | None — Top-K keeps no cross-candidate free-form knowledge. |
## Configuration
- `general.max_iterations` (100) — number of select → propose → evaluate → admit steps.
- `population.capacity` (null) — uncapped keep-all by default, matching the SkyDiscover reference (which enforces no population cap); set an int to bound the archive.
- `selection_policy.num_inspirations` (4) — K, the number of context programs (ranks 2..K+1) shown alongside the rank-1 parent.
- `seed` (0) — RNG seed passed to the policy for reproducibility.
- `general.inner_retry_times` (1) — attempts per iteration when a proposal fails to parse or evaluate (1 = a single attempt).
## When to use
Reach for Top-K when you want a deterministic, no-knobs baseline: it always pushes hardest on the current best, so it converges fast and is easy to reason about, but it has no mechanism to escape a local optimum once the leaderboard stabilizes. Use it to validate a task and evaluator end-to-end before spending budget on adaptive search. When you need exploration or sustained diversity, prefer a sibling such as `adaevolve` (UCB/G-signal adaptive tiers) or `evox` (island topology + strategy co-evolution); when you instead want fixed independent sampling rather than greedy refinement, look at `best_of_n`.
## Source
Ported from SkyDiscover's `topk` search strategy (`TopKDatabase`, UC Berkeley Sky Computing Lab); this is a SkyDiscover port realized as a Galapagos scaffold.
**Fidelity to SkyDiscover.** Behavior matches `TopKDatabase.sample` exactly — parent = rank 1, context = ranks 2..K+1, uncapped keep-all leaderboard, deterministic greedy elitism, K (`num_inspirations`) = 4 — including the lone-seed first step, where Galapagos (like SkyDiscover) uses the single seed program as its own context (`inspirations=[parent]`).