Variational Best-of-N Alignment

## Abstract

Abstract Best-of- N 𝑁 N italic_N (Bo N 𝑁 N italic_N ) is a popular and effective algorithm for aligning language models to human preferences.
The algorithm works as follows: at inference time, N 𝑁 N italic_N samples are drawn from the language model, and the sample with the highest reward, as judged by a reward model, is returned as the output.
Despite its effectiveness, Bo N 𝑁 N italic_N is computationally expensive; it reduces sampling throughput by a factor of N 𝑁 N italic_N .
To make Bo N 𝑁 N italic_N more efficient at inference time, one strategy is to fine-tune the language model to mimic what Bo N 𝑁 N italic_N does during inference.
To achieve this, we derive the distribution induced by the Bo N 𝑁 N italic_N algorithm.
We then propose to fine-tune the language model to minimize backward KL divergence to the Bo N 𝑁 N italic_N distribution.
Our approach is analogous to mean-field variational inference and, thus, we term it variational Bo N 𝑁 N italic_N (vBo N 𝑁 N italic_N ).
To the extent this fine-tuning is successful and we end up with a good approximation, we have reduced the inference cost by a factor of N 𝑁 N italic_N .
Our experiments on a controlled generation task suggest that while variational Bo N 𝑁 N italic_N is not as effective as Bo N 𝑁 N italic_N in aligning language models, it is close to Bo N 𝑁 N italic_N performance as vBo N 𝑁 N italic_N appears more often on the Pareto frontier of reward and KL divergence compared to models trained with KL-constrained RL objective.

## 1 Introduction

Language models are pre-trained on large corpora to model a distribution over natural language text.(^1^11Many language models are also used to model text in non-natural languages, e.g., programming languages.)
Beyond their initial pre-training, they are often additionally fine-tuned on domain-specific data through a process called supervised fine-tuning (SFT).
The goal of SFT is to enable the model to better perform various downstream tasks of interest.
While the fine-tuned model, called the reference model in our paper, is indeed typically much better at performing the downstream task of interest, e.g., dialogue generation or summarization, it may still generate undesirable content, e.g., harmful or offensive text.
To mitigate this issue, aligning the reference model to human preferences has become a fundamental step in the development of modern large language models (Touvron et al., ; OpenAI et al., ; Gemini et al., ).

The degree to which text is aligned with human preferences is typically operationalized using a real-valued reward function.
Rather than constructing a reward function by hand, it is typically estimated from a dataset of human preferences.(^2^22In some cases, the reward model is not estimated from human preference data. It is either known, e.g., code-based execution scores, or given by a classifier, e.g., toxicity or sentiment classifiers.)
And, after estimation, we expect the reward function to return higher values for text that is more likely to be preferred by humans, and lower values for text that is more likely to be dispreferred.
Then, given an estimated reward function, an alignment algorithm further alters the reference models in a manner such that it places the highest probability on that text that is high reward under the reward model *and* high probability under the reference model.

Alignment algorithms can be taxonomized into two groups: (i) alignment via fine-tuning, where we change the language model’s parameters to achieve alignment (Christiano et al., ; Rafailov et al., ), and (ii) alignment through inference (Nakano et al., ; Mudgal et al., ).
A common alignment-via-fine-tuning method is reinforcement learning from human feedback (RLHF; Christiano et al., ; Stiennon et al., ; Ouyang et al., ).
RLHF typically consists of further fine-tuning the language model under a KL-constrained RL objective, which is made up of two terms: a term that encourages the model to maximize the reward, and a term that discourages high KL divergence between the language model and the reference model.
This objective is often maximized with an RL algorithm, e.g., proximal policy optimization (PPO; Schulman et al., ).
A common alignment through inference is the Best-of-$N$ (Bo$N$; Nakano et al., ; Touvron et al., ) algorithm.
As such, it does *not* require any fine-tuning of the language model.
The algorithm is straightforward: One draws $N$ samples from the reference model and returns the text that achieves the highest reward among those $N$ samples.
The Bo$N$ algorithm has also been effectively applied in controlled decoding (Yang & Klein, ; Mudgal et al., ) and to generate a dataset for supervised fine-tuning (Touvron et al., ).

Despite its simplicity, Bo$N$ has proven incredibly practical in generating high-reward text that still has high probability under the reference model.
Theoretically, Yang et al. () prove that under some simplifying assumptions, the Bo$N$ distribution is asymptotically equivalent to the optimal distribution under the KL-constrained RL objective.
Empirically, it has been repeatedly shown (Gao et al., ; Rafailov et al., ; Mudgal et al., ) that Bo$N$ often appears on the frontier of reward and KL curves, surpassing the performance of models fine-tuned with RLHF.
However, the main factor preventing Bo$N$ from replacing fine-tuning methods for alignment is its significant computational overhead during inference.
Even when sampling is done in parallel, Bo$N$ decreases the text generation throughput by a factor of $N$.
This drawback limits its practicality for generating text from large language models.

To speed up Bo$N$, we devise a scheme to convert it into an alignment-via-fine-tuning algorithm rather than an alignment-via-inference algorithm.
To this end, we first formally derive the probability distribution induced by the Bo$N$ algorithm.
Then, we approximate this distribution by minimizing the reverse KL divergence between the language model and the Bo$N$ distribution. This leads to an optimization objective that we refer to as the vBo$N$ objective. By analyzing a lower bound of this objective, we find that it behaves similarly to the KL-regularization objective in the limit, i.e., $N\rightarrow 1$ or $N\rightarrow\infty$. Importantly, the vBo$N$ objective has a unique and useful property: it is insensitive to applying any monotonically increasing function to the reward values. This distinctive feature, along with the empirical success of the Bo$N$ algorithm, suggests that the vBo$N$ objective is a promising and interesting objective to explore.
Finally, we fine-tune the language model using PPO to optimize the vBo$N$ objective.
Our scheme allows us to achieve performance close to that of the Bo$N$ algorithm while increasing the inference throughput by a factor of $N$.

We experiment with our method in a controlled generation task, generating movie reviews with positive sentiment, and consider a binary sentiment classifier as the reward model.
We compare our method, which we term as variational Bo$N$ (vBo$N$), against models fine-tuned with the KL-constrained RL objective.
Our results suggest that models fine-tuned with the vBo$N$ objective are most likely to generate movie reviews with positive sentiment.
Additionally, these models deviate less from the reference model than those fine-tuned with KL-constrained RL objectives.

## 2 Background: Reinforcement Learning from Human Feedback

Let ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}$ be an alphabet, a finite, non-empty set of symbols.
A string is a finite sequence of symbols drawn from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}$.
A language model is a distribution over strings ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}\in{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma
}^{*}$, where ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}^{*}$ is the set of all strings over the alphabet ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}$.
In this paper, we consider language models, e.g., those based on neural networks, that are parameterized by a real vector ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
\theta}}\in{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{\Theta}}$, denoted as ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color
[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}
}}}$.
Furthermore, we restrict ourselves to language models that are differentiable functions of ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
\theta}}$.
In conditional generation tasks, e.g., summarization or dialogue generation, it is desirable to prompt the language model with a string ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
x}}\in{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma
}^{*}$.
Consequently, we consider prompted language models, i.e., those that give a conditional distribution over response strings ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}$, given a prompt string ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
x}}$, as ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color
[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}
}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}}\mid{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}
{0,0,0}\boldsymbol{x}})$. However, for notational convenience, we will drop the explicit conditioning on the prompt ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
x}}$ and simply write ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color
[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}
}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}})$.

Algorithms for RLHF fine-tune the language model to increase the expected reward of the strings sampled from it while not diverging too far from the reference model.
RLHF consists of three steps.
First, the language model is fine-tuned on a task-specific dataset using the maximum-likelihood objective.
Recall we term the language model after this step the reference model and show that with ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$.
Next, a reward model ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}\colon{
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}^{*}
\rightarrow{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\mathbb{R}}$ is trained to capture human preferences; the reward of a string is high if it is preferred by humans. Finally, the reference model is fine-tuned to maximize the KL-constrained RL objective,

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathcal{J} }^{\textsc{rl}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\boldsymbol{\theta}})=\operatorname*{{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big {]}-\beta\,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}D _{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\boldsymbol{\theta}}}}\,\|\,{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}\big{)},$ (1) $$

where ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{
kl}}}(\cdot)$ is the KL divergence between two distribution. This objective encourages the model to put more probability mass on strings that have high rewards under the reward model while penalizing it not to deviate too far from the reference model. Levine () show that the optimal probability distribution that maximizes this objective is

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }\pi_{\boldsymbol{\theta}}^{\star}}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})=\frac{1}{Z}\,{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\exp \Big{(}\frac{1}{\beta}r({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor} {rgb}{0,0,0}\boldsymbol{y}})\Big{)},\quad Z=\sum_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\in{\color[rgb]{ 0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}^{*}}{\color[rgb]{ 0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y }})\exp\Big{(}\frac{1}{\beta}r({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big{)}.$ (2) $$

${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{
\boldsymbol{\theta}}^{\star}}$ is simply the reference model reweighted by the exponent of reward values and normalized by the partition function $Z$.
Notably, we can not directly sample from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{
\boldsymbol{\theta}}^{\star}}$ because the partition function $Z$ may be difficult to compute—it involves an infinite sum after all.
However, a heuristic approach to sampling from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{
\boldsymbol{\theta}}^{\star}}$ would be to sample many strings from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$ and only keep those that have high rewards.
Indeed, this heuristic is the motivation behind the Bo$N$ algorithm.

## 3 Deriving the Best-of- N 𝑁 N italic_N Objective

Best-of-$N$ algorithm is a simple alignment-via-inference algorithm.
The algorithm works as follows.
Let $Y_{N}=\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}}^{(n)}\}_{n=1}^{N}$ be the multi-set containing $N$ i.i.d samples from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$.
Then, Bo$N$ algorithm returns ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}^{\star}$, where(^3^33We assume that the $\operatorname*{argmax}$ is unique, or ties are broken in a well-defined manner.)

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ y}}^{\star}=\operatorname*{argmax}_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(n)}\in Y_{N}}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(n)}).$ (3) $$

We show the probability distribution induced from Bo$N$ sampling algorithm with ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}$.
Importantly, ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}$ is *not* the optimal distribution under Eq. 1, the KL-constrained RL objective.(^4^44Under some simplifying assumptions, however, Yang et al. () show that ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{ bon}}}$ is asymptotically equal to ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{ \boldsymbol{\theta}}^{\star}}$.)
Nevertheless, the Bo$N$ algorithm often performs well—even compared to RLHF-based methods.
This raises the question: under what optimization objective is ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}$ the optimal distribution?
To derive such an objective, we begin by computing the probability of strings under ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}$.

###### Proposition 1 .

Suppose ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}\colon{
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}^{*}
\rightarrow{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\mathbb{R}}$ is a one-to-one mapping.
Then, the probability that a string ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}\sim{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{
\text{bon}}}$ is given by

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{ bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})=\sum_{i=1}^{N}{N\choose i}\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})^{i},$ (4) $$

where we define $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}(R)$ as

$$ $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}( R)\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathbb{P}}\left({\color[rgb]{ 0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})<R\right).$ (5) $$

###### Proof.

See App. A.
∎

We now describe how to fine-tune the language model to approximate ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}$ by minimizing the reverse KL divergence between ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color
[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}
}}}$ and ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}$. Concretely, we maximize the following objective:

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }\mathcal{J}^{\textsc{vBoN}}}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}})=-{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\big{(}{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{ 0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}} \mid\mid{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_ {\text{bon}}}\big{)}$ $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{ \text{bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }\boldsymbol{y}})-\log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\boldsymbol{\theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big{]}$ $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{ \text{bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }\boldsymbol{y}})\Big{]}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor }{rgb}{0,0,0}\mathrm{H}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\big{)}$ $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log\sum_{i=1}^{N}{N\choose i}\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})^{i} \Big{]}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \mathrm{H}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}}}}\big{)}.$ (6) $$

This is an entropy-regularized objective, where we use the probability of the string under the Bo$N$ distribution as the reward and discourage the model from having low entropy.

###### Proposition 1 .

###### Proof.

#### Monotonically invariant.

An important property of the variational Bo$N$ objective is that it is invariant to applying any monotonically increasing function to rewards. This is because the vBo$N$ objective relies on reward values solely through $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}$, which, as defined in Eq. 5, remains unchanged under any monotonically increasing transformation of reward values.
This implies that the vBo$N$ objective is insensitive to the outliers and the scale of rewards. This property is especially important as RL algorithms are notoriously sensitive to the scale of reward values (Henderson et al., ; Schaul et al., ).

#### Approximating log ⁡ F ⁢ ( ⋅ ) F ⋅ \log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{%
F}}(\cdot) roman_log roman_F ( ⋅ ) .

Maximizing Eq. 6 requires us to compute $\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{
F}}(\cdot)$ for any ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$. This, however, is computationally expensive, as we have to sum over the probabilities of all strings that have rewards less than ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$. Fortunately, we can instead maximize a lower bound of Eq. 6 using a Monte Carlo estimator of $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}(\cdot)$.
Concretely, we can write $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}(\cdot)$ as an expectation,

$$ $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}} \big{(}R\big{)}=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}}\big{[} \mathbbm{1}\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }r}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})<R\}\big{]}.$ (7) $$

We approximate $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}
\big{(}R\big{)}$ using $M$ i.i.d. samples from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$, termed ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}^{(1)},\ldots,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{
0,0,0}\boldsymbol{y}}^{(M)}\overset{\mathrm{i.i.d.}}{\sim}{\color[rgb]{0,0,0}
\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}$, and
$\widehat{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{
\mathrm{F}}}\big{(}R\big{)}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{
{=}}}\frac{1}{M}\sum_{m=1}^{M}\mathbbm{1}\{{\color[rgb]{0,0,0}\definecolor[
named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(m)})<R\}$.
We then take $\log$ of this Monte Carlo estimator as a biased, but consistent estimator of $\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{
F}}(\cdot)$ in Eq. 6.(^5^55Using Jensen’s inequality, we show biasedness. Concretely, note the following lower bound $\displaystyle\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}{\mathrm{F}}\big{(}R\big{)}$ $\displaystyle=\log\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(1)},\ldots,{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(M)}}\left[ \frac{1}{M}\sum_{m=1}^{M}\mathbbm{1}\{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(m)})<R\}\right]$ (8a) $\displaystyle\geq\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(1)},\ldots,{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(M)}}\left[ \log\left(\frac{1}{M}\sum_{m=1}^{M}\mathbbm{1}\{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{(m)})<R\} \right)\right],$ (8b) where Jensen’s inequality is applicable because $\log$ is concave. Consistency can be shown with an application of the delta method (§5.5.4; Casella & Berger, ).)
In § 5.1 we empirically assess how many samples we need so that $\log\widehat{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
{\mathrm{F}}}$ converges to $\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{
F}}$ and find that the convergence happens after taking only $250$ samples.

## 4 Comparing Bo N 𝑁 N italic_N and RL Objectives

To explore the connection between the vBo$N$ objective and the KL-regularized RL objective, we derive two lower bounds for ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathcal{J}^
{\textsc{vBoN}}}$. Through these lower bounds, we can get more insights on how the reward function is used in the variational Bo$N$ objective, and why this objective discourages high KL divergence from the reference model.

To derive the first lower bound, we substitute the Bo$N$ distribution in Eq. 4 into the vBo$N$ objective in Eq. 6. We then use Jensen’s inequality to bound this objective, as explained in the following theorem.

###### Theorem 2 .

Let $\alpha=\frac{(N+2)(N-1)}{2}$, $\beta=\frac{N(N+1)}{2}$, and $\gamma=\frac{N(N-1)}{2}$.
Then, we have ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathcal{J}^
{\textsc{vBoN}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{
0,0,0}\boldsymbol{\theta}})\geq{\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}L_{1}}({\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}})$, where we further define

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{1}}({ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\gamma \operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[}\log\color[rgb]{0,0,0 }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\Big{]}- \alpha{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \mathrm{H}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}}}}\big{)}-\beta{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}\big{)}.$ (9) $$

###### Proof.

See App. C.
∎

We can already see the connection between ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{1}}({
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
\theta}})$ and the KL-regularized RL objective, Eq. 1. They both encourage maximizing a function of reward values. In the Bo$N$ objective this function is $F(\cdot)$, while in the KL-regularized RL objective, it is an identity function. Furthermore, both objectives include a negative KL-divergence term between the language model and the reference model. ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{1}}({
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
\theta}})$ further encourages the model to have low entropy.
In fact, we can show that Thm. 2 also holds for $\alpha=0,\beta=1,\gamma=N-1$. This further simplifies ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{1}}$ to arrive at a looser lower bound, which we call ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}$, that is even more similar to the KL-regularized RL objective.

###### Theorem 3 .

We have ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathcal{J}^
{\textsc{vBoN}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{
0,0,0}\boldsymbol{\theta}})\geq{\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}L_{1}}({\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}})\geq{\color[rgb]{0,0,0}
\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}({\color[rgb]{0,0,0}
\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}})$, where

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }L_{2}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}( N-1)\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb} {0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[}\log\color[rgb]{0,0,0 }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\Big{]}- {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{ kl}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}}}}\,\|\,{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}\big{)}.$ (10) $$

###### Proof.

See App. D.
∎

Empirically, we observe that models that are fine-tuned to maximize ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}({
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
\theta}})$ perform competitively to the ones that are fine-tuned to maximize the vBo$N$ objective; see App. F for experimental results.
Interestingly, if we compare Eq. 10 to the KL-constrained RL objective, Eq. 1, we see they are very similar.
Both objectives consist of two terms: one for maximizing a function of reward values and another to prevent the model from diverging too much from the reference model.

Comparing Eq. 10 and Eq. 1 further suggests that $N$ (in the vBo$N$ objective) acts as a regularization parameter.
As $N\rightarrow 1$, the optimal distribution gets closer to ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$, which has the same effect as $\beta\rightarrow\infty$ in Eq. 1.
Furthermore, as $N\rightarrow\infty$, the optimal distribution only generates the string with the maximum rewards, which is equivalent to $\beta\rightarrow 0$ in Eq. 1.
Importantly, in both limits, the optimal distribution under the KL-regularized RL objective and the vBo$N$ objective are equivalent.

###### Theorem 2 .

###### Proof.

###### Theorem 3 .

###### Proof.

## 5 Experiments

Figure: (a) $4\%$ of points on Pareto front belong to BoNBoN, $4\%$ to PPO, $42\%$ to DPO, and $50\%$ to vBo$N$.
Refer to caption: x1.png

We now employ the variational Bo$N$ objective, Eq. 6, to fine-tune language models.
We perform an open-ended text generation task where the goal is to generate movie reviews with positive sentiment.

The reference model, ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$, is GPT-IMDB(^6^66Specifically, we use [https://huggingface.co/lvwerra/gpt2-imdb](https://huggingface.co/lvwerra/gpt2-imdb).), a version of GPT-2 (Radford et al., ) fine-tuned on imdb corpus (Maas et al., ). We use a binary sentiment classifier,(^7^77Specifically, we use [https://huggingface.co/lvwerra/distilbert-imdb](https://huggingface.co/lvwerra/distilbert-imdb).) denoted as ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}p}$, with two classes $\{\textsc{pos},\textsc{neg}\}$ as the reward model, and define ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})
\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\color[rgb]{0,0,0}
\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}p}(\textsc{pos}\mid{\color[rgb]
{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$. Following Rafailov et al. (), we sample $5000$ movie reviews from the training set of imdb dataset and for each sample, we randomly choose a prefix length between $2-8$ and take that prefix as the prompt. We further generate $512$ prompts in the same way from the test set of imdb that we use to evaluate our models.

We fine-tune the reference model with PPO using the vBo$N$ objective Eq. 6. Then, we compare the performance of the fine-tuned model (vBo$N$) to the exact Bo$N$ (Bo$N$), i.e., applying Bo$N$ at inference time.

We implement and compare the following existing methods for language model alignment:

- •
Bo$N$-SFT: Perhaps the most straightforward way to approximate Bo$N$ distribution is to fine-tune the model to maximize the likelihood of the samples taken with Bo$N$ algorithm. Unfortunately, we find that SFT is incapable of achieving a good trade-off between achieving high rewards and low KL divergence, see App. G for the experimental results.
- •
PPO: We use PPO to optimize the KL-constrained objective in Eq. 1. We use the default hyperparameters in trlx library (Havrilla et al., ) for fine-tuning with PPO.
DPO.
Direct preference optimization (DPO; Rafailov et al., ) is a popular alternative to RLHF that does not require training a reward model. Following DPO’s experimental setup, we generate $6$ reviews per prompt and use the resulting $12$ pairwise comparisons per prompt to construct DPO’s contrastive loss.(^8^88One could argue that DPO has a slight advantage over other methods in this setup since it has seen $6$ unique generations per prompt during training, while the others only have seen one (or $2$ with BoNBoN). Nevertheless, we observe that vBo$N$ is more effective than DPO.)
- •
BoNBoN: Concurrent work (Gui et al., ) explores another approach to approximate Bo$N$ distribution. Assuming that the reference model distribution ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$ is continuous, Gui et al. (Theorem 3; ) prove that the expected difference between the relative likelihood, i.e., $\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{
\text{bon}}}(\cdot)}{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{
rgb}{0,0,0}\pi_{\textup{ref}}}(\cdot)}$, of the Best-of-$N$ response and the Worst-of-$N$ response is $\frac{1}{2\beta}=\frac{1}{(N-1)\sum_{k=1}^{N-1}1/k}$.
They use this property to construct a loss function similar to that of IPO (Azar et al., ). Furthermore, they add another term to the loss function, which simply maximizes the likelihood of the Best-of-$N$ response. The final loss function is a convex combination of the IPO-like loss and the negative log-likelihood loss, regulated by a hyperparameter $\alpha$.(^9^99Following the authors’ recommendation, we set $\alpha$ so that both terms contribute equally to the final loss.)

Figure: Figure 2: Estimates of $\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{ F}}(\cdot)$ with increasing the number of Monte Carlo samples. We test an adversarial prompt (left plot), a neutral prompt (middle plot), and a prompt with a positive sentiment (right plot). Overall, we hardly see any difference between the estimates after taking $200$ samples. For the adversarial prompt, the distribution of rewards is peaked, and we do not see any changes in our estimator after taking only $100$ samples.
Refer to caption: x3.png

We fine-tune models by varying the degree of regularization. For Bo$N$ approaches, that is achieved by varying $N$, and for DPO and PPO, we vary $\beta$.(^10^1010See App. E for more details regarding the regularization hyperparameters.) Importantly, $N$ in vBo$N$ is a hyperparameter, meaning that we do *not* need to generate more samples from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$ when we increase $N$. However, with Bo$N$ and BoNBoN methods, we need to increase the number of samples from the reference model as we increase $N$.

We generate movie reviews using fine-tuned models based on prompts from our test set and then measure three metrics: (i) KL divergence between the fine-tuned model and the reference model, (ii) win rate, defined as the percentage of times the fine-tuned model’s generations receive higher rewards compared to the reference model’s generations; and (iii) average rewards obtained by the fine-tuned model’s sampled strings.

For Bo$N$ method, following Gao et al. (), we report the empirical upper bound of $\log N-\frac{N-1}{N}$ for KL divergence in our plots. Furthermore, the win rate of Bo$N$ over the reference model can be computed analytically and is equal to $\frac{N}{N+1}$.

We visualize the win rate vs. KL curves in Fig. 4(a), and Fig. 4(b) the average rewards of generations under ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color
[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}
}}}$ vs. the KL divergence. As expected, Bo$N$ is the most effective approach; however, this comes at an extra inference cost that grows with $N$. We observe that among the fine-tuning methods, our variational approximation to Bo$N$ gets closest to the performance of Bo$N$, as it appears more often on the Pareto front of the two curves compared to other methods. Notably, we observe that DPO performs better than PPO in terms of win rates but worse in terms of average rewards; this could be attributed to the contrastive nature of DPO’s loss function.

#### DPO.

Direct preference optimization (DPO; Rafailov et al., ) is a popular alternative to RLHF that does not require training a reward model. Following DPO’s experimental setup, we generate $6$ reviews per prompt and use the resulting $12$ pairwise comparisons per prompt to construct DPO’s contrastive loss.(^8^88One could argue that DPO has a slight advantage over other methods in this setup since it has seen $6$ unique generations per prompt during training, while the others only have seen one (or $2$ with BoNBoN). Nevertheless, we observe that vBo$N$ is more effective than DPO.)

### 5.1 Error in Estimating log ⁡ F ⁢ ( ⋅ ) F ⋅ \log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{%
F}}(\cdot) roman_log roman_F ( ⋅ )

We empirically quantify the error when estimating $\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{
F}}(\cdot)$ for a finite number of i.i.d samples from ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup
{ref}}}$. To get a better intuition on the error of our estimators, in Fig. 2, we visualize the estimators for $3$ different prompts: one adversarial prompt (left plot), where the prompt itself has a negative sentiment, one neutral prompt (middle plot), and one prompt with a positive sentiment (right plot). We vary the number of Monte Carlo samples from $10$ to $600$. We observe that for all the $3$ prompts, the estimated CDF hardly changes after $200$ samples. When using the adversarial prompt, we observe that the reward distribution is negatively peaked, and the estimated CDF does not change after taking only $100$ samples.

We then quantify the change in the estimator by performing a two-sample Kolmogorov–Smirnov test (Hodges, ). The test measures the closeness of two empirical cumulative distribution functions. Concretely, the test statistic is

$$ $\sup_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}}\in{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\Sigma}^{*}}\left|\widehat{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}}_{M_{1}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}- \widehat{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{ \mathrm{F}}}_{M_{2}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\right|,$ (11) $$

where $\widehat{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{
\mathrm{F}}}_{M_{1}},\widehat{\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}}_{M_{2}}$ are estimated CDFs from $M_{1}$ and $M_{2}$ samples respectively. The statistics show the magnitude of the difference between the two empirical distributions of samples. The null hypothesis is that the two distributions are identical.

Table: Table 1: Measuring the estimation error with increasing the sample size. After $250$ samples, the estimated CDF is unchanged for all the prompts.

In Tab. 1, for each sample size $M$, we compare the estimated CDF with $M$ samples to the estimated CDF with $600$ samples. If the two distributions are identical according to the test, we can reliably use the $M$ sample to estimate the CDF. We report the number of prompts (out of $5000$ prompts) for which we reject the null hypothesis, meaning that the distributions are not identical. Furthermore, for those prompts, we report the average test statistics and $p$-values. In general, for very few prompts, the null hypothesis is rejected. Moreover, with $250$ samples, the estimated CDFs are identical to the estimated CDF with $600$ samples for all prompts.

## 6 Conclusion

Motivated by the effectiveness of the Bo$N$ algorithm, we formally derive a variational approximation to the distribution induced by Bo$N$ algorithm via fine-tuning language models. Our analysis highlights the similarities and distinctions between the variational Bo$N$ objective and the KL-constrained RL objectives. Our empirical findings reveal that models fine-tuned using the variational approximation to Bo$N$ not only attain high reward values but also maintain proximity to the reference models. Crucially, inference on the fine-tuned models with the vBo$N$ objective remains as cost-effective as inference on the original reference model.

## Acknowledgements

We thank Ahmad Beirami for the fruitful discussion in the early stages of this project. Afra Amini is supported by the ETH AI Center doctoral fellowship.

## Appendix A Proof of Prop. 1

See 1

###### Proof.

The proof follows Casella & Berger (, Theorem 5.4.3). To compute ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}})$, we first define two events: (i) the event that all $N$ samples have rewards less than or equal to ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$, and (ii) the event that all $N$ samples have rewards less than ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$. The probability of those events is as follows:

$$ $\displaystyle p_{1}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}\boldsymbol{y}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=} }}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathbb{P} }(\text{all $N$ samples have rewards $\leq{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$})=\Big{(}\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}+{\color [rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}} ({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol {y}})\Big{)}^{N}$ (12a) $\displaystyle p_{2}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}\boldsymbol{y}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=} }}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathbb{P} }(\text{all $N$ samples have rewards $<{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$})=\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N}.$ (12b) $$

Note that for Eq. 15a to hold, we need the assumption that the reward function is a one-to-one mapping.(^11^1111If the reward function is not a one-to-one mapping, we need to devise a tie-breaking strategy. See App. B for further discussion.) Furthermore, given this assumption, ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}})$ is the probability that *at least* one of the sampled strings out of $N$ samples have the reward exactly equal to ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$ and the rest of the samples have rewards less than or equal to ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$. Given how we defined $p_{1}$ and $p_{2}$, we have ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{
bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}})=p_{1}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{
rgb}{0,0,0}\boldsymbol{y}})-p_{2}({\color[rgb]{0,0,0}\definecolor[named]{
pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})$.

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{ bon}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})=\Big{(}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}+{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big{)} ^{N}-\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm {F}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r }({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})\big{)}^{N}=\sum_{i=1}^{N}{N\choose i}\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})^{i}.$ (13) $$

∎

###### Proof.

## Appendix B Strategies for Non-Injective Reward Functions

If the reward function is not a one-to-one mapping, we need a tie-breaking strategy for Bo$N$ algorithm. We formalize this as defining a total order ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\prec_{{
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}}}$ on ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\Sigma}^{*}$ as follows: for any two strings ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}_{1}$ and ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}_{2}$, if ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}_{1})
<{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}_{2})$ then we have ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}_{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\prec
_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}}}{
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y
}}_{2}$. If ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}_{1})
={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[
rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}_{2})$ then ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}_{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\prec
_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}}}{
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y
}}_{2}$ only if ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}}_{1}\prec{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}
\boldsymbol{y}}_{2}$, where $\prec$ is some arbitrary but fixed total order, e.g., lexicographic order. Therefore, we define $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}(
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{
y}})$ as

$$ $\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}( {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ y}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathbb{P}}\big{(}{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}^{\prime} {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\prec_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}}}{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\big{ )}.$ (14) $$

We then need to define the two events and their probabilities, $p_{1}$ and $p_{2}$, given this total order on strings, as follows:

$$ $\displaystyle p_{1}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}\boldsymbol{y}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=} }}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathbb{P} }(\text{all $N$ samples are }{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\preceq_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}}}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})=\Big{(}\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\big{)}+{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})\Big{)}^{N}$ (15a) $\displaystyle p_{2}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}\boldsymbol{y}})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=} }}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathbb{P} }(\text{all $N$ samples are }{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\prec_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}}}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})=\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\big{)}^{N}$ (15b) $$

The rest of the proof is the same as with the one-to-one reward functions.

## Appendix C Proof of Thm. 2

See 2

###### Proof.

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor} {rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\boldsymbol{\theta}}}}\mid\mid{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{bon}}}\big{)}=\operatorname*{{\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}} }}}\Big{[}\log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}\boldsymbol{y}})-\log{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{bon}}}({\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big{]}$ (16a) $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\log\sum_{i=1}^{N}{N\choose i}\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})^{i}\Big{]}$ (16b) $\displaystyle\leq\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\sum_{i=1}^{N}\log{N\choose i}\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})^{i}\Big{]}$ (16c) $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\sum_{i=1}^{N}\log{N\choose i}-\sum_{i=1}^{N}\log\color[rgb]{ 0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big {)}^{N-i}-\sum_{i=1}^{N}\log{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb]{0,0,0}\definecolor [named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})^{i}\Big{]}$ (16d) $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\sum_{i=1}^{N}\log{N\choose i}-\log\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\sum_{i= 1}^{N}(N-i)-\log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\pi_{\textup{ref}}}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\sum_{i=1}^{N}i\Big{]}$ (16e) $\displaystyle\leq\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\frac{N(N-1)}{2}\log\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}-\frac{N(N+1)}{2}\log{\color [rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}} ({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol {y}})\Big{]}$ (16f) $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\frac{N(N+1)}{2}\log{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb]{0,0,0}\definecolor [named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})-\frac{N(N-1)}{2}\log\color [rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(} {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big {)}\Big{]}$ (16g) $\displaystyle=\frac{N(N+1)}{2}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}\big{)}+\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[}\frac{-(N+2)(N-1)}{2} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\frac{N(N-1)}{2}\log\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\Big{]}$ (16h) $\displaystyle=\frac{N(N+1)}{2}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}\big{)}+\frac{(N+2)(N-1)}{2}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathrm{H}}\big{(}{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\big{)}-\operatorname*{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_ {{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}}\Big{[}\frac{N(N-1)}{2}\log\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\Big{]}$ (16i) $$

In Eq. 16c, because $-\log(x)$ is convex for $x\geq 0$, we applied Jensen’s inequality to obtain the upper bound.
Abstracting away from the three multiplicative factors, naming them $\gamma$, $\alpha$ and $\beta$, we end up with the following function

$$ $\!\!\!{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \mathcal{J}^{\textsc{vBoN}}}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}})=-{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\big{(}{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{ 0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}} \mid\mid{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_ {\text{bon}}}\big{)}\geq\gamma\operatorname*{{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\log \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}} \big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y }})\big{)}-\alpha{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\mathrm{H}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}}}})-\beta{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\left({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}\right),$ (17) $$

which is a bound for some settings of $\gamma$, $\alpha$ and $\beta$.
∎

###### Proof.

## Appendix D Proof of Thm. 3

See 3

###### Proof.

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0 }D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor} {rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\boldsymbol{\theta}}}}\mid\mid{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{bon}}}\big{)}=\operatorname*{{\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[ rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}} }}}\Big{[}\log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}\boldsymbol{y}})-\log{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{bon}}}({\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big{]}$ (18a) $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\log\sum_{i=1}^{N}{N\choose i}\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})^{i}\Big{]}$ (18b) $\displaystyle\leq\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\sum_{i=1}^{N}\log{N\choose i}\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ ref}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})^{i}\Big{]}$ (18c) $\displaystyle\leq\underbrace{\operatorname*{{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\sum_{i=1}^{N}\log\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[ named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-i}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})^{i} \Big{]}}_{=-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} L_{1}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{\theta}})}$ (18d) $\displaystyle\leq\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}{\mathrm{F}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}^{N-1}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\Big{]}$ (18e) $\displaystyle=\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{ \theta}}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0} \boldsymbol{y}})-\log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{ rgb}{0,0,0}\pi_{\textup{ref}}}({\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})-(N-1)\log\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb] {0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\Big{]}$ (18f) $\displaystyle={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}\big{)}-(N-1 )\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[}\log\color[rgb]{0,0,0 }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{F}}\big{(}{\color[rgb ]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}})\big{)}\Big{]} \mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}-{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}({\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}).$ (18g) $$

The inequality in Eq. 18e stems from the fact that we drop positive terms in the summation and only keep the first term. Therefore, the lower bound for our objective is:

$$ ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\mathcal{J}^ {\textsc{vBoN}}}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{ 0,0,0}\boldsymbol{\theta}})=-{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{ \color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\text{ bon}}}\big{)}\geq(N-1)\operatorname*{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\mathbb{E}}}_{{\color[rgb]{0,0,0}\definecolor[named ]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{y}}\sim{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}}\Big{[} \log\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}{\mathrm{ F}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}r} ({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\boldsymbol {y}})\big{)}\Big{]}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb }{0,0,0}D_{\textsc{kl}}}\big{(}{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\pi_{{\color[rgb]{0,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0,0}\boldsymbol{\theta}}}}\mid\mid{\color[rgb]{0,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pi_{\textup{ref}}}\big{)}.$ (19) $$

∎

###### Proof.

## Appendix E Hyperparameters

To visualize the trade-off between the expected rewards and KL divergence, we vary the degree of the visualization using the following hyperparameters for each method:

- •
Bo$N$-SFT: $N\in[10,50,90,130,170,210,250,290,330,370,410,450,490,530,570,600]$ with $2$ different seeds, resulting in $32$ runs.
- •
PPO: $\beta\in[0.005,0.01,0.02,0.03,0.04,0.05,0.1,0.2,0.3,0.4,0.5,1.,2.,3.,4.,5.]$ with $2$ different seeds, resulting in $32$ runs.
- •
DPO: $\beta\in[0.01,0.1,0.2,0.3,0.4,0.5,1.,2.,3.,4.,5.]$ with $3$ different seeds, resulting in $33$ runs.
- •
BoNBoN and vBo$N$: $N\in[1,2,3,4,8,16,32,64,128,256,512]$ with $3$ different seeds, resulting in $33$ runs.
- •
vBo$N$ with ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}$ bound: $\beta\in[0.005,0.01,0.02,0.03,0.04,0.05,0.1,0.2,$
$0.3,0.4,0.5,1.,2.,3.,4.,5.]$ with $2$ different seeds, resulting in $32$ runs. Note that comparing Eq. 6 and Eq. 1, we have $N=\frac{1}{\beta}+1$.

Figure: Figure 3: Comparing models trained with the vBo$N$ objective and its lower bound (${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}$). We observe that the performance of the two methods is very close to each other.
Refer to caption: x4.png

Figure: (a) $4\%$ of points on Pareto front belong to BoNBoN, $4\%$ to PPO, $42\%$ to DPO, and $50\%$ to vBo$N$.
Refer to caption: x6.png

## Appendix F Comparing the vBo N 𝑁 N italic_N Objective and L 2 subscript 𝐿 2 {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}} italic_L start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Lower Bound

We compare the performance of models fine-tuned with the vBo$N$ objective and its lower bound (${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}L_{2}}$) in Fig. 3. We observe that the performance of the models is very close to each other.

## Appendix G Additional Experiments with Bo N 𝑁 N italic_N -SFT

We further experiment with training with maximum likelihood objective on Bo$N$ generations when varying $N$. The results are depicted in Fig. 4. We observe that Bo$N$ diverges too much from the reference model compared to other fine-tuning methods for alignment.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Please see my comments in the Weakness part of the reviews.

Why BoNBoN is called with that name? Please explain.

“We visualize the win rate vs. KL curves in Fig. 6a, and Fig. 6b the average rewards of generations under πθ vs. the KL divergence”. Please mention that these figures are in the appendix.
soundness: 3
strengths: vBoN is a novel and effective approach converting BoN from an alignment-via-inference algorithm to an alignment-via-fine-tuning algorithm. Models fine tuned with the vBoN objective achieves high reward values closer to the BoN approach, while achieving probabilities closer to the reference model. Importantly, it is as cost-effective as inference on the original reference model. In comparison , the original BoN approach is N times more expensive.

Provided theoretical connections showing how vBoN is compared with other alignment objectives
summary: The best-of-N alignment strategy has proven very useful in generating text with high-rewards that still has a high probability under the reference model. Several studies have shown that BoN often outperforms models simply fine-tuned with RLHF. However, this improvement in BoN comes at computational overhead during inference. 

This paper proposes Variational BoN (vBoN), a scheme that converts BoN from an alignment-via-inference algorithm to an alignment-via-fine-tuning algorithm. Basically, vBoN  derives the probability distribution induced by the BoN algorithm and then approximates this distribution by minimizing the reverse KL divergence between the language model and the BoN distribution. The model is optimized for the vBoN objective using the PPO algorithm. 

The proposed objective is evaluated on controlled generation and summarization tasks, showing performance close to that of the BoN algorithm while being as cost effective as inference on the original reference model.
weaknesses: Section 2 and 3 can be improved significantly by improving the notations and explanations and by bringing important details from Appendix to the main part of the paper. Currently I often find these two sections a bit confusing as well as a bit hard to appreciate some of the claims the authors have made in the paper. For example, in Eq 4, F(r(y)) will be defined as F(r(y) ) = P (r(y) < r(y) ), using Eq 5?  With this I am not sure how the vBoN objective is insensitive to applying any monotonically increasing function to the reward values?

Another important weakness of the paper is the current evals in the paper. Despite using the standard benchmarks for controlled generation and summarization, the evaluation chose not to report on standard metrics along with rewards and proximity to reference model comparisons.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: - "It is invariant to applying any monotonically increasing function to rewards" might not be entirely correct. Although monotonicity and insensitivity to reward scale are indeed related, the exact nature of this relationship is still unknown.
- The extent of the loss introduced by using the Monte Carlo estimator to maximize the lower bound of Equation (6) compared to the original formula remains unclear.
- The models used in the experiments by the authors are relatively outdated. I 'm curious if this method could achieve similar results on more recent models, such as the LLaMA-3 series.
- The trend of vBoN changes relatively smoothly with temperature adjustments; what causes this smoother trend?
soundness: 3
strengths: - The authors conducted rigorous and thorough theoretical derivations in the paper, clarifying the process from the motivation behind the vBo𝑁 proposal to its transformation into an optimizable objective. This is highly beneficial for readers interested in optimization theory and can provide new insights for tackling more complex optimization problems.
- The vBo𝑁 method is highly effective. Moreover, despite the substantial theoretical derivations, the illustrations used by the authors to present results and compare methods are clear and easy to read, helping readers to quickly grasp the potential of vBo𝑁 for their applications.
summary: In this paper, the authors propose a novel optimization objective for reinforce ment learning in large language models: vBo𝑁. Inspired by the Bo𝑁 method during the inference phase, the authors have designed an innovative loss to aid model alignment training. Building on this, the authors have transformed the proposed loss into the easily optimizable vBo𝑁 by relaxing the optimization lower bound. The authors validated the potential of vBo𝑁 optimization on two tasks using the IMDB movie review dataset and the Reddit TLDR dataset, and compared it with other contemporary methods such as PPO and DPO, demonstrating the unique potential of the vBo𝑁 method.
weaknesses: - Less Persuasive Experiments: While we understand that conducting RLHF is always exceedingly costly, for instance, PPO requires maintaining four sets of model parameters, the fact that the validation of the vBo𝑁 method was only focused on movie review completion and text summarization datasets makes it lacks persuasiveness. We would like to understand the potential applications of vBo𝑁 in broader and more challenging tasks, such as code generation, mathematical problem solving, and multi-step reasoning. The experimental section of the paper is not as solid as the theoretical section.
- Lacking Efficiency Testing: One of the motivations behind the vBo𝑁 method is to address the additional overhead of the Bo𝑁 method during inference, which vBo𝑁 resolves by introducing additional training. Therefore, I believe that an analysis of the training costs of vBo𝑁 is a crucial issue that must be discussed in the paper. Based on the experimental results, I could even accept that the training efficiency of vBo𝑁 is slightly inferior to methods like PPO. Moreover, beyond absolute costs, relative costs are also worth considering, such as a comparison of the performance of vBo𝑁 and PPO under the same computational-power/time/data con straints. If the authors could address either of these two aspects, or preferably both, it would significantly enhance the completeness and the soundness of the paper.
- Several key symbols and terms in the formulas are not defined, making it challenging for readers to understand the equations' meaning. A glossary would greatly improve readability.
- In the "Summarization" section, the authors refer to the reward models with different names ("pythia-2.8B reward model" and "pythia-6.9B model"), but it’s unclear if these models differ in architecture or purpose (see Section 6).
- The experiments focus solely on summaries from the “relationship” and “relationship advice” subreddits for training and then evaluate performance on in-distribution and out-of-distribution Reddit posts.
- This paper provides inadequate detail when introducing the advantages and disadvantages of other alignment methods (such as RLHF and direct preference optimization). In particular, it lacks sufficient background information and details on how these methods are applied to text generation or summarization tasks , which may make it difficult for readers to understand the relative advantages of the methods proposed in this paper.
﻿
Others
-  In the paper, the authors refer to the input of the LLM as a ‘string’. Switching to the term ‘token’ would align better with most readers’ pref erence and expectations, especially there is no cross-tokenizer-aspect that requires natural language level operations in vBo𝑁.
- For those practitioners who are more focused on practical implementa tion, including a pseudocode for the vBo𝑁 alignment would enhance the readability of the paper. Moreover, vBo𝑁 does include more complex op erations beside the usual training pattern. I’d like to suggest authors to include one in the paper, even in the appendix.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1.Refer to the weakness 1 and 3, would you please further explain the efficiency of the method?
2.Refer to the weakness 2, would you please clarify the definition of your objective?
soundness: 2
strengths: The motivation of this article is quite clear, and it includes several experiments to support its claims. Additionally, the overall structure of the article is fairly complete, including some theoretical derivations.
summary: This paper proposes a more direct preference-align method vBoN for LLMs based on the Best-of-N approach. The authors construct a new fine-tuning objective function using the scoring results from a reward model. By directly aligning the output distribution of the LLMs to the output distribution of the Best-of-N method, the authors aim to simplify the BoN inference process and achieve better alignment efficiency compared to other preference alignment methods. Experiment results are demonstrated to try to validate the claims.
weaknesses: 1. The effectiveness of the vBon method is questionable. Although vBon utilizes reward model scoring to depict a target distribution closer to BoN, it requires a large number of samples (controlled by N or M in the article) to generate the corresponding preference data. The efficiency of this method is not high when the sample size is large.
2. The paper is hard to follow. Some definitions lack explanation and need clarification from the authors, such as the function F(.) used in Equations 4 and 5. 
3. There is a lack of more convincing experiments to show the significant enhancement of alignment efficiency.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. The sentence right below equation (6) (the vBoN objective) states that "This is an entropy-regularized objective, where we...*discourage* the model from having low entropy". And this can be seen clearly in the objective (to be maximized) as well. However, in the text below equation (9), which is a lower bound for the vBoN objective, it is mentioned that L1(\theta) further *encourages* the model to have low entropy. Can you provide an interpretation of why this L1 lower bound encourages low entropy, while the original vBoN objective encourages high entropy?

2. Legend labels, as well as axis labels and numbers, are missing from Figure 4, which is one of the more important figures in the paper. Legend labels are also missing from Figures 5 and 6.

3. The abstract mentions that finetuning with the vBoN objective is "analogous to mean-field variational inference", but this parallel is not discussed in the main text of the paper. 

4. In Section 5, the BoN-SFT baseline is considered, but its performance is not competitive since it has high KL divergence from the reference model. Was a KL-constrained version of BoN-SFT considered?

5. Like vBoN, both the the BoNBoN and BOND (Sessa et al, 2024) methods attempt to convert BoN to a finetuning-time alignment method. Why was BoNBoN, but not BOND, reported as a baseline in Section 5?

Nit: There is a typo at the end of Section 5, where the references to Fig. 6a and Fig. 6b should instead refer to Fig. 2a and Fig 2b.
soundness: 3
strengths: 1. Clear motivation: vBoN is naturally motivated from the goal of reaping the gains of BoN without incurring the inference-time computational overhead.

2. Strong theoretical grounding, and compelling comparison of vBoN lower bounds with the standard KL-regularized RL objective.

3. Sound experimental setup: The win rate/average rewards vs KL curves in Figure 2 show a clean comparison against several important baselines, and the breakdown of how often each method appears on the Pareto front was also a nice statistic to report. The ablation and analysis to understand sensitivity to number of samples for the logF() approximation in the vBoN objective (Figure 3 and Table 1) were also clean and well-presented.
summary: This paper proposes to "distill" the gains from the best-of-N (BoN) inference-time alignment algorithm during finetuning, thereby improving a LLM's alignment without incurring the (linear in N) inference-time costs of BoN. They do this by deriving the distribution induced by the BoN algorithm, then defining the finetuning objective (which they call vBoN) to minimize the model's reverse KL divergence to this distribution. On the theoretical front, they derive some lower bounds for this vBoN objective and show that these lower bounds resemble the standard KL-constrained RL objective. Through experiments on controlled sentiment generation and summarization, they empirically show that PPO using the vBoN objective is the most effective technique for alignment via finetuning (though inference-time BoN still outperforms all finetuning-time alignment methods).
weaknesses: 1. It is stated in the paper that, under some basic simplifying assumptions, the optimal distribution under the KL-regularized RL objective and the vBoN objective are asymptotically equivalent (Section 1, equation (2), Section 4). The paper also shows that lower bounds for the vBoN objective closely resemble the KL-constrained RL objective, and that models finetuned to maximize these lower bounds perform very similarly to those finetuned to maximize the vBoN objective. On the other hand, the paper shows that models finetuned to maximize the vBoN objective substantially outperform models finetuned to optimize the KL-constrained RL objective. This empirical evidence in some sense challenges the theoretical observations. Why, then (and under what conditions), is vBoN better than KL-constrained RL?

2. The paper demonstrates the effectiveness of vBoN on two tasks: Sentiment control (which is somewhat of a toy task) and Summarization (which is less of a toy task). However, several important baselines (e.g., DPO and BoNBoN) are only reported for the sentiment control task, and not for the summarization task. Why weren't these baselines included for the (less toy) summarization task?

See additional questions in the "Questions" section.

Meta-review: Best-of-N (BoN) aligns language models to human preferences by selecting the highest-reward sample from N outputs, but it is computationally expensive.  Variational BoN (vBoN) addresses this limitation by fine-tuning the model to approximate BoN’s distribution, thereby reducing inference costs while maintaining strong performance.

This paper is well-written and easy to understand.  Compared to BoN, vBoN demonstrates significantly higher inference efficiency.  The authors have incorporated reviewers' suggestions, including adding an efficiency analysis, improving clarity, and providing additional baselines.  These revisions enhance the quality of the work, and I believe the paper merits acceptance.

I also recommend that any additional experiments promised by the authors in their response to reviewers are thoroughly completed and included in the final version.

Decision: Accept (Poster)