Generate-and-Select: A Simple Framework for Bayesian Optimization with LLM Proposals

Optimization over structured discrete domains is difficult because the set of possi- ble candidates is vast and often dominated by invalid or low-quality inputs. Large language models (LLMs) have emerged as capable generators of plausible, high- quality candidates in such domains, but generation alone does not determine how to allocate scarce evaluations. Bayesian optimization (BO) provides a princi- pled mechanism for this allocation. Existing BO–LLM hybrids, however, often tightly couple generation and optimization, which can both obscure their individual contributions and degrade performance. To address this limitation, we propose generate-and-select (GaS), a modular iterative approach in which, at each step, a black-box LLM adds proposals to a cumulative candidate pool, a standard ac- quisition rule selects candidates from this pool for evaluation, and the resulting observations inform the next step. A regret decomposition into support, discovery, and selection terms exposes the central tradeoff: restricting selection to generator- reachable candidates can reduce selection complexity but may exclude strong candidates or delay their discovery. Across four tasks, GaS matches or outperforms prompt-based LLM optimizers and a coupled BO–LLM baseline, establishing a strong, interpretable baseline.