# TextBO: Bayesian Optimization in Language Space for Eval-Efficient Self-Improving AI

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Self-rewarding alignment and self-training, one of 13 directions in Synthetic data and self-improvement for LLMs.
- Builds on 46 of its 95 references that are in the map.
- First posted on arXiv 15 Nov 2025.

## Placed in

- Synthetic data and self-improvement for LLMs / [Self-rewarding alignment and self-training](https://mlsanity.com/synth/self-rewarding-alignment-and-self-training/)

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

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [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)
- [DeepSeek-V3 Technical Report](https://mlsanity.com/paper/2412.19437/) (2024)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback](https://mlsanity.com/paper/2309.00267/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [Automated Design of Agentic Systems](https://mlsanity.com/paper/2408.08435/) (2024)
- [Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models](https://mlsanity.com/paper/2510.04618/) (2025)
- [ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory](https://mlsanity.com/paper/2509.25140/) (2025)
- [Judging the Judges: A Systematic Study of Position Bias in LLM-as-a-Judge](https://mlsanity.com/paper/2406.07791/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Model Context Protocol (MCP): Landscape, Security Threats, and Future Research Directions](https://mlsanity.com/paper/2503.23278/) (2025)
- [Video models are zero-shot learners and reasoners](https://mlsanity.com/paper/2509.20328/) (2025)
- [Helping or Herding? Reward Model Ensembles Mitigate but do not Eliminate Reward Hacking](https://mlsanity.com/paper/2312.09244/) (2023)
- [Generalizing Verifiable Instruction Following](https://mlsanity.com/paper/2507.02833/) (2025)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [DS-Agent: Automated Data Science by Empowering Large Language Models with Case-Based Reasoning](https://mlsanity.com/paper/2402.17453/) (2024)
- [Theoretical guarantees on the best-of-n alignment policy](https://mlsanity.com/paper/2401.01879/) (2024)
- [xbench: Tracking Agents Productivity Scaling with Profession-Aligned Real-World Evaluations](https://mlsanity.com/paper/2506.13651/) (2025)
- [LLM Generated Persona is a Promise with a Catch](https://mlsanity.com/paper/2503.16527/) (2025)
- [The Alternative Annotator Test for LLM-as-a-Judge: How to Statistically Justify Replacing Human Annotators with LLMs](https://mlsanity.com/paper/2501.10970/) (2025)
- [Exploring the Frontier of Vision-Language Models: A Survey of Current Methodologies and Future Directions](https://mlsanity.com/paper/2404.07214/) (2024)
- [Many-Shot In-Context Learning in Multimodal Foundation Models](https://mlsanity.com/paper/2405.09798/) (2024)
- [Quantifying Variance in Evaluation Benchmarks](https://mlsanity.com/paper/2406.10229/) (2024)
- [Test-Time Preference Optimization: On-the-Fly Alignment via Iterative Textual Feedback](https://mlsanity.com/paper/2501.12895/) (2025)
- [Fine-Tuning and Prompt Optimization: Two Great Steps that Work Better Together](https://mlsanity.com/paper/2407.10930/) (2024)

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

- [LLM Personas as a Substitute for Field Experiments in Method Benchmarking](https://mlsanity.com/paper/2512.21080/) (2025)
- [The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows](https://mlsanity.com/paper/2608.06714/) (2026)
- [Offline-to-Online Creative Optimization with Generative Models and Adaptive Testing](https://mlsanity.com/paper/2607.23696/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have enabled self-improving AI systems that iteratively generate, evaluate, and refine their outcomes. Recent studies show that prompt-optimization-based self-improvement can outperform state-of-the-art reinforcement-learning fine-tuning of LLMs, but performance is typically measured by generation efficiency. However, in many applications, the constraint is evaluation efficiency: obtaining reliable feedback is far more costly than generating candidates. To optimize for evaluation efficiency, we extend Upper Confidence Bound-Bayesian Optimization (UCB-BO), a framework known for optimal evaluation-efficiency guarantees, to the language domain. Doing so is challenging for two reasons: (i) gradients needed for UCB-BO are ill-defined in discrete prompt space; and (ii) UCB-style exploration relies on a surrogate model and acquisition function, which only live implicitly in the LLM. We overcome these challenges by proving that combining simple textual gradients (LLM-proposed local edits) with the Best-of-N selection strategy statistically emulates ascent along the gradient of the canonical UCB acquisition function. Based on this result, we propose TextBO, a simple, evaluation-efficient self-improving algorithm that operates purely in language space without explicit surrogates or calibrated uncertainty models. We empirically validate TextBO on automated ad-alignment tasks using a persona-induced preference distribution, demonstrating superior performance per evaluation compared to strong baselines such as Best-of-N and GEPA. We also evaluate TextBO's Best-of-N multi-step textual-gradient mechanism on agentic AI benchmarks by augmenting GEPA with it and show that it significantly outperforms standard GEPA. In sum, TextBO is a simple and principled framework for AI self-improving system design that bridges prompt optimization with classical Bayesian optimization.