Technical Summary: LILO: Bayesian Optimization with Natural Language Feedback

1. Problem Definition

The paper addresses the challenge of optimizing expensive-to-evaluate black-box functions where the true objective is not a directly measurable scalar but rather a complex, subjective preference of a Decision Maker (DM). In many real-world scenarios, the utility function $g(y)$ mapping outcomes $y$ to a satisfaction score is unknown and difficult to express in a closed form.

Traditional Preference-Based Bayesian Optimization (PBO) methods rely on structured feedback, such as pairwise comparisons or scalar ratings. However, these formats are often restrictive, failing to capture high-level goals, trade-offs, and qualitative constraints that decision makers naturally express in natural language. Conversely, using Large Language Models (LLMs) as end-to-end optimizers often lacks calibrated uncertainty and principled exploration-exploitation trade-offs, leading to poor sample efficiency.

The goal is to solve the composite optimization problem:
$$x^* := \arg \max_{x \in X} g(f(x))$$
where $f: X \to Y$ is the black-box system and $g: Y \to \mathbb{R}$ is the latent utility function, utilizing free-form natural language feedback from the DM to guide the search.

2. Methodology: LILO Framework

The authors propose Language-in-the-Loop Optimization (LILO), a hybrid framework that integrates the expressivity of LLMs with the reliability of Gaussian Process (GP)-based Bayesian Optimization. LILO positions the LLM as a supporting agent for feedback interpretation rather than the optimizer itself.

Core Workflow

The optimization proceeds in $T$ sequential trials, each consisting of three stages:

1. Candidate Generation & Experimentation:

   • A batch of candidate inputs $\{x_i\}$ is selected.
   • For the first trial ($n=1$), candidates are either sampled uniformly or generated via LLM prompting if prior knowledge is provided.
   • For subsequent trials, a batch acquisition function (e.g., Log Noisy Expected Improvement) selects candidates based on the current GP proxy model $M_{n-1}$.
   • The black-box function $f$ is evaluated to produce observable outcomes $y_i = f(x_i)$.

2. Feedback Acquisition:

   • The LILO agent generates a batch of questions ($B_{pf}$) for the DM based on the accumulated experimental data and previous feedback.
   • The DM provides free-form natural language answers ($a_j$).
   • This feedback is stored in a preference feedback dataset $D_{pf}$.

3. Utility Estimation via LLM Labeling + GP Modeling:

   • Labeling: The LLM acts as an interpreter, converting the accumulated natural language feedback into structured pairwise preference labels between observed outcomes. Given a pair of outcomes $(y, y')$, the LLM determines which is preferred based on the DM's textual feedback.
   • Budgeting: To manage LLM costs, labeling is performed under a budget $K$. The paper proposes a sequential strategy using the qEUBO (Expected Utility of Best Option) acquisition function to select the most informative pairs for labeling, rather than random sampling.
   • Modeling: The labeled pairwise preferences are used to fit a Pairwise Gaussian Process (GP) surrogate model $M_n$ over the input space $X$. This model approximates the composite utility $u(x) = g(f(x))$.
   • The GP model provides a posterior distribution over utility with calibrated uncertainty, which drives the next round of candidate selection.

Incorporating Prior Knowledge

LILO supports "warm-starting" by incorporating textual prior knowledge ($P_{prior}$). Instead of random initialization, the LLM is prompted to generate initial candidate points based on the DM's domain expertise (e.g., "inputs within these ranges should bring good results"), leveraging the LLM's pre-trained domain knowledge.

3. Key Contributions

The paper outlines five primary contributions:

1. LILO Framework: A novel BO framework that elicits utility information via free-form natural language, offering a more expressive interface than standard pairwise or scalar feedback.
2. Utility Estimation Mechanism: A scalable approach combining LLM-based preference labeling with GP modeling, enabling calibrated uncertainty and principled exploration under noisy, indirect feedback.
3. Performance Superiority: Empirical evidence showing LILO outperforms both conventional PBO baselines (relying on quantitative feedback) and LLM-only optimizers across synthetic and real-world benchmarks.
4. Prior Knowledge Integration: A method to incorporate textual priors to warm-start optimization, significantly improving early-stage performance.
5. Compatibility with Unstructured Outcomes: Demonstration that LILO can optimize over high-dimensional, unstructured outcomes (e.g., text summaries) without requiring an explicit surrogate model over the outcome space $Y$, relying instead on the LLM's ability to interpret outcomes.

4. Experimental Results

The authors evaluated LILO on 10 environments, including synthetic multi-objective functions (DTLZ2), vehicle safety simulators, car cab design, thermal comfort models, and neural architecture search (NAS-Bench-201). They also tested a text summarization task with unstructured textual outcomes.

Key Findings

• Sample Efficiency: LILO consistently outperforms baselines, particularly in the early stages of optimization. In feedback-limited regimes, a single natural language message from the DM was found to be roughly equivalent to 8–16 pairwise comparisons or scalar evaluations in terms of optimization progress.
• Comparison to Baselines:
  • vs. LLM-only: LLM-only methods (direct or 2-step) often plateau or fail to improve meaningfully as iterations increase, lacking the convergence guarantees of BO.
  • vs. Quantitative BO: LILO outperforms "True Utility BO" and "Preference BO" (which use ground-truth scalar or pairwise labels) in early trials. The advantage diminishes as the number of trials increases, but the information density of natural language provides a significant head start.
• Pairwise vs. Scalar Labeling: The study found that prompting the LLM for pairwise comparisons yields more reliable utility estimates and better optimization progress than prompting for direct scalar utility values.
• Prior Knowledge: Incorporating domain priors via LLM initialization substantially improved the starting point and overall performance.
• Unstructured Outcomes: In the text summarization benchmark, LILO successfully optimized decoding parameters using natural language feedback, matching the performance of baselines with maximum oracle feedback.

5. Significance and Claims

The paper claims that LILO represents a significant step forward in making Bayesian Optimization accessible for problems with complex, subjective objectives. By placing the LLM in a supporting role to translate rich, unstructured language into structured preference signals, the framework preserves the sample efficiency, stability, and calibrated uncertainty of traditional BO while offering a flexible, information-dense feedback channel.

The authors emphasize that LILO is particularly well-suited for real-world settings with complex multi-metric trade-offs (e.g., online experimentation, design optimization) where explicit objectives are unavailable or difficult to formalize. They acknowledge that while LILO excels in feedback-limited regimes, its performance relative to quantitative baselines may converge over very long horizons, and future work could explore hybrid approaches combining unstructured language with structured quantitative feedback.

The code for reproducing the results is made available at https://github.com/facebookresearch/lilo.