PaperlayerView exact revision on arXiv

Source-linked AI summary

When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting

Ariel Smogorghevski, Nir Rosenfeld, Yaniv Romano

arXiv:2609.00905v1cs.LGstat.COstat.ML

TL;DR

Conditional sampling in generative modeling lacks exact pointwise target-density evaluations, although pairwise judgments are readily available. Pref-MH converts stochastic binary comparisons into an exact MH sampler, and experiments demonstrate its use across text, image, and molecular generation. The method is optimal among specified exact reversible competitors but relies on a Bradley-Terry assumption that may not hold exactly for human, LLM, or VLM judges.

  • Problem

    Generative models lack a rigorous way to ensure samples satisfy desired semantic properties and follow the full target conditional distribution when pointwise density ratios are unavailable.

  • Method

    Pref-MH uses stochastic binary pairwise comparisons to implement an exact reversible MH sampler without evaluating pointwise scores or plugging in estimated acceptance ratios.

  • Results

    Pref-MH supports general state spaces and arbitrary proposal kernels, is Peskun–Tierney optimal among fixed-budget exact reversible competitors, and works across synthetic, text, image, and molecular-design tasks.

  • Takeaways & Limitations

    Comparative feedback can serve as a direct interface for defining sampling distributions when desired quality is difficult to reduce to a pointwise score.

  • Takeaways & Limitations

    Pref-MH assumes an underlying Bradley-Terry latent score, which may not hold exactly for LLM, VLM, or human judges.

Abstract

from arXiv · show

Sampling from distributions conditioned on desired semantic properties is an emerging challenge in modern generative modeling. Metropolis-Hastings (MH) provides a principled route to conditional sampling, but requires access to exact pointwise target-density evaluations, which are not available in generative settings. Meanwhile, pairwise comparisons by humans or model "judge" are highly accessible and have proved valuable across diverse applications. We introduce Pref-MH, a general exact MH sampler for judge-induced conditional distributions using only stochastic binary pairwise comparisons. Our key observation is that the MH unnormalized density ratio matches the preference odds of the Bradley-Terry (BT) choice model. The central challenge is that while MH requires precise ratio computation, BT judges provide only sampled binary feedback. To this end, we develop a valid accept/reject rule whose resulting Markov chain provably converges to the target distribution. We further show that, for a fixed proposal kernel and budget, Pref-MH is optimal in the Peskun-Tierney sense among this class of exact reversible acceptance rules. Experiments on text generation and molecular design with LLM judges, as well as image generation with VLM judges, demonstrate that Pref-MH provides a practical and flexible approach to conditional sampling when comparative feedback is relatively easy to obtain.

1 Introduction

The paper introduces Pref-MH, an exact MH sampler that uses stochastic pairwise preferences instead of pointwise target-density evaluations to sample judge-induced conditional distributions. It connects MH ratios to Bradley-Terry preference odds and demonstrates practical use across conditional generation tasks.

  • Motivation: Conditional sampling can produce diverse outputs satisfying desired properties, unlike methods that return only a single best solution.The paper motivates applications including molecular design with trade-offs among efficacy, toxicity, and synthesizability.
  • Motivation: Generative models make conditional generation accessible, but prompting alone does not guarantee correct target-distribution sampling or controlled variation.The motivating examples include helpful, polite, Shakespearean responses.
  • Contribution: Pref-MH addresses the lack of pointwise density ratios by using stochastic binary pairwise comparisons to construct an exact MH sampler for judge-induced conditional distributions.Its stationary distribution matches the desired target, with support for general state spaces and arbitrary proposal kernels.
  • Methodological insight: The MH acceptance ratio corresponds theoretically to Bradley-Terry preference odds under a Gibbs-structured conditional target.The equivalence links target-density ratios with judges’ latent preference strengths.
  • Contribution: A randomized accept/reject mechanism avoids fixed-budget plug-in estimation, whose errors can distort the chain’s stationary distribution.The impossibility result motivates the paper’s alternative exact acceptance mechanism.
  • Experiments: Pref-MH is evaluated on synthetic, text, image, and molecular-design tasks, with molecular experiments showing better external evaluation than MH baselines without pairwise LLM judgments.The molecular-design evaluation uses MolSkill, a human-expert quality score not used to guide sampling.

2 Problem Setup and Background

The paper defines a judge-induced conditional target by reweighting a base generative distribution toward samples judged more likely to satisfy a desired property. Pref-MH retains a user-specified proposal kernel but replaces inaccessible target-ratio evaluation with pairwise comparison feedback.

  • Problem setup: The sample space X contains candidate outputs, while M denotes a property such as instruction adherence, factual correctness, or stylistic fidelity.A judge evaluates whether an input admits M.
  • Problem setup: The judge-induced target reweights the base distribution p0 toward samples that judge J considers more likely to exhibit M.The judge probability is denoted pJ(M | x).
  • Problem setup: Only sample access to pairwise comparisons is assumed, rather than direct access to the judge probability pJ(M | x).This makes the likelihood ratio pJ(M | x′)/pJ(M | x) the remaining challenge in the MH ratio.
  • Multiple conditions: Multiple desiderata can be represented jointly as M = (M1, . . . , Mm), including helpfulness, politeness, and stylistic fidelity.The exposition begins with one property before returning to the multi-condition case.
  • Metropolis–Hastings: MH proposes x′ from a user-chosen kernel q(x′ | x), then accepts or rejects it to construct a chain whose stationary distribution matches the target.The proposal may be global or local, and Pref-MH can combine with any valid proposal kernel under convergence conditions.
  • Acceptance ratio: Substituting the judge-induced target into the MH ratio leaves a factor involving pJ(M | x′)/pJ(M | x), which cannot be directly evaluated in this setting.The base-density and proposal terms are tractable or design choices.

3 Proposed Method: Exact Sampling from Preference-Based Judges

Pref-MH converts Bradley–Terry preference odds into an exact, implementable MH sampler using a fixed number of binary judge queries. Its N-vote rule preserves the judge-induced target for finite budgets, converges under standard MH conditions, and is Peskun–Tierney optimal among comparable exact rules.

  • Preference-based MH: Under the latent-score assumption pJ(M | x) ∝ exp(s(x)), Bradley–Terry preference odds equal the likelihood ratio required by MH.This links pairwise comparisons between candidates to the target-density ratio without requiring direct access to the latent score.
  • Impossibility and construction: The oracle BT-MH acceptance rule cannot be implemented exactly by any finite fixed-budget procedure using only binary votes for every comparison probability.The impossibility holds for nondegenerate proposal moves and finite N.
  • Impossibility and construction: Pref-MH queries the judge N times, counts proposal-favoring votes K, and adjusts the tractable MH baseline ratio before applying accept/reject.More favorable votes upweight the baseline ratio, while fewer favorable votes downweight it.
  • Exactness and convergence: As N grows, the vote-based factor converges almost surely toward the ideal win-rate ratio, making the acceptance update approach the full MH rule.The family is therefore an exact fixed-budget approximation whose behavior becomes closer to the ideal update with larger comparison budgets.
  • Exactness and convergence: For every finite N ≥1, the N-vote rule with a valid proposal kernel satisfies detailed balance and has the judge-induced target π as its stationary distribution.Under standard MH regularity assumptions, the resulting chain converges in distribution to π from every initialization in its support.
  • Optimality and extensions: For fixed proposal kernel, judge, and comparison budget, the N-vote rule maximizes acceptance probability for every proposed move among exact reversible competitors.This is the stated Peskun–Tierney dominance result.

4 Experiments

Experiments test Pref-MH on synthetic targets, multi-property text and image generation, and molecular design. Across these settings, the method approaches known targets, improves semantic or visual-condition satisfaction, and aligns molecular samples more closely with medicinal-chemist preferences while retaining other quality measures.

  • 4.1 Synthetic validation: In the synthetic validation, Pref-MH approaches the known target even with one judge query per proposal, whereas plug-in MH plateaus at large error with N = 4.The comparison uses cumulative empirical total variation distance between the sampled chain and the true target.
  • 4.2 Multi-condition text generation: For multi-property story generation, Pref-MH with separate judges performs best across all properties under both pointwise and Bradley–Terry evaluation metrics.The separate variant uses one pairwise judge per property, while the joint variant assesses all properties together.
  • 4.2 Multi-condition text generation: The gap between separate and joint Pref-MH suggests that decomposing the conditioning criteria improves performance on the tested stylistic properties.The evaluated properties are elevated language, gothic or dramatic atmosphere, and frequent dialogue.
  • 4.3 Image generation in continuous space: Pref-MH achieves a 63.6% image success rate for containing all three desired objects, versus 7.4% for Pointwise-MH and 4.5% for the base model.Average aesthetic scores are 6.395, 6.289, and 6.287 for Pref-MH, Pointwise-MH, and the base model, respectively.
  • 4.4 De novo molecular design from preference feedback: In molecular design, Pref-MH achieves the best MolSkill mean and median while maintaining high diversity and synthetic-accessibility scores.MolSkill evaluates alignment with medicinal-chemist follow-up preference, independently of the sampling objective.

5 Discussion

Pref-MH provides exact, flexible sampling from judge-defined distributions, while relying on a Bradley–Terry assumption whose practical violations remain unresolved. Comparative feedback can serve as a direct interface for defining sampling distributions, though human-judge use may require more efficient algorithms.

  • Method and scope: Pref-MH supports exact MCMC with pairwise comparisons, arbitrary proposal kernels, and general state spaces under a latent Bradley–Terry score assumption.The authors identify violations of this assumption by humans, LLMs, or VLMs as an open direction.
  • Broader significance: Comparative feedback can define sampling distributions directly rather than serving only as an evaluation signal, especially when quality is difficult to reduce to a pointwise score.The paper notes that this mechanism could in principle use human experts as judges.
  • Practical boundary: Human-judge deployments may face infeasible annotation burdens unless Pref-MH uses efficient proposal functions.The discussion specifically motivates efficient versions that exploit clever proposals.
  • Related work: Best-of-N and controlled-decoding methods generally return selected outputs or rely on proxy rewards rather than sampling an explicitly specified conditional distribution.Multiple properties can also require scalarizing, transforming, or combining objectives or reward models.
  • Related work: Pseudo-marginal and related methods address exact sampling when ideal MH ratios are unavailable by replacing target quantities with unbiased estimators on augmented state spaces.This places Pref-MH within established research on MCMC from inexact inputs.

C Experimental Details and Additional Results

The appendix contains the complete experimental setups and additional quantitative and qualitative results supporting the paper’s main experiments.

  • The appendix provides complete experimental setups underlying the main-text experiments and additional quantitative and qualitative results.

C.1 Synthetic validation

The synthetic experiment tests whether Pref-MH converges to a known target using only binary comparisons, separating its exact accept/reject construction from an invalid empirical-odds alternative. Oracle MH and Pref-MH approach the true target, whereas the plug-in sampler plateaus away from it.

  • Setup: The synthetic validation uses a known, non-uniform target over X = {0, 1, ..., 240} with several separated modes and no direct score access for preference-only samplers.This controlled design tests convergence under a nontrivial preference-induced target.
  • Setup: The target is constructed from a non-uniform base distribution and a latent score with three Gaussian-shaped modes.The score is s(k) = 5/240 k + 0.9 g60,13(k) + 0.7 g130,21(k) + 1.0 g200,13(k).
  • Methods: Each proposal receives K ∼ Binomial(N, pJ(k ≺ k′)) votes favoring it, with N ∈ {1, 2, 4}; all samplers share a symmetric global-plus-local proposal.The global move probability is γ = 0.88, while the local nearest-neighbor component has probability 0.12.
  • Methods: Oracle MH uses latent-score access as a reference, while Pref-MH uses only binary judge outcomes and the plug-in method uses empirical win-rate odds.The plug-in construction sets acceptance to 0 or 1 at K = 0 or K = N.
  • Results: Figure 5 compares empirical distributions from Oracle MH, Pref-MH, and the invalid plug-in sampler with the exact target using N = 2 votes per proposal.
  • Results: Both Oracle MH and Pref-MH approach the true target, whereas the plug-in sampler’s TV distance plateaus away from zero despite the same comparison budget.The experiment satisfies the BT model exactly, so the separation isolates the accept/reject construction.

C.2 Multi-condition text generation

The text experiment tests whether preference-based MH can steer a language model toward three stylistic properties and compares separate property judges with a joint judge. Separate-judge Pref-MH performs best across reported criteria, while preference-based variants outperform pointwise counterparts.

  • Task and motivation: The experiment generates story openings targeting elevated language, gothic or dramatic atmosphere, and frequent direct dialogue.Separate variants use one judge per property; joint variants use one judge for the conjunction.
  • Experimental setup: The base LLM samples neutral story openings from 50 scenarios, with up to 192 new tokens at temperature 0.9.The neutral prompt prevents direct instruction to satisfy the hidden criteria.
  • Methods: Pref-MH (sep.) queries each property-specific judge N = 3 times per proposal, whereas Pref-MH (joint) queries one conjunction judge N = 3 times.The separate method records each judge’s favorable-vote count independently.
  • Methods: Pointwise-MH variants replace binary comparisons with normalized 1–10 absolute ratings for separate properties or the full conjunction.The evaluation reports both pointwise scores and Bradley–Terry coefficients from pairwise comparisons.
  • Evaluation: Each MH chain runs for 300 steps after base-model initialization, discards 50 burn-in states, and retains the final 50 states for evaluation.
  • Results: Pref-MH (sep.) performs best under every reported pointwise and pairwise criterion, with a particularly pronounced advantage over Pref-MH (joint) for dialogue.The results suggest that several property-specific judges provide a more discriminative signal than one judge assessing a complex conjunction.
  • Results: Both preference-based variants outperform their pointwise counterparts, indicating that the comparative evaluation signal contributes beyond using MH alone.

C.3 Image generation in continuous space

The image-generation experiment applies Pref-MH in a continuous diffusion latent space, using separate vision-language judges for three visual conditions. Pref-MH substantially improves simultaneous constraint satisfaction while preserving comparable aesthetic quality.

  • Experimental setup: Pref-MH evolves a Markov chain in SDXL-Turbo’s continuous latent space while VLM judges evaluate decoded images.The base state distribution is the Gaussian prior, and proposals mix local, wider, and independent-refresh pCN moves.
  • Experimental setup: Three separate judges assess individual semantic properties rather than remaining objects or general image aesthetics.Each comparison uses the judge dedicated to its criterion; Pref-MH queries each judge nine times per proposal.
  • Results: The trajectories and quantitative results show that preference-based sampling combines specialized semantic judges directly over a complex continuous modality.The experiment runs chains for 3000 steps and records additional samples every 300 steps.

C.5 Machine translation

The machine-translation experiment compares preference-based sampling with QUEST and pointwise scoring under matched proposal and query-budget conditions. Pref-MH leads on reference-based lexical metrics, while XCOMET reveals a trade-off with QUEST’s optimized quality-estimation signal.

  • Sampling methods: Pref-MH replaces QUEST’s scalar CometKiwi reward with pairwise judgments while sharing the generator, proposal, QE information, and query budget with Pointwise-MH.Both LLM-guided methods use five randomized pairwise or pointwise judge queries per proposal.
  • Experimental setup: All three samplers use the same suffix-regeneration proposal and differ only in how translation quality enters acceptance decisions.The proposal retains a sampled prefix and regenerates the remaining suffix from the base model.
  • Results: Pref-MH obtains the best BLEU, chrF, and TER in both translation directions and significantly outperforms every tested QUEST temperature and Pointwise-MH.The comparison uses WMT23 test sets and a chain-mean protocol after burn-in.
  • Results: At smaller β, QUEST achieves higher XCOMET scores than Pref-MH, but this advantage disappears and eventually reverses as β increases.No tested QUEST configuration improves on Pref-MH simultaneously on XCOMET and any of BLEU, chrF, or TER.
  • Results: Pref-MH significantly outperforms Pointwise-MH on all four evaluation metrics in both translation directions despite matched experimental resources.The four metrics are BLEU, chrF, TER, and XCOMET-XL.

C.6 Compute resources and assets

This material combines compute and licensing details with a proof that finite binary-vote procedures cannot reproduce the oracle BT-MH acceptance probability for every comparison probability. Exact fixed-budget sampling is not thereby ruled out.

  • Compute resources: The remaining experiments use internal GPU clusters with either eight NVIDIA H200 or eight RTX PRO 6000 Blackwell GPUs.The listed systems include 2.0 TB RAM and substantial Xeon CPU capacity.
  • Compute resources: Machine translation required approximately 15 hours per direction, image generation approximately 6 hours, text generation 10–12 hours, and molecular design approximately 48 hours.No pretrained generative or judge model was fine-tuned.
  • Assets and licenses: The experiments use existing models, datasets, codebases, and evaluation tools under their corresponding licenses.The listed assets include Llama, WMT23, SDXL-Turbo, Qwen models, COMET/XCOMET, MARS, and MolSkill.
  • Proof of Theorem 1: With a finite binary-vote budget, the marginal acceptance probability is a polynomial in the unknown comparison probability p of degree at most N.This polynomial structure underlies the contradiction used in the impossibility proof.
  • Proof of Theorem 1: No fixed-budget procedure using only N binary judge samples can reproduce the oracle BT-MH acceptance probability for every p ∈(0, 1).The result excludes exact oracle-rule reproduction, not exact fixed-budget sampling altogether.
  • Proof of Theorem 2: The single-judge acceptance rule satisfies detailed balance with respect to π and therefore has π as a stationary distribution.The theorem is obtained as the single-judge case of the multi-judge exactness result.

D.3 Convergence of the Pref-MH chain

Under proposal regularity conditions, the Pref-MH chain inherits irreducibility and aperiodicity from its proposal kernel. Combined with detailed balance, these properties yield convergence to the target distribution from every initialization in the support of π.

  • Proposal regularity: The proposal must be π-irreducible, with some finite-step proposal path reaching every measurable set of positive π-probability.The condition is stated using the m-step proposal kernel without accept/reject steps.
  • Proposal regularity: Admissible proposals require finite positive baseline ratios and corresponding reverse support, while proposal transitions must remain in the target support almost surely.These are support and regularity conditions imposed on the proposal kernel.
  • Irreducibility: Every admissible proposal has strictly positive marginal acceptance probability under Pref-MH.Because the judge preference probability lies strictly between zero and one, accepted proposal paths retain positive probability.
  • Aperiodicity: A zero-vote event has positive probability and causes rejection, giving the chain a positive probability of remaining in its current state.Together with π-irreducibility, this establishes aperiodicity.
  • Convergence: Detailed balance makes π stationary, and the regularity conditions imply convergence from every initialization in the support of π.The proof extends almost-everywhere convergence by showing the chain reaches the full-measure convergence set almost surely.
  • Convergence: Once the chain enters the full-measure convergence set, it remains there because proposals stay in the target support and rejection leaves the current state unchanged.Applying the Markov property at the hitting time completes the convergence argument.

D.4 Proof of Theorem 3

The multi-judge N-vote rule is exact: under the multi-judge Bradley–Terry assumptions, it yields a reversible chain with target πm and converges to it. With a fixed proposal kernel and comparison budget, it also Peskun–Tierney dominates every exact competitor.

  • Exactness: Theorem 4 establishes detailed balance for the multi-judge N-vote rule, so the resulting chain is reversible and has πm as a stationary distribution.This holds for every integer N ≥1 when combined with a valid proposal kernel q.
  • Convergence: The rule converges in total variation to πm from every initialization in supp(πm).The proof uses reversibility, irreducibility inherited from the proposal kernel, aperiodicity, and a full-measure-set argument.
  • Peskun–Tierney optimality: For every proposed move, the multi-judge N-vote rule has acceptance probability at least as large as any exact fixed-budget competitor.The comparison assumes the same proposal kernel q, N queries per judge, and detailed balance with respect to πm.
  • Competitor class: Competing rules may depend on all binary outcomes and internal randomness, but their marginal acceptance probabilities remain bounded by the N-vote rule under exactness.Vote counts are independently binomial across judges, and competitors must satisfy detailed balance with respect to πm.
  • Peskun–Tierney optimality: This pointwise acceptance dominance implies Peskun–Tierney domination over transitions into every set of states different from the current state.The conclusion follows because both procedures use the same proposal kernel.

E Conditional Target Derivation

The multi-condition target combines a base distribution with judge-induced likelihood factors for the desired conditions. Under conditional independence of the judges given x, these factors multiply and yield the normalized conditional target used in the main text.

  • Model specification: The construction starts with candidate objects x drawn from a base distribution p0 and associates each condition Mi with a judge likelihood pJi(Mi | x).The conditions M1, . . . , Mm represent the desired properties, and the judges J1, . . . , Jm provide their likelihood factors.
  • Conditional independence: The judge-induced events M1, . . . , Mm are assumed conditionally independent given x.Formally, pJ(Mi | x, M−i) = pJi(Mi | x) for each condition i.
  • Target derivation: Bayes’ rule gives a conditional distribution proportional to p0(x) pJ(M1, . . . , Mm | x), normalized over the candidate space.The denominator integrates this unnormalized expression against the base distribution.
  • Target derivation: Under conditional independence, the joint judge likelihood decomposes into the product of the condition-specific likelihood factors.This produces the multi-condition target used in the main text.
Loading 2609.00905v1…