# Hyperband-based Bayesian Optimization for Black-box Prompt Selection

arXiv: https://arxiv.org/abs/2412.07820 · HTML: https://mlsanity.com/paper/2412.07820/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 64 references that are in the map.
- First posted on arXiv 10 Dec 2024.

## Builds on (most cited first, 30 of 46)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs](https://mlsanity.com/paper/2406.11695/) (2024)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [WikiHow: A Large Scale Text Summarization Dataset](https://mlsanity.com/paper/1810.09305/) (2018)
- [A System for Massively Parallel Hyperparameter Tuning](https://mlsanity.com/paper/1810.05934/) (2018)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Instruction Induction: From Few Examples to Natural Language Task Descriptions](https://mlsanity.com/paper/2205.10782/) (2022)
- [Compositional Exemplars for In-context Learning](https://mlsanity.com/paper/2302.05698/) (2023)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [GrIPS: Gradient-free, Edit-based Instruction Search for Prompting Large Language Models](https://mlsanity.com/paper/2203.07281/) (2022)

## Built on by (most cited first, 10 of 10)

- [Do LLMs Memorize Recommendation Datasets? A Preliminary Study on MovieLens-1M](https://mlsanity.com/paper/2505.10212/) (2025)
- [Adaptive Prediction-Powered AutoEval with Reliability and Efficiency Guarantees](https://mlsanity.com/paper/2505.18659/) (2025)
- [Meta-Prompt Optimization for LLM-Based Sequential Decision Making](https://mlsanity.com/paper/2502.00728/) (2025)
- [CAPO: Cost-Aware Prompt Optimization](https://mlsanity.com/paper/2504.16005/) (2025)
- [FedPOB: Sample-Efficient Federated Prompt Optimization via Bandits](https://mlsanity.com/paper/2509.24701/) (2025)
- [Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery](https://mlsanity.com/paper/2602.03132/) (2026)
- [Embedding by Elicitation: Dynamic Representations for Bayesian Optimization of System Prompts](https://mlsanity.com/paper/2605.19093/) (2026)
- [The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows](https://mlsanity.com/paper/2608.06714/) (2026)
- [Adaptive Simulation Experiment for LLM Policy Optimization](https://mlsanity.com/paper/2604.08779/) (2026)
- [Evidence-Gated LLM Priors for Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2606.01730/) (2026)

## Abstract (arXiv)

Optimal prompt selection is crucial for maximizing large language model (LLM) performance on downstream tasks, especially in black-box settings where models are only accessible via APIs. Black-box prompt selection is challenging due to potentially large, combinatorial search spaces, absence of gradient information, and high evaluation cost of prompts on a validation set. We propose HbBoPs, a novel method that combines a structural-aware deep kernel Gaussian Process with Hyperband as a multi-fidelity scheduler to efficiently select prompts. HbBoPs uses embeddings of instructions and few-shot exemplars, treating them as modular components within prompts. This enhances the surrogate model's ability to predict which prompt to evaluate next in a sample-efficient manner. Hyperband improves query-efficiency by adaptively allocating resources across different fidelity levels, reducing the number of validation instances required for evaluating prompts. Extensive experiments across ten diverse benchmarks and three LLMs demonstrate that HbBoPs outperforms state-of-the-art methods in both performance and efficiency.