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

arXiv:2608.02612 · cs.CL, cs.LG, cs.NE · Submitted 2026-05-20 · Read on arXiv

Listen

Radio episode about this paper

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.

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

Yokohama National University

cs.CL, cs.LG, cs.NE

Submitted: 2026-05-20

Updated: 2026-11-13

Comments: Accepted to NeurIPS 2026 (Evaluations & Datasets Track)

Code: https://github.com/shiralab/bbowp-bench

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 77/100

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…

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

Summary

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. p. 52 [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. p. 71 Pro exhibits exceptionally high kurtosis, with a sharp and narrow peak strictly concentrated around its median, resulting in highly homogeneous objective function values

Conclusion and Future Directions

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. OptiMUS: Scalable optimization modeling with (MI)LP solvers and large language models. p. 9 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. p. 9 Algorithms for hyper-parameter optimization In NeurIPS 2011 Google DeepMind. p. 9 Gemini 3 Flash Model Card https://deepmind. p. 9google/models/model-cards/gemini-3-flash/, December 2025 Google DeepMind. p. 9 Gemini 3.1 Pro Model Card https://deepmind. p. 9google/models/model-cards/gemini-3-1-pro/, February 2026 Ryoki Hamano, Shota Saito, Masahiro Nomura, and Shinichi Shirakawa CMA-ES with margin lower bounding marginal probability for mixed integer black box optimization In Proceedings of the Genetic and Evolutionary Computation Conference pages 639–647 2022 Ryoki Hamano, Shota Saito, Masahiro Nomura, Kento Uchida, and Shinichi Shirakawa CatCMA: Stochastic optimization for continuous integer and categorical variables In Proceedings of the Genetic and Evolutionary Computation Conference GECCO ’24 page 656–664 New York NY USA 2024 N. p. 9 Hansen, A. Auger, R. Ros, O. Mersmann, T. p. 9 Tušar, and D. p. 9 Brockhoff COCO: A platform for comparing continuous optimizers in a black-box setting Optimization Methods and Software 36:114–144 2021 doi: https://doi. p. 9org/10.1080/10556788. p. 92020.1808977 Nikolaus Hansen and Andreas Ostermeier Adapting arbitrary normal mutation distributions in evolution strategies The covariance matrix adaptation In Proceedings of the IEEE International Conference on Evolutionary Computation pages 312–317 IEEE 1996 Florian Häse, Matteo Aldeghi, Riley J. p. 9 Hickman, Loïc M. p. 9 Roch, Melodie Christensen, Elena Liles, Jason E. p. 9 Hein, and Alán Aspuru-Guzik Olympus: a benchmarking framework for noisy optimization and experiment planning Machine Learning: Science and Technology 2(3):035021 July 2021 ISSN 2632-2153 doi: 10. p. 91088/2632-2153/abedc8 Riley Hickman, Priyansh Parakh, Austin Cheng, Qianxiang Ai, Joshua Schrier, Matteo Aldeghi, and Alán Aspuru-Guzik Olympus enhanced: benchmarking mixed parameter and multi objective optimization in chemistry and materials science May 2023 Chenyu Huang, Zhengyang Tang, Shixi Hu, Ruoqing Jiang, Xin Zheng, Dongdong Ge, Benyou Wang, and Zizhuo Wang ORLM: A customizable framework in training large models for automated optimization modeling Operations Research 2025a Xuhan Huang, Qingning Shen, Yan Hu, Anningzhe Gao, and Benyou Wang LLMs for mathematical modeling Towards bridging the gap between natural and mathematical languages In Luis Chiruzzo, Alan Ritter, and Lu Wang editors Findings of the Association for Computational Linguistics NAACL 2025 pages 2678–2710 Albuquerque New Mexico April 2025b Association for Computational Linguistics ISBN 979-8-89176-195-7 doi: 10. p. 918653/v1/2025. p. 9findings-naacl Yoshihiko Ozaki, Shuhei Watanabe, and Toshihiko Yanase OptunaHub A platform for black box optimization 2026 URL https://arxiv.org/abs/2510.02798 Florian Pfisterer, Lennart Schneider, Julia Moosbauer, Martin Binder, and Bernd Bischl YAHPO Gym - an efficient multi-objective multi fidelity benchmark for hyperparameter optimization In Isabelle Guyon Marius Lindauer Mihaela van der Schaar Frank Hutter Roman Garnett editors Proceedings of the First International Conference on Automated Machine Learning volume 188 of Proceedings of Machine Learning Research pages 3/1–39 PMLR 25–27 Jul 2022 URL https://proceedings. p. 9mlr.press/v188/pfisterer22a.html Rindra Ramamonjison, Haley Li, Timothy Yu, Shiqi He, Vishnu Rengan, Amin Banitalebi-dehkordi, Zirui Zhou, and Yong Zhang Augmenting operations research with auto formulation of optimization models from problem descriptions In Yunyao Li and Angeliki Lazaridou editors Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing Industry Track pages 29–62 Abu Dhabi UAE December 2022a Association for Computational Linguistics doi: 10.18653/v1/2022. p. 9emnlp-industry.4 URL https://aclanthology. p. 9org/aclanthology.org/page 3> Rindranirina Ramamonjison, Timothy Yu, Raymond Li, Haley Li, Giuseppe Carenini, Bissan Ghaddar, Shiqi He, Mahdi Mostajabdaveh, Amin Banitalebi-Dehkordi, Zirui Zhou and Yong Zhang NL4Opt competition: Formulating optimization problems based on their natural language descriptions In Marco Ciccone Gustavo Stolovitzky and Jacob Albrecht editors Proceedings of the NeurIPS 2022 Competitions Track volume 220 of Proceedings of Machine Learning Research pages 189–203 PMLR 28 Nov–09 Dec 2022b NL4Opt competition: Formulating optimization problems based on their natural language descriptions In Marco Ciccone Gustavo Stolovitzky and Jacob Albrecht editors Proceedings of the NeurIPS 2022 Competitions Track volume 220 of Proceedings of Machine Learning Research pages 189–203 PMLR 28 Nov–09 Dec 2022b

How the training signal is built

The system prompt instructs the LLM to generate a JSON content that defines all of the following items based on the description: search space and the best choice of an optimization algorithm The policy directs the LLM to flexibly control search space size by reducing dimensionality, adjusting numerical parameter ranges, or reducing categorical choices The LLM is instructed to choose the optimization algorithm that is most suitable for the defined search space and given budget The output format requires reasons for search space design and algorithm choice in specific aspects

Where the gains come from

The results show 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 Formulation Ranking Score (FRS) metric quantifies the quality of a configuration (a, S) relative to those distributed according to P(a,S) Analysis of EPDFs reveals that GPT-5 mini successfully covers a desirable region with high-quality solutions by shifting the bulk of the probability mass rightward to a median of 0.824 However, Gemini 3. p. 8

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Meta-solver capability improvement: LLMs can be improved to better infer important variables and set appropriate ranges in search space design, particularly when problem descriptions are less informative or the search space is highly problem-specific.

  2. Algorithm selection refinement: The system should be enhanced to select optimization algorithms that are more suitable for the defined search space and given budget, demonstrating a highly rational shift in model behavior against the evaluation budget as observed in the paper.

  3. Search space quality assessment: Implement a mechanism to disentangle whether high performance stems from a robust optimization algorithm or a well-designed search space by analyzing the empirical probability density function of objective function values within the designed search space.

Sources

Related papers