# BayesPO: Bayesian Prompt Optimization via Parallel-Tempered Gradient-Guided Discrete MCMC

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 20 references that are in the map.
- First posted on arXiv 17 Jul 2026.

## Builds on (most cited first, 11 of 11)

- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [Instruction Induction: From Few Examples to Natural Language Task Descriptions](https://mlsanity.com/paper/2205.10782/) (2022)
- [Black-Box Prompt Optimization: Aligning Large Language Models without Model Training](https://mlsanity.com/paper/2311.04155/) (2023)
- [Gradient-Based Constrained Sampling from Language Models](https://mlsanity.com/paper/2205.12558/) (2022)
- [Reprompting: Automated Chain-of-Thought Prompt Inference Through Gibbs Sampling](https://mlsanity.com/paper/2305.09993/) (2023)
- [GReaTer: Gradients over Reasoning Makes Smaller Language Models Strong Prompt Optimizers](https://mlsanity.com/paper/2412.09722/) (2024)
- [Energy-Based Models with Applications to Speech and Language Processing](https://mlsanity.com/paper/2403.10961/) (2024)
- [Principled Gradient-based Markov Chain Monte Carlo for Text Generation](https://mlsanity.com/paper/2312.17710/) (2023)
- [An Exploratory Study of Bayesian Prompt Optimization for Test-Driven Code Generation with Large Language Models](https://mlsanity.com/paper/2512.15076/) (2025)

## Abstract (arXiv)

Prompt optimization adapts large language models (LLMs) without updating model parameters, but many automatic prompt optimizers remain heuristic search procedures over candidate instructions. This paper studies prompt optimization as Bayesian posterior sampling over discrete prompt tokens. We define a posterior distribution by combining a task likelihood term, which rewards prompts that explain input-output examples, with a language-model prior, which favors fluent instructions. This converts prompt optimization into an energy-based posterior sampling problem, for which gradients can be used to guide discrete Markov chain Monte Carlo (MCMC) proposals over vocabulary tokens. We refer to our framework as BayesPO, short for Bayesian Prompt Optimization. In this paper, BayesPO is instantiated with Markov chain Monte Carlo: it uses a Metropolis-Hastings corrected Gibbs-with-Langevin (GwL) proposal and integrates parallel tempering for global exploration of rugged LLM-induced energy landscapes. The concrete sampler further adapts the GwL sampler to the practical constraints of non-weight-tied LLM embeddings. Experiments with Qwen2.5 models show that the sampler discovers semantically meaningful prompts on diagnostic tasks, that parallel tempering helps escape a local optimum in a poetry completion task, and that post-optimizing APE prompts on 24 instruction-induction subtasks improves average accuracy from 60.04% to 63.23%. The study also reveals two main limitations: energy minimization may overfit small optimization sets, and the current sampler remains computationally expensive. These findings position Bayesian prompt sampling as a principled post-optimization tool and point to a promising direction for probabilistic prompt optimization.