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

• URL: http://arxiv.org/abs/2607.16001v1
• Date: Fri, 17 Jul 2026 14:39:05 GMT
• Title: BayesPO: Bayesian Prompt Optimization via Parallel-Tempered Gradient-Guided Discrete MCMC
• Abstract summary: BayesPO is instantiated with Markov chain Monte Carlo and integrates parallel tempering for global exploration of rugged energy landscapes.<n> Experiments with Qwen2.5 models show that the sampler discovers semantically meaningful prompts on diagnostic tasks.<n>Post-optimizing APE prompts on 24 instruction-induction subtasks improves average accuracy from 60.04% to 63.23%.
• Score: 10.650418686153921
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Embedding by Elicitation: Dynamic Representations for Bayesian Optimization of System Prompts [22.060204303535187]
  System prompts are a central control mechanism in modern AI systems, shaping behavior across conversations, tasks, and user populations.<n>We study this aggregate feedback setting as sample-constrained black-box optimization over discrete, variable-length text.<n>We introduce ReElicit, a Bayesian optimization framework based on emphembedding by elicitation.
  arXiv  Detail & Related papers  (2026-05-18T20:28:17Z)
• GFlowPO: Generative Flow Network as a Language Model Prompt Optimizer [51.31263673158136]
  GFlowPO casts prompt search as a posterior inference problem over latent prompts regularized by a meta-prompted reference-LM prior.<n>GFlowPO consistently outperforms recent discrete prompt optimization baselines.
  arXiv  Detail & Related papers  (2026-02-03T10:30:03Z)
• Prompt Optimization Via Diffusion Language Models [73.9599434962714]
  We propose a diffusion-based framework for prompt optimization.<n>Our method enables flexible, span-level prompt updates without requiring access or modifying the downstream language model.<n>We show that moderate diffusion step counts provide the best balance between refinement quality and stability.
  arXiv  Detail & Related papers  (2026-01-30T00:00:54Z)
• LLM Based Bayesian Optimization for Prompt Search [6.764478031814792]
  We propose an algorithm for prompt engineering to enhance text classification with Large Language Models.<n>The proposed BO-LLM algorithm is evaluated on two datasets, and its advantages are discussed in this paper.
  arXiv  Detail & Related papers  (2025-10-05T22:32:50Z)
• Can Prompt Difficulty be Online Predicted for Accelerating RL Finetuning of Reasoning Models? [65.18157595903124]
  This work investigates iterative approximate evaluation for arbitrary prompts.<n>It introduces Model Predictive Prompt Selection (MoPPS), a Bayesian risk-predictive framework.<n>MoPPS reliably predicts prompt difficulty and accelerates training with significantly reduced rollouts.
  arXiv  Detail & Related papers  (2025-07-07T03:20:52Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  We propose an optimization-based structural pruning that learns the pruning masks in a probabilistic space directly by optimizing the loss of the pruned model.<n>We achieve this by learning an underlying Bernoulli distribution to sample binary pruning masks.<n>Experiments conducted on LLaMA, LLaMA-2, LLaMA-3, Vicuna, and Mistral models demonstrate the promising performance of our method in efficiency and effectiveness.
  arXiv  Detail & Related papers  (2024-06-15T09:31:03Z)
• A Block Metropolis-Hastings Sampler for Controllable Energy-based Text Generation [78.81021361497311]
  We develop a novel Metropolis-Hastings (MH) sampler that proposes re-writes of the entire sequence in each step via iterative prompting of a large language model. Our new sampler allows for more efficient and accurate sampling from a target distribution and (b) allows generation length to be determined through the sampling procedure rather than fixed in advance.
  arXiv  Detail & Related papers  (2023-12-07T18:30:15Z)
• A Bayesian approach for prompt optimization in pre-trained language models [1.980639720136382]
  In this paper we focus on hard prompt tuning (HPT) which directly searches for discrete tokens to be added to the text input with-out access to the large language model (LLM) In this paper we use BoTorch, a library for Bayesian optimization research built on top of pyTorch.
  arXiv  Detail & Related papers  (2023-12-01T10:10:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.