Open-Ended Discovery

concept
discoveryoptimizationiterative-searchresearch

Open-ended discovery is a class of problems where the objective is clear but the optimal solution is unknown. One-shot generation is insufficient; strong solutions must be discovered through iterative proposal, testing, revision, and progress over time.

Characteristics

  • A well-defined evaluator exists — you can score any candidate
  • No ground-truth answer is known — you cannot verify optimality
  • The search space is vast and poorly understood — promising directions must be discovered empirically
  • Progress requires sustained effort — knowledge accumulates across attempts

Examples: best heuristic for a logistics problem, most efficient GPU kernel, tightest circle packing, optimal polyomino arrangement.

Formal structure

A task is specified by a description x and an evaluator E. Evaluating candidate y returns a score s and feedback f. Each improvement step consists of four stages: retrieve (construct working context from memory), propose (generate candidate), evaluate (score it), update (incorporate findings into memory) (source).

The key question is who controls these stages. In fixed evolutionary search, external algorithms govern all four. In autonomous evolution, agents control timing and realization. This distinction determines how effectively the search adapts to the problem’s structure.

LLM-based approaches

The dominant paradigm embeds LLMs in evaluator-guided evolutionary loops:

  • Fixed evolutionary search: FunSearch (Romera-Paredes et al., 2024), AlphaEvolve (Novikov et al., 2025), OpenEvolve, ShinkaEvolve, EvoX — LLM proposes mutations, external algorithm manages selection and population
  • Autonomous evolution: CORAL (Qu et al., 2026) — agents control the full search process, accumulating knowledge through shared persistent memory

CORAL’s results suggest autonomous approaches outperform fixed search on this problem class, achieving 3-10x higher improvement rates with far fewer evaluations.

Evaluator limitations

A key open question: many real open-ended problems have incomplete, ambiguous, or missing evaluators. CORAL assumes a well-specified evaluator. When evaluation itself is uncertain, it may need to co-evolve with solutions — through iterative refinement, learned critics, or human-agent negotiation over what constitutes progress.