🤖 AI

Embedding by Elicitation: Dynamic Representations for Bayesian Optimization of System Prompts

The paper introduces ReElicit, a Bayesian optimization framework that leverages large language models to dynamically elicit adaptive, interpretable feature embeddings from aggregate feedback, enabling efficient optimization of variable-length system prompts without per-example labels.

Original authors: Zhiyuan Jerry Lin, Benjamin Letham, Samuel Dooley, Maximilian Balandat, Eytan Bakshy

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiyuan Jerry Lin, Benjamin Letham, Samuel Dooley, Maximilian Balandat, Eytan Bakshy

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 teach a very talented but slightly stubborn robot how to answer questions. You can't talk to the robot directly to say, "You got this specific math problem wrong because you forgot to carry the one." Instead, you only get a single number at the end of a long day: "Today, the robot got 85% of the questions right."

This is the problem the paper tackles: How do you improve a robot's instructions (called a "system prompt") when you only get a vague, overall score, not a detailed report card?

The authors, from Meta, propose a new method called ReElicit. Here is how it works, broken down into simple concepts:

1. The Problem: The "Black Box" Dilemma

Usually, when you tune a machine learning model, you have a lot of data. You know exactly which answers were right and which were wrong. But in the real world (like a customer service bot), you might only know that "User satisfaction went up 2% this week."

Trying to guess the perfect instructions by just randomly changing words and hoping for the best is like trying to find a specific needle in a haystack by throwing random needles at it. It's too slow and inefficient.

2. The Solution: The "Translator" Robot

The authors realized that instead of searching through millions of possible sentences, they could ask a "smart" Large Language Model (LLM) to act as a translator.

Here is the analogy:

The Goal: You want to find the perfect recipe for a cake, but you only get a taste score (e.g., "8/10") after baking it. You can't taste the ingredients individually.
The Old Way: You just guess new recipes randomly.
The ReElicit Way: You ask a master chef (the LLM) to look at your past recipes and their scores. The chef says, "I think the secret isn't the flour or the sugar; it's the balance of vanilla and baking soda."

The chef then creates a simple map (a "feature space") with just two or three axes:

How much vanilla? (0 to 1)
How much baking soda? (0 to 1)

Now, instead of searching through infinite recipes, you are just searching for the perfect spot on this tiny, simple map.

3. The Process: A Three-Step Dance

The paper describes a loop where the computer does three things repeatedly:

Elicit (Ask the Chef): The system looks at the prompts it has tried and their scores. It asks the LLM: "What are the 2 or 3 most important 'ingredients' (semantic features) that make a prompt good for this specific task?" The LLM invents these features on the fly (e.g., "clarity of reasoning" or "use of examples").
Optimize (The Navigator): The system uses a mathematical tool called Bayesian Optimization. Think of this as a smart navigator that looks at the map and says, "We haven't tried the spot where 'clarity' is high and 'examples' are medium yet. Let's go there." It picks a target point on the map.
Realize (The Baker): The system asks the LLM again: "Okay, write a prompt that hits that exact target on our map." The LLM writes the new instructions. The system tests them, gets a new score, and the loop starts again.

4. Why It's Special: "Re-eliciting"

The clever part is that the "map" isn't static. As the system tries more prompts and gets more scores, it asks the LLM to redraw the map.

Maybe at first, the LLM thought "length" was important.
But after 10 tries, the LLM realizes, "Actually, length doesn't matter; it's about how the instructions are structured."
So, the LLM updates the map to reflect this new understanding. This allows the system to adapt as it learns.

5. The Results

The authors tested this on 10 different difficult tasks (like solving math problems or identifying sarcasm). They gave ReElicit a very tight budget: it could only test 30 different prompts total.

The Competition: They compared ReElicit against other methods that just guess prompts, evolve them like bacteria, or critique them one by one.
The Winner: ReElicit consistently found the best prompts. It was better at finding the "needle in the haystack" because it stopped guessing randomly and started navigating a smart, evolving map.

Summary

In short, ReElicit is a method that uses an AI to invent its own language to describe what makes a prompt good. Instead of searching through the messy, infinite world of text, it translates the problem into a simple, clean map, finds the best spot on that map, and then translates that spot back into a perfect set of instructions. It does this by constantly updating its own map as it learns from new results.

The paper claims this is the most effective way to tune AI instructions when you only have a single, overall score to guide you, rather than a detailed list of errors.

Technical Summary: Embedding by Elicitation for Bayesian Optimization of System Prompts

Problem Setting

The paper addresses the challenge of optimizing system prompts in modern AI systems under aggregate feedback constraints. In many deployment scenarios, prompt performance is measured by population-level metrics (e.g., task completion rates, safety incident rates, user satisfaction) rather than per-example labels, error traces, or textual critiques. The optimizer observes only a single scalar score for each deployed prompt variant.

This setting transforms prompt optimization into a sample-constrained black-box optimization problem over discrete, variable-length natural language. Standard Bayesian Optimization (BO) is difficult to apply directly because:

Representation: BO typically operates in fixed, low-dimensional Euclidean spaces, whereas prompts are complex, structured text objects.
Realization: Mapping optimized points in a latent space back to deployable text usually requires auxiliary encoders/decoders or hand-crafted kernels, which are not directly available for arbitrary system prompts.
Data Scarcity: Fitting surrogates in high-dimensional text embedding spaces (e.g., thousands of dimensions) with very few observations yields uninformative posteriors.

Existing Automatic Prompt Optimization (APO) methods often rely on granular feedback (per-example labels, critiques) or assume specific interfaces (soft prompts, fixed candidate pools), making them unsuitable for this aggregate-only, hard-prompt setting.

Methodology: ReElicit

The authors propose ReElicit, a Bayesian Optimization framework based on embedding by elicitation. The core idea is to use a Large Language Model (LLM) not just as a prompt generator, but as an adaptive builder of a semantic representation space.

The optimization loop proceeds in three phases per iteration:

Dynamic Feature Elicitation:
- Given the task description and the history of evaluated prompts with their scalar scores, the LLM proposes a set of task-relevant, interpretable semantic feature axes (e.g., "explicitness of reasoning," "tone control").
- The LLM then maps the historical prompts into a compact continuous space $[0, 1]^{d_t}$ based on these features.
- To ensure robustness, multiple candidate feature sets are generated and evaluated via cross-validation (CV) against the observed scores. The set with the lowest CV error is selected. If $t > 1$ , the previous feature set is re-evaluated on the expanded history and included as a candidate.
Bayesian Optimization in Feature Space:
- A Gaussian Process (GP) surrogate model is fitted to the embedded prompt scores.
- An acquisition function (e.g., $q$ -LogNoisyExpectedImprovement) selects target feature vectors in the continuous space that balance exploration and exploitation. These targets represent desired semantic properties, not text strings.
Realization and Refinement:
- The LLM realizes each target feature vector as a deployable system prompt.
- Because the inverse map from continuous features to text is lossy, the LLM performs feature-gap refinement. It analyzes the difference between the target features and the features of the generated prompt, then iteratively modifies the text to reduce this gap, ensuring the final prompt aligns with the BO-selected semantic direction.

This process repeats, allowing the representation to adapt ("re-elicitation") as new prompt-score data arrives, refining the semantic axes that distinguish high- and low-performing prompts.

Theoretical Analysis

The paper provides a theoretical analysis of reachability: under what conditions does a point near-optimal in the elicited embedding correspond to a good prompt in the original text space?

Assumptions: The authors assume the existence of an "oracle" semantic embedding where the objective function is smooth (Lipschitz continuous in the latent space). They assume the elicited embedding approximates this oracle within a bounded error $\eta_t$ .
Result: Theorem 1 establishes that if a prompt is $\delta$ -suboptimal in the approximated objective (elicited space), it is $\epsilon$ -suboptimal in the true objective, where $\epsilon = \delta + 2BL\eta_t$ . Here, $B$ is the RKHS norm bound and $L$ is the Lipschitz constant.
Implication: The gap between the optimized feature space and the true prompt quality is bounded by the representation error. Dynamic re-elicitation serves to reduce $\eta_t$ over time, tightening the guarantee that feature-space optimization leads to true prompt improvement.

Experimental Results

The authors evaluate ReElicit on ten system prompt optimization tasks (covering GSM8K, MMLU, and BIG-Bench Hard) under a strict 30-evaluation budget (6 batches of 5 prompts). The feedback interface is strictly aggregate-only (one scalar score per prompt).

Baselines:
ReElicit is compared against four representative aggregate-only baselines adapted for hard prompts:

APE: History-free sampling.
OPRO: Generation conditioned on score-sorted history.
PromptBreeder: Evolutionary mutation and recombination.
TextGrad-style: Critique-based refinement using scalar trajectories.

Key Findings:

Performance: ReElicit achieves the strongest aggregate performance profile. It is either the numerically best method or statistically indistinguishable from the best on all ten tasks.
Consistency: It has the highest pairwise win-or-tie rate across task-seed pairs, indicating robustness rather than overfitting to a single benchmark.
Component Analysis:
- Feature Stability: Elicited features are highly stable under repeated extraction but adapt conservatively across iterations (measured by Linear CKA).
- Predictiveness: Dynamic features yield lower GP cross-validation MSE than static features or mean predictors.
- Actionability: Prompts with smaller feature gaps to BO targets are more likely to improve the best-so-far score.
Ablations: Removing feature-gap refinement or replacing BO with random sampling causes the most significant performance drops. Freezing features (static representation) or independent extraction yields smaller, often non-significant degradations, suggesting the initial elicitation is already effective but dynamic adaptation provides further gains.

Significance and Claims

The paper claims that LLMs can serve as adaptive semantic representation builders, not just prompt generators, for Bayesian optimization over natural language artifacts.

Methodological Contribution: ReElicit bridges the gap between discrete text optimization and continuous BO by using the LLM to construct a compact, interpretable, and task-specific latent space on the fly.
Practical Impact: It offers a viable path for optimizing system prompts in real-world deployment settings where only aggregate, population-level metrics are available, avoiding the need for per-example labels or complex encoder-decoder training.
Generalizability: The "embedding by elicitation" pattern is presented as a recipe for optimizing any language-describable structured artifact where candidates are text, constraints are textual, and evaluation is an expensive scalar measurement.

The authors remain modest regarding the scope, noting that their experiments use offline benchmark accuracy as a proxy for deployment metrics (like user satisfaction) and that the method's efficiency is measured in target-model evaluations rather than total LLM calls. They emphasize that the approach is an "apples-to-apples" comparison within the aggregate-only hard-prompt setting.