BBOWP-Bench: Evaluating LLMs on Black-Box Optimization Word Problems

summary

The gist

Formulating an optimization problem strongly affects the quality of the final solution, yet good formulations usually require substantial expertise The paper introduces Black-Box Optimization Word…

In short

The paper introduces BBOWP, a problem where a system must infer both a search space and an optimization algorithm from a natural language description of an optimization task. It creates BBOWP-Bench to test Large Language Models (LLMs) as meta-solvers. Evaluations show LLMs can select algorithms but struggle with designing good search spaces, highlighting the need for better tools in automated optimization modeling.

Key concepts

BBOWP
A novel problem setting where a system receives a natural language description of a black-box optimization task. The system's job is to figure out the best search space and the most suitable optimization algorithm to minimize an objective function within a given evaluation budget.
BBOWP-Bench
A benchmark suite designed to test LLMs on BBOWP. It pairs natural language problem descriptions with executable objectives and reference formulations, allowing for reproducible assessment of how well an LLM can perform the inference task.
Formulation Ranking Score (FRS)
A metric used to measure the quality of a search space and algorithm pair. It calculates the probability that a randomly drawn configuration from the LLM's suggested pair performs better than another configuration, indicating how effective their combined choice is.
EPDF Analysis
Analyzing the Empirical Probability Density Function (EPDF) of objective function values within a designed search space helps determine if high performance comes from a good algorithm or a well-designed search space. For example, some models create narrow, homogeneous spaces.

Terminology used across episodes

This episode discusses

The paper

BBOWP-Bench: Evaluating LLMs on Black-Box Optimization Word Problems · Read on arXiv

Yutaro Yamada, Kei Hiroshima, Nozomu Yoshinari, Kento Uchida Shinichi Shirakawa

Yokohama National University

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "BBOWP-Bench: Evaluating LLMs on Black-Box Optimization Word Problems".

Jane: Here's the gist of the paper. Formulating an optimization problem strongly affects the quality of the final solution, yet good formulations usually require substantial expertise The paper introduces Black-Box Optimization Word Problems (BBOWP), a novel problem setting in which a system must infer both a search space and an optimization algorithm from a natural-language description of a black-box optimization task This work establishes the BBOWP Benchmark Suite (BBOWP-Bench), which pairs natural-language problem descriptions with design-variable domain definitions, executable evaluation environments, and human-designed reference formulations The benchmark covers 23 instances from four different application domains and supports reproducible assessment through actual black-box optimization runs Problem Formulation and Evaluation Protocol BBOWP is formulated for settings in which the problem description may be written by a non-expert, so the underlying objective function is not assumed to be fully specified beforehand The input for BBOWP is a natural-language problem description d, which includes information such as the problem background, the target performance metric, and the maximum number of function evaluations Nmax The output for BBOWP is a search space S and an optimization algorithm a The quality of the answer (a, s) can be measured by the final solution quality when running algorithm a to minimize the objective function on search space s within given budget Nmax, denoted as (a∗, S∗) = argmina∈A, S∈S E

V(a, S, Nmax): The BBOWP-Bench design approximates an ideal evaluation protocol using a fixed executable objective together with an adapter that maps generated search spaces to the variable space expected by the executable environment Benchmark Design and Data Description The BBOWP-Bench pairs natural-language problem descriptions with pre-built executable objectives and their problem descriptions derived from existing real-world BBO benchmarks The benchmark provides pre-built executable objectives and their problem descriptions derived from existing real-world BBO benchmarks (see Section 4.2) For each instance, the benchmark prepares a JSON record containing canonical variables, their domains, and default values used by the executable environment The task descriptions are prepared in three difficulty levels: Easy, Intermediate, and Hard LLM Performance Analysis The paper evaluates four representative LLMs—Gemini 3 Flash

Google DeepMind, 2025: , Gemini 3.1 Pro

Google DeepMind, 2026: , GPT-5 mini

OpenAI, 2025b: , and GPT-5.2

OpenAI, 2025a: —as meta-solvers The evaluation assesses their ability to select suitable algorithms based on the given evaluation budget Sensitivity to Problem Domains and Difficulties reveals that while models are capable of selecting suitable algorithms for the evaluation budget when provided with detailed problem descriptions, they often struggle with search space design, particularly in identifying important variables and setting appropriate ranges when problem descriptions are less informative Search Space Quality Metrics To evaluate the quality of a pair consisting of a selected algorithm a and a search space S, the paper proposes the Formulation Ranking Score (FRS) metric FRS(a, S) = Pr(a′,S′)∼P(a,S)(y(a, S) ≤ y(a′, S′)) The empirical probability density function (EPDF) of objective function values within the search space designed by the LLMs is analyzed to understand the mechanical causes behind FRS observed in Section 5.4 For instance, Gemini 3.1 Pro exhibits exceptionally high kurtosis, with a sharp and narrow peak strictly concentrated around its median, resulting in highly homogeneous objective function values The empirical evaluations demonstrate that while current LLMs are capable of selecting suitable algorithms, they sometimes struggle with search space design, particularly in identifying important variables and balancing their ranges The paper suggests future work could involve using an additional LLM to map the generated identifier to a pre-defined identifier more appropriately Another possible future direction is generating a new algorithm tailored to given tasks using an agent-based meta-solver The proposed benchmark can support research on automated formulation for blackbox optimization, potentially reducing the expertise required to apply optimization methods The paper also notes that BBOWP-Bench has limitations, such as the removal of generated variables whose identifiers are not included in the alias dictionaries and lack of support for conditional search space information References Ali Ahmaditeshnizi, Wenzhi Gao, and Madeleine Udell.

Tom: OptiMUS: Scalable optimization modeling with (MI)LP solvers and large language models.

Jane: In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp editors Proceedings of the 41st International Conference on Machine Learning volume 235 of Proceedings of Machine Learning Research pages 577–596 PMLR 21–27 Jul 2024 James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl.

Tom: Algorithms for hyper-parameter optimization In NeurIPS 2011 Google DeepMind.

Title and authors: Tom: So, to summarize what they found in BBOWP-Bench, it’s that while current LLMs can pick a suitable optimization algorithm based on the budget and description, their ability to design the search space is still weak when descriptions aren't super detailed.

Jane: The benchmark is designed so you have a natural language problem description, and the output has to be two things: a search space and an algorithm.

Lu: The paper sets up this evaluation protocol by using a fixed executable objective function along with an adapter that translates the generated search spaces into what the real environment expects.

Meng: From my side, I'm thinking about deployment; if I deploy an LLM to formulate problems, I need to know how reliable those formulations are under real operational pressure.

Tom: The paper shows that they have tested four different large language models—Gemini three Flash, Gemini three point one Pro, GPT-five mini, and GPT-five point two—as meta-solvers for this task.

Jane: They showed that sensitivity to the problem domains and the difficulty levels reveals those struggles we talked about earlier regarding variable identification.

Lu: They found that some models, like Gemini three point one Pro, can actually find a desirable region with high-quality solutions by shifting the probability mass of their search space rightward toward a median value of zero point eight two four.

Meng: That sounds promising for finding good areas, but I still have to ask what happens when the problem is really messy and doesn't fit those clean distributions.

Tom: The paper suggests future work could involve using another LLM to map the generated identifier to a pre-defined one in a better way, or maybe using an agent-based meta-solver.

Jane: It points toward moving away from just having one LLM do everything and toward systems that can check their own work or collaborate on the formulation process.

Lu: And they also pointed out some limitations to the benchmark itself, like they removed generated variables whose identifiers weren't in specific dictionaries, which limits its real-world applicability.

The paper's summary: Tom: So the authors suggest a few ways to improve these LLMs for this task. One big suggestion is that we need better meta-solver capability so they can infer more important variables and set ranges more accurately when descriptions are sparse.

Jane: That ties directly into the search space design issue; if the model can figure out *which* variables matter, it makes choosing the ranges much easier to get right.

Lu: They also advocate for refining algorithm selection, showing that models need a way to make a more "rational shift" in behavior based on how much evaluation budget they have available.

Meng: I agree with that; selecting an algorithm should be tied directly to the budget and the expected complexity of the search space, not just a generic choice.

Tom: And they proposed this formulation-level comparison and downstream assessment through actual black-box optimization runs as a way to actually judge if the formulation quality is good.

Jane: So it’s not enough for an LLM to *say* it picked the right thing; we need to see if that choice actually leads to a better solution when you run the objective function.

Lu: They also emphasized using analysis of the empirical probability density function, or EPDF, of objective function values within those search spaces as a way to understand the underlying causes of poor performance.

Meng: That sounds like a necessary step for production because it lets us see if we’re getting good solutions or just randomly picking points in the space.

Tom: The paper is trying to reduce that reliance on human experts who have to be optimization specialists by creating these benchmarks for auto-formulation.

The paper's improvements: Jane: So, wrapping up, the main implication of BBOWP-Bench is that we can see where current LLMs succeed and where they still need more help when it comes to automatically formulating complex black-box optimization problems.

Tom: The paper shows that while LLMs are capable of selecting algorithms based on a budget, their search space design skills are still weak when the problem descriptions lack detail.

Lu: They highlight the gap between simply picking an algorithm and actually designing a meaningful search space that leads to good solutions under those specific evaluation conditions.

Meng: From a deployment standpoint, this means we can’t just hand over a natural language prompt and expect perfect optimization setup; we need more robust formulation tools.

Lalam: I'm fairly certain the direction is toward using additional LLMs to help map the generated identifiers better, or maybe even an agent-based meta-solver that can iterate on the search space design itself.

Tom: It seems like this benchmark pushes us to make AI not just good at finding answers, but good at structuring the question correctly for optimization.

Jane: It’s a step toward reducing the expertise barrier for applying optimization methods in areas like hyperparameter tuning, which is where most of this work is happening.

Lu: Ultimately, BBOWP-Bench provides a framework that can support research into automated formulation while still acknowledging the real limitations of what LLMs can do right now.

Conclusion: Tom: So we just finished looking at BBOWP-Bench, which is this new benchmark for testing how well large language models can figure out optimization problems just from a natural language description.

Jane: Right, so the main idea is that these models have to do two things: figure out the right search space and pick the best optimization algorithm from just words.

Lu: The benchmark pairs those natural language descriptions with real executable evaluation environments and even has human-designed reference formulations to see how good the LLM’s choices are.

Meng: It's interesting because it tests if the model can actually make a rational choice, not just guess randomly about what variables matter.

Lalam: My analysis shows that while models can pick an algorithm, they often struggle with designing the search space itself, especially when the problem description isn't super detailed.

Tom: That’s what we saw too; sensitivity to different problem domains showed that if the description is vague, they get messy when it comes to setting up those variable ranges.

Jane: They proposed a metric called Formulation Ranking Score or FRS to actually rank the quality of the pair of an algorithm and a search space.

Lu: The paper shows that some models, like Gemini three point one Pro, can find high-quality solutions by shifting the probability mass in their search space toward a median value around zero point eight two four.

Meng: That’s good data on where they are succeeding in terms of finding promising regions within the search space.

Tom: But we need to remember that this is still just an evaluation protocol, so it tells us what's possible with current LLM generation techniques under these constraints.

Jane: It shows that while models can select algorithms, they aren't always great at the deep mechanics of search space design when the prompt isn't perfect.

Lu: The authors suggest future work should look at using another LLM to map those generated identifiers to more specific ones or maybe an agent-based meta-solver.

Meng: If we’re thinking about deployment, we need that kind of refinement so we aren't shipping models that just pick algorithms blindly without a solid reason.

Lalam: I'm pretty confident in the direction they are pointing; it seems like moving toward more structured ways for the AI to reason about variable importance is the next logical step.

Tom: So, BBOWP-Bench gives us a concrete way to measure if these models can move beyond just selecting an algorithm and actually designing a good search space.

Jane: It’s a solid piece of work because it forces us to look at the whole process—from the natural language description all the way to how well that translates into actual optimization results.

Lu: This benchmark supports research into automated formulation, which could really help lower the expertise needed for applying optimization methods in black-box settings.

Meng: It’s a good tool, but we still need to see if these kinds of formulations hold up when we run them on real traffic or complex system data at scale.

Lalam: I think this paper really highlights that the next frontier isn't just better language understanding, but better structure for optimization itself.

More episodes

← Home