🤖 machine learning

BoLT: A Benchmark to Democratize Black-box Optimization Research for Expensive LLM Tasks

This paper introduces BoLT, the first benchmark that democratizes black-box optimization research for expensive LLM tasks by providing reproducible, real-data-driven surrogate models to evaluate and improve optimization methods for hyperparameters, prompts, and configurations.

Original authors: Ruth Wan Theng Chew, Zhiliang Chen, Apivich Hemachandra, Bryan Kian Hsiang Low

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ruth Wan Theng Chew, Zhiliang Chen, Apivich Hemachandra, Bryan Kian Hsiang Low

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to bake the perfect loaf of sourdough bread. You have a few knobs to turn: how much flour, how much water, how long to let it rise, and what temperature to bake it at. If you guess randomly, you might waste a lot of dough and time before finding a recipe that works.

In the world of Artificial Intelligence (specifically Large Language Models, or LLMs), researchers face a similar problem but on a massive scale. They need to tune thousands of "knobs" (like training speed, data mixtures, and prompts) to get the AI to work well. However, testing one single setting can cost thousands of dollars in computer time and take days to run. Because it's so expensive, most researchers just guess or use simple rules of thumb, which often leads to subpar results.

This paper introduces BOLT, a new tool designed to help researchers find the best settings without actually having to spend the money to run the expensive tests every time.

Here is how BOLT works, using some everyday analogies:

1. The Problem: The "Expensive Taste Test"

Imagine you are a chef trying to find the perfect spice blend for a new soup. The catch is that making a full pot of soup takes 24 hours and costs $1,000. You can't afford to make 100 different pots to see which one tastes best.

Current situation: Researchers usually just guess the spices or try a few random combinations.
The goal: They want a smart system (called "Black-Box Optimization") that can look at a few pots, learn the pattern, and predict the perfect blend with very few tries.
The hurdle: Until now, testing these smart systems required actually making the expensive pots of soup, which most researchers couldn't afford.

2. The Solution: The "Magic Simulator" (Emulators)

BOLT solves this by providing a Magic Simulator.
Instead of making real, expensive pots of soup, BOLT uses a "surrogate model" (a smart computer program trained on data from thousands of real soup experiments that were already done).

How it works: You ask the simulator, "What would happen if I used 20% more salt?" The simulator instantly gives you an answer based on its training, costing you almost nothing in time or money.
The result: Researchers can now test their smart optimization strategies thousands of times on this cheap simulator to see which one works best, before ever touching the real, expensive AI training.

3. The Three Main "Recipes" BOLT Tests

The paper tests this simulator on three specific types of "cooking" problems that AI researchers face:

Hyperparameter Optimization (HPO): This is like adjusting the oven temperature and timer. The researchers are tuning the settings of the AI training process itself (like how fast it learns).
Data Mixture Optimization (DMO): This is like deciding the ratio of ingredients. Should the AI learn more from math books, coding manuals, or general conversation? BOLT helps find the perfect mix of data to feed the AI.
Prompt Optimization (PO): This is like writing the perfect instruction card for the chef. Instead of changing the ingredients, you change how you ask the AI to solve a problem. BOLT helps find the exact wording that gets the best result.

4. What They Found

The researchers used BOLT to test many different "smart search" algorithms (the chefs trying to find the best recipe).

The Winner: They found that a specific type of smart search called Bayesian Optimization (which is like a chef who remembers every failed attempt and uses that memory to make a better guess next time) consistently outperformed the old, random guessing methods.
The Challenge: They also discovered that these smart search tools need to be tweaked to handle the specific quirks of AI problems, such as dealing with "noisy" results (where the soup tastes slightly different every time you make it) or high-dimensional spaces (where there are too many ingredients to count).

5. Why This Matters

Before BOLT, the community of people who study "smart search" (Black-Box Optimization) was stuck testing their ideas on fake, easy math problems that didn't look like real AI challenges.

Democratization: BOLT acts as a public playground. Now, a researcher with a laptop can test their new ideas against real-world AI problems without needing a supercomputer.
Reproducibility: Because everyone is using the same "Magic Simulator," they can compare their results fairly, knowing they are all testing on the exact same ground.

In short: BOLT is a free, open-source toolkit that lets researchers practice and perfect their "smart search" strategies for AI on a cheap, fast simulator, so they can eventually apply those strategies to the real, expensive AI models to get better results faster.

Technical Summary: BOLT - A Benchmark to Democratize Black-box Optimization Research for Expensive LLM Tasks

Problem Statement

Optimizing Large Language Model (LLM) configurations—specifically hyperparameters, data mixtures, and prompts—is critical for performance but is currently approached heuristically in practice, often leading to suboptimal outcomes. While Bayesian Optimization (BO) and other Black-Box Optimization (BBO) methods offer principled, sample-efficient solutions for noisy, expensive, and derivative-free problems, their application to LLMs is severely hindered by computational costs. Most BBO researchers lack the resources to validate new methods on real LLM tasks. Consequently, the field relies on synthetic test functions or small-scale classical machine learning benchmarks (e.g., BBOB, HPO-B) that fail to capture the specific challenges of modern LLM optimization, such as mixed-variable search spaces, simplex constraints, and high-dimensional embeddings. This gap impedes the development and assessment of BBO methods tailored for LLMs.

Methodology: The BOLT Benchmark

To address these limitations, the authors introduce BOLT (Benchmark for optimization of expensive LLM Tasks), the first LLM-centric benchmark designed to democratize research for the BBO community. BOLT replaces expensive, irreproducible LLM training loops with lightweight, deterministic emulators (surrogate models) trained on over 20,000 real LLM experimental evaluations.

Core Components

Task Families: BOLT covers three active areas of LLM research, each framed as a derivative-free optimization problem:
- Hyperparameter Optimization (HPO): Optimizing LoRA fine-tuning configurations (rank, alpha, target modules, learning rate, batch size) for Qwen3 models (4B and 8B) on the OpenMathInstruct-2 dataset.
- Data Mixture Optimization (DMO): Optimizing the proportion of instruction-following, math, and code data across two training stages for a Qwen3-4B model.
- Prompt Optimization (PO): Selecting optimal prompts for mathematical reasoning from a pre-generated corpus of 5,014 candidates, evaluated on the MATH-500 benchmark.
Problem Variants & Challenges: Each task family includes variants designed to test specific BBO challenges:
- Multi-fidelity: Continuous (token count) and discrete (model size) fidelity settings to test cost-aware optimization.
- Multi-objective: Simultaneous optimization of multiple metrics (e.g., IFEval, MATH-500, MBPP+).
- Heteroscedastic Noise: Input-dependent noise modeling for data mixture optimization.
- High Dimensions: Prompt optimization tasks ranging from 128 to 768 dimensions (using Matryoshka Representation Learning embeddings).
- Constraints: Simplex constraints for data mixtures and mixed-variable spaces (continuous, integer, categorical) for hyperparameters.
Emulator Construction:
- HPO and DMO: Trained using 2-layer Multi-Layer Perceptrons (MLPs) on real experimental data.
- PO: Utilizes tabular data from pre-generated prompt candidates and their embeddings, as interpolation in embedding space is not easily decodable to natural language.
- Validation: Emulators are validated using Spearman's rank correlation ( $\rho_s$ ) between predictions and held-out test sets, ensuring high fidelity in ranking candidates (e.g., $\rho_s \approx 0.96$ for HPO).

Key Contributions

A Suite of LLM-Centric BBO Problems: The authors introduce three task families grounded in real LLM objectives, spanning mixed-variable spaces, simplex constraints, multi-fidelity, multi-objective, and high-dimensional settings.
Democratization via Emulators: By providing validated surrogate models and tabular datasets, BOLT allows researchers to benchmark BBO methods without access to expensive LLM infrastructure, ensuring reproducibility and accessibility.
Extensive Empirical Evaluation: The paper benchmarks a wide range of BO methods (including LogNEI, GIBBON, MES, PES) against standard baselines (Random, TPE, CMA-ES, NSGA-2) across all BOLT tasks.

Experimental Results

The authors evaluated numerous acquisition functions and optimization strategies on BOLT:

HPO: GP-based BO methods (specifically LogNEI, MF-MES, and MF-GIBBON) consistently outperformed non-GP baselines (TPE, CMA-ES, BOHB) across single-fidelity and multi-fidelity settings. However, the selection of acquisition functions showed sensitivity to cost scales and exploration parameters (e.g., $\beta$ in UCB).
DMO: NEI-based methods dominated single-objective tasks, while NEHVI with batch selection ( $q=5$ ) significantly outperformed evolutionary baselines (NSGA-2) on multi-objective tasks, achieving similar Pareto front quality with 50x fewer function evaluations. Noise-aware methods (LogNEI+MLHGP) showed modest improvements in heteroscedastic settings.
PO: Standard acquisition functions (LogEI, LogNEI, UCB) failed to scale in high-dimensional embedding spaces, plateauing near random search performance. Local search methods adapted for discrete spaces (dTuRBO and dBAxUS) combined with LogNEI achieved substantial gains, reaching log simple regret of -10 to -15. Batch evaluation further accelerated convergence. Notably, subspace reduction (dBAxUS) was less effective at lower dimensions (PO-128) where variance was not concentrated in a low-dimensional active subspace, suggesting LLM embeddings may not always satisfy the low-rank assumptions of such methods.

Significance and Claims

The paper claims that BOLT is a critical step toward modernizing BBO research for LLMs. By providing a reproducible, accessible, and realistic benchmark, BOLT:

Validates the potential of BO: It demonstrates that mature BBO methods, particularly those based on entropy search and noisy expected improvement, are effective for LLM tasks but require adaptation to specific structural challenges (e.g., simplex constraints, discrete search spaces).
Highlights gaps: It exposes the limitations of current methods in high-dimensional, discrete, and constrained settings, underscoring the need for new algorithmic developments.
Enables progress: It removes the computational barrier that previously prevented the BBO community from engaging with LLM-specific optimization problems, fostering the development of more efficient and principled LLM pipeline optimization strategies.

The authors remain modest, noting that the emulators are trained on specific configurations (e.g., smaller token budgets, non-thinking models) and may not represent the absolute best achievable performance of frontier models, but the optimization challenges themselves (mixed variables, constraints, noise) are intrinsic to LLM tasks and remain consistent across configurations.