Guaranteed Generation from Large Language Models
Authors: Minbeom Kim
Thibaut Thonet
Jos Rozen
Hwaran Lee
Kyomin Jung
Marc Dymetman
Venue: ICLR 2025 Poster (2025)
Keywords: Guaranteed Generation
Controlled Text Generation
LLM Alignment
Limitations of Autoregressive Models
Rejection Sampling
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose a method for ensuring strict satisfaction of constraints in large language models while preserving generative capabilities.

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.

Published as a conference paper at ICLR 2025
GUARANTEED GENERATION FROM LARGE LANGUAGE MODELS
Minbeom Kim Marc Dymetman
Thibaut Thonet?
Jos Rozen? Hwaran Lee
Kyomin Jung'
Seouul National University ?NAVER Labs Europe NAVER AI Lab *Sogang University
5 Independent Researcher
ABSTRACT
As large language models (LLMs) are increasingly used across various applica- tions, there is a growing need to control text generation to satisfy specific con- straints or requirements. This raises crucial question: Is possible to guarantee strict constraint satisfaction in generated outputs while preserving the distribu- tion of the original model as much as possible? We first define the ideal dis- tribution the closest the original model, which also always satisfies the expressed constraint as the ultimate goal of guaranteed generation. We then state fundamental limitation, namely that it is impossible to reach that goal through autoregressive training alone. This motivates the necessity of combining raining-time and inference-tes methods enforce such guarantees. Based on this insight, we propose GUARD, 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 spe- eific proposal and the target ideal distribution simultaneously optimizes inference speed and distributional closeness. To validate these theoretical concepts, we con- duct extensive experiments on two text generation settings with hard-to-satisfy constraints: lexical constraint scenario and sentiment reversal scenario. These experiments show that GUARD achieves perfect constraint satisfaction while al- most preserving the idcal distribution with highly improved inference efficiency. GUARD provides a principled approach to enforcing strict guarantees for LLMS without compromising their generative capabilities.
INTRODUCTION
Large language models (LLMs) have demonstrated remarkable capabilities in generating human-
like texts across a wide range of applications (OpenAl 2023: Diang et al. 2023 Yoo et al.) (024))
Due to their usefulness, I.LMs are being increasingly integrated into various downstream services and critical decision-makinn processes (Zelch et al. 2023 Arora & Arora 2023 Kung et al., 2023).
However, this widespread adoption raises concerns about both the reliability and the safety LLM outputs, especially in high-stake scenarios where unintended behaviors could have significant con- sequences (Casper et al., 2023). Hence, it is crucial to address two key questions: (1) How can 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 's useful dis- tribution 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 (Zhang et al., 2024a), where LLMS are conditioned on specific attributes increase the likelihood of producing desired outputs. However, the associated methods do not provide the means to ensure that all generated out- puts strictly meet the desired constraints a problem we refer to as guaranteed generation. This
Wook done during an internship at NAVER Labs Europe.
"Correspondence {mi nbeomk m8 ac.kr, marc.dyymetman@gaai ccom

---

Published as a conference paper at ICLR 2025
Training
Inference
X3Gl+>
goumne mashed
6-1
b-1
KL O
(1) Rejection sompling
(2) Antoregresive training
(3) GUARD
Rejection sampling (1) can directly emulate g from a, but it may incur a large inference cost when constraint b is hard to satisfy. In the case of autoregressive training (2), it is in general impossible for such model to reach (see Theorem[]] [T] GUARD (3), on the other hand, first learns approx- imation a' of g and then performs simple form of rejection sampling using a' as the proposal. This approach yields a distribution 9' which (i) strictly satisfies constraint b, (ii) minimizes inference cost, and (iii) is highly similar to g. Properties (ii) and (iii) are simultaneously enforced by minimizing (L(glla") as illustrated in the rightmost diagram (see Theorem
Figure I: GUARD overview.
the gap we seek address here. Our primary objective is then to study, in-depth, the character- istics 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 base LLM by introducing the notion of gold distribution, g. i.c., the ideal distribution we target. It is represented by a filtered energy- based model (EBM) (LeCun et al., 2006) that always satisfies the specified constraint - c.g., binary filter function while minimally diverging from the original distribution a associated with the base LLM. Although we can compute the probability g(v) for any arbitrary text y, this does not imply the existence of an autoregressive model a' with the same distribution as g. We present an impossibility theorem (Theorem D 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 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 address these issues, we propose GUARD a simple framework for guaranteed generation that combines approximation of the ideal distribution g into proposal distribution a' with rejection sampling from the latter proposal. We establish a theorem (Theorem [ about the relationship among the proposal a', the GUARD output g', and the ideal distribution g through information geometry, by using the Pythagorean theorem for Information Projections (I-projections) (Csiszár & Shields, 2004). As shown in Figure 1 this theorem states how it is possible 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' towards g. We present several approaches for this approximation, stressing in particular the application to our situation of the Distributional Policy Gradient (DPG) technique (Parshakova al.) 2019] Khalifa et al. 202T Korbak et al.) 2022a b) Go et al. (023) 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 rarely satisfies the constraint b. We evaluate how closely our GUARD-basee g' approximates the gold distribution g while maintaining high acceptance rate in two scenarios with extensive analysis: a scenario with lexical constraints requiring specific strings to included, and a sentiment reversal scenario with 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' 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:
TThe code is available at https://githhb..cmhavveauuuuu
2

---

Published as a conference paper at ICLR 2025
1. The definition of the distribution & 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-tima methods with inference-ting time methods.
2. The proposal of the GUARD framework, combining method for approximating g by an autoregressive model a' with rejection sampler for enforcing the constraint; a proof that (L'glla') controls both the efficiency of this sampler and its divergence relative to g.
3. Experiments with lexical and positive ending constraints, demonstrating that using GUARD leads to significantly improving the acceptance rate over rejection sampling from the base LLM a. while providing an excellent approximation to gi analysis of the DPG and prompting approximation techniques, and the apparent limitations of prompting with re- spect to the diversity of g in contrast to DPG; the warm-start combination of both tech- niques to speed up the approximation process.
2 FORMALIZATION OF GUARANTEED GENERATION
2.1 DEFINITION OF THE GOLD MODEL
Suppose that we have autoregressive language model with vocabulary V, and let a(y) be the probability of the output sequence y E y = V Our goal is to transform a into a model such that whenever p generates y, then y satisfies the hard constraint b, where b is binary function over Y. Formally, this means that p(y) > = b(y) = 1 for any y E Y. In other words, we want p to filter out outputs that do not respect the constraint
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 to minimally distort the distribution associated with a. This criterion naturally leads the following model g, which we will refer to as the gold filtered model, or simply gold model:
g(v) x a(y) b(y),
(1)
where gly) is the normalized distribution proportional to the value a(y) bly), in other words g(y) 2 ((y)) b(y), with Z = Eyey a(y) b(v).
It is easy to see that 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 for discussion):
g is the distribution a conditioned by the fact that satisfies b, i.e., gvy) a(y [b(y) 1]). g is the I-projection (Csiszár & Shields 2004) of a on the linear space of distributions p that respect the constraint everywhere, that is, such that Vy E V.,(v) > 0 + b(y) = (in Figure [ C was informally denoted by "b = 1²)) In other words, g is the distribution p in that minimizes the divergence (lL(plla).
2.2 FROM GOLD MODEL TO SAMPLER
While g is well-defined distribution, it not immediately associated with a sampler, that is, to a procedure for generating samples following the distribution g. In particular, is not defined in an autoregressive form (which would directly result a sampler), but in the form of an Energy-Based Model (LeCun et al. 2006), as the distribution corresponding to the normalization of the product a(y) b(g)
2 An autoregressive model such as can he seen both as a generator of sequences E ) (that is, as a sampler) and as probability distribution over V. where a(y) is the probability of We sometimes use the notation both for the generator and for the distribution, when there is no risk of confusion. Note that many distributions, such as y below, not have this double nature: g is not directly associated with sampler.
E(y), where E(y) is the "energy" EE2) where Z is a normalization constant. Equivalently, can be presented in the form p(y) x P(y) where P is nonnegative function of (also called a "potential") ").. In our specific case, this potential equal a(y) b(y).
Formally, EBM is any distribution p presented in the form p(y)
of In other words, p(y)= = -Exx)
3

---

Published as a conference paper at ICLR 2025
In order to associate a sampler to 9. 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, we show below. Alternativly, to provide a "good enough" approximation to but is far from obvious how to ensure that such sampler will both satisfy the constraint b and remain close to the gold model. A third approach is to use the ARM a' as a "proposal" inside some Monte-Carlo (MC) inference-time procedure. The framework that we propose, GUARD, of this kind. It strictly guarantees the constraint and attempts to remain close to the gold model, while minimizing inference costs.
ARM a' could be considered in order
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' such that the distribution associated to a' is equal to g? A first attempt could be to sample a large dataset of y's from delete all y's that do contain the token "bad", and fine-tune a on the resulting dataset to obtain a'. However, while a' 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
However, fine-tuning is not the only way to produce autoregressive models. Another approach would be as follows: we could, at each timestep / of the generation of y. remove the token "bad" from the softmax vector p(- p(-1y/e), and renormalize this vector to sum to 1. This would result in an ARM a', strictly satisfying the constraint, but would actually cause a' to have a distribution different from g. a phenomenon detailed in App. C.2
So, obtaining an ARM with distribution g is not obvious, even in very simple cases as above, and we discuss in App. C22 why this is a widespread problem in practice. As we mention there, we are only aware of a 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 We define a function from V to Rd polynomial-time computable (PTC) if and only if it can be computed in polynomial time relative to the length of its argument. A binary predicate is said to be PTC if it is PTC function of its argument. An ARM is considered PTC if and only if the computation of the softmax vector at each step t is a PTC function of the prefix up that step.
The following result was inspired by the pioneering work of Lin et al. 2020b) on the general limita- tions of ARMs. See App. C.3 for a detailed statement and self-contained proof, adapted to the case of filtered models.
Theorem 1. Under the assumption P + NP, there exists PTC ARM and PTC biCary predicate b such that no PTC ARM d' has the same distribution as
Proof intuition. We construct an that generates sequences encoding 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 distribution whose support consists of all the sequences encoding a problem instance and valid solution. If a' were an ARM that corresponded to g. then it would be possible check in polynomial time whether given problem instance carried a non-zero probability mass, and therefore to decide the satisfiability of the problem instance, in contradiction the generally accepted conjecture P # NP.
Interpretation: In practice, the PTC condition is satisfied by all standard ARM architectures. from Recurrent Neural Networks to Transformers of different flavors. Then, in essence, the theorem implies that it is in general impossible to fit y with an ARM under such architectures.
'It should be noted more generally that because fine-tuning a model a into a' never puts zero probability mass on any token, any sequence such that a(y) > 0 is still such that a' 2'(y) > 0. that is, fine-tuiing can never fully eliminate any sequence. This implies that all techniques relying solely on fine-tuning e.g., PPO (Schulman al. 2017) or DPO (Rafailov al. 2023
limited in their ability enforce strict constraints.
4

---

Published as a conference paper at ICLR 2025
2.4 CLAIM: INFERENCE- TIME METHODS ARE NEEDED
While it can be difficult or even impossible to exactly fit 9 with an ARM a', it is still possible to approximate with such a model and this can be done with various approaches such as (i) training a' through Supervised Fine-Tune Tuning (SFT) or DPG (Parshakova et al. 2019), or else (ii) through prompting a with an instruction or few-shot examples attempting to express the constraint in nat- ural language. While the resulting model a' has the advantage that it can be used efficiently for generation, typically does not strictly enforce b, our primary requirement, and we are not aware of general techniques that would allow ARM a' to strictly enforce b while simultaneously limiting the distortion of a' relative to g.
Claim: To achieve this objective, we posit that one has to rely some inference-lime Monte-Carlo (MC) algorithm that exploits the ARM approximation a' 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 pler used in GUARD, that we present now, is a basic form of rejection sampling, but with attractive properties compared to other approaches.
Setropolis-Hasting (Metropolis et al. 1953). The sam-
3 THE GUARD FRAMEWORK AND ITS PROPERTIES
Inside the GUARD framework, we assume that a' some autoregressive approximation to g. The GUARD sampler is then elementary form of rejection sampling which can be described by the following algorithm: sample y from a' until b(y) = 1, then return this y (Algorithm 1). We assume that there exists at least one y E y s.t. a' dv( O and b(y) 1. Such a procedure obviously guarantees that any sample y satisfies the constraint, our fundamental requirement.
We remark that in the special case where a' a, are simply sampling from 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. C.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 However, the third important criterion, efficiency, falls short when a rarely satisfies the constraint which is equivalent to (L(glla) being large (see Eq. 9 in App. C.5).
By approximating & with some a' that has small KL(glla') relatively to KL(g]la) in other words, a' 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 leeelbeeloww below (see also the rightmost panel of Figure| lT characterizes this trade-off formally. Here, for a given a', g' = La denotes both the sampler resulting from Algorithm [ and the associated distribution. A Ru. = bby) denotes the acceptance rate of the algorithm, that is, the probability that a sample from a' respects constraint b and thus is accepted (see App. C.5).
Theorem 2. We have KL(glla') kL(gllg') + KLlg'(laa)) = Kll(gll')) - log ARge
Proof sketch (see App. C.6 for details). The first equality results from the fact that g' is the I- projection of a' on C and from the Pythagorean identity for I-projections (Csiszár & Shields 2004). The second identity obtained from a simple derivation showing that <L(g'laa') = log Z'
- log ARa,, where Z' is the partition function Z' = Eyey a' (v) b(y).
Interpretation: (L(glla') is measure of the divergence of a' from g. As we saw earlier, it is typically impossible to narrow it to O, but we can reduce it by approximation techniques. KL(gllg') measures the divergence of the sampler g' from the gold distribution g, and - -log ARa E [0, oo) measures the "inefficiency" of the sampler, where - logg ARg = 0 corresponds to a maximum acceptance rate of 1. Because KL divergences are non-negative, KLL(gila') is upper bound of both (gllgllg") and - log Z', which means that controlling the approximation quality of a' relative to g is the key to both controlling the quality of g' relative to g and also the efficiency of Algorithm
Approximating the target distribution This last observation motivates the need to minimize (L(g)|aa) to obtain a suitable a'. We consider several methods to achieve this. (1) Prompting can be used to encourage the output respect the given constraint technique we refer to as
5

---

Published as a conference paper at ICLR 2025
constraint-awars prompting (CAP). (2) Another approach consists in using Supervised Fine- Fine-Tuning (SFT). This involves sampling a large number of y's 's from a, filtering them based on b to create a dataset representing the g distribution, and then fine-tuning on this dataset. However, when AR,, is low, very few samples are retained, making this approach inefficient and difficult to use in prac- tice, 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 (Parshakoval al. 2019; Korbak al. 2022b) Go al. 2023) here applied to the specific case of filtered models. This method samples from a proposal initialized with a and updates a' by performing gradient descent on KL(glla"). It is important to mention that while both DPG and SFT seek to minimize (L(glla' (l) (see App. C.7 for more details), one key difference between them is that DPG is adaptive: as the proposal a' approaches y, the frequency and quality of gradient updates increase, making more efficient than SFT (Khalifa et al. (02T). While the original DPG technique shares SFT's initial low AR, during carly training, we can improve this behavior by using constraint for the initial proposal - a method we refer to "warm-start DPG - to accept 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. D as Algorithm 2
prompting
GUARD vs. MCMC and related sampling techniques Simple rejection sampling as in Algo- rithm D 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) (Robert& & Casella 2004), 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[] [] We report in App. ppp.|Hess eeeperimett show- ing that IMH converges very slowly, making it an impractical approach, and motivating our choice of Algorithm| combined with a focus on finding a good approximator a' to g. We also present in App. H some experiments based on Quasi-Rejection Sampling (QRS) (Eikema et al. 2022) a technquee also converging to in the limit which, while still being more costly than Algorithm I is shown to present certain advantages over IMH.
use an autoregressive model as its proposal, and
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 approxi- mation methods within GUARD: CAP, SFT, and DPG 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 [ Since g' is filtered by rejection sampling in GUARD and thus satisfies the first cri- terion by definition, our main metrics in the experiments are the distributional closeness (L(g|lg') and the inference cost defined by the acceptance rate AR Additional details about our metrics are provided in App.
We considering two scenarios, text generation under 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 rarely respect the constraint b (i.e., KL(g]la) log AR, high)
'Training and evaluation were done using the disco toolkit: https: www.:ttt..co//aaae/t/eaeee 'In terms of computation costs, reducing the inference cost related to the acceptance rate AR,,' 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'. which is independent of the inference cost.
"Note that in this work our evaluation focus is in terms of the closeness of g' to the target gold model rather than in terms of the performance of g' on downstream tasks like the ones proposed in benchmarks such CommonGen (Lin et al. (2020a) tasks that see as directly influencing the design of the constraint and therefore the gold model g. which then approximated with g'.
'If the acceptance rate of the base LLM 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.

---

Published as a conference paper at ICLR 2025
Relative position of 'amazing' in the text.
3-
2-
Goldg g
CAPaased
Gold
DPG
0.0
0.2
CAP-based
0.4
0.8
0.8
1.0
Figure 2: 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.)
4.1 UNCONDITIONAL GENERATION WITH LEXICAL CONSTRAINTS
Task description Our first task is to generate a text under a lexical constraint, i.c., such that a specific keyword is included in the generation. The LLM generates text y of 30 tokens, starting with the (bos) token. The lexical constraint b(y) then either rejects or accepts this generated text based whether it contains the string of the keyword. We Gemma-2B (Riviere al. (024)) as our base LLM a. We define the constraint as the binary function that is equal to if and only the generated text y contains the string "amazing", following the experimental setup from Khalifa it al. (2021). This constraint has an acceptance rate ARt of approximately 0.0023 (i.e., on average, one sample is accepted every 435 samples drawn) under the original distribution with ancestral sampling and a temperature of 1.
Empirical results Figure g illustrates the learning curves of (L,(gla')) 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 ARg, resulting in a limited supply of training data, relatively to the budget. Moreover, progresses, the increasing discrepancy between the policy and the sampler a (due the off-policy nature of SFT) causes to reach a plateau and stop improving after certain point. In contrast, DPG shows steady and stable improvement, ulti- mately achieving a better [glllaa) than SFT. We explain this superior performance through two key factors: (1) adaptive proposal the proposal distribution a' in DPG adaptively becomes closer the target distribution g over time; and (2) increasing Alt.' acceptance rate AR,, increases, providing more samples and thus a richer signal for estimating gra- dients. Additionally, warm-start DPG, i.e., initializing DPG with a(- ((-ICAP) to leverage constraint- aware prompt, encourages the model to generate "amazing". improves the initial acceptance rate, and allows to avoid the slow early exploration stage where training samples searce. This results in consistently better performance throughout the whole training process.
Mea somplar
SFT
DPG Baktee with at
BPG intttee with aQCAPI
Kuggiaar
training
10c 100K 200K
4D0K
B0CK
sampling budget
Figure 3: Evolution of (alllaa)) as a function of the number of samples used for training with lexical constraints.
the proposal a' becomes better, the
Figure 4 depicts the results of the trade-off between ARa and KL(gllg") under a fixed sampling budget (800K). The point labeled as ÿ reflects the upper-bound performance as- sociated 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 (i.c., a 435x improve- ment with respect a). Both DPG and SFT show signifi- cantly improved acceptance rates in comparison to a. How- ever, DPG consistently demonstrates superior distributional similarity, measured by KL(gllg'). 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( (CA),, it leverages the high initial A AR, enable suffi-
SIT
*
o
6 10
12
KU/glia
Figure 4: Results terms (L(gllg") (i.e., distributional distance) and
log(AR..) (i.e., inference cost) in the lexical constraint scenario. The dot- ted line indicates their sum, (L(glla'), as stated in Theorem

---

Published as a conference paper at ICLR 2025
cient sampling. This, in turn, allows for rapid reduction of (L(gllg") As a result, the figure shows that this warm-start DPG strictly points. This means that for any given point representing SFT result, warm-start DPG offers better acceptance rate and a lower KI. divergence simultaneously. In summary, the GUARD algo- rithm increases the acceptance rate from 0.0023 to 0.416 (almost 180x) compared to the base LLM a while maintaining minimal distributional distortion.
all SFT
Analysis This section analyzes the deeper phenomena underlying the KL(gllg') results shown above. First, we visualize in Figure the repartition of samples from the gold distribution g. DPG- based g'. and CAP-based g' using UMAP (Melnnes et al. 2018) after embedding them through DistilBERT (Sanh et al. 2019). DPG-based g' and gold distribution y overlap in similar regions, while the samples from CAP-based g' cluster in distinct area. This qualitative observation goes in line with the quantitative results from Figure 4 which reported a better (Llllg'") for DPG-based g' compared to CAP-based g'. Additionally, the CAP-based samples show reduced diversity (i.e., lower coverage). To quantify this loss of diversity, we measured Self-BLEU (Zhu et al. 2018). i.e., the n-gram similarity within the same sample group, and the average semantic similarity between sample embeddings.
As shown in Table [] samples obtained from I and DPG- based o' exhibit similar diversity scores. However, samples filtered through constraint-aware prompting show a signifi- cantly narrower range of diversity. This reduced diversity is also evident in the positional bias analysis in Figure 2 which studies the relative position of the string "amazing" in the generated text. Samples from and DPG-based g' show a rel- atively uniform distribution of "amazing" across token posi- tions, whereas samples prompted to include the string "amaz- ing" led to heavy concentration of this word in early positions. and analysis with other lexical constraints are provided in App. samples.
Approach
2 g-an
3-gran
4:gam
similuity
Goll
0.15
0.117
0.022
0.365
bosed
CAP
0.4%6
0.760
0.193
0.156
0.488
Table I: Diversity of the samples gen- erated by each approach in the lexical constraint scenario. Lower scores indi- cate greater diversity.
Additional experimental details along with examples of generated
4.2 CONDITIONAL GENERATION WITH POSITIVE ENDING CONSTRAINT
Task description Next, we consider a more general guaranteed generation scenario with two fac- tors: (1) conditional generation with prefixes, and (2) threshold- -ased constraints. The common us- age 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 thresholded real-valued function (e.g., to distinguish between positive and negative sentiments). To reflect these two aspects, we investigate story generation task with positive ending constraint for sentiment reversal. In this task, given negative story opening X, the LLM must generate a story continuation and a last sentence Z where the story ending Z is highly positive (see Tables 8 and 2 for examples).
First, we prepared a positive sentiment scorer bycore (y) Hart- mann 2022) and defined our binary, fhreshold-based con- straint as (v) = if and only if (score(y) > т. We then selected our set of openings X by collecting negative story openings from the ROCStories test set (Mostafazadeh et al. 2016). using only the first two sentences of stories for X and imposing that (X) < 0.05. To incorporate the domain knowledge of ROCStories, we use GPT-2 (Radford et al. 2019) fine-tuned on the ROCStories training set as our base LLM a. In this task, given a negative opening X, a comple- tion y = [Y; Z] is accepted if its final sentence Z satisfies b Dscore (Z) > 0.98. The acceptance rate for the base LLM a sample is accepted ev- ery 200 samples drawn). In other words, rejection sampling from a approximately incurs a 200 reduction in the acceptance rate compared to the ideal sampler ÿ.
Madl sumpier Se1
DPG in tistiiee with at DPG titiiee with sTCAA)
Cellnn
200K
500K
1.M
sampling budget
Figure 5: Evolution of KL(gl as function of the number of samples used for training in sentiment reversal.
is AR, 0.005 (i.e., on average,
8

---

Published as a conference paper at ICLR 2025
ERGaeeee Deooee g
Agpoowdh
Serarte
3-gram
4:gaa
5.rrin
Gold
0.784
0.160
0.45%
0.337
0.876
CAP-basol.
0.554
CURI D OPO-EWAYY CAP A
3523
Scrienic 210
Figure 6: 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 com- pletions generated by each method. (Best viewed in color.)
Table 2: Diversity of the samples gener- ated by each approach in the sentiment reversal scenario. Lower scores indicate greater diversity.
Empirical results The sentiment reversal experiment shows similar results as the lexical con- straint experiment. As illustrated in Figure [ SFT reaches a plateau and stops improving after certain point. In contrast, DPG continues improve steadily as its proposal model adaptively approaches the gold model g. ultimately outperforming SFT for a 1.5M sampling budget. Nonethe- less, using 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 ((-ICAP) results in the best training efficiency. This technique bypasses the inefficient early exploration phase by leveraging large amount of accepting samples thanks to prompting.
As shown Figure 7 constraint-aware prompting improves the acceptance rate without any training. but results in dis- tribution 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 op- timize (L())la') demonstrate an increase in AR while si- multaneously showing less divergence from the target distri- bution. DPG, in particular, exhibits a distribution closer to the gold model g. In summary, the GUARD algorithm yields an AR improvement from 0.005 to 0.306 (almost 60x) com- pared while preserving high proximity to g.
CAP
- loglAR) =
aQCAP)
rellain
Kitollen
Figure 7: Results in terms of (L(gllg')
(i.e.. distributional distance) and log(AR (i.c., inference cost) in the sentiment reversal scenario.
Analysis As with the lexical contraint experiments, we plot in Figure 6 UMAP visualization of the DisilBBERT-embeddee samples obtained from g. DPG- based g', and CAP-based g'. Similarly to these experiments, the samples from g and DPG-based g' overlap in the same regions, while the samples from the CAP-based g' result in a more restricted coverage. This visualization confirms that while prompting can increase AR without sampling, also leads to a reduction in distributional diversity. To quantitatively measure this phenomenon, again calculated Self-BLEU scores and the average similarity between embeddings.
The results reported in Table 2 indicate that when conditioning a specific prefix, the diversity is relatively lower compared to unconditional generation (as seen in Table [T. Nonetheless, samples from DPG-based g' and g exhibit similar diversity levels. Instead, samples obtained through CAP resulted in higher similarity, i.e., lower diversity. Figure 6|emmnsttatess that a positional bias is also observed in the case of sentiment constraint. Compared to y and DPG-based g', when prompting to include positive ending, the story continuation shows a more abrupt early shift towards positivity. This further confirms the existence of positional bias in the constraint- 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. G. including examples of generated samples.
prompting behavior
RELATED WORK
LLM alignment LLM alignment techniques are widely regarded as the de facto method for in- tegrating external desirable properties (c.g., helpfulness or harmlessness) into base language mod- els (Kim et al.] 2024). These techniques require access to a preference dataset, which consists of prompts, each associated with several completions, one of which is labeled preferable based on

---

Published as a conference paper at ICLR 2025
criteria like human judgment. Popular approaches in this family include RLHF (Ouyang et al. 2022). which trains a reward model from the preference dataset and fine-tunes the LLM through PPO (Schulman et al., 2017), and DPO (Rafailov et al. 2023), which combines these steps to di- rectly 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. (2024a) for a more comprehensive survey. Existing approaches include prompting to integrate the constraint (Zhang & Song 2022 Yang et al. 2023), )
training techniques related to reinforcement learning (Khalifa et al. 202 Korbak et al. [022b Go ct al. 2023 Lu et al. 2022a) or learning local discriminators to encourage constraint satisfaction
(Meng al.) 2022). else relying on enference-time methods to impose the conditions without
updating the original language model (Dathathri et al. 2019 Krause et al.] [0200] Yang & Klein
2021
Lu et al. 2022b; Liu al. 2021 Eikema et al. 2022; Mireshghallah al. 2022 Kim al.
2023
Mudgal et al. 2023 Chakraborty et al. 2024).
The previously cited papers do not foeus on strictly enforcing constraint satisfaction. However, two recent works (Zhang et al., [202) 2024b) address this issue. Similarly to us, they are able to produce outputs that strictly satisfy the constraint, while maintaining proximity to the original model. They do so by approximating the LLM with a Hidden Markov Model (HMM), and by exploiting the dynamic programming properties of HMMs. This approach enables the computation of a weighted intersection of the HMM with a constraint over lexical items, resulting in a new HMM that always
respects the constraint. Two key differences between their approach and ours are that (i) we handle arbitrary constraints not necessarily of lexical nature which would be difficult to do through HMMs or similar finite-state mechanisms, and (ii) our focus is on producing an efficient sampler that is distributionally close to the gold target distribution g that intrinsically represents the constraint b. In contrast, their focus is on producing a decoder that performs well on downstream tasks that have looser relation to the constraint. We provide more details on these and some other related works in App. B
6 CONCLUSION AND DISCUSSION
In this work, formalize how to guarantee that LLMs perfectly meet specified requirements with- out compromising their usefulness. We first present a thcoretical foundation addressing this chal- lenge 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-satisty 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 compli- ance with specified requirements without diminishing the model's utility. For instance, in safety alignment tasks, GUARD could ensure that the model generates content accordance with ethical guidelines and policy constraints, while achieving minimal loss of helpfulness. Similarly, in tack- ling 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 relia- bility of LLMs. We believe that GUARD has the potential to improve both the safety and efficacy of language models across wide range of applications.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to thank Laurent Besacier and Germán Kruszewski for their valuable feedback on this work.
MK acknowledges that this work was partially supported by Institute of Information & commu- nications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics & NO.RS-2021-1121 1021-11211343, Artificial Intelligence Graduate School Pro- gram (Seoul National University)l.
REFERENCES
Anmol Arora and Ananya Arora. The promise of large language models in health care. The Lancet, 401(10377)x641, 2023.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34:27381-27394, 2021.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307. 15217, 2023.
Souradip Chakraborty, Soumya Suvra Ghosal, Ming Yin. Dinesh Manocha, Mengdi Wang, Am- rit Singh Bedi, and Furong Huang. Transfer q star: Principled decoding for Ilm alignment. arXiv preprint Xrv::220055 20495, 2024.
Imre Csiszár and Paul C. Shields. Information theory and statistics: A tutorial. Commun. Inf. Theory, 1(4):417-528, December 2004.
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung. Eric Frank, Piero Molino, Jason Yosin- ski, and Rosanne Liu. Plug and play language models: A simple approach to controlled text generation. arXiv preprint 19Iiv:191..02.66 2019.
Bryan Eikema, Germán Kruszewski, Christopher Dance, Hady Elsahar, and Marc Dymetman. An upproximate sampler for energy- emergy-based models with divergence diagnostics. Transactions Machine Learning Research, 2022.
Dongyoung Go, Tomasz Korbak, Germán Kruszewski, Jos Rozen, Nahyeon Ryu, and Marc Dymet- man. Aligning language models with preferences through f-divergence minimization. arXiv preprint arXiv:2.302.08215. 2023.
Jochen Hartmann. Emotion english distilroberta-base. httpp::/hugggiiii http://hgggggggac...o//o/e co/
2022.
Edward J Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie, Yoshua Bengio, and Nikolay Malkin. Amortizing intractable inference in large language models. In The Twelfth International Conference on Learning Representations, 2024.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.066 2023.
Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
Muhammad Khalifa, Hady Elsahar, and Mare Dymetman. A distributional approach to controlled text generation. In International Conference on Learning Represeniationss 2021.
Minbeom Kim, Hwanhee Lee, Kang Min Yoo, Joonsuk Park, Hwaran Lee, and Kyomin Jung. Critic- guided decoding for controlled text generation. In Findings of the Association for Computational Linguistics: ACI. 2023, pp. 4598 4612, 2023.

---

Published as a conference paper at ICLR 2025
Minbeom Kim, Hwanhee Lee, Joonsuk Park, Hwaran Lee, and Kyomin Jung. Advisorqa: To- wards helpful and harmless udvice-seeking question answering with collective intelligence. arXiv preprint XXt1:2404.118266 2024.
Tomasz Korbak, Hady Elsahar, German Kruszewski, and Mare Dymetman. Controlling conditional language models without catastrophic forgetting. In International Conference on Machine Learn- ing, pp. 1199--1 1528. PMLR, 2022a.
Tomasz Korbak, Hady Elsahar, Germán Kruszewski, and Marc Dymetman. On reinforcement learn- ing and distribution matching for fine-tuning language models with catastrophic forgetting. Advances in Neural Information Processing Systems, 10116220--622,,, 2022b.
Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq Joty, Richard
Socher, and Nazneen Fatema Rajani. Gedi: Generative discriminator guided sequence generation. arXiv preprint arXiv:2009.06336 2020.
Germán Kruszewski, Jos Rozen, and Mare Dymetman. disco: toolkit for distributional control of generative models. arXiv preprint arXiv:2303.05431 2023.
Tiffany H. Kung, Morgan Cheatham, Arielle Medenilla, Czarina Sillos, Lorie De Leon, Camille Elepaño, Maria Madriaga, Rimel Aggabao, Giezel Diaz-Canie Candido, James Maningo, et al. Per- formance of chatgpt usmle: Potential for ai-assisted medical education using large language models. PLoS digital health, 2(2):c0000199 2023.
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, Fujie Huang, et al. A tutorial on energy- based learning. Predicting structured data, 1(0), 2006.
Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. CommonGen: A Constrained Text Generation Challenge for Generative Common- sense Reasoning. arXiv preprint arXiv:1911.08.
2020a.
Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R Gormley, and Jason Eisner. Limitations of autore- gressive models and their alternatives. arXiv preprint arXiv:2010.1 1939, 2020b.
Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A Smith, and Yejin Choi. Dexperts: Decoding-ting controlled text generation with experts and anti-experts. arXiv preprint arXiv:2105.03002 2021.
Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer, 2004.
Ximing Lu, Sean Welleck, Liwei Jiang, Jack Hessel, Lianhui Qin, Peter West, Prithviraj Am- manabrolu, and Yejin Choi. Quark: Controllable text generation with reinforced unlearning. arXiv preprint arXiv:2205.136:3 2022a.
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, et al. Neurologic a*esque decoding: Constrained text generation with lookahead heuristics. In Proceedings of the 2022 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 780-799, 2022b.
Leland Mclnnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint
2018.
Tao Meng, Sidi Lu, Nanyun Peng, and Kai-Wei Chang. Controllable text generation with neurally- decomposed oracle. In Advances in Neural Information Processing Systems, volume 35, 2022.
Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6); 1953.
Fatemehsadat Mireshghallah, Kartik Goyal. and Taylor KirngKKikatttic... Mix and match: Learning- free controllable text generation using energy language models. arXiv preprint S.ti:2203.13299) 2022.
12

---

Published as a conference paper at ICLR 2025
Mehryar Mohri. Sinite-state transducers in language and speech processing. Computational Lin- guistics, 23(2):269 311, 1997.
Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruy Batra, Lucy Vander- wende, Pushmeet Kohli, and James F. Allen. A corpus and cloze evaluation for deeper under- standing of commonsense stories. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp- 839 1199-849222 2016.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng-Tze Cheng, Michael Collins, Trevor Strohman, et al. Controlled decoding from language models. arXiv preprint arXiv:2310. 17022, 2023.
OpenAI. Gpt-4 technical report. arXiv preprint arXiv:2303.087774, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35: 27730-27744, 2022.
Tetiana Parshakova, Jean-Mare Andreoli, and Mare Dymetman. Distributional reinforcement learn- ing for energy-based based sequential models. arXiv preprint arXiv:19/2.08517, 2019.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding Learning. Cambridge University Press, 2023.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 188):9 2019.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model secretly a reward model. In Advances in Neural Information Processing Systems 36: Annual Conference Neural Infor- mation P Processing Systems 2023, NeurlPS 2023, 2023.
Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. Gemma 2: Improving open language models at a practical size. arXiv preprint arXiv:2408.00/ 18, 2024.
Christian P. Robert and George Casella. Monte Carlo Statistical Methods. Springer, 2004.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 108, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1.XXvv/007.000 170.0063477 2017.
Brandon T. Willard and Rémi Louf. Efficient Guided Generation for Large Language Models. arXiv preprint 30XXi:22007.09702, 2023.
Kevin Yang and Dan Klein. FUDGE: Controlled text generation with future discriminators. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, 2021.
Kexin Yang, Dayiheng Liu, Wenqiang Lei, Baosong Yang, Mingfeng Xue, Boxing Chen, and Jun Xie. Tailor: A soft- soft-prompt-based approach to attribute-based controlled text generation. In Pro- ceedings of the 61st Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Longg Papers), pp. 410-427, 2023.
Kang Min Yoo, Jaegeun Han, Sookyo In, Heewon Jeon, Jisu Jeong, Jaewook Kang, Hyunwook Kim, Kyung-Min Kim, Munhyong Kim, Sungju Kim, et al. Hyperclova x technical report. arXiv preprint 4r04 01554, 2024.
Ines Zelch. Matthias Hagen, and Martin Potthast. Commercialized generative ai: A critical study of the feasibility and ethics of generating native advertising using large language models in conver- sational web search. arXiv preprint arXiv:2310.04892 2023.
13

---

Published as a conference paper at ICLR 2025
Hanqing Zhang and Dawei Song. Discup: Discriminator cooperative unlikelihood homppttunnng for controllable text generation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. pp. 2392-3406, 2022.
Hanqing Zhang, Haolin Song, Shaoyu Li, Ming Zhou, and Dawei Song. A survey of controllable text generation using transformer-based pre-trained language models. ACM Comput. Surv., 56(3): 64:1-64:37, 2024a.
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for au- (oregressive language generation. In International Conference on Machine Learning, pp. 40932- 40945, 2023.
Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng. Adapt- able Logical Control for Large Language Models. arXiv preprint arXiv:2406. 13892, 2024b.
Yaoming Zhu, Sidi Lu, Lei Zheng, Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. Texygen: A benchmarking platform for text generation models. In Proceedings of the 41st International ACM SIGIR Conference on Research Development in Information Retrieval, pp. 1097-1100, 2018.
14

---

Published as a conference paper at ICLR 2025
A LIMITATIONS
It is important to acknowledge the limitations of the GUARD framework, in particular when the filtering model 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 way that it is able to accurately identify such outputs is undoubtedly important, but beyond the scope of the present work.
B COMPLEMENTS ON RELATED WORK
Relation of our work to Zhang et al. 2023 2024b) Similar to us, the approach from Zhang al. (203) is able to produce outputs that always satisfy the constraint, while maintaining proximity to the original model. does so by approximating the LLM with HMM, which, in contrast the LLM, supports a dynamic programming approach to complying with lexical constraints over the output, and therefore the ability to weigh the long-term consequences of local next-token choices relative to these constraints. When the HMM approximation to the LLM is good enough (which depends in particular on the number of states of the HMM), the same HMM can used inference time with different lexical constraints without need of retraining.
While such an approach is relevant for guaranteed generation, we note several fundamental differ- ences with what we do:
1. We handle arbitrary logical constraints (that is, binary predicates), not necessarily of lexical nature, which would be difficult to handle through HMMs or similar finite-state mechanisms.
2. We give central status to the "gold" constrained distribution which is the distribution that minimally deviates from the original distribution while still fully satisfying the con- straint, and we evaluate the quality of our sampler in terms of distributional distance to this distribution g. Zhang et al. (2023) do not focus on the evaluation reference distribution, but rather on the evaluation of decoder in terms of downstream tasks which have a looser relation with the constraint.
sampler relative to
3. We study the trade-off between the quality of the sampler and its efficiency in the context of simple rejection sampling mechanism based of and show that quality and efficiency are both directly controlled by the divergence (L[9llaa). This in turns motivates interest in approximation technique that focuses on minimizing this divergence, such as DPG.
autoregressive approximation a'
The work from Zhang et al. (023) is extended in a follow-up (Zhang et al. 2024b) which considers lexical constraints defined through deterministic finite automata. As side observation, in App. C.2 (Solvable instances of the problem), we have briefly mentioned that case the base ARM and the lexical constraint are based weighted finite state automata, the intersection of these automata could be constructed and sampled from. We note that such weighted automata are naturally very much related to HMMs, and might be interesting study in their own right.
NADO sampler (Meng et al. 2022) The NADO distribution introduced in Meng et al. (2022) is trained with an objective similar to ours - namely, it tries to approximate a distribution compara- ble our gold filtered distribution g. As a training method to obtain an autoregressive distribution similar to our a', it has some analogies with (i) SFT, by training on samples from the filtered distri- bution, and (ii) DPG, by also performing a kind of distributional matching, but with more emphasis on local (i.e., token-level) decisions. Contrary to DPG, NADO does not directly have the objective of minimizing the divergence KL(glla'). which is the determining factor for the success of GUARD as shown in Theorem 2 Using NADO for a' would nonetheless be interesting as a follow-up work, to see whether the value its divergence is competitive with the cases we have explored, leading to improved performance for GUARD.
15

---

Published as a conference paper at ICLR 2025
C ADDITIONAL BACKGROUND AND THEORETICAL DETAILS
C.I CHARACTERIZATION OF
We have defined the distribution و through the formula ( 7 aayy) bly), with Z Eyey a(v) b(y). It is straightforward to see that g is simply the distribution of renormalized over the subset Vi = (y E b(y) 1) and equivalently that g is the distribution of conditioned on b(y) = 1, in other words g(v) = a(y (b(v) = 1)).
A less obvious observation is the fact that g is also the I-projection (Csiszár & Shields 2004 Section 3) of a on the space of all distributions over y that satisfy the constraint bly)
everywhere Thus, according the definition of I-projection, g the distribution p this space that minimizes the divergence KL(pliug a). In other words, is, among the distributions that fully satisfy the con- straint, the one that minimally distorts a, in terms of KL divergence fact that further supports our characterization of g as the ideal guaranteed model associated with and
Let's provide a self-contained proof of that fact. We have:
KL(glla) Ey log g(y)
Byng log a(y)b(u) log Z Bygu log b(y) log Z,
(2)
a(y)
7 aay)
p(y) g(y)
Z ply)) a(y)b(y)
ply) a(y)
KL((plg) y log
Eysp log
loog Z Eyyp log
log 7 + KL(plla).
Hence we have KL(p]la) (L + (L [a)] and because KL divergences are nonnegative, see that (L(glla) I KL((lla) which proves that g is the unique distribution in that minimizes (L(plla), namely, that g is the I-projection of a on C.
Controlling the distortion of a's capabilities through the use of The fact that g = 2 2a(y) b(y) implies that for any two sequences v. with bly) b(y') = and a(y) > 0, we
1
have g(v) > 0 and:
( g(v)
a(v')
alv)
In words, this means that if v/ is times more likely than y relative to the original model and if both y and y' respect the constraint, than y' is still exactly a times more likely than y relative to g.
For example, suppose that, relative to the sentence "Potatoes were first cultivated in South Amer- ica" 100 times more likely than the sentence "Potatoes were first cultivated in Africa", and that both sentences satisfy the constraint, then the first sentence will still be 100 times more likely than the second relative to g.
So g does not distort the knowledge/reasoning capabilities of outputs that respect the con- straint. This property is not true for alternative models, even they only produce outputs respecting the constraint, and is clear advantage of g as a target model.
C.2 ON THE LIMITATIONS OF AUTOREGRESSIVE MODELS IN REPRESENTING g
We start the discussion with two simple examples illustrating the difficulty of representing with an autoregressive model.
Avoidance example First, come back to the situation described in the main text where the constraint 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 the token "bad". Furthermore, fine-tuning would be pretty inefficient, even as an approximator, for this "avoidance" situation:
" can also be seen, in the terminology of (Csiszár & Shields 2004 ) the linear variety of distributions 1, because here is
p that satisfy the expectation constraint (also called moment constraint) Tyyspb(y) function with values in {0, I, and therefore such p's are identical with p's that satisfy the constraint on all y 10 Uniqueness comes from the fact that any p such that KI-(glla) [a) (p.(p) (a) is also such that (Il())))) hecause of the identity above and therefore such that p g-
16

---

Published as a conference paper at ICLR 2025
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(-lu<<t), and renormalize this vector to sum to 1 1 This would result in autoregressive model a' that always respects the constraint, but whose distribution would differ from g. Intuitively, this would be because the distribution for 9, which corresponds 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' would ignore any such influence
Enforcement example Conversely, rather than trying to avoid 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) a large dataset from o, keep only the sequences containing "good", and fine-tune an ARM a' on the resulting dataset. However, while a' would be better than a at producing sequences containing "good". it could still produce other sequences. and therefore would not strictly guarantee the con- straint (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 contain- ing 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 (eos) token). This would result in an ARM a', which would guarantee strict satisfaction of the constraint, but the distribution of the sequences produced by a' 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 produce "good" at later stage, a' would totally ignore such influence of "good" over the early tokens. We intuitively expect that a' would tend to produce longer sequences than g. because there would be little incentive to produce "good" early on during the generation! [3] This was verified through a simple experiment in App. F (Comparison to a heuristic sampler), which confirmed that such an approach does not provide a satisfactory approximation to g.
iff y contains the token "good". Here, we could again sample
In the two previous examples, of course, we did not provide a proof that modeling g with an autore- gressive 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 probabilistic weighted finite-state automaton (WFSA) (Mohri) 1997). a classical form of autoregressive model, and such constraints as the presence or absence of 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 y through an ARM would be
"This is special case of a more general technique based on lexical constraints described by finite-state automata, see c.g. WWillard & Louf (2023).
The intuition may be elearer with more cituation-specifii word such "malaria": in order to climinate sequences containing this word from a, g has depreciate the probability of prefixes that naturally lead to that word- - such as "This proliferation
mosquitoes raises the risk of" - while an a' intervening on the local generation of "malaria" would not perform such anticipation.
"Aggin, the intuition might be clearer if the constraint was about producing a rarer word than "good", associated with specific situation, for instance "trophy". Sequences from a containing this word, which would be selected by 9. would tend to start differently than generic sequences from a, but a' would not show this kind of influence.
"Zhang et al. (0024b) recently proposed a technique with some similarities to what we are describing here, by performing the intersection of an HMM (a formalism with strong connections with WFSAs) with a finite- state automaton imposing lexical constraints. In order to apply this technique to standard neural LLM, the authors propose to first approximate this LLM with an HMM, before applying the finite-state constraints. See Section lnd Bpp.Bfoor for more details that work.
17

---

Published as a conference paper at ICLR 2025
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 is the constraint which imposes the presence of certain prefix [9 : M/l at the beginning of the generated sequence y. is easy to wel)s Vt++ al-Ily1;;... gt++11 +1 and so
that the generative process that samples Ut+1 ~ a(-I[yn;; autoregressive model a' that has the same distribution as However, again, this is 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.
on, in the standard way, corresponds
No general solution exists To conclude, seems challenging to model g with an ARM. Thcorem [ |ctually proves that the general problem is unsolvable, by relying more abstract mathematical situation.
that in practice, even in quite simple cases, it
C.3 DETAILS ABOUT THEOREM
A more precise statement of Theorem 1 is provided below:
Theorem 1' Under the assumption P + NP, there exists a polynomial-time computable (PTC) ARM and a PTC binary predicate b such that PTC ARM a' has the same suppor as the gold model g. and in particular, has the same distribution as
In this statement, when we speak of an "autoregressive model", we mean a model m over sequences y E V*, with V finite vocabulary of tokens, which generates y in the following way:
1. At each time-step 6, given the prefix V<t [yii...; St- i] of already generated tokens, function / is applied on the prefix, where (Vcr) E IR VI, In other words, the value of the function vector of real numbers over the vocabulary V.
2. A softmax transformation applied to the vector fV):), yielding probability distribution over V.
3. The token y is sampled from this distribution, and the generation proceeds recursively.
As for the PTC qualification, we say that a function is PTC it can be computed in polynomial time relative the length of its argument. In particular, the function is PTC iff it is computable in polynomial time relative to the length t 1 of the prefix yer. and the binary predicate b PTC iff computable in polynomial time relative to the length of y.
The PTC assumption about f is essential here. is satisfied by all standard implementations of autoregressive models, from RNNs Transformers of different flavors. As for the PTC assumption about 6, without it, the theorem would be devoid of interest.
C.3.1 PROOF SKETCH
Consider any NP-complete problem, for instance 3SAT (Karp, 2010), a problem also con- sidered by (Lin al., 2020b). Now consider textual sequence y of the following form: problemte iassiggnentt where the first part is some encoding of a 3SAT problem instance over boolean variables, and the second part the encoding of candidate assignment (i.e. 0 or for each of the l variables.
Two examples of such sequence encodings would be 16
r1 V x2 V r3 -11 V
-33 #
110
x1 V =2 x3 :-11 -z3 010
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 the length of y. On the other hand, under the standard conjecture
The support of a distribution over y is the set of y's such that p(v) > 0. Here the token vocabulary would be V {x, 0. 1, 2, 3, 7,8, 7,
18

---

Published as a conference paper at ICLR 2025
that P * NP, it is impossible, by looking at the problem instance, to check in polynomial time whether this probler 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 se- quences, all sequences that cover any syntactically well-formed problem ass i gnment, even the assi assignment is only a possible candidate, but does not actually satisfy the problem in- stance Whatever the exact nature of a, the key point is that, for any sequence y encoding well-formatee problemtt a s grment, we have a(y) > O. Crucially, this is true whether or not the ass assignment is actually valid relative to the problem.
Given this a, now consider predicate b(y) that checks two aspects, a syntactic one and semantic one:
1. Syntactic check: whether y respects the format jects y.
and if not,
2. Semantic check: assuming that the first check was successful, b now checks that the gnment 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, (qy) is a distribution that gives positive probability to any y of the form probl 1 em assi gnment, where the ass i gnment satisfies the prob em, and zero probability to any other y. Thus the support of g the set of probl em gnment: y/s that are valid.
Now suppose that there exists some PTC autoregressive model a' such that the support of a' is equal to the support of g. Then y is generated by a' iff y is of the form probl ee www.aasignnntni assiggnent, where ass iggment satisfies problem. In particular, this means that a' starts by generating probles em that is satisfiable, and furthermore, that it can only generate satisfiable problems. Now, this provides us with decision procedure to determine whether a given probles problem is satisfiable not, namely, we give the problem, em as a prefix to a', and ask a' whether it gives a zero probability or a positive probability this prefix. This can be done by running a' autoregressively over this prefix.
The time complexity of that decision procedure can be computed as follows. Let us write the pre- fix pref in the form pref [M1; [21;;...;: :.p,,, with pl denoting the prefix length. Then we have a' (pref)) = a' (xx) )- )-a((22/=1)) (Iz]/=))..... .....-a' ( invoke the autoregressive model to compute the probability of xe given the previous tokens. This computation occurs in polynomial time relative to t. Therefore, the whole autoregressive computa- tion of a' (pref) is performed in polynomial time relative the length of the prefix pl.
1])- where at each step a' (xrl. iI)
Overall, we now have a polynomial time algorithm that decides whether the problem as encoded by pref is satisfiall.. This contradicts the P & NP conjecture, and we conclude that the support of a' is different from the support of g, and in particular that, as distributions, a' o 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 base model. Indeed, we are just speaking of a model a being conditioned by a predicate b. This may allow 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 aa gnment, by delegating the syntactic verification to b, an obvi- ously polynomial-tine check; and, more importantly, (2) to avoid looking for a proof relying on the
Such an 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 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 actually need for our proof.
19

---

Published as a conference paper at ICLR 2025
impossibility of finding in polynomial time valid assignment for satisfiable problem instance, because this would involve preliminary distinction between satisfiable and unsatisfiable instances, something that cannot be done in polynomial time. Our proof avoids this issue completely, by focus- ing on full probl em# aas gnment pairs, of which the validity is easily checked polynomial time.
C.4 CHARACTERIZATTIN OF g'
Let ('(v) = d'((bb(y) and p' (v) be the distribution such that p'(v) x (y) Then p'e) = P'
a'(y)-1 b(y). According to the fundamental result about rejection sampling. see (Liu) 2004, Section 2.2), p' is the distribution obtained by sampling y ~ a' and accepting y with probability r(y). which our case is either 0 or 1. This is exactly what Algorithm [ does, and therefore g has the same distribution as p', in other words:
with z' = Eyer P'y). We have P'(y) S d'(y) 1, and r(y) = P'(y)
O'(v) = z a''())(())) x a' (z)b(u).
(4)
(5)
We finally note that when a, Eq. implies that the distribution g' associated with Algorithm is actually equal to the gold model
C.5 RELATIONSHIP BETWEEN KL(g'(aa)) AND ACCEPTANCE RATE AR
By the same reasoning in App. C.4 applicd to d', we see that g' (v) a' d'())(y)). and therefore g'(v) = z (v)b(y) where Eyey ((y))
easy to see that Z' is also the probability that a sample from a' is accepted by Algorithm | namely the acceptance rate ARa' and therefore AR,' Z'.
We then have (L(g'lla') = Eyngg log ('v)) (v)) hence:
b(y) Byngg log 1 z log Z'
KL(g'lla')= Byng' log Z'
log ARR
(7)
Because and g special cases of a' and g' respectively, also have:
KL(g (a) - log
(8)
log A AR.-
(9)
C.6 CORE THEOREM ABOUT GUARD
The fact that
KL[glla') KLL(llo') KL(g'lla')
a consequence of the Pythagorean Identity for I-projections, as stated in Theorem 3.2 of Csiszár & Shields (2004). In order to apply the theorem, we observe that the set C of distributions p such that ply) > += b(v) = is identical to the linear family of distributions that respect the expectation constraint E. byy) = 1, because in our case b(y) can only take the values 0 or 1. The distribution g' is the I-projection of a' onto C, and according to the theorem, for any distribution p E C, we have conclude (see Figure 8).
(Ll(a)aa)) KLl(plo')) KL-(g' (la))"lla"). Because g is in C,
20

---

Published as a conference paper at ICLR 2025
a'
(I(''llaa)
(L(olla')
log ARo
g'
g KL[g|]g')
C
Figure 8: (Same as right panel of Figure 1 The g' distribution is the 1-projection of a' onto the space of distributions respecting the constraint, that is, is the distribution p in C that minimizes KI-pplaa). The Pythagorean theorem says that, for any such distribution p. (L(plla') KL(plls') ) KL(g'lla) particular (L(glla') KL(glly') + (L(g') (['](l")). Independently this fact, we have (L where AR, is the acceptance rate associated with Algorithm
log ARa',
We can also provide a simple, direct proof of this equality for our specific case. We have:
g(v)
Byyng log Zzg(y)
Kl-(gllg') Ry log g'(y)
d'(y)b(y)
g(v) log Zz + KL(g)la').
log Zz yng log
a'
g'(y) Ey log a' d'(y)b(y)
KL(g'lla') Eyyog log a'(y)
7'a'
log Z'
Hence KL(glla') (L(g + (L'g'lla').
We then apply the identity from Eq. and conclude the proof.
C.7 MINIMIZATION OF (L(gllaa)
As discussed Section 3 and in the interpretation of Theorem minimizing KL(g](a') results in finding suitable a' for GUARD. In this section, show that both the SFT and DPG approximation techniques seek to minimize this objective.
The SFT loss corresponds to the cross- coss-entropyy of the model a' to be learned, using samples from g, i.e, -Ey-g log a' (y). Minimizing this term with respect to a' is equivalent to minimizing (L[gglaa)
since KL'glla') Ey-g log g(v) Ey-g (oggg(v) - Eyng log a' (y) Hg Eyy- log a'yy) where ('(
Hy the entropy of g, which is a constant independent of
The objective of DPG is also to minimize the KL divergence (or equivalently, the cross-entropy) between the target distribution and the learned policy a' = Ty as detailed in Parshakova et al. 2019 Section 3.2). The derivation be summarized follows: VoKL(gl|Tg
Vo(Hg s(y) V log To(y), where the last step is ob- En log Ty))) = EEywg Ve log (e()) = - Ey xe(x)
tained by applying importance sampling using Ty as the proposal. Performing gradient descent
on -Eywno a(y) Vo log To(y) leads to the DPG update rule shown Line 21 of Algorithm below).
(see
()(
D GUARD'S TRAINING ALGORITHM
Algorithm 2 illustrates the GUARD training process with DPG. The optional orange-colored steps referring to the warm-start initialization of DPG focus
which correspond to what increasing the AR,, through the CAP proposal, while the remaining steps follow the version of the DPG algorithm presented in Go al. (2023 Algorithm 1). By initializing DPG training with
21

---

Published as a conference paper at ICLR 2025
Algorithm 2 GUARD training with warm-start DPG
1: Input: a(-), b()), CAP, total sampling budget BG, CAP sampling budget bg
2: < a(.)
Policy
3:
4: b Initialization with CAP proposal
5: +
Dataset of CAP samples
6: Sample [3/1..... ..................... ,,....,, Vbg from a(-[CAP)
7: for 1 to bg do
8: if b(y,) = then
9: Append y/ to
10: Fine-tune policy my on dataset D
12: b Training with To proposal
P(v)= + a(y)b(y)
Unnormalized target 4 Partition function & Sample count
14: Z 7+0 0
N
16: while N < BG by do
Remaining sampling budget BG bg
Sample y from T
18:
N N +1
(N- (N alvl0(s)
Z
Moving average estimate of Z
20:
p(u) + P
21:
<- 0 + ply)
Vo logno(y)
Core DPG update rule
ma(y]
Output: no
high-AR To obtained through CAP, supply large number of samples to the KL(glla') minimization process, leading to more efficient training.
E ADDITIONAL METRICS DETAILS
Acceptance Rate AR represents the proportion outputs sampled from that satisfy the constraint b(y). Formally AR. is defined the expected value of the constraint function b(y) under the language model distribution a', which is given by AR, = Ey-ar (byy). Higher AR,, indicates the sampler has faster inference speed.
Distributional Closeness In Theorem 2, we aim to minimize the KL divergence between the gold distribution g and the distribution produced by our framework. We can estimate the quality of GUARD, represented by KL(gllg'), by using the following identity:
KL(gllg') Ryyng log g(y) Engn log a(y)b(v) Z' Z d'(y)(uu) Enyng log d'
a(y)
Z
log Z
(10)
g'(y)
where the expectations relative to g can be estimated by obtaining samples from g through sampling from a and filtering with b, and where the values of Z and Z' can be obtained by exploiting the equalities Z AR,, Z' AR, (see App. C.5 and by estimating these acceptance rates.
In practice, these computations were performed using the disco (Kruszewski et al. (023) toolki 1B and the estimations are made using 220 (i.e., approximately IM) samples from a. After filtering with b, we obtained around 2,300 samples from g in the lexical constraints experiment (AR, 0.0023) and 5,000 samples from g in the sentiment reversal experiment (AR, 0.005).
Self-BLEU BLEU evaluates how similar a language model's output is to candidate references using n-gram matching. Similarly, Self-BLEU Zhu et al. (2018) measures the diversity of generated outputs by selecting K samples from the model's 's output and calculating the average BLEU score of
22

---

Published as a conference paper at ICLR 2025
Hyperparameter
Value
Base LLM a(-)
Gemma-20 2 20
Max sequence length
30
Learning rate
1.41e-5
Optimizer
Adam
DPG #samples per step SFT batch size per step
{2000, 5000, 10000)
16, 32, 64)
Sampling budget used with a(-ICAP)
10000
Prompt used for warm-start proposal a(-ICAP)
Next sentence should contain "amazing"
Table 3: Hyperparameters used for the lexical constraint experiment.
each sample against the remaining K- - 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 dis- tribution (g or g¹). We then randomly select 10,000 pairs of outputs from these 500 samples and embed them measure their cosine similarity in the embedding space. The average of these sim- ilarity scores is then calculated. For the lexical constraint experiment, we encoded the Gemma-2B model outputs using the Gemma-7H model. In the sentiment reversal experiment, we encoded the GPT-2 model outputs using BERT.
F LEXICAL CONSTRAINT EXPERIMENT
Additional details For the lexical constraint experiment, use Gemma-2B (Riviere al. 2024) to generate 30 tokens through ancestral sampling, starting with (bos) 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 nucleus sampling. The sampling budget is defined as the number of samples drawn from proposal a, a(-[CAP) or af 19 for training purposes. For DPG, this is #samples per step x step size, while for SFT, it is batch size x step size. In the case of SFT, sampling is done only from a, so the expected training set size is sampling budget x ARg. For DPG, as the adaptive proposal gradually approaches g. the number of samples increases with each step during training. Naturally, A is initially low, resulting in fewer samples, but this disadvantage can be mitigated by sampling from a(-ICAP) 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
Additional analysis Based on the experiments discussed in the main body of the paper, we analyze how the phenomena observed in the analysis reflected in the actual text. As shown in Table texts generated from the DPG-based g' 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
Comparison to a heuristic sampler We performed a simple experiment using the heuristic sam- pler for keyword enforcement described in the Enforcement example paragraph of App. C.2 using "amazing" as the keyword to include in 30-token generated text as in the experimental setting of Section [4_] We define a sampler that checks whether we have already produced the string "amaz- ing" within the first 29 tokens, and if not, forces the generation of "amazing" as the last token. With the Gemma-2B tokenizer, the string "amazing" can be generated with the single token [amazing] (along with [ama, zing), etc.), and we can easily design the sampler produce this token as the 30th token "amazing" does not appear earlier. For such sampler 8, we found that (L[g]|s) 6.06, which is a significantly larger divergence than KL KL (llgg 0.633 for warm-start DPG-based g' as
19 More precisely, the evolving - in other words what denoted by no in Algorithm 2 ce co/ /oogo gemm 2b
23

---

Published as a conference paper at ICLR 2025
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 merged with pandas data. change:
How to change the decimal separator in MS Word?
amazing:
Write a text containing "amazing". as shown below.
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" paragraph with 'amazing":
Text examples with 'amazing'.
The following sentence contains the keyword 'amazing'.
Table 4: Constraint-aware prompts used for the lexical constraint experiment.
Relative position of 'restaurant' the text
Relative position 'world' in
18
2.0
38-
1.5
3.5
1.0
1.0-
0.5
0.5
Gold g
0.0
0.2
based gf
0.8
Gold g
0.0
0.2
CAPbased
0.4
0.5
0.8
1.
Figure 9: Additional positional bias analysis using the "restaurant" and "world" strings.
reported in Figure More generally, the divergence (L(gl|s) is much greater than the divergences obtained for any g based on DPG or SFT, whose values are always smaller than 3. This result ap- pears to be consistent with the behavior we had anticipated in App. C.2 namely the poor ability of s to approximate g due to the biased positioning of "amazing" the generated sequence.
G SENTIMENT REVERSAL EXPERIMENT
Additional details The lexical constraint experiment was set in an unconditional generation con- text (i.e., without any prefix), which makes the distortion due to prompting particularly severe. Therefore, it necessary to thoroughly examine the phenomena that occur when KL(glly' in- creases in conditional generation setting. For this experiment, from the ROCStories test set (Mostafazadeh et al.) 2016). 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 this experiment are respectively shown in Tables b 7 and 8 To define b(y), i.e., accept reject generated story, used threshold criterion based on an existing emotion text classifie 22 using the "joy" class probability output. Specifically, accepted stories where the "joy" class probability of the last sentence exceeded 0.98.
selected negative story openings
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' have a natural flow
24

---

Welcome Guest, Published as a conference paper at ICLR 2025
DPG-based g'
CAP-based g'
To be successful when lackling difficult prob- lemss and amazing your customers you need a space to think and solve these concerns. At CKWI, our expert and
1. amazinng ads on TV: They broke the adver- tising law and added more than 5 numbers to admit simulation! 2. Agata
Staten Island world renowned for dog- friendly beaches and amazing shops. The zoo park is always hit for residents and tourists alike. Visits
most amazing facts about marine animals. paragraphs: paragraph, paragraph. extension: zoom calculations: result of calculation appli- cation programming: application
Things wouldn't be so amazing without all that PERFECTNESS which call 'Love'... Thanks Vernachael. I'm dropping by
We do believe having great relationship with clients invaluable, therefore we strive make your playing experience as comfortable, amazing and exciting
Join Uzbekistan.
amazing journey In Southern agree, that is truly amazing. like the fact it is all customisable.
17 days Arrive in Tashkent and upon arrival, we will pick you up from the Airport
That's nice bet it stinks out the exhaust fumes
Table 5: Example of generated samples for the lexical constraint experiment. Red-colored text indicates the occurrence of the required string "amazing".
Hyperparameter
Value
Base LLM a(-)
GPT2-Finetune-
Max sequence length
80
Learning rate
1.4le-5
Optimizer
Adam
DPG #samples per step
10000
SFT batch size per step Sampling budget used with a(-ICAP)
64
10000
Prompt used for warm-start proposal a(-ICAP)
This is happy ending story:
Table 6: Hyperparameters used for the sentiment reversal experiment.
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'.
A note about the Story Infilling task of (Hu et al., 2024) Our sentiment reversal experiment bears some connections with the Story Infilling task from Hu et al. (2024) Section 4.2), where the authors consider the task of generating the middle (fourth) sentence of 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 (Bengio al. 202T) 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 story in such a way that the story ends a fully specified sentence). In other words, our version of the task can be considered as soft Story Infilling. Additionally, the base model we use is GPT-2 fine-tuned on the ROCStories training set, as in Hu et al. (2024). However, our approach is quite different both in the goal and in the method used. We are trying obtain sampler g' that produces texts coming from a distribution close to where 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 by the constraint that they end on specific sentence, but only use 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 the middle sentence in the ROCStories test set, while we evaluate our results in terms of the divergence with the gold distribution and of the efficiency of the sampler in producing positive endings.
positive sentence (instead of ending with
the gold distribution
25

---

Published as a conference paper at ICLR 2025
This a happy ending story:
In the end, it was story that had a truly happy ending,
This is my positive ending story.
Eventually, it turned into really fantastic day:
Here is example of paragraph starting up with negative sentiment but ending positively:
Happy ending story:
Eventually, it turned into really happy day!
There was a little bit of bad luck, but it was a happy day!
was so lucky even there were some obstacles.
Table 7: Constraint-aware prompts 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 bad kid. He never followed his parents advice.
Bobby registered his son for tee ball. His son wasn't 't having a good time.
Table 8: Negative story openings used for the sentiment reversal experiment.
H DISCUSSION OF ADDITIONAL SAMPLING TECHNIQUES: IMH AND QRS
This section contrasts the efficiency of GUARD inference time with one MCMC technique, IMH (Robert & Casella 2004), and one variant of rejection sampling, QRS (Eikema et al. 2022). It com- pares outputs from these different sampling methods, starting with specific proposal distribution a': rejection sampler g' as GUARD, IMH sampler, and QRS sampler. QRS is an extension of re- jection sampling that offers two benefits over IMH 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 by allowing quantification of the output probability of y.
QRS implements the acceptance criterion corresponding to accepting y with probability min(1, (e) ), where 3 a positive hyperparameter with the following properties:
1. As 3 approaches O, QRS becomes equivalent to the GUARD form of rejection sampling (Al (Algorithm D.
2. As increases, QRS more closely approximates g, but at the of additional inference time.
This comparison permits an analysis of the trade-off between sampling accuracy and computational cost across these different methods.
H.1 EXPERIMENTAL SETTING
Directly comparing the GUARD sampler with MCMC methods like IMH is challenging. When
we run the IMH algorithm for certain number of steps n, we obtain distribution denoted as p (x).
While we can sample from pf*), we cannot evaluate ((n) (x:) for a given x (see Eikema 2022
which presents a significant obstacle to estimating the KL divergence.
Note that, in the experiments below, in order to compare IMH and QRS, we use approximate measure available for both.
26

---

Published as a conference paper at ICLR 2025
DPG-based g'
CAP-based g'
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 starled treating him. He has much betler 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. hope my grandma gets beller soon. Best of luck! Ever!
My uncle couldn't afford health care. He got sick last year. The only way around was by prescription. A doctor arranged to have me take antiretrovirals and a lot of painkillers, He had wonderful month treatment and feel much better today.
My uncle touldn't afford health care. He got sick last year. Luckily he gol home healthy. was wonderful to be able to share our kitchen with our children. It feels much better than we ever knew.
Mike was a bad kid. He never followed his purents advice. He mishchaving and frightened. He tried learn from his own mis- lakes. Eventually, he was a very good buy. He is very grateful. This gift has made huge dif- ference to my son.
Mike was a bad kid. He never followed his parents advice. However, he did learn new trick. He learned how to play the guitar. can't 't wail to see how he plays! hope all that gets passed 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 sev- eral small cuts, then her mother ate her favorite slice. So she and her mom very happy!
Allie came home late last night. Her mother was very mad al her. She decided to surprise her grandma and surprise her. Allie packed her things and got ready to go. Everyone had a great day!
Table Example of generated stories for 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.
Pasition of aamadinn""
Position of "amazing"
194
176
31%
12%
<5. 63--282-138 1111111
Position in
(a) Distribution g'
Gold distribution g
Figure 10: Two hase (projected) distributions for comparing with QRS and IMH. Starting from the distribution in (a), the goal of each statistical sampler is to generate similar distribution to (b). For elearer analysis of the phenomenon, conducted experiments using proposal a' with relatively large divergence, resulting in (L(gllg') 2.
Although cannot directly calculate p("), 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 म, we could estimate 722) by counting the relative frequency of 2's in the sample, and similarly for any in this space.
27

---

Published as a conference paper at ICLR 2025
AR/Quality Trade-off from QRS and IMH
g'
IMH
A..Divergence Projection
0.22
0.54
p=
2
Log scale of AR degradation
Figure 11: Starting from the top-left point (i.e., initial g¹), this figure illustrates the improvement of the projected KL over KL(gll9') for both IMH and QRS and the associated additional inference costs. We note that QRS achieves a reasonable compromise when 3 = Z 28
Based on this insight, we propose the following approach for providing least an approximate estimation of (p (p!n)) 24
1. We build small finite partition X of 10 bins for the textual space X, with projection mapping / (xx from the large space X to the low-dimensional space X.
2. We generate sample of 1000 points from p and use f to project these points into points of X. We get an estimate p(z) for any E in X.
3. We do the same for p(*), obtaining estimates p(r) (T).
4. We can then estimate (p)
5. Then, by considering different values of (but keeping the projection fixed), we can monitor how (L( 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 "aaaazin"" in the generated text. We project the texts from and g based on which of the 10 bins the relative position "amazing" falls into (see Figure Using this method enables to compute form of KL divergence for IMH and to this form for comparison with QRS as shown in Figure
H.2 EXPERIMENTAL RESULTS
Figure 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 high cost in terms of additional inference time: to halve the projected KL divergence
which is a lower bound of the KL divergence, see Footnote 24 QRS requires 1.36 times the inference cost of Algorithm [ while 10% of the original KI,,
IMH requires times the cost. Moreover, to reduce the KI. divergence QRS uses almost 10 times the inference cost of Algorithm [ 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.
Actually, this technique provides lower-bound of the true KL divergence, consequence of the Data Processing incquality (DPT) of Information Theory (Polyanskiy & Wu 2023)..
"IMH performs a random walk n times an initially accepted sample to improve its quality, where is hyperparameter, and where the last 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.
28


Reviews:
[{"review_id": "k0Xr2PDqY4", "reviewer": "Reviewer_DNMP", "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.", "questions": "I wonder if the distribution used by [3] would be a better proposal distribution for rejection sampling, compared to SFT, CAP or DPG.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "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.", "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:\n\nFUDGE [1]: trains auxiliary classifiers on existing classification datasets and uses the classifiers to guide generation to satisfy the constraint.\n\nNeuroLogic A*esque Decoding [2]: performs lookahead decoding with heuristic functions that estimate how likely the constraint will be satisfied. \n\nNADO [3]: trains auxiliary classifiers on data sampled from LLMs and uses the classifiers to guide generation to satisfy the constraint.\n\nGeLaTo [4]: uses an Hidden Markov Model to enforce the constraint\n\nOutlines [5]: uses regex/finite-state machines to mask out next tokens that would violate the constraint.\n\nIn 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).\n\nSimilarly, 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].\nFor 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].\n\n[1] Kevin Yang and Dan Klein. 2021. FUDGE: controlled text generation with future discriminators. In NAACL-HLT. Association for Computational Linguistics.\n\n[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.\n\n[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.\n\n[4] Zhang, H., Dang, M., Peng, N., & Van den Broeck, G. (2023, July). Tractable control for autoregressive language generation. In \nInternational Conference on Machine Learning (pp. 40932-40945). PMLR.\n\n[5] Willard, B. T. & Louf, R. Efficient Guided Generation for Large Language Models. arXiv preprint. arXiv: 2307.09702 [cs.CL] (2023).\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6vpAoNBRJX", "reviewer": "Reviewer_2U8J", "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.", "questions": "1. How do you get the gold samples in Fig. 4&7?\n2. 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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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.", "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:\n1. 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.\n2. The content of Theorem 2 is too simple to be a theorem. It's OK to put it as an equation.\n3. 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. \n4. 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.\n5. 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.\n6. Text in figures and tables are too small to be viewed on A4 paper, please consider rearranging the layout.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dbfcpMU5h0", "reviewer": "Reviewer_hVqd", "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.", "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})$. \n\nAlso, since $\\mathrm{KL}(g || a') > 0$, questions remain about the quality and efficiency of the proposed methods, especially in comparison to other baseline techniques:\n- How do generated answers compare to baselines? Does $g'$ still capture the same capabilities as the original model $a$? \n- How efficient is the approach compared to baselines? How frequent are answers from $a'$ accepted compared to the answers from $a$?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n- **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.\n- **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.", "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:\n- 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).\n- 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).\n\n**Presentation**: In several parts, the work lacks precision and conciseness:\n- First, critical aspects such as the approximation and minimization of $KL(g || a’)$ remain unclear (see question 1 below).\n- 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).\n- 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”.\n- 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.\n\n---\nK. Yang and D. Klein. 2021. Fudge: Controlled text generation with future discriminators. arXiv preprint arXiv:2104.05218.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "60GprR9G1O", "reviewer": "Reviewer_vMCq", "summary": "This work proposes the GUARD framework, which guarantees strict constraint satisfaction for generated outputs of LLMs.\nIt 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.", "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.\n* What is \"ancestral sampling\" - line 308?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I found the problem and the proposed solution very interesting and intuitive.\nThe experiments seem reasonable, the results good and I see no major evaluation missing.\nThe auxiliary investigations in Fig 4 & 7 as well as Tab. 1 and 2 are very insightful.", "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.\nHowever, 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.\n\nMinor:\n* 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. \nAlso I could see that it performs better than DPG with CAP in this setting, as the distribution is less degenerate I guess.\n* 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.\n* 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.\n\nRemarks (just as info for camera ready):\n* SFT is not introduced on first occurance in line 200, but in 255/256.\n* The order of Fig. 3 and 4 is reversed", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)