Technical Summary: BayesEvolve

Problem Statement

Autonomous scientific discovery systems increasingly leverage Large Language Models (LLMs) to generate and select hypotheses. However, current paradigms, such as those seen in FunSearch and AlphaEvolve, primarily condition LLM proposals on experimental memory. This memory typically consists of archives of high-scoring candidates or heuristic summaries of recent trials.

The authors argue that this archive-guided approach leaves evidence in an implicit form. While a list of past experiments indicates "what happened," it fails to explicitly encode:

1. What the agent currently believes about unevaluated hypotheses.
2. The uncertainty associated with those beliefs.
3. Which experiment would be most informative next.

This limitation leads to two primary costs: the agent cannot reason about predicted quality beyond the observed archive, and it risks either over-concentrating on early elite candidates or continuing unfocused exploration without converting evidence into a directed search strategy.

Methodology: BayesEvolve

The paper introduces BayesEvolve, a framework that reframes autonomous discovery as belief-state evolution. Instead of treating past evaluations as unstructured memory, BayesEvolve maintains an explicit, uncertainty-aware predictive belief state over candidate quality.

Core Components

1. Explicit Belief State:
   At each step $t$, the system maintains a posterior belief $P(y | h, D_t)$ over the objective value $y$ for a hypothesis $h$, given the evaluation history $D_t$. In the experiments, this is implemented as a Gaussian Process (GP) posterior:
   $$P(y | h, D_t) = \mathcal{N}(\mu_t(h), \sigma^2_t(h))$$
   where $\mu_t(h)$ is the predicted objective and $\sigma_t(h)$ is the posterior uncertainty. The framework is noted to be agnostic to the specific surrogate model or candidate representation.

2. Belief-Guided Selection:
   To select the next candidate from a pool $C_t$, BayesEvolve uses an uncertainty-aware score. Since the goal is minimization, the selection rule combines the predicted mean and the uncertainty:
   $$a_t(h) = -\mu_t(h) + \beta_t \sigma_t(h)$$
   Crucially, the uncertainty coefficient $\beta_t$ is annealed (decaying) over time:
   $$\beta_t = \beta_0 \frac{n_0}{t}$$
   where $n_0$ is the number of shared initialization evaluations. This design encourages broad exploration early in the process and shifts toward exploitation of the belief mean as evidence accumulates.

3. Workflow:
   The system initializes with $n_0$ random evaluations. In each subsequent step, it fits/updates the belief state, constructs a candidate pool (from LLM proposals and/or archive mutations), computes the acquisition score for all candidates, selects the best one, evaluates it, and updates the history.

Key Contributions

The paper outlines four primary contributions:

• Formulation: It reframes LLM-guided discovery as explicit belief-state maintenance rather than relying solely on archive memory.
• Algorithm: It introduces a belief-guided selection rule featuring an annealed uncertainty bonus that dynamically shifts the balance from exploration to exploitation.
• Evaluation: It evaluates BayesEvolve on shifted BBOB-style black-box optimization tasks, demonstrating superior performance compared to archive- and memory-guided LLM baselines.
• Analysis: It provides evidence that the belief state is predictive on held-out candidates and that the system exhibits productive late-stage concentration rather than unfocused exploration.

Experimental Results

The evaluation was conducted on five shifted BBOB-style minimization functions (Sphere, Ellipsoid, Rastrigin, Rosenbrock, Ackley) in dimension $d=5$. The setup used a fixed budget of $T=100$ evaluations and compared BayesEvolve against Random-LLM, Archive-LLM, Memory-LLM, and a non-LLM GP-BO baseline.

• Performance: BayesEvolve achieved the best mean normalized objective throughout the budget and the best final performance at 100 evaluations (0.195 vs. 0.229 for GP-BO and 0.473 for Archive-LLM). The gains were most significant relative to memory-guided LLM baselines.
• Belief Quality: The posterior mean was strongly rank-correlated with realized objective values (Spearman $\rho = 0.774$). However, the belief state was not perfectly calibrated, with empirical coverage of 0.433 for one-sigma intervals.
• Ablation Studies:
  • Mean-only selection already substantially improved over archive search, indicating that the predictive mean is the primary driver of performance.
  • Annealed Uncertainty: Adding the decaying uncertainty bonus yielded the best final score, confirming that uncertainty is most useful when exploration is gradually reduced.
  • Diversity: Unlike Random-LLM or GP-BO which maintained high diversity throughout, BayesEvolve reduced diversity in the late stage while achieving the lowest objective. This suggests "productive concentration" rather than unproductive archive collapse.

Significance and Claims

The paper claims that explicit belief-state evolution is a useful principle for autonomous scientific discovery. The results support three specific claims:

1. Explicit belief states improve sample efficiency relative to archive and heuristic-memory baselines.
2. The learned belief state serves as a predictive tool for held-out candidates, rather than merely acting as a prompt artifact.
3. Decision rules matter: while the posterior mean drives most gains, an annealed uncertainty bonus optimizes the transition from exploration to exploitation.

Limitations and Scope:
The authors explicitly note that the current work is a controlled testbed using shifted BBOB-style numerical optimization. It does not yet cover full program generation or laboratory discovery domains. Additionally, the GP belief state, while predictive, is imperfectly calibrated, and its scaling limitations suggest a need for sparse or neural surrogates in future work with larger evaluation budgets. The diversity analysis indicates a focus on "productive concentration," suggesting future work should explore richer notions of semantic and structural diversity for complex hypothesis spaces.