Guaranteed Generation from Large Language Models

## Abstract

Abstract As large language models (LLMs) are increasingly used across various applications, there is a growing need to control text generation to satisfy specific constraints or requirements. This raises a crucial question: Is it possible to guarantee strict constraint satisfaction in generated outputs while preserving the distribution of the original model as much as possible? We first define the ideal distribution — the one closest to the original model, which also always satisfies the expressed constraint — as the ultimate goal of guaranteed generation. We then state a fundamental limitation, namely that it is impossible to reach that goal through autoregressive training alone. This motivates the necessity of combining training-time and inference-time methods to enforce such guarantees. Based on this insight, we propose GUARD , a simple yet effective approach that combines an autoregressive proposal distribution with rejection sampling.
Through GUARD ’s theoretical properties, we show how controlling the KL divergence between a specific proposal and the target ideal distribution simultaneously optimizes inference speed and distributional closeness. To validate these theoretical concepts, we conduct extensive experiments on two text generation settings with hard-to-satisfy constraints: a lexical constraint scenario and a sentiment reversal scenario. These experiments show that GUARD achieves perfect constraint satisfaction while almost preserving the ideal distribution with highly improved inference efficiency. GUARD provides a principled approach to enforcing strict guarantees for LLMs without compromising their generative capabilities.

## 1 Introduction

Large language models (LLMs) have demonstrated remarkable capabilities in generating human-like texts across a wide range of applications [, , ].
Due to their usefulness, LLMs
are being increasingly
integrated into various downstream services and critical decision-making processes [, , ]. However, this widespread adoption raises concerns about both the reliability and the safety of LLM outputs, especially in high-stake scenarios where unintended behaviors could have significant consequences []. Hence, it is crucial to address two key questions: (1) How can we guarantee that all generated sequences from these powerful models meet specific constraints or requirements? and (2) How can we achieve this while preserving the original model’s useful distribution as much as possible? These two primary questions naturally lead to a third, practically important, question: (3) How can we simultaneously obtain the two previous properties
at a limited inference cost?

Similar issues have been studied in the context of controlled text generation [],
where LLMs are conditioned on specific attributes to increase the likelihood of producing desired outputs.
However, the associated methods do not provide the means to ensure that all generated outputs strictly meet the desired constraints — a problem we refer to as guaranteed generation. This is the gap we seek to address here. Our primary objective is then to study, in-depth, the characteristics of guaranteed generation within theoretically tractable scenarios.
We attempt to clarify, both theoretically and experimentally, fundamental questions related to this critical topic, including how strict constraint enforcement affects the original properties of LLMs.

First, we formalize the concept of guaranteed generation over a
base LLM by introducing the notion of a gold distribution, $g$, i.e., the ideal distribution we target.
It
is
represented by a filtered energy-based model (EBM) [] that always satisfies the specified constraint $b$ — e.g., a binary filter function — while minimally diverging from the original distribution $a$ associated with the base LLM.
Although we can compute the probability $g(y)$ for any arbitrary text $y$, this does not imply the existence of an autoregressive model $a^{\prime}$ with the same distribution as $g$.
We present an impossibility theorem (Theorem 1), demonstrating that in fact an exact match of this ideal distribution $g$ through an autoregressive model is generally impossible.

Still, as we will see, it is possible to train an autoregressive model to approximate $g$. However, finding such an approximation that strictly satisfies $b$ is far from obvious in both theory and practice. This insight motivates the use
of inference-time methods such as Monte-Carlo sampling techniques.
These methods exploit such approximations as proposal models and can strictly guarantee $b$,
but they typically come with
high inference costs that make their adoption impractical.

In order to address these issues,
we propose GUARD,(^1^11The implementation of our framework, along with the code to replicate our experiments, will be made available soon.)
a simple framework for guaranteed generation that combines approximation of the ideal distribution $g$ into a proposal distribution $a^{\prime}$ with rejection sampling from the latter proposal.
We establish a theorem (Theorem 2) about the relationship among the proposal $a^{\prime}$, the GUARD output $g^{\prime}$, and the ideal distribution $g$ through information geometry, by using the Pythagorean theorem for Information Projections (I-projections) [].
As shown in Figure 1, this theorem states how it is possible to optimize both inference speed at sampling time (by improving the acceptance rate) and distributional closeness while strictly satisfying guarantees, by optimizing the approximation of the proposal $a^{\prime}$ towards $g$. We present several approaches for this approximation, stressing in particular the application to our situation of the Distributional Policy Gradient (DPG) technique [, , , , ] for training a parametric model to approximate an arbitrary unnormalized target distribution represented by an EBM.

To validate these theoretical concepts, we conduct experiments in scenarios where the base LLM $a$ rarely satisfies the constraint $b$.
We evaluate how closely our GUARD-based $g^{\prime}$ approximates the gold distribution $g$ while maintaining a high acceptance rate in two scenarios with extensive analysis: a scenario with lexical constraints requiring specific strings to be included, and a sentiment reversal scenario with a positive ending constraint for stories with a negative opening. We demonstrate the effectiveness of GUARD in these scenarios and highlight the benefits of a novel warm-start variant of DPG, which involves initializing the training of $a^{\prime}$ using constraint-aware prompting
to bypass inefficient early stages of the proposal. Furthermore, we analyze how the original properties of the base model are degraded when the proposal diverges from the ideal distribution, thus connecting our theoretical results with empirical findings.

In summary, the main contributions of the paper are:

- 1.
The definition of the distribution $g$ as the ideal target for guaranteed generation; the proof that $g$ is, in general, unattainable by autoregressive models, and therefore by fine-tuning alone; the need to complement training-time methods with inference-time methods.
- 2.
The proposal of the GUARD framework, combining a method for approximating $g$ by an autoregressive model $a^{\prime}$ with a rejection sampler for enforcing the constraint; a proof that $\text{KL}(g||a^{\prime})$ controls both the efficiency of this sampler and its divergence relative to $g$.
- 3.
Experiments with lexical and positive ending constraints, demonstrating that GUARD both significantly improves the acceptance rate and provides an excellent approximation to $g$; an analysis of the DPG and prompting approximation techniques, and the apparent limitations of prompting with respect to the diversity of $g$ in contrast to DPG; the warm-start combination of both techniques to speed up the approximation process.

## 2 Formalization of Guaranteed Generation

### 2.1 Definition of the gold model

Suppose that we have an autoregressive language model $a$ with vocabulary $V$, and let $a(y)$ be the probability of the output sequence $y\in{\mathcal{Y}}=V^{*}$.(^2^22 An autoregressive model such as $a$ can be seen both as a generator of sequences $y\in{\mathcal{Y}}$ (that is, as a sampler) and as a probability distribution over ${\mathcal{Y}}$, where $a(y)$ is the probability of $y$. We sometimes use the notation $a$ both for the generator and for the distribution, when there is no risk of confusion. Note that many distributions, such as $g$ below, do not have this double nature: $g$ is not directly associated with a sampler.)
Our goal is to transform $a$ into a model $p$
such that whenever $p$ generates $y$, then $y$ satisfies the *hard constraint* $b$, where $b$ is a binary function over ${\mathcal{Y}}$. Formally, this means that $p(y)>0\Rightarrow b(y)=1$ for any $y\in{\mathcal{Y}}$. In other words, we want $p$ to filter out outputs that do not respect the constraint $b$.

Clearly,
the above
filtering requirement can be satisfied by many models; in particular, it would be trivially satisfied by any model generating only a single sequence
$y$ fulfilling the constraint. So, additionally, we desire the target model $p$ to minimally distort the distribution associated with $a$. This criterion naturally leads to the following model $g$, which we will refer to as the gold filtered model, or simply gold model:

$$ $\displaystyle g(y)\propto a(y)\,b(y),$ (1) $$

where $g(y)$ is the normalized distribution proportional to the value $a(y)\,b(y)$, in other words $g(y)=\frac{1}{Z}a(y)\,b(y),\text{ with }Z=\sum_{y\in{\mathcal{Y}}}a(y)\,b(y)$.

It is easy to see that $g$ is simply the distribution $a$ renormalized over the set of $y$’s that satisfy the constraint $b(y)=1$.
We can characterize $g$ equivalently as follows (see App. A.1 for details):

- •
$g$ is the distribution $a$ conditioned by the fact that $y$ satisfies $b$, i.e., $g(y)=a(y\ |\ [b(y)=1])$.
- •
$g$ is the I-projection [] of $a$ on the linear space
${\mathcal{C}}$ of distributions $p$ that respect the constraint everywhere, that is, such that $\forall y\in{\mathcal{Y}},p(y)>0\Rightarrow b(y)=1$ (in Figure 1, ${\mathcal{C}}$ was informally denoted by “$b=1$”). In other words, $g$ is the distribution $p$ in ${\mathcal{C}}$ that minimizes the divergence $\text{KL}(p||a)$.

### 2.2 From gold model to sampler

While $g$ is a well-defined distribution, it is not immediately associated with a sampler, that is, to a procedure for generating samples following the distribution $g$. In particular, $g$ is not defined in an autoregressive form (which would directly result in a sampler), but in the form of an Energy-Based Model [], as the distribution corresponding to the normalization of the product $a(y)\,b(y)$.(^3^33Formally, an EBM is any distribution $p$ presented in the form $p(y)\propto e^{-E(y)}$, where $E(y)$ is the “energy” of $y$. In other words, $p(y)=\frac{1}{Z}e^{-E(y)}$ where $Z$ is a normalization constant. Equivalently, $p$ can be presented in the form $p(y)\propto P(y)$ where $P$ is a nonnegative function of $y$ (also called a “potential”). In our specific case, this potential is equal to $a(y)\,b(y)$.)

In order to associate a sampler to $g$, several approaches are possible. The first one consists of trying to find an autoregressive model (ARM) whose distribution is identical to $g$.
Unfortunately, this is impossible in general, as we show below.
Alternatively,
an ARM $a^{\prime}$ could be considered in order to provide a
“good enough” approximation to $g$, but it is far from obvious how to ensure that such a sampler will both satisfy the constraint $b$ and remain close to the gold model. A third approach is
to use the ARM $a^{\prime}$ as a “proposal” inside some Monte-Carlo (MC) inference-time procedure. The
framework that we propose, GUARD, is of this kind. It strictly guarantees the constraint and attempts to remain close to the gold model, while minimizing inference costs.

### 2.3 Limits of autoregressive models for filtering purposes

Let’s consider the following simple formal example, to build some intuition. Let $a$ be a standard ARM and suppose that our constraint $b(y)$ is satisfied if and only if the sequence $y$ does not contain the token “bad”. Is it possible to find an ARM $a^{\prime}$ such that the distribution associated to $a^{\prime}$ is equal to $g$? A first attempt could be to sample a large dataset of $y$’s from $a$, delete all $y$’s that do contain the token “bad”, and fine-tune $a$ on the resulting dataset to obtain $a^{\prime}$. However, while $a^{\prime}$ would tend, to some extent, to avoid “bad” more often than $a$, it would not strictly guarantee this avoidance: standard fine-tuning methods never result in a softmax that is exactly zero on any token, including the token “bad”, implying that the generation of an invalid output would remain possible.(^4^44It should be noted more generally that because fine-tuning a model $a$ into $a^{\prime}$ never puts a zero probability mass on any token, any sequence $y$ such that $a(y)>0$ is still such that $a^{\prime}(y)>0$, that is, fine-tuning can never fully eliminate any sequence. This implies that all techniques relying solely on fine-tuning — e.g., PPO [] or DPO [] — are limited in their ability to enforce strict constraints.)

However, fine-tuning is not the only way to produce autoregressive models. Another approach would be as follows: we could, at each timestep $t$ of the generation of $y$, remove the token “bad” from the softmax vector $p(\cdot|y_{<t})$, and renormalize this vector to sum to 1.
This would result in an ARM $a^{\prime}$, strictly satisfying the constraint, but would actually cause $a^{\prime}$ to have a distribution different from $g$, a phenomenon detailed in App. A.2.

So, obtaining an autoregressive model with distribution $g$ is not obvious, even in very simple cases as above, and we discuss in App. A.2 why this is a widespread problem in practice. As we mention there, we are only aware of very few special cases where the problem is solvable, but, as we will now discuss, we do have a clear negative result: the problem has no general solution.

##### A fundamental impossibility result

The following result was inspired by the pioneering work of Lin et al. [] on the general limitations of autoregressive models. See App. A.3 for a precise statement and self-contained proof, adapted to the case of filtered models.

###### Theorem 1 .

There exists an autoregressive model $a$ and a binary predicate $b$ such that the gold model $g$ associated with $a$ and $b$ cannot be obtained by an autoregressive model $a^{\prime}$.

Proof intuition. We construct an $a$ that generates sequences encoding an instance of an NP-hard problem followed by a candidate solution to that problem, and a $b$ that checks (in polynomial time)
the validity of the proposed solution. Then $g$ is a distribution whose support consists of all the sequences encoding a problem instance and a valid solution. If $a^{\prime}$ were an ARM that corresponded to $g$, then it would be possible to check in polynomial time whether a given problem instance carried a non-zero probability mass, and therefore to decide the satisfiability of the problem instance, in contradiction to the generally accepted conjecture $P\neq NP$.

###### Theorem 1 .

### 2.4 Claim: inference-time methods are needed

While it can be difficult or even impossible to exactly fit $g$ with an ARM $a^{\prime}$, it is still possible to approximate it with such a model and this can be done with various approaches such as (i) training $a^{\prime}$ through SFT or DPG [], or else (ii) through prompting $a$ with an instruction or few-shot examples attempting to express the constraint $b$ in natural language.
While the resulting model $a^{\prime}$ has the advantage that it can be used efficiently for generation, it typically does not strictly enforce $b$, our primary requirement, and we are not aware of general techniques that would allow an ARM $a^{\prime}$ to strictly enforce $b$ while simultaneously limiting the distortion of $a^{\prime}$ relative to $g$.

Claim: To achieve this objective, we posit that one has to rely on some inference-time Monte-Carlo (MC) algorithm that exploits the ARM approximation $a^{\prime}$ as a proposal sampler but only retains samples satisfying the constraint $b$.

Such MC samplers can take different forms, from simple approaches such as Rejection Sampling to more involved MCMC techniques such as Metropolis-Hastings [].
The sampler used in GUARD, that we present now,
is a basic form of rejection sampling, but with attractive properties compared to other approaches.

## 3 The GUARD framework and its properties

Inside the GUARD framework, we assume that $a^{\prime}$ is some autoregressive approximation to $g$.
The GUARD sampler
(Algorithm 1) is then an elementary form of rejection sampling.
We assume
that there exists at least one $y\in{\mathcal{Y}}$ s.t. $a^{\prime}(y)>0$ and $b(y)=1$. We then sample from $a^{\prime}$ until we find such a $y$, and return it. Such a procedure obviously guarantees that any sample $y$ satisfies the constraint, our fundamental requirement.

Figure: Algorithm 1 GUARD sampler

We remark that in the special case where $a^{\prime}=a$, we are simply sampling from $a$ until we satisfy the constraint, and it is then easy to show that the sampler we obtain has exactly the same distribution as $g$ (see App. A.4). In this case, the GUARD sampler meets two criteria: (1) it strictly satisfies the constraint, and (2) its associated distribution is close to $g$ — in fact, it is equal to $g$.
However, the third important criterion, efficiency, falls short when $a$ rarely satisfies the constraint $b$, which is equivalent to $\text{KL}(g||a)$ being large (see Eq. 7 in App. A.5).

By approximating $g$ with some $a^{\prime}$ that has a small $\text{KL}(g||a^{\prime})$ relatively to $\text{KL}(g||a)$ — in other words, $a^{\prime}$ is a better approximation to $g$ than $a$ — we can greatly improve the efficiency of GUARD, by sacrificing exact distributional match to $g$. Our core Theorem 2 below (see also the rightmost panel of Figure 1) characterizes this trade-off formally.
Here, for a given $a^{\prime}$, $g^{\prime}=g^{\prime}_{a^{\prime}}$ denotes both the sampler resulting from Algorithm 1 and the associated distribution. $AR_{a^{\prime}}\doteq\mathbb{E}_{y\sim a^{\prime}}b(y)$ denotes the acceptance rate of the algorithm, that is, the probability that
a sample from $a^{\prime}$ respects constraint $b$ and thus is accepted (see App. A.5).

###### Theorem 2 .

We have $\text{KL}(g||a^{\prime})=\text{KL}(g||g^{\prime})+\text{KL}(g^{\prime}||a^{
\prime})=\text{KL}(g||g^{\prime})-\log AR_{a^{\prime}}$.

Proof sketch (see App. A.6 for details). The first equality results from the fact that $g^{\prime}$ is the I-projection of $a^{\prime}$ on ${\mathcal{C}}$ and from the Pythagorean identity for I-projections [].
The second identity is obtained from a simple derivation showing that $\text{KL}(g^{\prime}||a^{\prime})=-\log Z^{\prime}=-\log AR_{a^{\prime}}$, where $Z^{\prime}$ is the partition function $Z^{\prime}\doteq\sum_{y\in{\mathcal{Y}}}a^{\prime}(y)\,b(y)$.

Interpretation: $\text{KL}(g||a^{\prime})$ is a measure of the divergence of $a^{\prime}$ from $g$. As we saw earlier, it is typically impossible to narrow it to 0 0, but we can reduce it by approximation techniques. $\text{KL}(g||g^{\prime})$ measures the divergence of the sampler $g^{\prime}$ from the gold distribution $g$, and $-\log AR_{a^{\prime}}\in[0,\infty)$ measures the “inefficiency” of the sampler, where $-\log AR_{a^{\prime}}=0$ corresponds to a maximum acceptance rate of $1$. Because KL divergences are non-negative, $\text{KL}(g||a^{\prime})$ is an upper bound of both $\text{KL}(g||g^{\prime})$ and $-\log Z^{\prime}$, which means that controlling the approximation quality of $a^{\prime}$ relative to $g$ is the key to both controlling the quality of $g^{\prime}$ relative to $g$ and also the efficiency of Algorithm 1.

###### Theorem 2 .

##### Approximating the target distribution

This last observation motivates the need to minimize $\text{KL}(g||a^{\prime})$ to obtain a suitable $a^{\prime}$. We consider several methods to achieve this. (1) Prompting can be used to encourage the output to respect the given constraint — a technique we refer to as constraint-aware prompting (CAP). (2) Another approach consists in using Supervised Fine-Tuning (SFT).
This involves sampling a large number of $y$’s from $a$, filtering them based on $b$ to create a dataset representing the $g$ distribution, and then fine-tuning $a$ on this dataset. However, when $AR_{a}$ is low, very few samples are retained, making this approach inefficient and difficult to use in practice, although it may still be useful for scientific analysis and comparisons.
(3) The last method we consider is the Distributional Policy Gradient (DPG) technique for general EBMs [, , ] here applied to the specific case of filtered models. This method samples $y$ from a proposal $a^{\prime}$ initialized with $a$ and updates $a^{\prime}$ by performing gradient descent on $\text{KL}(g||a^{\prime})$.
It is important to mention that one key difference between DPG and SFT is that DPG is adaptive; as the proposal $a^{\prime}$ approaches $g$, the frequency and quality of gradient updates increase, making it more efficient than SFT [].
While the original DPG technique
shares SFT’s initial low $AR_{a}$ during early training, we can improve this behavior
by using constraint-aware prompting
for the initial proposal — a method we refer to as “warm-start DPG” — to accept a rich amount of samples, thereby providing abundant gradient signals.
Based on our experiments, this combination appears to be the most effective for guaranteed generation, and it is the one that we advocate. The full algorithm for warm-start DPG training in GUARD is provided
in App. B as
Algorithm 2.

##### GUARD vs. MCMC and related sampling techniques

Simple rejection sampling as in Algorithm 1 might at first sight seem naive relative to some more sophisticated techniques, such as Markov Chain Monte Carlo (MCMC) approaches. One such technique, Independent Metropolis-Hastings (IMH) [], can use an autoregressive model as its proposal, and construct a random walk that converges to $g$ in the limit, while still guaranteeing a strict respect of the constraint. On inspection, however, each individual move of this random walk implies — and therefore is at least as costly as — a full run of Algorithm 1. We
report in App. F experiments showing that IMH converges very slowly, making it an impractical approach, and motivating our choice of Algorithm 1 combined with a focus on finding a good approximator $a^{\prime}$ to $g$.
We also present in App. F some experiments based on Quasi-Rejection Sampling (QRS) [] — a technique also converging to $g$ in the limit — which, while still being more costly than Algorithm 1, is shown to present certain advantages over IMH.

## 4 Experiments

In this section, we describe the experiments conducted to evaluate the GUARD framework on simple
guaranteed generation scenarios.
As discussed in the previous section, we compare three approximation methods within GUARD: CAP, SFT, and DPG.(^5^55Training and evaluation were done using the disco toolkit: [https://github.com/naver/disco](https://github.com/naver/disco).) We have three main desiderata on GUARD’s outputs: (1) strict adherence to constraint $b$, (2) similarity to the gold distribution $g$, and (3) limited inference cost.(^6^66 In terms of computation costs, reducing the inference cost related to the acceptance rate $AR_{a^{\prime}}$ is our main focus, because this is the one involved in deployment. However, we also consider the training cost, in terms of the sampling budget required for training the approximation $a^{\prime}$, which is independent of the inference cost.)
Since $g^{\prime}$ is filtered by rejection sampling in GUARD and thus satisfies the first criterion by definition, our main metrics in the experiments are the distributional closeness $\text{KL}(g||g^{\prime})$ and the inference cost defined by the acceptance rate $AR_{a^{\prime}}$. Additional details about our metrics are provided in App. C.

We are considering two scenarios, text generation under a lexical constraint (Section 4.1) and story generation under a positive ending constraint for sentiment reversal (Section 4.2), where samples from the base LLM $a$ rarely respect the constraint $b$ (i.e., $\text{KL}(g||a)=-\log AR_{a}$ is high).(^7^77 If the acceptance rate of the base LLM $a$ is high enough, we can simply perform rejection sampling on proposal $a$ without any training. However, when violations of constraint $b$ are frequent, alternative methods are needed. This is the setting we explore in our experiments.)

### 4.1 Unconditional generation with lexical constraints

##### Task description

Our first task is to generate a text under a lexical constraint, i.e., such that a specific keyword is included in the generation.
The LLM generates a text $y$ of 30 tokens, starting with the $\langle bos\rangle$ token. The lexical constraint
$b(y)$ then either rejects or accepts this generated text based on whether it contains the string of the keyword.

We use Gemma-2B [] as our base LLM $a$. We define the constraint $b$ as the binary function that is equal to 1 if and only if the generated text $y$ contains the string “amazing”, following the experimental setup from Khalifa et al. []. This constraint has an acceptance rate $AR_{a}$ of approximately 0.0023 under the original distribution $a$ with ancestral sampling and a temperature of 1.

Figure: Figure 2: Evolution of $\text{KL}(g||a^{\prime})$ as a function of the number of samples used for training with lexical constraints.
Refer to caption: x2.png

##### Empirical results

Figure 2 illustrates the learning curves of $\text{KL}(g||a^{\prime})$ for various methods according to the sampling budget, i.e., the number of samples drawn from the proposal during training.
SFT, which involves sampling $y$ from $g$, struggles due to the low $AR_{a}$, resulting in a limited supply of training data, relatively to the budget. Moreover, as training progresses, the increasing discrepancy between the policy $a^{\prime}$ and the sampler $a$ (due to the off-policy nature of SFT) causes it to reach a plateau and stop improving after a certain point.
In contrast, DPG shows steady and stable improvement, ultimately achieving a better $\text{KL}(g||a^{\prime})$ than SFT. We explain this superior performance through two key factors: (1) adaptive proposal — the proposal distribution $a^{\prime}$ in DPG adaptively becomes closer to the target distribution $g$ over time; and (2) increasing $AR_{a^{\prime}}$ — as the proposal $a^{\prime}$ becomes better, the acceptance rate $AR_{a^{\prime}}$ increases, providing more samples and thus a richer signal for estimating gradients.
Additionally, warm-start DPG, i.e., initializing DPG with $a(\cdot|\text{CAP})$ to leverage a constraint-aware prompt, encourages the model to generate “amazing”,
improves the initial acceptance rate, and allows us to avoid the slow early exploration stage where training samples are scarce. This results in consistently better performance throughout the whole training process.

Figure: Figure 3: Results in terms of $\text{KL}(g||g^{\prime})$ (i.e., distributional distance) and $-\log(AR_{a^{\prime}})$ (i.e., inference cost) in the lexical constraint scenario. The dotted line indicates their sum, $\text{KL}(g||a^{\prime})$, as stated in Theorem 2.
Refer to caption: x3.png

Figure 3 depicts the results of the trade-off between $AR_{a^{\prime}}$ and $\text{KL}(g||g^{\prime})$ under a fixed sampling budget (800K). The point labeled as $\tilde{g}$ reflects the upper-bound performance associated to an ideal (but non-existent) sampler of the gold model, which would have no distributional difference with
$g$
while achieving an acceptance rate of 1 (i.e., a 435$\times$ improvement with respect to $a$).
Both DPG and SFT show significantly improved acceptance rates in comparison to $a$. However, DPG consistently demonstrates superior distributional
similarity, as measured by $\text{KL}(g||g^{\prime})$.
Interestingly, the CAP approach enforces a high acceptance rate without any training procedure, but it results in
distributions that greatly diverge
from the target $g$.
Nevertheless, when DPG is initialized with $a(\cdot|\text{CAP})$, it leverages the high initial $AR_{a^{\prime}}$ to enable sufficient sampling. This, in turn, allows for a rapid reduction of $\text{KL}(g||g^{\prime})$.
As a result, the figure shows that this warm-start DPG strictly Pareto-dominates all SFT points.
This means that for any given point representing an SFT result, warm-start DPG offers a better acceptance rate and a lower KL divergence simultaneously.
In summary, the GUARD algorithm increases the acceptance rate by almost 180$\times$ compared to the base LLM $a$ while maintaining minimal distributional distortion.

##### Analysis

Figure: Figure 4: Left: UMAP visualization of the samples generated by different approaches in the lexical constraint scenario. Right: distribution of the relative position for the string “amazing” within the full sequences generated by each method. (Best viewed in color.)
Refer to caption: x4.png

This section analyzes the deeper phenomena underlying the $\text{KL}(g||g^{\prime})$ results shown above.
First, we visualize in Figure 4 the repartition of samples from the gold distribution $g$, DPG-based $g^{\prime}$, and CAP-based $g^{\prime}$ using UMAP [] after embedding them through DistilBERT [].
DPG-based $g^{\prime}$ and gold distribution $g$ overlap in similar regions, while the samples from CAP-based $g^{\prime}$ cluster in a distinct area. This qualitative observation goes in line with the quantitative results from Figure 3, which reported a better $\text{KL}(g||g^{\prime})$ for DPG-based $g^{\prime}$ compared to CAP-based $g^{\prime}$.
Additionally, the CAP-based samples show reduced diversity (i.e., lower coverage). To quantify this loss of diversity, we measured Self-BLEU [], i.e., the $n$-gram similarity within the same sample group, and the average semantic similarity between sample embeddings.

**Table 1: Diversity of the samples generated by each approach in the lexical constraint scenario. Lower scores indicate a greater diversity.**
| Approach | Self-BLEU $\downarrow$ | Semantic<br>similarity $\downarrow$ |  |  |  |
| --- | --- | --- | --- | --- | --- |
| 2-gram | 3-gram | 4-gram | 5-gram |  |  |
| Gold $g$ | 0.315 | 0.117 | 0.057 | 0.032 | 0.365 |
| DPG-based $g^{\prime}$ | 0.342 | 0.124 | 0.067 | 0.040 | 0.372 |
| CAP-based $g^{\prime}$ | 0.438 | 0.260 | 0.193 | 0.156 | 0.488 |

As shown in Table 1, samples obtained from $g$ and DPG-based $g^{\prime}$ exhibit similar diversity scores. However, samples filtered through constraint-aware prompting show a significantly narrower range of diversity. This reduced diversity is also evident in the positional bias analysis in Figure 4, which studies the relative position of the string “amazing” in the generated text.
Samples from $g$ and DPG-based $g^{\prime}$ show a relatively uniform distribution of “amazing” across token positions, whereas samples prompted to include the string “amazing” led to a heavy concentration of this word in early positions.
Additional experimental details and analysis with other lexical constraints are provided in App. D, along with examples of generated samples.

### 4.2 Conditional generation with a positive ending constraint

##### Task description

Next, we consider a more general guaranteed generation scenario with two factors: (1) conditional generation with prefixes, and (2) threshold-based constraints. The common usage of LLMs often involves conditional generation based on prefixes (e.g., when a prompt is used), and requirements are not always strictly binary by definition, as was the case for lexical constraints. They could instead be the result of a thresholded real-valued function (e.g., to distinguish between positive and negative sentiments).
To reflect these two aspects, we investigate a story generation task with a positive ending constraint for sentiment reversal. In this task, given a negative story opening $X$, the LLM must generate a story continuation $Y$ and a last sentence $Z$ where the story ending $Z$ is highly positive (see Tables 8 and 9 for examples).

Figure: Figure 5: Evolution of $\text{KL}(g||a^{\prime})$ as a function of the number of samples used for training in sentiment reversal.
Refer to caption: x6.png

First, we prepared a positive sentiment scorer $b_{score}(y)$ [] and defined our binary, threshold-based constraint as $b_{\tau}(y)=1$ if and only if $b_{score}(y)>\tau$. We then selected our set of openings $X$ by collecting negative story openings from the ROCStories test set [], using only the first two sentences of stories for $X$ and imposing that $b_{score}(X)<0.05$.
To incorporate the domain knowledge of ROCStories, we use GPT-2 [] fine-tuned on the ROCStories training set as our base LLM $a$. In this task, given a negative opening $X$, a completion $y=[Y;Z]$ is accepted if its final sentence $Z$ satisfies $b_{score}(Z)>0.98$.
The acceptance rate for the base LLM $a$ is $AR_{a}$ = 0.005; in other words, rejection sampling from $a$ approximately incurs a 200$\times$ reduction in the acceptance rate compared to the ideal sampler $\tilde{g}$.

##### Empirical results

Figure: Figure 6: Results in terms of $\text{KL}(g||g^{\prime})$ (i.e., distributional distance) and $-\log(AR_{a^{\prime}})$ (i.e., inference cost) in the sentiment reversal scenario.
Refer to caption: x7.png

The sentiment reversal experiment shows similar results as the lexical constraint experiment. As illustrated in Figure 5, SFT reaches a plateau and stops improving after a certain point. In contrast, DPG continues to improve steadily as its proposal model adaptively approaches the gold model $g$, ultimately outperforming SFT for a 1.5M sampling budget. Nonetheless, using $a$ as the initial proposal in DPG results in inefficient learning due to rare gradient signals stemming from $a$’s very low acceptance rate.
However, we observe that initializing DPG with the proposal $a(\cdot|\text{CAP})$ results in the best
training efficiency. This technique
bypasses the inefficient early exploration phase by leveraging a large amount of accepting samples thanks to prompting.

As shown in Figure 6, constraint-aware prompting improves the acceptance rate without any training, but results in a distribution that greatly diverges from $g$.
Due to GPT-2 being a smaller model than Gemma-2B, the AR improvement from prompting is relatively less pronounced than in the lexical constraint experiment.
In contrast, SFT and DPG, which optimize $\text{KL}(g||a^{\prime})$, demonstrate an increase in AR while simultaneously showing less divergence from the target distribution. DPG, in particular, exhibits a distribution closer to the gold model $g$.
In summary, the GUARD algorithm yields an AR improvement of around 60$\times$ compared to $a$ while preserving a high proximity to $g$.

##### Analysis

Figure: Figure 7: Left: UMAP visualization of the samples generated by different approaches in the sentiment reversal scenario. Right: average positivity scores for each sentence position in the completions generated by each method. (Best viewed in color.)
Refer to caption: x8.png

**Table 2: Diversity of the samples generated by each approach in the sentiment reversal scenario. Lower scores indicate a greater diversity.**
| Approach | Self-BLEU $\downarrow$ | Semantic<br>similarity $\downarrow$ |  |  |  |
| --- | --- | --- | --- | --- | --- |
| 2-gram | 3-gram | 4-gram | 5-gram |  |  |
| Gold $g$ | 0.744 | 0.569 | 0.458 | 0.337 | 0.876 |
| DPG-based $g^{\prime}$ | 0.753 | 0.578 | 0.469 | 0.344 | 0.868 |
| CAP-based $g^{\prime}$ | 0.827 | 0.701 | 0.621 | 0.554 | 0.956 |

As with the lexical contraint experiments,
we plot in Figure 7 a UMAP visualization of the DistilBERT-embedded samples obtained from $g$, DPG-based $g^{\prime}$, and CAP-based $g^{\prime}$.
Similarly to these experiments, the samples from $g$ and DPG-based $g^{\prime}$ overlap in the same regions, while the samples from the CAP-based $g^{\prime}$ result in a more restricted coverage.
This visualization confirms that while prompting can increase AR without sampling, it also leads to a reduction in distributional diversity. To quantitatively measure this phenomenon, we again calculated Self-BLEU scores and the average similarity between embeddings.

The results reported in Table 2 indicate that when conditioning on a specific prefix, the diversity is relatively lower compared to unconditional generation (as seen in Table 1). Nonetheless, samples from DPG-based $g^{\prime}$ and $g$ exhibit similar diversity levels. Instead, samples obtained through CAP resulted in higher similarity, i.e., lower diversity. Figure 7 demonstrates that a positional bias is also observed in the case of a sentiment constraint. Compared to $g$ and DPG-based $g^{\prime}$, when prompting to include a positive ending, the story continuation shows a more abrupt early shift towards positivity. This further confirms the existence of a positional bias in the constraint-aware prompting behavior — similarly to the lexical constraint scenario — and illustrates how this bias leads to distributional distortion.
We provide additional details and results for this setting in App. E
, including examples of generated samples.

## 5 Related work

##### LLM alignment

LLM alignment techniques are widely regarded as the de facto method for integrating external desirable properties (e.g., helpfulness or harmlessness) into base language models. These techniques require access to a preference dataset, which consists of prompts, each associated with several completions, one of which is labeled as preferable based on criteria like human judgment. Popular approaches in this family include RLHF [], which trains a reward model from the preference dataset and fine-tunes the LLM through PPO [], and
DPO [], which combines these steps to directly fine-tune the model on the preference dataset.
While these methods enable models to generate outputs that are better aligned with the implicit properties and values expressed in the preference dataset, such as harmlessness, there remains a gap between alignment and the goal of ensuring that all outputs are harmless. Alignment does not provide a straightforward means to enforce explicit constraints, as required in our guaranteed generation task.
Consequently, despite their effectiveness, these alignment techniques, when used in a stand-alone manner (i.e., without additional inference-time processing), do not guarantee the satisfaction of a specific property or constraint in all generated outputs.

##### Controlled text generation

More closely related to our goal of guaranteed generation is the line of work on controlled text generation,
which explicitly defines conditions or constraints (e.g., in the form of predicates) that outputs should
satisfy. This topic gathers a large body of literature, and we thus let the reader refer to Zhang et al. [] for a more comprehensive survey. Existing approaches include prompting to integrate the constraint [, ],
techniques related to reinforcement learning [, , ], or relying on inference-time methods to impose the conditions without updating the original language model [, , , , , , , ]. Although these methods allow for the explicit definition of constraints, as required in guaranteed generation, they share the same limitation as alignment techniques: they cannot enforce strict constraint satisfaction.

## 6 Conclusion and discussion

In this work, we formalize how to guarantee that LLMs perfectly meet specified requirements without compromising their usefulness. We first present a theoretical foundation addressing this challenge and state that it cannot be resolved using autoregressive models alone. To overcome this limitation, we introduce the GUARD framework, which approximates the gold distribution during training and exploits rejection sampling at inference time. To validate it empirically, we conduct experiments on two scenarios with hard-to-satisfy constraints, and confirm that outputs generated through GUARD provide guaranteed generation with significantly faster inference, while closely resembling the gold distribution.

The GUARD framework is potentially applicable to various crucial tasks that require strict compliance with specified requirements without diminishing the model’s utility.
For instance, in safety alignment tasks, GUARD could ensure that the model generates content in accordance with ethical guidelines and policy constraints, while achieving minimal loss of helpfulness.
Similarly, in tackling the issue of jailbreaking — where users attempt to manipulate language models into producing prohibited or harmful content — GUARD could enforce compliance with safety protocols while maintaining the quality and informativeness of the responses.
By integrating GUARD into these scenarios, we could effectively prevent the generation of undesirable outputs and enhance the reliability of LLMs.
We believe that GUARD has the
potential to improve both the safety and efficacy of language models across a wide range of applications.

##### Limitations

It is important to acknowledge the limitations of the GUARD framework, in particular when the filtering model $b$
fails to accurately assess the outputs relative to the true underlying requirements. In such cases, GUARD, while respecting $b$, could still produce undesirable outputs. The problem of designing the filter $b$ in such a way that it is able to accurately identify such outputs is undoubtedly important, but beyond the scope of the present work.

## Appendix A Additional background and theoretical details

### A.1 Characterization of g 𝑔 g italic_g

We have defined the distribution $g$ through the formula $g(y)=\frac{1}{Z}a(y)\,b(y)$,
with $Z=\sum_{y\in{\mathcal{Y}}}a(y)\,b(y)$. It is straightforward to see that $g$ is simply the distribution of $a$ renormalized over the subset ${\mathcal{Y}}_{1}\doteq\{y\in{\mathcal{Y}}:b(y)=1\}$ and equivalently that $g$ is the distribution of $a$ conditioned on $b(y)=1$, in other words $g(y)=a(y\ |\ [b(y)=1])$.

A less obvious observation is the fact that $g$ is also the I-projection [, Section 3]
of $a$ on the space $\mathcal{C}$ of all distributions over ${\mathcal{Y}}$ that satisfy the constraint $b(y)=1$ everywhere.(^8^88$\mathcal{C}$ can also be seen, in the terminology of [], as the linear variety of distributions $p$ that satisfy the expectation constraint (also called moment constraint) $\mathbb{E}_{y\sim p}b(y)=1$, because here $b$ is a function with values in $\{0,1\}$, and therefore such $p$’s are identical with $p$’s that satisfy the constraint on all $y$’s.)
Thus, according to the definition of I-projection, $g$ is the distribution $p$ in this space that minimizes the divergence $\text{KL}(p||a)$. In other words, $g$ is, among the distributions that fully satisfy the constraint, the one that minimally distorts $a$, in terms of KL divergence — a fact that further supports our characterization of $g$ as the ideal guaranteed model associated with $a$ and $b$.

Let’s provide a self-contained proof of that fact. We have:

$$ $\displaystyle\text{KL}(g||a)$ $\displaystyle=\mathbb{E}_{y\sim g}\log\frac{g(y)}{a(y)}$ $\displaystyle=\mathbb{E}_{y\sim g}\log\frac{a(y)b(y)}{Z\ a(y)}$ $\displaystyle=-\log Z+\mathbb{E}_{y\sim g}\log b(y)$ $\displaystyle=-\log Z,$ $\displaystyle\text{KL}(p||g)$ $\displaystyle=\mathbb{E}_{y\sim p}\log\frac{p(y)}{g(y)}$ $\displaystyle=\mathbb{E}_{y\sim p}\log\frac{Z\ p(y)}{a(y)b(y)}$ $\displaystyle=\log Z+\mathbb{E}_{y\sim p}\log\frac{p(y)}{a(y)}$ $\displaystyle=\log Z+\text{KL}(p||a).$ $$

Hence we have $\text{KL}(p||a)=\text{KL}(p||g)+\text{KL}(g||a)$, and because KL divergences are nonnegative, we see that $\text{KL}(g||a)\leq\text{KL}(p||a)$ which proves that $g$ is the unique(^9^99Uniqueness comes from the fact that any $p$ such that $\text{KL}(g||a)=\text{KL}(p||a)$ is also such that $\text{KL}(p||g)=0$ — because of the identity above — and therefore is such that $p=g$.) distribution $p$ in $\mathcal{C}$ that minimizes $\text{KL}(p||a)$, namely, that $g$ is the I-projection of $a$ on $\mathcal{C}$.

### A.2 On the limitations of autoregressive models in representing g 𝑔 g italic_g

We start the discussion with two simple examples illustrating the difficulty of representing $g$ with an autoregressive model.

##### Avoidance example

First, we come back to the situation described in the main text where the constraint $b$ prohibits the token “bad” to appear in $y$. We saw that fine-tuning could not completely guarantee this constraint, because it would never put zero mass on the token “bad”.
Furthermore, fine-tuning would be pretty inefficient, even as an approximator, for this “avoidance” situation: a huge dataset would probably be necessary for significantly reducing the probability of “bad”, because the fine-tuning process would only see examples not containing “bad”, with no explicit negative examples.
As mentioned in the text, another approach, not involving fine-tuning, would be, at each timestep $t$ during
the generation of $y$, to remove the token “bad” from the softmax vector $p(\cdot|y_{<t})$, and renormalize this vector to sum to 1. This would result in an autoregressive model $a^{\prime}$ that always respects the constraint, but whose distribution would differ from $g$. Intuitively, this would be because the distribution for $g$, which corresponds to natural sequences from $a$ not containing “bad”, would anticipate early on, for the initial tokens of $y$, the fact that “bad” cannot appear later, while $a^{\prime}$ would ignore any such influence.(^10^1010The intuition may be clearer with a more situation-specific word such as “malaria”: in order to eliminate sequences containing this word from $a$, $g$ has to depreciate the probability of prefixes that naturally lead to that word — such as “This proliferation of mosquitoes raises the risk of” — while an $a^{\prime}$ intervening on the local generation of “malaria” would not perform such anticipation.)

##### Enforcement example

Conversely, rather than trying to avoid a certain token such as “bad”, we could try to enforce the presence of a token such as “good” somewhere in the sequence $y$. In other words, we would have $b(y)=1$ iff $y$ contains the token “good”. Here, we could again sample a large dataset from $a$, keep only the sequences containing “good”, and fine-tune an ARM $a^{\prime}$ on the resulting dataset. However, while $a^{\prime}$ would be better than $a$ at producing sequences containing “good”, it could still produce other sequences, and therefore would not strictly guarantee the constraint (although this fine-tuning would probably be more effective as an approximator than in the previous example of avoiding “bad”, because at least it could rely on instances explicitly containing the token). Again, we could try another autoregressive approach: we could, at each step of the generation of $y$, check whether we have already produced the token “good”, and if not, continue the generation of $y$ (i.e., prevent the generation of an $\langle eos\rangle$ token). This would result in an ARM $a^{\prime}$, which would guarantee strict satisfaction of the constraint, but the distribution of the sequences produced by $a^{\prime}$ would be very different from $g$. This is because, similarly to the previous case, while $g$ would anticipate in its distribution over early tokens the necessity to produce “good” at a later stage, $a^{\prime}$ would totally ignore such influence of “good” over the early tokens. Experiments could be conducted to confirm this fact, with the intuitive expectation that $a^{\prime}$ would tend to produce longer sequences than $g$, because there would be little incentive to produce “good” early on during the generation.(^11^1111Again, the intuition might be clearer if the constraint was about producing a rarer word than “good”, associated with a specific situation, for instance “trophy”. Sequences from $a$ containing this word, which would be selected by $g$, would tend to start differently than generic sequences from $a$, but $a^{\prime}$ would not show this kind of influence.)

In the two previous examples, of course, we did not provide a proof that modeling $g$ with an autoregressive model was impossible, but what we can say is that we are unaware of a technique for doing so, in both cases, and are skeptical about its existence.

##### Solvable instances of the problem

For these two examples, the situation with standard LLMs such as $a$, built over neural networks, contrasts strongly with what would be the case if $a$ were an $n$-gram language model. In that case, $a$ would be equivalent to a probabilistic weighted finite-state automaton [], a classical form of autoregressive model, and such constraints as the presence or absence of a specific token could be realized through intersection between such automata, resulting in another probabilistic automaton, with the same distribution as $g$. However, such intersections, which rely on dynamic programming over the finite set of states of these models, are unavailable in the domain of neural LMs. Thus, to summarize, if $a$ were an $n$-gram language model, where $b$ was a constraint similar to those considered in the two examples above, the problem of modeling $g$ through an ARM would be solvable.
Another instance where this problem is solvable — staying this time in the familiar domain of neural language models — is when $a$ is a standard LLM, and $b$ is the constraint which imposes the presence of a certain prefix $[y_{1};\ldots;y_{t}]$ at the beginning of the generated sequence $y$. It is easy to see that the generative process that samples $y_{t+1}\sim a(\cdot|[y_{1};\ldots;y_{t}])$, $y_{t+2}\sim a(\cdot|[y_{1};\ldots;y_{t+1}])$, and so on, in the standard way, corresponds to an autoregressive model $a^{\prime}$ that has the same distribution as $g$.
However, again, this is a very special case, and as soon as the constraint does not refer to such an initial section of $y$, the problem becomes much more challenging.

##### No general solution exists

To conclude, we see that in practice, even in quite simple cases, it seems challenging to model $g$ with an ARM. Theorem 1 actually proves that the general problem is unsolvable, by relying on a more abstract mathematical situation.

### A.3 Details about Theorem 1

A more precise statement of Theorem 1 is provided below:

###### Theorem 1’ .

There exists a polynomial-time computable (PTC) autoregressive model $a$ and a PTC binary predicate $b$ such that
no PTC autoregressive model $a^{\prime}$ has the same support(^12^1212The support of a distribution $p$ over ${\mathcal{Y}}$ is the set of $y$’s such that $p(y)>0$.)
as the gold model $g$, and in particular, has the same distribution as $g$.

In this statement, when we speak of an “autoregressive model”, we mean a model $m$ over sequences $y\in V^{*}$, with $V$ a finite vocabulary of tokens, which generates $y$ in the following way:

- 1.
At each time-step $t$, given the prefix $y_{<t}=[y_{1};\ldots;y_{t-1}]$ of already generated tokens, a function $f$ is applied on the prefix, where $f(y_{<t})\in\mathbb{R}^{|V|}$. In other words, the value of the function is a vector of real numbers over the vocabulary $V$.
- 2.
A softmax transformation is applied to the vector $f(y_{<t})$, yielding a probability distribution over $V$.
- 3.
The token $y_{t}$ is sampled from this distribution, and the generation proceeds recursively.

As for the PTC qualification, we say that a function is PTC iff it can be computed in polynomial time relative to the length of its argument. In particular, the function $f$ is PTC iff it is computable in polynomial time relative to the length $t-1$ of the prefix $y_{<t}$, and the binary predicate $b$ is PTC iff it is computable in polynomial time relative to the length of $y$.

The PTC assumption about $f$ is essential here. It is satisfied by all standard implementations of autoregressive models, from RNNs to Transformers of different flavors. As for the PTC assumption about $b$, without it, the theorem would be devoid of interest.

###### Theorem 1’ .

#### A.3.1 Proof sketch

Consider any NP-complete problem, for instance 3SAT [], a problem also considered by []. Now consider a textual sequence $y$ of the following form:
problem#assignment, where the first part is some encoding of a 3SAT problem instance over $k$ boolean variables, and the second part is the encoding of a candidate assignment (i.e. 0 or 1) for each of the $k$ variables.

> Two examples of such sequence encodings would be:(^13^1313$V=\{x,0,1,2,3,4,5,6,7,8,9,\vee,\neg,{;},\#\}$ is the token vocabulary.) $\displaystyle x1\vee\neg x2\vee x3\ ;\neg x1\vee\neg x3\ \#\ 1\ 1\ 0$ $\displaystyle x1\vee\neg x2\vee x3\ ;\neg x1\vee\neg x3\ \#\ 0\ 1\ 0$ where the candidate assignment in the first example satisfies the problem instance (is “valid”), while it does not in the second example (is “invalid”).

As is obvious, it is possible to check the validity of the assignment relative to the problem instance in polynomial time relative to the length of $y$.
On the other hand, under the standard conjecture that $P\neq NP$, it is impossible, by looking at the problem instance, to check in polynomial time whether this problem instance is satisfiable. In other words, it is impossible to check whether
there exists an assignment that is valid relative to this problem instance.

Now consider a PTC autoregressive model $a$ that is able to generate, possibly among other sequences, *all* sequences that cover any syntactically well-formed problem#assignment, even if the assignment is only a possible candidate, but does not actually satisfy the problem instance.(^14^1414Such an $a$ could be trivial, for instance it could generate all sequences of finite length over a vocabulary of tokens relevant for encoding the problem instance and the candidate assignment, even those that do not respect the proposed format, but it could also easily be much more focused on generating sequences of the proper syntactic format, for instance by being fine-tuned on such sequences. However, we do not want to require that $a$ only generates sequences of the proper syntactic format, because, although it is the case that this requirement can be fulfilled by certain autoregressive models, it requires more sophisticated machinery than what we actually need for our proof.)
Whatever the exact nature of $a$, the key point is that, for any sequence $y$ encoding a well-formatted problem#assignment, we have $a(y)>0$. Crucially, this is true whether or not the assignment is actually *valid* relative to the problem.

Given this $a$, now consider a predicate $b(y)$ that checks two aspects, a syntactic one and a semantic one:

- 1.
Syntactic check: whether $y$ respects the format problem#assignment, and if not, rejects $y$.
- 2.
Semantic check: assuming that the first check was successful, $b$ now checks that the assignment satisfies the problem.

Both checks can be done in polynomial time, as could be easily shown by being more precise on the exact nature of the encoding done, and by constructing small programs that would perform both checks. We do not go into the details here, that are both lengthy and straightforward.

Based on these $a$ and $b$, $g(y)$ is a distribution that gives positive probability to any $y$ of the form problem#assignment, where the assignment satisfies the problem, and a zero probability to any other $y$. Thus the support of $g$ is the set of problem#assignment $y$’s that are valid.

Now suppose that there exists some PTC autoregressive model $a^{\prime}$ such that the support of $a^{\prime}$ is equal to the support of $g$.
Then $y$ is generated by $a^{\prime}$ iff $y$ is of the form problem#assignment, where assignment satisfies problem. In particular, this means that $a^{\prime}$ starts by generating a problem that is satisfiable, and furthermore, that it can only generate satisfiable problems.
Now, this provides us with a decision procedure to determine whether a given problem is satisfiable or not, namely, we give the problem as a prefix to $a^{\prime}$, and ask $a^{\prime}$ whether it gives a zero probability or a positive probability to this prefix. This can be done by running $a^{\prime}$ autoregressively over this prefix.

The time complexity of that decision procedure can be computed as follows. Let us write the prefix $pref$ in the form $pref=[x_{1};\ldots;x_{pl}]$, with $pl$ denoting the prefix length.
Then we have $a^{\prime}(pref)=a^{\prime}(x_{1})\cdot a^{\prime}(x_{2}|x_{1})\cdot\ldots\
\cdot a^{\prime}(x_{pl}|[x_{1};\ldots;x_{pl-1}])$, where at each step $a^{\prime}(x_{t}|[x_{1};\dots;x_{t-1}])$ we invoke the autoregressive model to compute the probability of $x_{t}$ given the previous tokens. This computation occurs in polynomial time relative to $t$. Therefore, the whole autoregressive computation of $a^{\prime}(pref)$ is performed in polynomial time relative to the length of the prefix $pl$.

Overall, we now have a polynomial time algorithm that decides whether the problem, as encoded by $pref$ is satisfiable. This contradicts the $P\neq NP$ conjecture, and we conclude that the support of $a^{\prime}$ is different from the support of $g$, and in particular that, as distributions, $a^{\prime}\neq g$, which ends the proof.

Note. We believe both the statement of the theorem and its proof have some novelty relative to previous discussions of the limitations of autoregressive models. First, concerning the statement, our focus is on filtered autoregressive models, that is, conceptually very simple modifications of a base model. Indeed, we are just speaking of a model $a$ being conditioned by a predicate $b$. This may allow a clearer intuition of what is really going on. Second, concerning the proof, we take care (1) to avoid a delicate (albeit possible) autoregressive characterization of syntactically well-formed $y$’s of the form problem#assignment, by delegating the syntactic verification to $b$, an obviously polynomial-time check; and, more importantly, (2) to avoid looking for a proof relying on the impossibility of finding in polynomial time a valid assignment for a satisfiable problem instance, because this would involve a preliminary distinction between satisfiable and unsatisfiable instances, something that cannot be done in polynomial time. Our proof avoids this issue completely, by focusing on full problem#assignment pairs, of which the validity is easily checked in polynomial time.

### A.4 Characterization of g ′ superscript 𝑔 ′ g^{\prime} italic_g start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT

Let $P^{\prime}(y)\doteq a^{\prime}(y)b(y)$ and $p^{\prime}(y)$ be the distribution such that $p^{\prime}(y)\propto P^{\prime}(y)$. Then $p^{\prime}(y)=\frac{1}{Z^{\prime}}P^{\prime}(y)$ with $Z^{\prime}\doteq\sum_{y\in{\mathcal{Y}}}P^{\prime}(y)$. We have $P^{\prime}(y)\leq a^{\prime}(y)\cdot 1$, and $r(y)\doteq\frac{P^{\prime}(y)}{a^{\prime}(y)\cdot 1}=b(y)$. According to the fundamental result about rejection sampling, see [, Section 2.2], $p^{\prime}$ is the distribution obtained by sampling $y\sim a^{\prime}$ and accepting $y$ with probability $r(y)$, which in our case is either 0 0 or $1$. This is exactly what Algorithm 1 does, and therefore $g^{\prime}$ has the same distribution as $p^{\prime}$, in other words:

$$ $\displaystyle g^{\prime}(y)$ $\displaystyle=\frac{1}{Z^{\prime}}a^{\prime}(y)b(y),$ (2) $\displaystyle\propto a^{\prime}(y)b(y).$ (3) $$

We finally note that when $a^{\prime}=a$, Eq. 3 implies that the distribution $g^{\prime}$ associated with Algorithm 1 is actually equal to the gold model $g$.

### A.5 Relationship between KL ( g ′ | | a ′ ) \text{KL}(g^{\prime}||a^{\prime}) KL ( italic_g start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT | | italic_a start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT ) and Acceptance Rate A ⁢ R a ′ 𝐴 subscript 𝑅 superscript 𝑎 ′ AR_{a^{\prime}} italic_A italic_R start_POSTSUBSCRIPT italic_a start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT end_POSTSUBSCRIPT

By the same reasoning as in App. A.4, applied to $a^{\prime}$, we see that $g^{\prime}(y)\propto a^{\prime}(y)b(y)$, and therefore $g^{\prime}(y)=\frac{1}{Z^{\prime}}a^{\prime}(y)b(y)$ where $Z^{\prime}=\sum_{y\in{\mathcal{Y}}}a^{\prime}(y)b(y)$.

It is easy to see that $Z^{\prime}$ is also the probability that a sample from $a^{\prime}$ is accepted by Algorithm 1, namely the acceptance rate $AR_{a^{\prime}}$,
and therefore $AR_{a^{\prime}}=Z^{\prime}$.

We then have $\text{KL}(g^{\prime}||a^{\prime})=\mathbb{E}_{y\sim g^{\prime}}\log\frac{g^{
\prime}(y)}{a^{\prime}(y)}$, hence:

$$ $\displaystyle\text{KL}(g^{\prime}||a^{\prime})=\mathbb{E}_{y\sim g^{\prime}} \log\frac{b(y)}{Z^{\prime}}$ $\displaystyle=\mathbb{E}_{y\sim g^{\prime}}\log\frac{1}{Z^{\prime}}$ $\displaystyle=-\log Z^{\prime}$ (4) $\displaystyle=-\log AR_{a^{\prime}}\ .$ (5) $$

Because $a$ and $g$ are special cases of $a^{\prime}$ and $g^{\prime}$ respectively, we also have:

$$ $\displaystyle\text{KL}(g||a)$ $\displaystyle=-\log Z$ (6) $\displaystyle=-\log AR_{a}\ .$ (7) $$

### A.6 Core theorem about GUARD

Figure: Figure 8: (Same as right panel of Figure 1.) The $g^{\prime}$ distribution is the I-projection of $a^{\prime}$ onto the space ${\mathcal{C}}$ of distributions respecting the constraint, that is, $g^{\prime}$ is the distribution $p$ in ${\mathcal{C}}$ that minimizes $\text{KL}(p||a^{\prime})$. The Pythagorean theorem says that, for any such distribution $p$, $\text{KL}(p||a^{\prime})=\text{KL}(p||g^{\prime})+\text{KL}(g^{\prime}||a^{ \prime})$, in particular $\text{KL}(g||a^{\prime})=\text{KL}(g||g^{\prime})+\text{KL}(g^{\prime}||a^{ \prime})$. Independently of this fact, we also have $\text{KL}(g^{\prime}||a^{\prime})=-\log AR_{a^{\prime}}$, where $AR_{a^{\prime}}$ is the acceptance rate associated with Algorithm 1.
Refer to caption: x10.png

The fact that

$$ $\text{KL}(g||a^{\prime})=\text{KL}(g||g^{\prime})+\text{KL}(g^{\prime}||a^{ \prime})$ $$

is a consequence of the Pythagorean Identity for I-projections, as stated in Theorem 3.2 of Csiszár and Shields []. In order to apply the theorem, we observe that the set $\mathcal{C}$ of distributions $p$ such that $p(y)>0\Rightarrow b(y)=1$ is identical to the linear family of distributions that respect the expectation constraint $\mathbb{E}_{y\sim p}b(y)=1$, because in our case $b(y)$ can only take the values 0 or 1. The distribution $g^{\prime}$ is the I-projection of $a^{\prime}$ onto $\mathcal{C}$, and according to the theorem, for any distribution $p\in\mathcal{C}$, we have $\text{KL}(p||a^{\prime})=\text{KL}(p||g^{\prime})+\text{KL}(g^{\prime}||a^{
\prime})$.
Because $g$ is in $\mathcal{C}$, we can conclude (see Figure 8).

We can also provide a simple, direct proof of this equality for our specific case. We have:

$$ $\displaystyle\text{KL}(g||g^{\prime})$ $\displaystyle=\mathbb{E}_{y\sim g}\log\frac{g(y)}{g^{\prime}(y)}=\mathbb{E}_{y \sim g}\log\frac{Z^{\prime}g(y)}{a^{\prime}(y)b(y)}$ $\displaystyle=\log{Z^{\prime}}+\mathbb{E}_{y\sim g}\log\frac{g(y)}{a^{\prime}( y)}=\log{Z^{\prime}}+\text{KL}(g||a^{\prime}).$ $\displaystyle\text{KL}(g^{\prime}||a^{\prime})$ $\displaystyle=\mathbb{E}_{y\sim g^{\prime}}\log\frac{g^{\prime}(y)}{a^{\prime} (y)}=\mathbb{E}_{y\sim g^{\prime}}\log\frac{a^{\prime}(y)b(y)}{Z^{\prime}a^{ \prime}(y)}$ $\displaystyle=-\log{Z^{\prime}}.$ $$

Hence $\text{KL}(g||a^{\prime})=\text{KL}(g||g^{\prime})+\text{KL}(g^{\prime}||a^{
\prime})$.

We then apply the identity from Eq. (5) and conclude the proof.

## Appendix B GUARD ’s training algorithm

Figure: Algorithm 2 GUARD training with warm-start DPG

Algorithm 2 illustrates the GUARD training process with DPG. The optional orange-colored steps — which correspond to what we are referring to as the warm-start initialization of DPG —
focus on increasing the $AR_{\pi_{\theta}}$ through the CAP proposal, while the remaining steps follow the version of the DPG algorithm presented in Go et al. [, Algorithm 1].
By initializing DPG training with a high-AR $\pi_{\theta}$ obtained through CAP, we can supply a large number of samples to the $\text{KL}(g||a^{\prime})$ minimization process, leading to more efficient training.

## Appendix C Additional metrics details

##### Acceptance Rate

$AR_{a^{\prime}}$ represents the proportion of outputs $y$ sampled from $a^{\prime}$ that satisfy the constraint $b(y)$.
Formally $AR_{a^{\prime}}$ is defined as the expected value of the constraint function $b(y)$ under the language model distribution $a^{\prime}$, which is given by $AR_{a^{\prime}}=\mathbb{E}_{y\sim a^{\prime}}[b(y)]$. Higher $AR_{a^{\prime}}$ indicates the sampler has a faster inference speed.

##### Distributional Closeness

In Theorem 2, we aim to minimize the KL divergence between the gold distribution $g$ and the distribution $g^{\prime}$ produced by our framework. We estimate the quality of GUARD, represented by $\text{KL}(g||g^{\prime})$, through the following method:

$$ $\displaystyle\text{KL}(g||g^{\prime})=\mathbb{E}_{y\sim g}\log\frac{g(y)}{g^{ \prime}(y)}$ $\displaystyle=\mathbb{E}_{y\sim g}\log\frac{a(y)b(y)}{Z}\frac{Z^{\prime}}{a^{ \prime}(y)b(y)}$ $\displaystyle=\mathbb{E}_{y\sim g}\log\frac{a(y)}{a^{\prime}(y)}-\log\frac{Z}{ Z^{\prime}}.$ $$

We measured distances using the disco [] toolkit.(^15^1515[https://github.com/naver/disco](https://github.com/naver/disco))

##### Self-BLEU

BLEU evaluates how similar a language model’s output is to candidate references using $n$-gram matching. Similarly, Self-BLEU [] measures the diversity of generated outputs by selecting $K$ samples from the model’s output and calculating the average BLEU score of each sample against the remaining $K-1$ samples. In this paper, we measured Self-BLEU using a set of $K=100$ outputs.

##### Semantic Similarity

First, we extract 500 outputs from each approach’s guaranteed output distribution ($g$ or $g^{\prime}$). We then randomly select 10,000 pairs of outputs from these 500 samples and embed them to measure their cosine similarity in the embedding space. The average of these similarity scores is then calculated. For the lexical constraint experiment, we encoded the Gemma-2B model outputs using the Gemma-7B model. In the sentiment reversal experiment, we encoded the GPT-2 model outputs using BERT.

## Appendix D Lexical constraint experiment

##### Additional details

For the lexical constraint experiment, we use Gemma-2B [] to generate 30 tokens through ancestral sampling, starting with $\langle bos\rangle$ or a specific prompt in the case of the CAP baseline. We chose ancestral sampling because it generates from the LLM’s original distribution without distortion, unlike top-$k$ or nucleus sampling.
The sampling budget is defined as the number of samples drawn from proposal $a$, $a(\cdot|\text{CAP})$ or $a^{\prime}$(^16^1616More precisely, the evolving $a^{\prime}$ – in other words what is denoted by $\pi_{\theta}$ in Algorithm 2.) for training purposes. For DPG, this is #samples per step $\times$ step size, while for SFT, it is batch size $\times$ step size. In the case of SFT, sampling is done only from $a$, so the expected training set size is sampling budget $\times$ $AR_{a}$. For DPG, as the adaptive proposal gradually approaches $g$, the number of samples increases with each step during training. Naturally, $AR_{a^{\prime}}$ is initially low, resulting in fewer samples, but this disadvantage can be mitigated by sampling from $a(\cdot|\text{CAP})$ in the early stage.
Detailed hyperparameters are provided in Table 3, and the list of constraint-aware prompts used in the experiments can be found in Table 4.

**Table 3: Hyperparameters used for the lexical constraint experiment.**
| Hyperparameter | Value |
| --- | --- |
| Base LLM $a(\cdot)$ | Gemma-2B(^17^1717[https://huggingface.co/google/gemma-2b](https://huggingface.co/google/gemma-2b)) |
| Max sequence length | 30 |
| Learning rate | 1.41e-5 |
| Optimizer | Adam |
| DPG #samples per step | {2000, 5000, 10000} |
| SFT batch size per step | {16, 32, 64} |
| Sampling budget used with $a(\cdot|\text{CAP})$ | 10000 |
| Prompt used for warm-start proposal $a(\cdot|\text{CAP})$ | Next sentence should contain “amazing”. |

**Table 4: Constraint-aware prompts used for the lexical constraint experiment.**
| Next sentence should contain ’amazing’. |
| --- |
| Write sentences with the given words. |
| diagnosis: Assessment of microscopical and clinical parameters in the diagnosis of diabetes mellitus. |
| pandas: Column headings differ in spreadsheet that is merged with pandas data. |
| change: How to change the decimal separator in MS Word? |
| amazing: |
| Write a text containing “amazing”, as shown below. |
| It is a really amazing day. |
| Amazing, amazing and amazing. |
| Truly amazing. |
| The following sentence contains the keyword ’amazing’. |
| This is an example of texts with the string ’amazing’ |
| A paragraph with ‘amazing’: |
| Text examples with ’amazing’. |
| The following sentence contains the keyword ’amazing’. |

##### Additional analysis

Figure: Figure 9: Additional positional bias analysis using the “restaurant” and “world” strings.
Refer to caption: x11.png

Based on the experiments discussed in the main body of the paper, we analyze how the phenomena observed in the analysis are reflected in the actual text. As shown in Table 5, texts generated from the DPG-based $g^{\prime}$ feature the word “amazing” in various positions, discussing specific topics. However, when forced to include “amazing” through CAP, the generated texts tend to include the word “amazing” early on while remaining generic and without delving into specific subjects. This positional bias occurs not only with the string “amazing” but also with other strings such as “restaurant” and “world” as shown in Figure 9.

**Table 5: Example of generated samples for the lexical constraint experiment. Red-colored text indicates the occurrence of the required string “amazing”.**
| DPG-based $g^{\prime}$ | CAP-based $g^{\prime}$ |
| --- | --- |
| To be successful when tackling difficult problems and amazing your customers you need a space to think and solve these concerns. At CKWI, our expert and | 1. amazing ads on TV: They broke the advertising law and added more than 5<br>5 numbers to admit simulation! 2. Agata |
| Staten Island is world renowned for its dog-friendly beaches and amazing shops. The zoo park is always a hit for residents and tourists alike. Visits | 3 most amazing facts about marine animals.<br>paragraphs: paragraph, paragraph.<br>extension: zoom<br>calculations: result of calculation<br>application programming: application |
| Welcome Guest,<br>We do believe having a great relationship with clients is invaluable, therefore we strive to make your playing experience as comfortable, amazing and exciting | Things wouldn’t be so amazing without all that PERFECTNESS which we call ’Love’……<br>Thanks Vernachael, I’m dropping by |
| Join us on an amazing journey In Southern Uzbekistan.<br>17 days Arrive in Tashkent and upon arrival, we will pick you up from the Airport | I agree, that is truly amazing. I like the fact it is all customisable.<br>That’s nice bet it stinks out the exhaust fumes |

## Appendix E Sentiment reversal experiment

**Table 6: Hyperparameters used for the sentiment reversal experiment.**
| Hyperparameter | Value |
| --- | --- |
| Base LLM $a(\cdot)$ | GPT2-Finetuned-ROCStories(^18^1818[https://huggingface.co/msintaha/gpt2-finetuned-rocstories](https://huggingface.co/msintaha/gpt2-finetuned-rocstories)) |
| Max sequence length | 80 |
| Learning rate | 1.41e-5 |
| Optimizer | Adam |
| DPG #samples per step | 10000 |
| SFT batch size per step | 64 |
| Sampling budget used with $a(\cdot|\text{CAP})$ | 10000 |
| Prompt used for warm-start proposal $a(\cdot|\text{CAP})$ | This is a happy ending story: |

**Table 7: Constraint-aware prompts used for the sentiment reversal experiment.**
| This is a happy ending story: |
| --- |
| In the end, it was a story that had a truly happy ending, |
| This is my positive ending story, |
| Eventually, it turned into a really fantastic day: |
| Here is an example of a paragraph starting up with a negative sentiment but ending positively: |
| Happy ending story: |
| Eventually, it turned into a really happy day! |
| There was a little bit of bad luck, but it was a happy day! |
| I was so lucky even there were some obstacles. |

**Table 8: Negative story openings used for the sentiment reversal experiment.**
| My uncle couldn’t afford health care. He got sick last year. |
| --- |
| Kevin’s dad had raised him alone after his mom left them. When his dad grew old and ill, Kevin was unhappy. |
| Allie came home late last night. Her mother was very mad at her. |
| Mike was a bad kid. He never followed his parents advice. |
| Bobby registered his son for tee ball. His son wasn’t having a good time. |

##### Additional details

The lexical constraint experiment was set in an unconditional generation context (i.e., without any prefix), which makes the distortion due to prompting particularly severe. Therefore, it is necessary to thoroughly examine the phenomena that occur when $\text{KL}(g||g^{\prime})$ increases in a conditional generation setting. For this experiment, we selected negative story openings from the ROCStories test set []. We retained only the first two sentences of all stories and chose five that had the lowest positive scores. The hyperparameters, constraint-aware prompts, and negative story openings used in this experiment are respectively shown in Tables 6,  7, and  8.
To define $b(y)$, i.e., to accept or reject a generated story, we used a threshold criterion based on an existing emotion text classifier(^19^1919[https://huggingface.co/michellejieli/emotion_text_classifier](https://huggingface.co/michellejieli/emotion_text_classifier)) using the “joy” class probability output. Specifically, we accepted stories where the “joy” class probability of the last sentence exceeded 0.98.

##### Additional analysis

The generated samples in Table 9 show patterns similar to those observed with the lexical constraint scenario. The stories obtained from the DPG-based $g^{\prime}$ have a natural flow like the original $g$, while the samples obtained from CAP exhibit abrupt sentiment changes, losing specificity in the process. This leads to significant differences in KL divergence between $g$ and $g^{\prime}$.

##### A note about the Story Infilling task of [ 10 ]

Our sentiment reversal experiment bears some connections with the Story Infilling task from Hu et al. [, Section 4.2], where the authors consider the task of generating the middle (fourth) sentence of a story, given the first three and the last (fifth) sentence of the story, using the ROCStories dataset for training and for test. They use the GFlowNet amortization framework [] to fine-tune their base model towards generating the middle sentence.
Our task is similar in spirit, because we try to complete the start of a story in such a way that the story ends on a positive sentence (instead of ending with a fully specified sentence). In other words, our version of the task can be considered as soft Story Infilling. Additionally, the base model $a$ we use is GPT-2 fine-tuned on the ROCStories training set, as in Hu et al. []. However, our approach is quite different both in the goal and in the method used. We are trying to obtain a sampler $g^{\prime}$ that produces texts coming from a distribution close to the gold distribution $g$ — where $g$ is the distribution $a$ filtered by the positive-ending constraint — and we insist on only sampling texts with a positive ending. In contrast, they do not try to filter texts from $a$ by the constraint that they end on a specific sentence, but only use $a$ as the starting point for their GFlowNet amortization, trained on the ROCStories dataset. They evaluate their results in terms of the similarity of the generated middle sentence to the middle sentence in the ROCStories test set, while we evaluate our results in terms of
the divergence with the gold distribution $g$ and of
the efficiency of the sampler in producing positive endings.

**Table 9: Example of generated stories for the sentiment reversal experiment. Blue-colored text corresponds to the imposed negative opening prefix, and red-colored text indicates the final sentence of the story, on which sentiment positivity is required.**
| DPG-based $g^{\prime}$ | CAP-based $g^{\prime}$ |
| --- | --- |
| My uncle couldn’t afford health care. He got sick last year. His aunt bought him medicine for his sick days. My aunt bought him some and started treating him. He has much better health than he had before. He is very grateful, and is doing better everyday. | My uncle couldn’t afford health care. He got sick last year. I hope someday he gets better. I hope my grandma gets better soon. Best of luck! Ever! |
| My uncle couldn’t afford health care. He got sick last year. The only way around it was by prescription. A doctor arranged to have me take antiretrovirals and a lot of painkillers. He had a wonderful 18 month treatment and I feel much better today. | My uncle couldn’t afford health care. He got sick last year. Luckily he got home healthy. It was wonderful to be able to share our kitchen with our children. It feels so much better than we ever knew. |
| Mike was a bad kid. He never followed his parents advice. He was misbehaving and frightened. He tried to learn from his own mistakes. Eventually, he was a very good boy. He is very grateful. This gift has made a huge difference to my son. | Mike was a bad kid. He never followed his parents advice. However, he did learn a new trick. He learned how to play the guitar. I can’t wait to see how he plays! I hope all that gets passed on to Mike someday! |
| Allie came home late last night. Her mother was very mad at her. She put a basket of cookies on the kitchen table. She went to the kitchen to make her dinner. She made several small cuts, then her mother ate her favorite slice. So she and her mom were very happy! | Allie came home late last night. Her mother was very mad at her. She decided to surprise her grandma and surprise her. Allie packed her things and got ready to go. Everyone had a great day! |

## Appendix F Discussion of additional sampling techniques: IMH and QRS

This section contrasts the efficiency of GUARD at inference time with one MCMC technique, IMH [], and one variant of rejection sampling, QRS [].
It compares outputs from these different sampling methods, starting with a specific proposal distribution $a^{\prime}$: rejection sampler
$g^{\prime}$ as in GUARD, IMH sampler,
and QRS sampler. QRS is an extension of rejection sampling that offers two benefits over IMH as a sampler for GUARD:
(1) It produces outputs $y$ that more closely approximate the target distribution $g$; (2) It still
enables tractable measurement of the distance from $g$, similarly to rejection sampling in Algorithm 1.(^20^2020Note that, in the experiments below, in order to compare IMH and QRS, we use an approximate measure available for both.)
by allowing quantification of the output probability of $y$.

QRS implements the acceptance criterion corresponding to accepting
$y$ with probability $\min(1,\frac{g(x)}{\beta a^{\prime}(x)})$, where $\beta$ is a positive hyperparameter with the following properties:

- 1.
As $\beta$ approaches 0, QRS becomes equivalent to the GUARD form of rejection sampling (Algorithm 1).
- 2.
As $\beta$ increases, QRS more closely approximates $g$, but at the cost of additional inference time.

This comparison permits an analysis of the trade-off between sampling accuracy and computational cost across these different methods.

### F.1 Experimental setting

Directly comparing the GUARD sampler with MCMC methods like IMH is challenging. When we run the IMH algorithm for a certain number of steps $n$, we obtain a distribution denoted as $p^{(n)}$. While we can sample from $p^{(n)}$, we cannot evaluate $p^{(n)}(x)$ for a given $x$ (see Eikema et al. []), which presents a significant obstacle to estimating the KL divergence.

Figure: (a) Distribution $g^{\prime}$
Refer to caption: x13.png

Although we cannot directly calculate $p^{(n)}$, we could estimate it using the law of large numbers. However, this becomes problematic when the sample space $X$ is very large, as in text generation cases. In contrast, if our sample space $X$ was small (e.g., $X=\{1,2,...,10\}$) and we had 10,000 samples from a given sampler $\pi$,
we could estimate $\pi(2)$ by counting the relative frequency of 2’s in the sample, and similarly for any $x$ in this space.

Based on this insight, we propose the following approach for providing at least an approximate estimation of $\text{KL}(p||p^{(n)})$:(^21^2121Actually, this technique provides a lower-bound of the true KL divergence, a consequence of the Data Processing Inequality (DPI) of Information Theory [].)

- 1.
We build a small finite partition $\bar{X}$ of 10 bins for the textual space $X$, with a projection mapping $f(x)=\bar{x}$ from the large space $X$ to the low-dimensional space $\bar{X}$.
- 2.
We generate a sample of 1000 points from $p$ and use $f$ to project these points into points $\bar{x}$ of $\bar{X}$. We get an estimate $\bar{p}(\bar{x})$ for any $\bar{x}$ in $\bar{X}$.
- 3.
We do the same for $p^{(n)}$, obtaining estimates $\bar{p}^{(n)}(\bar{x})$.
- 4.
We can then estimate $\text{KL}(\bar{p}||\bar{p}^{(n)})$.
- 5.
Then, by considering different values of $n$ (but keeping the projection $f$ fixed), we can monitor how $\text{KL}(\bar{p}||\bar{p}^{(n)})$ evolves with $n$. It is expected to decrease with $n$.

In this experiment, we focus on the lexical constraint scenario. Then, for the projection $f$, we can use the position of “amazing” in the generated text. We can project the texts from $g$ and $g^{\prime}$ based on which of the 10 bins the relative position of “amazing” falls into (see  Figure 10).
Using this method enables us to compute a form of KL divergence for IMH and to use this form for comparison with QRS as shown in Figure 23.

### F.2 Experimental results

Figure: Figure 11: Starting from the top-left point (i.e., initial $g^{\prime}$), this figure illustrates the improvement of the projected KL over $\text{KL}(\bar{g}||\bar{g}^{\prime})$ for both IMH and QRS and the associated additional inference costs. We note that QRS achieves a reasonable compromise when $\beta=Z$.(^23^2323IMH performs a random walk $n$ times on an initially accepted sample to improve its quality, where $n$ is a hyperparameter, and where the last $y$ in the random walk is returned. For comparison with the rejection-based samplers, we therefore consider the “acceptance rate” of IMH to be $1/n$.)
Refer to caption: x15.png

Figure 23 illustrates the quality/AR trade-off results.
Both QRS and IMH demonstrate improved output quality at the cost of additional inference time. However, QRS consistently Pareto-dominates IMH across the tested hyperparameters.

In the case of QRS and especially IMH, the quality gains come at a high cost in terms of additional inference time: to halve the projected KL divergence — which is a lower bound of the true KL divergence, see Footnote 21 —
QRS requires 1.36 times the inference cost of Algorithm 1, while IMH requires 10 times the cost. Moreover, to reduce the KL divergence to 10% of the original KL, QRS uses almost 10 times the inference cost of Algorithm 1, while IMH consumes 50 times this cost. This experiment demonstrates that the random walk nature of MCMC methods can struggle to efficiently mimic the gold distribution. This result highlights why accurately approximating $g$ with the proposal distribution is crucial: it can lead to more efficient sampling that diverges less from the target distribution without incurring the extreme computational costs associated with methods like IMH.

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: I wonder if the distribution used by [3] would be a better proposal distribution for rejection sampling, compared to SFT, CAP or DPG.
soundness: 2
strengths: The papers motivate an important challenge for the existing LLMs and provide proofs that it is theoretically intractable to sample from the LLM distributions conditioned on logical constraints.
summary: This paper motivates and studies the problem of constraining LLM generation on logical constraints with guarantees. The authors show that it is often intractable to directly sample from the LLM distribution conditioning on a logical constraint and propose the GUARD framework for solving this problem. GUARD performs rejection sampling on an approximate autoregressive distribution of the desired conditional distribution, which can be obtained via supervised fine-tuning, prompting or distributional policy gradient (DPG). The authors evaluate GUARD on two tasks: (1) generate a piece of text of 30 tokens while including the string "amazing" and (2) generate a story ending of positive sentiment given a story beginning of negative sentiment. The authors evaluate the aforementioned three alternatives for obtaining the approximate distribution.
weaknesses: The authors could have done a more extensive literature survey and demonstrate how their work relates to/differs from following approaches for constrained generation:

FUDGE [1]: trains auxiliary classifiers on existing classification datasets and uses the classifiers to guide generation to satisfy the constraint.

NeuroLogic A*esque Decoding [2]: performs lookahead decoding with heuristic functions that estimate how likely the constraint will be satisfied. 

NADO [3]: trains auxiliary classifiers on data sampled from LLMs and uses the classifiers to guide generation to satisfy the constraint.

GeLaTo [4]: uses an Hidden Markov Model to enforce the constraint

Outlines [5]: uses regex/finite-state machines to mask out next tokens that would violate the constraint.

In particular, the authors claim that they are not aware of general techniques that (1) guarantees the constraint is enforced and (2) limiting the distortion of the original distribution while such techniques, or related techniques that partially achieve (1) or (2), exist in literature: [4,5] achieves (1) and [1,2,3,4] tries to optimize for (2).

Similarly, for both tasks considered in the experiment section, the authors could have instead use existing benchmarks: for the task of generating text using given keywords, the authors could consider the CommonGen dataset [6] and compare their approach against [2,3,4].
For the task of sentiment control, the goal is to generate text such that an existing classifier assigns a score > some threshold. In this way, the authors might as well evaluate their approach on the task of formality control by replacing the sentiment classifier with a formality classifier and compare against [3]. Or the authors could consider the task of topic control and compare against [1].

[1] Kevin Yang and Dan Klein. 2021. FUDGE: controlled text generation with future discriminators. In NAACL-HLT. Association for Computational Linguistics.

[2] Lu, X., Welleck, S., West, P., Jiang, L., Kasai, J., Khashabi, D., ... & Choi, Y. (2021). Neurologic a* esque decoding: Constrained text generation with lookahead heuristics. arXiv preprint arXiv:2112.08726.

[3] Meng, T., Lu, S., Peng, N., & Chang, K. W. (2022). Controllable text generation with neurally-decomposed oracle. Advances in Neural Information Processing Systems, 35, 28125-28139.

[4] Zhang, H., Dang, M., Peng, N., & Van den Broeck, G. (2023, July). Tractable control for autoregressive language generation. In 
International Conference on Machine Learning (pp. 40932-40945). PMLR.

[5] Willard, B. T. & Louf, R. Efficient Guided Generation for Large Language Models. arXiv preprint. arXiv: 2307.09702 [cs.CL] (2023).

[6] Lin, B. Y., Zhou, W., Shen, M., Zhou, P., Bhagavatula, C., Choi, Y., & Ren, X. (2019). CommonGen: A constrained text generation challenge for generative commonsense reasoning. arXiv preprint arXiv:1911.03705.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. How do you get the gold samples in Fig. 4&7?
2. I notice that you discussed the relation to I-projection in line 136&242. How do such discussions help? I found that removing these contents does not affect understanding.
soundness: 3
strengths: Guaranteed generation is an important requirement in real applications of LLMs. Though relatively easy to come up with, the algorithm proposed in this paper do provide an effective solution for this problem. Meanwhile, Theorem 1 gives a good reminder for trials attempting to solve such problem without considering sampling strategies. Overall, I would be glad to see this paper being accepted, as an important progress under this specific problem.
summary: This paper focuses on how to guarantee generation of restricted text that satisfy some given constraints from large language models, while preserving distribution information in original model as much. Specially, this paper first proposed a theorem showing there exist distributions that are impossible to be fitted by a regular autoregressive model, so that sampling strategy should always be combined with. Then an algorithm named GUARD is proposed for this task. It first finetunes the model for higher acceptance rate, and then applies rejection sampling for strict guarantee. Experiments on two constrained generation tasks show that, GUARD achieves significantly higher acceptance rate, while keeping close to the ground truth distribution.
weaknesses: While this paper has its merit in terms of contribution, it did not give me a good impression at first glance. The following suggestions may be helpful to the authors:
1. Algorithm 1 is too short. It is frustrating to see a 3-line algorithm in a paper. Switching its position with that of Algorithm 2 would be much better.
2. The content of Theorem 2 is too simple to be a theorem. It's OK to put it as an equation.
3. For Theorem 1 in main text, I suggest to replace it with the complete version in appendix. The concept of PTC is central and should be highlighted in the main text. 
4. In section 2.3, It may not be a good idea to discuss the non-zero probability under softmax as an evidence for limits of autoregressive models, since it is not the key point and such shortcoming can be easily avoid by rejection sampling. I suggest to discuss the PTC property of common models instead, which will serve for Theorem 1.
5. In experiments, I did not find the exact numbers of AR of DPG. I notice that they are reported in the figures by coordinates, but exact numbers are also necessary.
6. Text in figures and tables are too small to be viewed on A4 paper, please consider rearranging the layout.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: - How is $\mathrm{KL}(g || a') =\mathrm{KL}(g || g') - \mathrm{AR}_{a'}$ computed? The gold distribution $g$ is not accessible and the acceptance rate $\mathrm{AR}$ is infeasible to compute as it requires considering all possible output sequences, which is of complexity $\mathcal{O} (| \mathcal{V} |^{T})$. 

Also, since $\mathrm{KL}(g || a') > 0$, questions remain about the quality and efficiency of the proposed methods, especially in comparison to other baseline techniques:
- How do generated answers compare to baselines? Does $g'$ still capture the same capabilities as the original model $a$? 
- How efficient is the approach compared to baselines? How frequent are answers from $a'$ accepted compared to the answers from $a$?
soundness: 3
strengths: - **Clear Motivation and Intuition:** The authors provide clear intuitions about the need for distribution-preserving constraint satisfaction in language models and the challenges this entails. They thoroughly motivate their approach for achieving strict control over generations without substantially deviating from the original model’s output distribution.
- **Theoretical Rigor:** The proposed method is supported by theoretical principles, providing a mathematically grounded mechanism that guarantees strict constraint satisfaction while preserving the original model’s output distribution.
- **Efficiency in Performance:** Empirically, the method achieves improved inference efficiency by increasing the acceptance rate compared to the original model while maintaining minimal distributional distortion.
summary: This work proposes GUARD, a method that combines an autoregressive proposal distribution with rejection sampling to guarantee the satisfaction of hard constraints in generated text while keeping the output close to the language model’s original distribution.
weaknesses: **Theory:** Although well-motivated, the novelty of the approach is somewhat unclear, as it largely combines established alignment techniques with a naïve rejection sampling method to achieve guaranteed generation from language models:
- First, the authors propose a specific prompt (CAP) and/or a fine-tuned model (SFT, DPG), denoted as $a’$, to approximate the gold distribution $g$. These methods are commonly used to align model outputs with desired behaviors. However, there is no guarantee that each method minimizes $KL(g || a’)$, even though the authors stress its importance for both quality and efficiency (lines 249-250).
- Second, $a’$ is used to generate answers that are then filtered through rejection sampling, which guarantees that constraint $b$ are satisfied but which has already been discussed in prior work (e.g., Yang and Klein, 2021).

**Presentation**: In several parts, the work lacks precision and conciseness:
- First, critical aspects such as the approximation and minimization of $KL(g || a’)$ remain unclear (see question 1 below).
- Second, essential insights into the efficiency of the method and the quality of the generated answers are insufficiently addressed (see questions 2 and 3 below).
- Third, the method assumes that constraints $b$ can be designed such that it respects the desired behavior. Since this is a core assumption of this work, it should not be considered “out of scope”.
- Fourth, consistency in terminology could be improved. For example, while “autoregressive model” is frequently referenced, the abbreviation “ARM” is introduced only in Section 2.2 and used inconsistently thereafter.

---
K. Yang and D. Klein. 2021. Fudge: Controlled text generation with future discriminators. arXiv preprint arXiv:2104.05218.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: * What is V^* in line 119? It is never defined and I can only find it used once in line 801 where I don't get its usage.
* What is "ancestral sampling" - line 308?
soundness: 4
strengths: I found the problem and the proposed solution very interesting and intuitive.
The experiments seem reasonable, the results good and I see no major evaluation missing.
The auxiliary investigations in Fig 4 & 7 as well as Tab. 1 and 2 are very insightful.
summary: This work proposes the GUARD framework, which guarantees strict constraint satisfaction for generated outputs of LLMs.
It utilizes rejection sampling at inference to guarantee constraint satisfaction as well as a variant of DPG to tune the language model towards a policy close to the "gold standard" policy to ensure distributional closeness during training.
weaknesses: I strongly agree that the major limitation of this approach in obtaining a filter b (also called verifyer in other areas), which I think is one of the most important research areas around LLMs right now.
However, I agree with the last paragraph in the main text, that this is out of scope for this work and any improvements in that direction will directly improve GUARD.

Minor:
* I understand why the baseline method described in line 172-176 and in App. A.2 has severe drawbacks, but for the simple constraint in the first experiment in Sec. 4.1, it would actually be a suitable baseline to compare to. 
Also I could see that it performs better than DPG with CAP in this setting, as the distribution is less degenerate I guess.
* It would be nice to have the two experiments performed with more than one model each, but I understand the computational demand arising from this.
* The claim in the third contribution is a bit too strong for me. GUARD itself does not improve the acceptance rate, it depends on the way a' is chosen right? So the improved DPG leads to higher acceptance rates.

Remarks (just as info for camera ready):
* SFT is not introduced on first occurance in line 200, but in 255/256.
* The order of Fig. 3 and 4 is reversed

Meta-review: ## Summary 

This paper addresses the challenge of ensuring strict constraint satisfaction in text generation by large language models while maintaining closeness to the original model’s distribution. The authors define an ideal distribution that satisfies the constraints and prove it cannot be achieved using autoregressive training alone. To address this, they propose GUARD, a method combining autoregressive proposal distributions with rejection sampling. Theoretical analysis shows that GUARD balances constraint satisfaction, distributional fidelity, and inference efficiency by minimizing KL divergence. Experimental results on lexical constraint generation and sentiment reversal demonstrate that GUARD achieves perfect constraint satisfaction with improved efficiency compared to other methods.

## Decision

The paper aims to address an important challenge for the existing LLMs and provide theoretical results related to this problem. The approach proposed in this paper provides an effective solution to this problem. The results are overall convincing. Overall, some of the reviewers had concerns about the novelty and not covering some of the relevant papers that should be cited, but it is not. I strongly encourage the authors to cite those relevant papers. I recommend the authors address all the concerns of the reviewers, including the citations for the camera-ready version of the paper.

Decision: Accept (Poster)