Research map / Large language models / Language, safety and interpretability
Hyperband-based Bayesian Optimization for Black-box Prompt Selection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes HbBoPs, combining a structural-aware deep kernel GP (separate instruction and exemplar embeddings) with Hyperband multi-fidelity scheduling over validation instances to select black-box LLM prompts sample- and query-efficiently.
Problem
Static black-box prompt selection from a combinatorial pool of instructions times few-shot exemplars, where each prompt evaluation costs many LLM calls on a validation set and gradients are unavailable.
Approach
Embed instructions and few-shot exemplars separately and feed them through a deep kernel GP to model prompt error, then use that GP as the proposal mechanism inside Hyperband, which varies the number of validation instances per prompt, so the method is both sample-efficient and query-efficient.
Key results
- Average normalized test error at full budget: HbBoPs 0.150 vs best full-fidelity HDBO 0.185 and best multi-fidelity TRIPLE-GSE 0.158 and TRIPLE-SH 0.159 (RS 0.214).
- At 0.25 budget, HbBoPs outperforms HDBO by about 35% and TRIPLE-SH by 24% on average normalized error.
- Ablation: structural-aware DK-GP improves over non-structural DK-GP by 9% and 13% at 0.5 and 1.0 budget; adding Hyperband and BO proposal yields 66-67% improvement over vanilla BO at 0.5 and 1.0 budget.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HbBoPs instead of full-fidelity or multi-fidelity competitors | Black-box prompt selection · 10 benchmarks × 3 LLMs, full budget | normalized test error: 0.150 vs 0.158 (TRIPLE-GSE); 0.150 vs 0.159 (TRIPLE-SH) | Helped |
| Use HbBoPs instead of HDBO | Black-box prompt selection · 10 benchmarks × 3 LLMs, 0.25 budget | normalized test error: approximately 35% | Helped |
| Use HbBoPs instead of TRIPLE-SH | Black-box prompt selection · 10 benchmarks × 3 LLMs, 0.25 budget | normalized test error: 24% | Helped |
| Replace vanilla BO with a non-structural deep-kernel GP (ablation) | BoPs, full-fidelity prompt selection · 10 benchmarks × 3 LLMs, 0.5 and 1.0 budget | normalized validation error: 11% at 0.5 budget; 38% at 1.0 budget | Helped |
| Add structural-aware prompt representations to the deep-kernel GP (ablation) | BoPs · 10 benchmarks × 3 LLMs, 0.5 and 1.0 budget | normalized validation error: 9% at 0.5 budget; 13% at 1.0 budget | Helped |
| Add Hyperband scheduling with a random proposal mechanism (ablation) | BoPs (structural-aware DK-GP) · 10 benchmarks × 3 LLMs, 0.5 and 1.0 budget | normalized validation error: 47% at 0.5 budget; 11% at 1.0 budget | Helped |
| Replace Hyperband's random proposal with the structural-aware Bayesian optimization proposal (ablation) | HB · 10 benchmarks × 3 LLMs, 0.5 and 1.0 budget | normalized validation error: 21% at 0.5 budget; 31% at 1.0 budget | Helped |
| Replace vanilla BO with complete HbBoPs (ablation) | Black-box prompt selection · 10 benchmarks × 3 LLMs, 0.5 and 1.0 budget | normalized validation error: 66% at 0.5 budget; 67% at 1.0 budget | Helped |
| Use HbBoPs with alternative encoders (MPNet or DistillRoBERTa) instead of BERT (ablation) | HbBoPs · 30 benchmark scenarios | normalized test error: BERT: 0.190 (0.006), 0.170 (0.006), 0.150 (0.005); MPNet: 0.193 (0.006), 0.173 (0.006), 0.158 (0.006); DistillRoBERTa: 0 | No clear effect |
| Use HbBoPs instead of TRIPLE-SH | Black-box prompt selection · Claude 3 Haiku, full-budget test error | median relative test improvement: -0.006 (0.035) | Hurt |
| Use HbBoPs instead of TRIPLE-SH | Black-box prompt selection · Mistral 7B Instruct, full-budget test error | median relative test improvement: -0.001 (0.047) | Hurt |
Surprising findings
- Few-shot exemplars often contribute more to prompt performance than the instruction itself, per prior empirical findings cited by the authors.
- Using small random validation subsets (e.g., 10 to 100 instances) leads to validation-optimal prompts with test errors far from optimal, due to noise.
Limitations
- Depends on embeddings from pre-trained encoders, adding computational overhead.
- Only considers instructions and few-shot exemplars; other prompt elements such as formatting remain unexplored.
- Evaluated in static setting with a fixed, a priori candidate pool of 250 prompts.
Experimental setup
Datasets: AI2 ARC GSM8K BIG-bench instruction induction subsets (antonyms, larger animal, negation, object counting, orthography starts with, se
Benchmarks: AI2 ARC GSM8K antonyms larger animal negation object counting orthography starts with second word letter sentiment word unscrambling
Metrics: normalized validation error normalized test error exact match error
Baselines: Random search Vanilla BO HDBO BOPCA EASE MIPROv2 TRIPLE-SH TRIPLE-GSE
Builds on: Hyperband deep kernel learning TRIPLE HDBO BOPCA
Closest papers by meaning
- PRESTO: Preimage-Informed Instruction Optimization for Prompting Black-Box LLMs (NeurIPS 2025 · similarity 0.87)
- GReaTer: Gradients Over Reasoning Makes Smaller Language Models Strong Prompt Optimizers (ICLR 2025 · similarity 0.86)
- Unleashing the Potential of Large Language Models as Prompt Optimizers: Analogical Analysis with Gradient-based Model Optimizers (AAAI 2025 · similarity 0.86)
- Scaling Prompt Synthesis for Large Language Model Reasoning (ICML 2026 · similarity 0.85)
- Multimodal Prompt Optimization: Why Not Leverage Multiple Modalities for MLLMs (ICLR 2026 · similarity 0.85)
- Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.