Improving LLM-based Global Optimization with Search Space Partitioning

Andrej Schwanke, Lyubomir Ivanov, David Salinas, Fabio Ferreira, Aaron Klein, Frank Hutter & Arber Zela · 2025

Read Improving LLM-based Global Optimization with Search Space Partitioning by Andrej Schwanke, Lyubomir Ivanov, David Salinas, Fabio Ferreira, Aaron Klein, Frank Hutter & Arber Zela (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21372.txt.

Introduction

Andrej Schwanke and co-authors improve language-model-driven global optimization by splitting the search space into parts in a 2025 paper. Large language models have recently emerged as effective surrogate models and candidate generators for optimizing expensive black-box functions. Despite promising results, they often struggle in high-dimensional search spaces or when domain-specific knowledge is missing, leading to sparse or uninformative suggestions.

Their algorithm, called HOLLM, partitions the search space into promising subregions before sampling new candidates. Focused local search inside good regions gives the model easier problems to solve one at a time. The method aims to keep the flexibility of language models while curing their weakest point, wandering unproductively in vast spaces.

Catalog record

CREATORAndrej Schwanke, Lyubomir Ivanov, David Salinas, Fabio Ferreira, Aaron Klein, Frank Hutter & Arber Zela
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-21372

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improving LLM-based Global Optimization with Search Space Partitioning Andrej Schwanke, Lyubomir Ivanov, David Salinas, Fabio Ferreira, Aaron Klein, Frank Hutter & Arber Zela Abstract Large Language Models (LLMs) have recently emerged as effective surrogate models and candidate generators within global optimization frameworks for expensive blackbox functions. Despite promising results, LLM-based methods often struggle in high-dimensional search spaces or when lacking domain-specific priors, leading to sparse or uninformative suggestions. To overcome these limitations, we propose HOLLM , a novel global optimization algorithm that enhances LLM-driven sampling by partitioning the search space into promising subregions. Each subregion acts as a “meta-arm” selected via a bandit-inspired scoring mechanism that effectively balances exploration and exploitation. Within each selected subregion, an LLM then proposes high-quality candidate points, without any explicit domain knowledge. Empirical evaluation on standard optimization benchmarks shows that HOLLM consistently matches or surpasses leading global optimization methods, while substantially outperforming global LLM-based sampling strategies. 1 Introduction and Motivation Global optimization ( Jones et al., 1998 ; Rios and Sahinidis, 2013 ) (also known as gradient-free or zeroth-order optimization) of blackbox functions, where the only information provided to the optimizer is the function value, is a fundamental challenge across numerous domains including hyperparameter tuning ( Snoek et al., 2012 ; Turner et al., 2021 ) , policy search ( Calandra et al., 2016 ) , molecular design and chemical engineering ( Langer and Tirrell, 2004 ; Hernández-Lobato et al., 2017 ) , just to name a few. Methods such as Bayesian optimization ( Shahriari et al., 2016 ; Garnett, 2023 ) and evolutionary algorithms ( Hansen, 2016 ) have been a standard and effective choice across various applications. However, they typically require assumptions regarding the underlying objective function’s nature, which consecutively affect algorithmic design choices. At the same time, recent advances in Large Language Models (LLMs) have demonstrated remarkable capabilities in generative modelling and reasoning ( Brown et al., 2020 ; OpenAI, 2023 ; Touvron and others, 2023 ) , suggesting their potential usage for optimization tasks as well ( Song et al., 2024 ) . Efforts in integrating LLMs within blackbox optimization algorithms as surrogate models or as candidate samplers have already shown encouraging results ( Yang et al., 2024 ; Liu et al., 2024 ; Zhang et al., 2023 ; Aglietti et al., 2025 ; Agarwal et al., 2025 ; Kristiadi et al., 2024 ) . Yet these methods typically rely on carefully engineered, domain - specific prompts, and in higher dimensions and complex search spaces the LLM’s suggestions tend to scatter sparsely, covering only a fraction of the domain ( Krishnamurthy et al., 2024 ) . As a motivating example, we investigated the capabilities of LLMs to simulate uniform sampling from a unit hypercube. In Figure 1(a) we show 80 samples drawn from the unit square [0,1]^{2} , comparing uniform sampling (blue) with Gemini-1.5’s ( Reid and others, 2024 ) attempt at simulating uniform sampling using the prompt provided in Listing 1 in Appendix I (green points), and Gemini-1.5 performing uniform sampling with 5 samples per smaller subregion, using the same prompt (red points). We can clearly notice that even in 2D the LLM demonstrates high bias when sampling, therefore failing to appropriately fill the space as it was tasked to, whilst partitioning the space and prompting the LLM 16 times yields a more faithful simulation. Another illustrative example is shown in Figure 1(b) , where we prompt Gemini-1.5 (using the prompt shown in 2 ) to sample close to the two global minima (red stars) of a quadratic function, given the input space boundaries. We can clearly notice the higher sampling bias when the input space is [0,1]^{2} instead of the smaller regions denoted via the dashed bounding boxes. Finally, in Figure 1(c) , we compute the Hausdorff distance, d_{H}(\mathcal{P},[0,1]^{8}) , between the set of N\in\{10,20,50,70,100\} sampled points \mathcal{P} and the 8-dimensional unit hypercube [0,1]^{8} . The blue curve indicates the values for standard uniform sampling and the other ones performed by various non-agentic LLMs. Similarly as in the 2D case, partitioning the hypercube into 32 regions and sampling within each (Gemini 1.5 + partitioning) notably improves the spatial coverage, enabling the LLM to more closely approximate uniform sampling. (a) (b) (c) Figure 1: ( a ) 80 samples in [0,1]^{2} : Gemini-1.5 simulating uniform sampling (green), and with region-wise partitioning (red) using the prompt in Listing 1 . ( b ) Gemini-1.5 prompted (see Listing 2 ) to generate 80 samples around the 2 minima (red crosses) globally (triangles) and withing the two bounding boxes (circles). ( c ) Hausdorff distance d_{H}(\mathcal{P},[0,1]^{8}) for uniform vs. LLM-simulated sampling in the 8-D hypercube. In this paper, we introduce Hierarchical Optimization with Large Language Models ( HOLLM ) , a novel blackbox optimization method that leverages adaptive spatial partitioning to guide LLM-based sampling. HOLLM iteratively builds a KD-tree on existing evaluation data, creating adaptive local partitions whose granularity evolves with sampling density. Each subregion is assigned a bandit-inspired utility score, balancing exploitation (regions with promising observed values) and exploration (geometrically large or statistically uncertain regions). Subregions are selected stochastically according to these scores, and LLMs then generate localized candidate proposals within the chosen regions. As LLMs trained on optimization literature and scientific data encode a valuable meta-prior about typical function behavior (e.g., local unimodality), we effectively harness this prior without assuming a fixed parametric surrogate (e.g., Gaussian Process). Furthermore, restricting candidate generation to smaller, lower-dimensional subregions significantly reduces LLM sampling difficulty compared to global high-dimensional sampling. We note that spatial partitioning heuristics have already proven effective in continuum-armed bandits ( Munos, 2011 ; Bubeck et al., 2011 ; Valko et al., 2013 ; Grill et al., 2015 ) , Trust Region Bayesian optimization ( Eriksson et al., 2019 ; Daulton et al., 2022 ) , and Monte Carlo Tree Search ( Kim et al., 2020 ; Wang et al., 2020 ; Yang et al., 2021 ) . The key contribution of this work is the integration of these partitioning ideas to substantially improve LLM-driven global optimization performance. Empirical evaluations on continuous and discrete benchmark functions, including hyperparameter optimization and real world tasks, demonstrate that HOLLM effectively balances exploration and exploitation, matching or outperforming state-of-the-art methods, including established Bayesian optimization variants and Trust Region algorithms, particularly in scenarios requiring efficient navigation of complex landscapes. Furthermore, compared to approaches that prompt the LLM to propose candidates globally, HOLLM achieves considerable gains by focusing LLM suggestions locally. We provide the implementation of our algorithm in the following repository: https://github.com/arberzela/mohollm.git . 2 Background and Related Work We consider the problem of maximizing a blackbox function f:\mathcal{X}\rightarrow\mathbb{R} where \mathcal{X} is a compact domain. The objective is to find x^{*}=\argmax_{x\in\mathcal{X}}f(x) through a sequence of function evaluations. In this blackbox setting, we do not have access to gradients or other properties of f , and can only observe function values at queried points. The performance of optimization algorithms in this context can also be measured using simple regret or cumulative regret . For a sequence of evaluated points x_{1},x_{2},\ldots,x_{t} , the simple regret after t iterations is defined as: r_{t}=f(x^{*})-\max_{i\in\{1,\ldots,t\}}f(x_{i}) , while the cumulative regret is: R_{t}=\sum_{i=1}^{t}(f(x^{*})-f(x_{i})) . Bayesian Optimization. Bayesian Optimization (BO) ( Garnett, 2023 ; Frazier, 2018

Read the complete text