Controllable Generation via Locally Constrained Resampling

## Abstract

Abstract Autoregressive models have demonstrated an unprecedented ability at modeling the intricacies
of natural language.
However, they continue to struggle with generating complex outputs that adhere to
logical constraints.
Sampling from a fully-independent distribution subject to a constraint is hard.
Sampling from an autoregressive distribution subject to a constraint is doubly
hard: We have to contend not only with the hardness of the constraint but also the
distribution’s lack of structure.
We propose a tractable probabilistic approach that performs Bayesian conditioning to
draw samples subject to a constraint.
Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods.
Starting from a model sample, we induce a local, factorized distribution which we can
tractably condition on the constraint.
To generate samples that satisfy the constraint, we sample from the conditional distribution,
correct for biases in the samples and resample.
The resulting samples closely approximate the target distribution and are guaranteed to satisfy
the constraints.
We evaluate our approach on several tasks, including LLM detoxification and solving Sudoku puzzles.
We show that by disallowing a list of toxic expressions our approach is able to steer the model’s outputs away from toxic generations, outperforming similar approaches to detoxification.
We conclude by showing that our approach achieves a perfect accuracy on Sudoku compared to < 50 % absent percent 50 <50\% < 50 % for GPT4-o and Gemini 1.5.

## 1 Introduction

The advent of large language models (LLMs) has brought about a paradigm shift towards
generating sequences of tokens that jointly constitute the desired output.
Such multi-token outputs exhibit an amount of structure to them: in free-form
generation, the model is expected to generate coherent paragraphs; in question
answering, it is expected to provide answers to the posed questions;
and in summarization, it is expected to condense lengthy documents into concise
summaries.
And while current LLMs are remarkably apt at generating fluent sentences, there
is a need for generations that go beyond that, exhibiting more intricate structure (Liu et al., ).
Such structure includes, e.g., API calls and code snippets (Wang et al., ), JSON schemas (OpenAI, ), logical puzzles (Mittal et al., ; Pan et al., ), all of which LLMs struggle with (Sun et al., ).

Consequently, several approaches to constraining LLMs were developed, all
bolstering a similar underlying idea: at every generation step *greedily*
mask the LLM outputs that could lead to the constraint being violated.
That is, the “defacto” recipe (Deutsch et al., ; Lundberg et al., ; Willard & Louf, ; Koo et al., ) for applying constraints to LLMs consists of the following:

- 1.
Based on the current state of the constraint, build a mask of valid next tokens.
- 2.
Mask out logits for invalid tokens, normalize, and sample.
- 3.
Based on the sampled token, update the constraint state for the next time step.

The above recipe is limited in a number of ways.
First, the masking process is *myopic* (Shih et al., ), as the constraint is enforced *greedily*
per-token rather than jointly across the entire generation.
This is as opposed to *Bayesian* conditioning,
where we consider the entire sequence.
Second, the constraint specification language is typically regular expressions,
which can be significantly more verbose than their target compilation forms,
deterministic finite automata (DFAs) (Gruber & Holzer, ; ; Koo et al., ).
Lastly, there exists classes of constraint functions that can only be described by
DFAs whose size grows exponentially in the size of their constraint.

In this work we develop an approach that departs from the previously established
recipe for constraining LLMs, tackling all the aforementioned shortcomings in the
process.
Our approach starts with the observation that *an LLM sample induces a local,
factorized distribution* $\tilde{p}$.
We use a tractable compilation form, *constraint circuits* (Darwiche, ),
that subsume DFAs on bounded-length strings while being more expressive
efficient (Choi et al., ).
That is, there are classes of functions that we can represent using constraint
circuits that we could not otherwise as efficiently represent using
DFAs (Bova, ).
Such constraint circuits can be specified as Boolean python functions, alleviating the
need for writing regular expressions or other domain specific languages.We show that we can leverage logical circuits to tractably condition $\tilde{p}$,
drawing samples that are biased yet provably satisfy the constraint.
Sampling from the LLM subject to a constraint $\alpha$ then entails conditioning $\tilde{p}$
on $\alpha$, drawing biased samples from $\tilde{p}(\cdot\mid\alpha)$, which we debias by reweighing
them proportionally to their probability under the LLM and resampling.
The returned samples are distributed according to the conditional LLM distribution while also satisfying the constraint.

We start our evaluation by testing our approach on the toy task of predicting shortest paths
under an autoregressive model, and observe a significant improvement upon the
baseline performance.
Next, we evaluate our approach on the task of LLM detoxification where we show
that, by virtue of its probabilistic nature, by simply disallowing a list of toxic expressions, our approach is able to steer the model away from toxic generations, outperforming previous approaches to detoxification.
Lastly, we show that our approach achieves a perfect accuracy on
Sudoku puzzles, compared to an almost $26\%$ and $45\%$ accuracy achieved by Gemini 1.5 Flash and GPT4-o models, respectively.

Figure: Figure 1: An illustration of our proposed approach. (left) An LLM induces a distribution over all possible sentences. Autoregressively sampling from the LLM distribution, we obtain a sentence ( ) $\tilde{\bm{y}}=$ [He’s, ␣full, ␣of, ␣sh!t]. This sentence $\tilde{\bm{y}}$ violates a constraint $\alpha$ that disallows toxic words, including the word “sh!t”. The subset of sentences that satisfy the constraint $\alpha$ ( ) are denoted by $\vdash m_{\alpha}\dashv$. (center) The sentence $\tilde{\bm{y}}$ induces a local, tractable approximation of the true distribution centered around $\tilde{\bm{y}}$. (right) We can efficiently condition this tractable approximation on the constraint $\alpha$, trimming away portions of its support that do not satisfy the constraint. Sampling from the LLM distribution subject to the constraint $\alpha$ then corresponds to sampling from the conditional approximate distribution and adjusting the sample weights using importance weighting. This yields a sentence ( ) $\bm{y}=$ [He’s, ␣full, time, ␣employed] that satisfies $\alpha$.

## 2 Background

### 2.1 Notation and Preliminaries

We write uppercase letters ($X$, $Y$) for Boolean variables and lowercase letters ($x$, $y$) for their instantiation ($Y=0$ or $Y=1$).
Sets of variables are written in bold uppercase ($\mathbf{X}$, $\mathbf{Y}$), and their joint instantiation in bold lowercase ($\bm{x}$, $\bm{y}$).
A literal is a variable ($Y$) or its negation ($\neg Y$).
A logical sentence ($\alpha$ or $\beta$) is constructed from variables and logical connectives ($\land$, $\lor$, $\lnot$,$\implies\!\!$), and is also called a (logical) formula or constraint.
A state or world $\bm{y}$ is an instantiation to all variables $\mathbf{Y}$.
A state $\bm{y}$ satisfies a constraint $\alpha$, denoted $\bm{y}\models\alpha$, if the sentence evaluates to true in that world. A state $\bm{y}$ satisfying a constraint $\alpha$ is said to be a model of $\alpha$.
We denote by $m(\alpha)$ the set of $\alpha$’s models.
Throughout this paper, in reference to DFAs, we limit our discussion to those defined on bounded-length inputs, which are equivalent to ordered binary decision diagrams, or OBDDs (Bryant, ).

### 2.2 A Probability Distribution over Possible Sentences

Let $\alpha$ be a logical constraint defined over Boolean variables $\mathbf{Y}=\{Y_{11},\dots,Y_{nk}\}$, where $n$ denotes the number of time steps in the
sentence, and $k$ denotes the size of the vocabulary, i.e., the number of possible
tokens at each time step.
An autoregressive model induces a probability distribution $p(\cdot)$ over
all possible sentences $\bm{y}$.
At every time step $i$, the autoregressive model ensures that exactly one
token is predicted; i.e., exactly one Boolean variable $\{Y_{i1},\dots,Y_{ik}\}$
can be set to true for each time step $i$.
We will write $\bm{y}_{i}$ to denote that variable $Y_{ij}$ is set to true in sentence
$\bm{y}$.
More precisely, we let $\bm{y}_{i}\in\{0,1\}^{k}$ be the one-hot encoding of $Y_{ij}$
being set to $1$ among $\{Y_{i1},\dots,Y_{ik}\}$.
The probability assigned by the autoregressive model to a sentence $\bm{y}$ is then defined as

$$ $p(\bm{y})=\prod_{i=1}^{n}p(\bm{y}_{i}\mid\bm{y}_{<i}),$ (1) $$

where $\bm{y}_{<i}$ denotes the sentence prefix, $\bm{y}_{1},\ldots,\bm{y}_{i-1}$.

### 2.3 The State of Conditional Autoregressive Sampling

Sampling from an autoregressive distribution conditioned on a logical constraint
$\alpha$ constitutes a major challenge: computing the *exact* conditional
distribution $p(\bm{y}\mid\alpha)=\frac{p(\bm{y},\alpha)}{p(\alpha)}$ is intractable even for the simplest constraints (Roth, ), e.g., asserting that the word “dog” appears at the end of the sentence.
Intuitively, conditioning on $\alpha$ requires that we compute the marginal probability
of the constraint $p(\alpha)$, in turn requiring that we enumerate all sentences ending
with the word “dog”.

The defacto approach has therefore been to *greedily* constrain the distribution,
at every time step masking out logits that lead to generations that violate the constraint,
followed by re-normalizing the conditional token distribution (Deutsch et al., ; Lundberg et al., ; Willard & Louf, ; Koo et al., ).
Let the conditioning of the constraint $\alpha$ on the prefix $\bm{y}_{<i}$, which we write as $\alpha_{|\bm{y}_{<i}}$,
be a *subconstraint* defined on $\mathbf{Y}_{i:n}$ that results from setting the variables $\mathbf{Y}_{1:i-1}$ to their values in $\bm{y}_{<i}$.
Semantically, $\alpha_{|\bm{y}_{<i}}$ denotes the set of $\bm{y}_{i:n}$ that, taken together with the prefix $\bm{y}_{<i}$, would satisfy the constraint.
Moreover, let $\beta_{i}\coloneqq\exists\bm{y}_{>i}\,\alpha_{|\bm{y}_{<i}}$ denote the set of tokens allowed at the $i$-th position such that there exists some completion $\bm{y}_{>i}$ of the sentence that satisfies the constraint $\alpha$, given the current prefix $\bm{y}_{<i}$.
Then we can define the above greedy, or *myopic*, distribution as

$$ $\displaystyle p^{\text{myopic}}(\bm{y}\mid\alpha)$ $\displaystyle\coloneqq\prod_{i=1}^{n}\frac{p(\bm{y}_{i},\beta_{i}\mid\bm{y}_{< i})}{\sum_{j}p(y_{ij},\beta_{i}\mid\bm{y}_{<i})}=\prod_{i=1}^{n}\frac{p(\bm{y} _{i}\mid\bm{y}_{<i})\liv\bm{y}_{i}\models\beta_{i}\riv}{\sum_{j}\,p(y_{ij}\mid \bm{y}_{<i})\liv y_{ij}\models\beta_{i}\riv},$ $$

Of note here is that since the approximate distribution is modeling
the joint probability of the sentence and the constraint, in principle, the
logical reasoning is sound, i.e., the constraint is guaranteed to hold.
Rather, the shortcoming is in the way the *probabilistic reasoning* is performed:
instead of normalizing the joint distribution by the
marginal probability of the constraint, we are performing it token-wise
steering us
towards sampling sequences that are locally likely rather than globally likely.

The second issue lies with the logical constraint along two different axes.
First is the lack of conciseness of the constraint specification language.
The most common language for specifying constraints is regular expressions
which can be significantly more verbose (Gruber & Holzer, ; ; Koo et al., )
compared to the equivalent logical form.
This is due to the inability to reference and reuse sub-expressions without introducing
additional features such as lookaround operations which can cause an exponential blowup
in the size of the target representations (Mamouras & Chattopadhyay, ), or backreferences that
allow us to describe non-regular languages at the expense of an exponential runtime due
to backtracking.
Second is the lack of succinctness of the target representation.
All of the current approaches compile the specified regular expressions into DFAs.
DFAs represent Boolean functions by recursively performing Shannon-decomposition on the function:
disjointing the value of the sub-function with the value of the current variable chosen to be
true and false, respectively.
Consequently, for many constraints of interest, the size of DFA can grow prohibitively.
It turns out there there exists another class of target representation that subsume DFAs on
bounded-length strings: at every step in the function decomposition we can branch not only
on the value of a single variable, rather an *entire sentence* (Darwiche, ).
This class of target representations, which we henceforth denote as *constraint circuits*
are not only more succinct than DFAs in practice, but are provably exponentially more succinct:
there are classes of functions with exponentially-sized DFAs but polynomially-sized constraint circuits (Bova, ).

## 3 Locally Constrained Resampling: A Tale of Two Distributions

We depart from the established recipe for conditional autoregressive sampling,
providing a treatment of the problem from first principles that tackles all
of the shortcomings detailed above.
The crux of our approach is the idea that we can approximate the intractable
autoregressive distribution $p(\bm{y})$ using a local, tractable distribution $\tilde{p}(\bm{y})$.
The distribution $\tilde{p}(\bm{y})$ is amenable to exact and efficient
probabilistic reasoning,
allowing us to efficiently condition on the constraint $\alpha$ and
draw samples from the distribution $\tilde{p}(\bm{y}\mid\alpha)$.
We can transform the biased samples drawn from $\tilde{p}(\bm{y}\mid\alpha)$
into samples from $p(\bm{y}\mid\alpha)$ by considering the discrepancy between the
probability of the sample under the true distribution and the approximate distribution.
More formally, we wish to draw samples from

$$ $p(\bm{y}\mid\alpha)=\frac{p(\bm{y},\alpha)}{p(\alpha)},$ (2) $$

which is intractable. Instead, we design a tractable proposal distribution $q$ such that
$q(\bm{y})>0$ whenever $p(\bm{y}\mid\alpha)>0$.
We associate with a *constrained sample* $\bm{y}$ an *unconstrained sample* $\tilde{\bm{y}}$, where $\bm{y}$ can be understood as a *projection* of $\tilde{\bm{y}}$ onto $\alpha$ s.t. $\bm{y}\models\alpha$.
We define our proposal as

$$ $q(\bm{y})=\sum_{\tilde{\bm{y}}}p(\tilde{\bm{y}})\cdot p_{\tilde{\bm{y}}}(\bm{y }\mid\alpha),$ (3) $$

where $p(\tilde{\bm{y}})$ is the autoregressive distribution, and $p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)$
is a distribution over projections $\bm{y}$ of the unconstrained $\tilde{\bm{y}}$ given the constraint
$\alpha$.
The above definition outlines a two-step procedure for sampling a sentence
$\bm{y}$ that satisfies a given constraint $\alpha$.
We sample a sentence $\tilde{\bm{y}}$ autoregressively from $p(\tilde{\bm{y}})$, followed by sampling $\bm{y}$
from the distribution conditioned on $\tilde{\bm{y}}$ and the constraint $\alpha$, $p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)$.
By incorporating the autoregressive distribution $p(\tilde{\bm{y}})$, we ensure that we can potentially generate any sentence.
$p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)$ then refines $\tilde{\bm{y}}$ by *projecting* it to satisfy the constraint $\alpha$.
It is straightforward to sample from $p(\tilde{\bm{y}})$, but what exactly is $p_{\tilde{\bm{y}}}(\bm{y})$, and how do we condition it on $\alpha$?
Moreover, a proposal distribution typically implies biased samples;
how do we correct for this bias?

### 3.1 A Sample Induces a Local, Tractable distribution

Our goal is to design a probability distribution $p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)$
that is first, tractable for conditioning on the constraint $\alpha$ and likelihood evaluation,
and second, assigns high probability mass to sentences that are close to the model sample $y$
and low probability mass to sentences that are far away, thereby providing a sample-efficient
approximation of the true distribution (Koller & Friedman, ).

As noted earlier, the hardness of computing the conditional probability
distribution in Equation 2 is in large part due to the autoregressive
nature of the LLM distribution.
A logical constraint might have exponentially-many solutions, yet lend itself
to reusing of solutions to sub-problems, and therefore a tractable computation of the
normalizing constant, the denominator in Equation 2.
An example being the $n$ choose $k$ constraint (Ahmed et al., ), where the
conditional distribution can be computed in quadratic time under
the fully-factorized distribution, despite having combinatorially many solutions.
Moving away from fully-factorized distribution and towards autoregressive distributions, however, requires that we enumerate all sentences, even for very simple constraints.

To sidestep the hardness of the autoregressive distribution, we attempt to move towards
the tractability of fully-factorized distributions, while retaining as much of the contextual
information.
To that end, we consider the *pseudolikelihood* $\tilde{p}(\cdot)$ of a sentence $\tilde{\bm{y}}$ (Besag, ; Ahmed et al., ), i.e.,

$$ $p(\tilde{\bm{y}})\approx\tilde{p}(\tilde{\bm{y}})\coloneqq\prod_{i}p(\tilde{ \bm{y}}_{i}\mid\tilde{\bm{y}}_{-i}),$ (4) $$

where $\tilde{\bm{y}}_{-i}$ denotes $\tilde{\bm{y}}_{1},\ldots,\tilde{\bm{y}}_{i-1},\tilde{\bm{y}}_{i+1},\ldots,
\tilde{\bm{y}}_{n}$.
Unfortunately, Equation 4 above would still not ensure the tractability of Equation 2
since different solutions depend on different sets of conditionals.
Instead, we define the pseudolikelihood of a sentence $\bm{y}$ *in the neighborhood
of a sentence* $\tilde{\bm{y}}$

$$ $\tilde{p}_{\tilde{\bm{y}}}(\bm{y})\coloneqq\prod_{i}p(\bm{y}_{i}\mid\tilde{\bm {y}}_{-i})$ (5) $$

which can be understood as the *contextualized probability* of a sentence $\bm{y}$ given the context $\tilde{\bm{y}}$.
We will next show how, given the structure of the contextualized pseudolikelihood distribution,
we are able to efficiently condition it on a constraint $\alpha$.
Furthermore, Ahmed et al. () have shown the contextualized pseudolikelihood distribution to be a local, high-fidelity approximation of the LLM distribution.
That is, the distribution has low entropy, considering only assignments centered around the model sample, while at the same
time having low KL-divergence meaning that
our approximation is faithful to the true distribution in the neighborhood of the model sample.

### 3.2 Constraint Compilation and Tractable Operations

We appeal to knowledge compilation, a class of methods that transform, or *compile*, a
logical constraint into a tractable target form which represents functions as parameterized
computational graphs, or *circuits*.
Knowledge compilers allow us to programmatically specify constraints as Python (Meert, )
or PyTorch functions (Ahmed et al., ) from which they construct circuits.
By enforcing certain structural properties on the compiled circuits we can enable the tractable
computation of corresponding classes of probabilistic queries over the encoded functions.
As such, circuits provide a language for both constructing and reasoning about tractable
representations.
An example of a logical constraint specified as a PyTorch function which gets compiled
into a constraint circuit is shown in the bottom left of  Figure 2 with the corresponding
circuit in  Figure 2, right.

Formally, a *logical circuit* is a directed, acyclic computational
graph representing a logical formula over variables $\mathbf{X}$.
Each node $n$ in the DAG encodes a logical sub-formula, denoted $[n]$.
Each inner node in the graph is an AND or an OR gate, and each leaf
node encodes a Boolean literal ($Y$ or $\lnot Y$).
We denote by $\mathsf{in}(n)$ the set of a node $n$’s children.
We associate with every node $n$ a *scope* function $\phi(\cdot)$ such that
$\phi(n)\subseteq X$ evaluates to the subset of variables the subfunction at $n$
is defined over.

A circuit is *decomposable* if the inputs of every AND gate depend on
disjoint sets of variables i.e. for $\alpha=\beta\land\gamma$, $\mathsf{vars}(\beta)\cap\mathsf{vars}(\gamma)=\varnothing$.
A circuit is said to be *structured-decomposable* if every AND
gate is decomposable, and any pair of AND gates sharing the same scope decompose
in the same way.
Intuitively, decomposable AND gates encode local factorizations over
variables of the function.
We assume that decomposable AND gates always have two inputs, a condition
enforceable on any circuit in exchange for a polynomial size increase (Vergari et al., ; Peharz et al., ).

A second useful property is *smoothness*.
A circuit is said to be *smooth* if the children
of every OR gate depend on the same set of variables i.e. for
$\alpha=\bigvee_{i}\beta_{i}$, we have that $\mathsf{vars}(\beta_{i})=\mathsf{vars}(\beta_{j})\ \forall i,j$. Decomposability and smoothness
are sufficient and necessary for tractable integration
over arbitrary sets of variables in a single pass, as they allow
larger integrals to decompose into smaller ones.

Further, a circuit is said to be *deterministic* if,
for any input, at most one child of every OR node has a non-zero
output i.e. for $\alpha=\bigvee_{i}\beta_{i}$, we have that $\beta_{i}\land\beta_{j}=\bot$ for all $i\neq j$.
Similar to decomposability, determinism induces a recursive
partitioning of the function, but over the support of the
function.
We consider a stronger form of determinism, *strong determinism*,
A circuit is said to be *strongly deterministic* if,
for every OR node, $\alpha=\bigvee_{i}(\beta_{i}\land\gamma_{i})$, the
$\beta_{i}$’s are mutually exclusive i.e., $\beta_{i}\land\beta_{j}=\bot$ for
any $i\neq j$.
Ensuring they are also exhaustive i.e., $\bigvee_{i}\beta_{i}=\top$,
along with structured-decomposability, we recover sentential decision diagrams
(Darwiche, ), or *constraint circuits*.

Given a constraint circuit $c_{\alpha}$ that encodes a logical constraint
$\alpha$ we can compute the pseudolikelihood $\tilde{q}(\alpha)$ by feeding
the probability of each literal at the corresponding leaf node and evaluating
the circuit upwards, taking sums at OR gates and products at AND gates.
This defines a distribution $p_{\bm{y}}(\tilde{y}\mid\alpha)$.
To sample from the distribution, starting from the root node, we trace the
circuit top-down, sampling a child at every OR-gate encountered.
Figure 2 (center) shows an example of computing such a distribution,
and Figure 2 (right) demonstrates the process of sampling from it.

Figure: Algorithm 1 Compute $\tilde{p}_{\bm{y}}(\tilde{\bm{y}}\mid\alpha)$

Figure: Algorithm 2 Locally Constrained Resampling

### 3.3 Intermezzo: Constraint Circuits and DFAs

Constraint circuits can implement decisions of the form

$$ $\bigvee_{i=1}^{m}\beta_{i}(X)\wedge\gamma_{i}(Y),$ (6) $$

at OR gates, where $\mathbf{X}$ and $\mathbf{Y}$ are disjoint *sets* of variables, as opposed
to DFAs that are restricted to Binary (or Shannon) decisions and therefore boil
down to very special decisions of the form

$$ $(\neg x\wedge\gamma_{1}(\mathbf{Y}))\vee(x\wedge\gamma_{2}(\mathbf{Y}))$ $$

where the variable $X$ is not in the variable set $\mathbf{Y}$.
Therefore, constraint circuits are exponentially more succinct than DFAs, i.e., there
are families of functions can only be represented by a exponentially-sized DFAs, but
have a polynomially-sized constraint circuit (Bova, ).
Barring such families of functions, constraint circuits are also empirically more succinct than DFAs (Xue et al., ).
In practice, this allows us to construct shallower (i.e., less layers) and wider (i.e., units per layer) constraint circuits that are more amenable to GPU parallelization (Liu et al., ), exhibiting a lower vectorized computational complexity (Ahmed et al., ).

### 3.4 Correcting Sample Bias: Importance Sampling… Resampling

We have now sampled $\bm{y}$ from our proposal distribution $q(\bm{y})$, where $\bm{y}$ is a projection of some latent unconstrained sample $\tilde{\bm{y}}$, and satisfies the constraint $\alpha$.
However, our proposal distribution $q(\bm{y})$ might not align perfectly with our target distribution $p(\bm{y}\mid\alpha)$.
We therefore need to account for the mismatch between the two distributions, which we can do by
defining importance weights that are a function of the original $\bm{y}$, and its projection $\tilde{\bm{y}}$.
We start by defining the true augmented distribution

$$ $p(\bm{y}\mid\alpha)\propto\sum_{\tilde{\bm{y}}}p(\bm{y},\alpha)\cdot p_{\bm{y} }(\tilde{\bm{y}}).$ (7) $$

This factorization reflects the process of first generating a constrained sentence $\bm{y}$, and marginalizing over all the unconstrained sentences $\tilde{\bm{y}}$ that could have given rise to $\bm{y}$, and can be therefore be thought of as reversing the proposal distribution.
We calculate the self-normalized importance weights

$$ $w=\frac{p(\bm{y},\alpha)\cdot p_{\bm{y}}(\tilde{\bm{y}})}{p(\tilde{\bm{y}}) \cdot p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)}$ (8) $$

These weights quantify the discrepancy between the proposal and target distributions, allowing us to correct for the biased sampling.
Note, however, that the importance sampling does not generate samples from the target distribution $p(\bm{y}\mid\alpha)$, only a set of
weighted particles.
Rather, to transform our weighted particles into samples drawn from $p(\bm{y}\mid\alpha)$ we need to apply a resampling step according to
the importance weights.
That is, given particles $\bm{s}_{i}$ with their corresponding importance weights $w_{i}$, if we resample
$\bm{s}_{i}$ with replacement from $\{\bm{s}_{1},\ldots,\bm{s}_{n}\}$ with probabilities proportional to the
importance weights i.e.,

$$ $\displaystyle p^{*}(\bm{s}_{i})$ $\displaystyle=\frac{w_{i}}{\sum_{j=1}^{n}w_{j}}$ $$

then $\bm{s}_{i}$ is drawn from the true the distribution in the limit of a large sample size $n$.
Our full algorithm is shown in Algorithm 2, and follows PyTorch syntax (Paszke et al., ).
One thing to note is the use of the $\mathtt{retokenize}$ function on line 6 in Algorithm 2,
where $\mathtt{canonize}$ returns the *canonical* tokenization of an expression (Geh et al., ).
This ensures that, e.g., in the case of language detoxification, we are banning all the possible ways of generating a given expression.(^1^11This issue has received an amount of attention in the past, see for instance [https://github.com/huggingface/transformers/issues/17504](https://github.com/huggingface/transformers/issues/17504))
We can now prove that Algorithm 2 is guaranteed to return samples that satisfy the
constraint $\alpha$.
Our algorithm is implemented in log-space to preserve numerical stability while handling very small probabilities.

###### Theorem 1 .

Locally Constrained Resampling in Algorithm 2 returns a sample $\bm{y}$ s.t. $\bm{y}\models\alpha$.

Figure: Figure 2: Constructing and sampling the proposal distribution. (Top left) We start by sampling a sentence $\tilde{\bm{y}}$ from the model $p$. Our goal is to compute the full conditional probability of every word in the vocab i.e., $\tilde{p}(\tilde{y}_{ij})\coloneqq p(\tilde{y}_{ij}\mid\tilde{\bm{y}}_{-i})$. We start by expanding the sampled sentence $\tilde{\bm{y}}$, including all sentences that are a Hamming distance of $1$ away from the sample $\bm{y}$. We proceed by (batch) evaluating the samples through the model, obtaining the joint probability of each sample. We then normalize along each column, obtaining the conditionals $p(\tilde{y}_{ij})$. (Bottom left) We can easily specify a logical constraint that prevents the word “ hate” from appearing as a simple python function that gets compiled in the constraint circuit on the right. (Center) A logical circuit encoding constraint $\lnot\text{hates}$, with a simplified vocab is shown in the figure. To construct the distribution $p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)$, we feed the computed contextual probabilities at the corresponding literals. We push the probabilities upwards, taking products at AND nodes and sums at OR nodes. This induces a distribution $p_{\tilde{\bm{y}}}(\bm{y}\mid\alpha)$. (Right) To sample a from this distribution, we start at the root of the circuit, sampling a child of every OR gate according to the logits of the distribution, and concatenating at every AND gate. In this case, we sample the sentence “He loves dogs” satisfying the constraint.

###### Theorem 1 .

## 4 Related work

There has been a long line of work tackling constrained generation with LLMs.
One of the earlier approaches was to use search-based decoding algorithms, such as NeuroLogic Decoding (Lu et al., ; ).
While these methods explicitly search for high-probability sequences that satisfy the constraint,
they face scalability issues due to the exponential growth of the search space as the sequence
length increases.
Another set of techniques that include GeDi (Krause et al., ), FUDGE (Yang & Klein, ), and NADO (Meng et al., ) employ auxiliary neural classifiers to approximate the intractable conditional
distribution, but do not guarantee that the constraint is satisfied and require that a classifier be trained
for every new constraint type.
Approximate inference methods attempt to approximate the intractable conditional distributions (Qin et al., ; Hu et al., ; Lew et al., ) but suffer from high variance and do not guarantee constraint satisfaction.

Recently Outlines (Willard & Louf, ) and Guidance (Lundberg et al., ), and along similar lines SGLang (Zheng et al., ), were proposed, also guaranteeing that the constraint is satisfied. Outlines employs a precompilation step where constraints specified in regular expressions are compiled into DFAs that are “indexed” to create a token-based overlay. This overlay guides the decoding process, ensuring adherence to the constraints. Koo et al. () recently recast the entire process in an automata-theoretic framework. Similar to Outlines, Guidance utilizes a trie to efficiently store and search through valid token continuations based on the grammar. This allows for dynamic vocabulary matching at each decoding step, offering flexibility potentially at the cost of impacting efficiency.
These approaches are considered the “defacto” approaches for constrained generation.

More recently, GeLaTo (Zhang et al., ) and subsequently CTRL-G (Zhang et al., ) have utilized Hidden Markov Models (HMMs) to guide the generation from LLMs towards constraint satisfaction, but requires training a new HMM for every target model.
The very recently proposed ASAp (Park et al., ) aims to debias the greedy approach through repeated sampling and discovery of mass assigned to non-grammatical completions, reducing each overapproximation to make it more accurate.
While similar in intention, our approach relies on a closed-form tractable approximation of the target distribution to correct for the bias, avoiding the need to oversample the LLM.

Finally, some other approaches no longer predictively mask logits, but instead sample unconstrained continuations and reject invalid ones post-hoc.
For example, PICARD (Scholak et al., ) converts the top-$k$ tokens to text and performs various levels of validation.
While such approaches are very simple in principle, and in fact perform exact Bayesian conditioning, the number of samples required can be prohibitive, especially when the constraint requires selecting low probability tokens.

**Table 1: Experimental results on Warcraft.**
| Test accuracy % | Exact | Consistent |
| --- | --- | --- |
| CNN-LSTM | $62.00$ | $76.60$ |
| + oversampling | $69.10\%$ | $84.50\%$ |
| + Gen-C (Ours) | $\mathbf{78.13\%}$ | $\mathbf{100\%}$ |

## 5 Experimental Evaluation

We evaluate our approach Gen-C on several tasks spanning a number
of domains.
We start by evaluating on Warcraft shortest-path finding, where we are given
an image of a Warcraft tilemap, and are tasked with *autoregressively*
generating one of the potentially many minimum-cost paths between two end points
conditioned on the map, where the cost is determined by the *underlying*
cost of the tiles spanned by the path.
We move on to evaluating on the classic, yet challenging, task of solving a $9\times 9$
Sudoku puzzle where an LLM is presented with an incomplete Sudoku puzzle and asked to
provide the solved puzzle without extraneous text.
We also evaluate on the task of LLM detoxification.
In this task, we are interested in the generations produced by an LLM when presented
with a prompt input by the user.
More specifically, we are interested not only in how good these models are at the modeling
aspect, but also how *toxic* their outputs might be, a measure which includes sexual
explicitness, identity attacks, and profanity, among others.
Our goal in this task is then to shift the model’s distribution away from toxic generations,
and toward nontoxic ones, all while maintaining its original ability to model text.
We believe this to be a timely and important problem due to the prevalence and widespread usage
of LLMs coupled with the fact that previous work (Gehman et al., )
has found non-negligible amounts of toxic, harmful, and abusive text in the corpora used to train LLMs.
Experimental details, hardware specifications, and training details are provided in the appendix.
The implementation for our approach and the code to reproduce all of our experiments will be made available at [https://github.com/KareemYousrii/Gen-C](https://github.com/KareemYousrii/Gen-C).

#### Warcraft Shortest Path

For this task, we follow the experimental setting set forth by
Pogančić et al. (), where our training set consists of $10,000$
terrain maps curated using Warcraft II tileset.
Each map encodes a $12\times 12$ grid superimposed on a Warcraft terrain map,
where each vertex is weighted according to the cost of the tile, which in turn
depends on type of terrain it represents e.g., earth has lower cost than water.
These costs are *not* presented to the network.
The task is then to generate a minimum-cost path from the upper left to the lower
right vertices, where the cost of a path is defined as the sum of costs of the vertices
visted by the edges along the path, and the minimum-cost path is not unique, i.e., there
are many correct paths with the minimum cost.
The minimum cost path from the top left and bottom right vertices is encoded as
an indicator matrix.

We use a CNN-LSTM model, where, presented with an image of a terrain map, we use a ResNet18
(He et al., ) to obtain a $128$ image embedding, which is then passed on to an LSTM with a
single layer, a hidden dim of size $512$, and at every time step predicts the next edge in
the path conditioned on the image embedding and previous edges.
The constraint used in this task is that the predicted
edges form a valid simple path from the upper left vertex to the lower right vertex.

As has been established in previous work (Xu et al., ; Ahmed et al., ; ),
the accuracy of predicting individual labels is often
a poor indicator of the performance of the neural network
in neuro-symbolic settings, where we are rather more interested in the accuracy of
our predicted structured object *exactly* matching the groundtruth label
, e.g., *is the prediction a shortest path?*, a metric which we denote “Exact” in our
experiments, as well as the accuracy of predicting objects that are *consistent*
with the constraint, e.g., *is the prediction a valid path?*, a metric
denoted “Consistent”. Our results are shown in Table 2.
We compare against two different baselines: the baseline model trained on the task, and
*oversampling*, whereby we draw many samples conditioned on the input image,
and then resample this distribution, a variant of our approach where the proposal
distribution is the autoregressive model itself.
We find that our approach improves the exact match from $62.00\%$ and $69.10\%$ to $78.13\%$ while
guaranteeing the sampled sequences of edges constitute valid paths.

#### Sudoku

Next, we consider the task of predicting a solution to a given Sudoku puzzle.
Here the task is, given a $9\times 9$ partially-filled grid of numbers
to fill in the remaining cells such that the entries each row, column,
and $3\times 3$ square are unique i.e., each number from $1$ to $9$
appears exactly once. We use the dataset provided by Wang et al. (), consisting of 10K Sudoku puzzles,
split into 9K training examples, and 1K test samples, all puzzles having 10 missing entries.

Each LLM is prompted with the string “Give me the solution of the following Sudoku without any extra text or quotes”
followed by the Sudoku Puzzle.
As baselines, we used Gemini 1.5 Flash and GPT-4o mini, and post-process the responses to remove
any extraneous text returned by the LLM.
We compare the baselines against Llama3-8B constrained using our approach Gen-C,
with the constraint that the elements of every row, column and $3\times 3$ square are unique.
Our results are shown in Table 2.
We see that where as Gemini and GPT4o are able solve only $26\%$ and $45\%$ of the Sudoku
puzzles, our approach consistently manages to recover the correct Sudoku Puzzle solution.

**Table 3: Evaluation of LLM toxicity and quality across different detoxification methods on Llama3-8b. Model toxicity is evaluated on the RealToxicityPrompts benchmark through Perspective API. Full, Toxic and Nontoxic refer to the full, toxic and nontoxic subsets of the prompts, respectively. PPL refers to the perplexity of Llama3-70B on the model generations using 5 different seeds. In line with Gehman et al. (); Wang et al. (), we characterize toxicity using two metrics: the Expected Maximum Toxicity over $5$ generations, and the Toxicity Probability of a completion at least once over 5 generations.**
| Models | Exp. Max. Toxicity  ($\downarrow$) | Toxicity Prob.  ($\downarrow$) | PPL  ($\downarrow$) |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Full | Toxic | Nontoxic | Full | Toxic | Nontoxic |  |  |
| Llama3-8B | $0.25$ | $0.43$ | $0.20$ | $14.26\%$ | $38.30\%$ | $~{}~{}7.60\%$ | $14.45$ |
| + Word Banning | $0.24$ | $0.40$ | $\mathbf{0.19}$ | $12.47\%$ | $32.43\%$ | $~{}~{}6.93\%$ | $\mathbf{14.50}$ |
| + Gen-C *(ours)* | $\mathbf{0.23}$ | $\mathbf{0.37}$ | $\mathbf{0.19}$ | $\mathbf{11.04\%}$ | $\mathbf{28.00\%}$ | $\mathbf{~{}~{}6.35\%}$ | $\mathbf{14.50}$ |

#### LLM detoxification

Lastly, we consider the task of LLM detoxification.
That is, we investigate the effectiveness of logical constraints, enforced using
Gen-C, at steering the model away from toxic prompted-generations.
We choose a *very* simple constraint to be enforced by Gen-C throughout this task, namely we ban any of a list of “bad words”, including profanity,
slurs, and swear words(^2^22List downloaded from [here](https://github.com/LDNOOBW/List-of-Dirty-Naughty-Obscene-and-Otherwise-Bad-Words).)
from appearing as part of the model’s generations.
Similar to previous work (Gehman et al., ; Wang et al., ),
we evaluate on the RealToxicityPrompts, a dataset of almost 100k prompts
ranging from nontoxic, assigned a toxicity score of 0 0, to very toxic, assigned
a toxicity score of $1$.
We focus on Llama3-8B (Radford et al., ) as a base model for detoxification.
As is customary,  (Gehman et al., ; Wang et al., ), we use
Perspective API, an online automated model for toxic language and hate speech detection,
to score the toxicity of our predictions.
It returns scores in the range 0 0 to $1.0$, corresponding to nontoxic on the one end,
and extremely toxic on the other.
The toxicity score can be interpreted as the likelihood of given person perceiving the text as being toxic or offensive.
Though not without limitations, studies (Wang et al., ; Welbl et al., )
have shown that the toxicity scores reported by Perspective API are very strongly correlated with human evaluations.

We compare Llama3-8B against Word Banning, which for this simple constraint
functions very similarly to Outlines (Willard & Louf, ) and Guidance (Lundberg et al., ).
It keeps track of the words generated so far, and prevents the banned expression from
appearing by setting its probability to 0 0.
Word Banning could therefore be seen of as a greedy approximation of what we might hope to achieve
using Gen-C: intuitively, it might not be able to recover from generating a sentence
associated with a toxic intent as a result of making greedy decision at every step of the generaton.
We report the *Expected Maximum Toxicity* and the *Toxicity Probability*.
The *Expected Maximum Toxicity* measures the worst-case toxicity by
calculating the maximum toxicity over $25$ generations under the same prompt
with different random seeds, and averaging the maximum toxicity over all prompts.
This metric can be seen as a measure of how intensely offensive a generation is.
*Toxicity Probability* estimates the empirical probability of generating
toxic language by evaluating the fraction of times a toxic continuation
is generated at least once over $25$ generations with different random seeds
for all prompts.
This metric can be seen as a measure of how likely the LLM is to be offensive.
Both of the above metrics are computed for the full set of prompts, only the toxic
subset of the prompts, and only the nontoxic subset of the prompts.
To understand the impact of detoxification, we evaluate the quality of the LLM
generations by measuring the perplexity of the generations according to Llama3-70B
averaged across $5$ different runs.
Our results are seen in Table 3.

We can see that word banning lowers the toxicity of the generations produced by
Llama3-8B at a negligible decrease in perplexity.
More specifically, we observe that it reduces the average worst-case toxicity as
well as the probability of producing a toxic generation when prompted with nontoxic prompts
by a modest $1\%$, but when prompted with nontoxic prompts the reduction in toxicity is much
higher at $3\%$ and almost $6\%$ for the expected maximum toxicity and toxicity probability,
respectively.
Moving on to constraining our Llama3-8B with our approach Gen-C attains
the same perplexity as using word banning, but greatly reduces the toxicity of Llama3-8B,
especially on toxic prompts where it results in almost twice as much the reduction in toxicity affected
by word banning, both in terms of the expected maximum toxcity as well as the toxicity probability.

## 6 Conclusion and Future Work

We proposed a new approach for constraining LLMs which we called Gen-C.
Given a logical constraint, Gen-C guarantees that an autoregressive model’s
generations satisfy the constraint.
Gen-C is probabilistically sound, while providing a concise constraint
specification language as well as an exponentially more succinct compilation form
compared to current defacto approaches to controlled generation.
We have showed that Gen-C can be applied to autoregressive models such
as LSTMs as well as large scale LLMs, outperforming the baselines on
the tasks of minimum-cost paths prediction, language as well as solving
Sudoku puzzles, where we achieved a perfect accuracy, beating both GPT-4o
and Gemini 1.5 by a large margin.
We have also shown that by virtue of its probabilistic nature, Gen-C is
able to outperform current approaches for constrained generation on LLM detoxification using only a list of toxic expressions as a constraint, relying on
probabilistic inference.

Moving forward, we envision extending and building upon Gen-C in a multitude of ways.
First, on the systems side since Gen-C extensively uses the language of tractable circuits,
we plan on a tight integration with circuits libraries, such as pyjuice (Liu et al., ) to
greatly improve the efficiency of our approach, as well as open the door for many potentially
interesting probabilistic queries.
Second, we hope to explore more applications of constrained generation, with one alluring possibility
being the use of constraints to improve the factual accuracy of current LLMs.

## Appendix A Proofs

See 1

###### Proof.

Let $\bm{y}=(\bm{y}_{1},\ldots,\bm{y}_{n})$ denote a string.
Let vocabulary $\mathcal{V}$ denote a set of subwords, or *tokens*.
A *tokenization* of a string $\bm{y}$ w.r.t. a vocabulary $\mathcal{V}$ is a sequence of tokens $\bm{v}=(v_{1},\ldots,v_{n})$ , such
that each $v_{i}\in\mathcal{V}$ and the concatenation of all tokens $v_{i}$ constitutes the string $\bm{y}$, i.e., $v_{1}\circ\dots\circ v_{n}=\bm{y}$.

An autoregressive distribution $p(\cdot)$ defines a conditional probability distribution over tokens,
and therefore, *induces a distribution over tokenizations of a given string $\bm{y}$* (Geh et al., )

$$ $p(\bm{v},\bm{y})=\begin{cases}\prod_{i=1}^{|\bm{v}|}p\left(v_{i}|v_{1},\dots,v _{i-1}\right)\text{~{}if~{}}\bm{v}\models\bm{y},\\ 0\quad\text{otherwise,}\end{cases}$ $$

where $\bm{v}\models\bm{y}$ denotes that $\bm{v}$ is a tokenization of $\bm{y}$.

We start by showing that, if the canonical tokenization of a string $\bm{y}$ does not satisfy $\alpha$,
then Algorithm 2 precludes any non-canonical tokenizations of the string $\bm{y}$.
To see that, observe that a non-canonical tokenization of a sentence $\bm{y}$ generated by Algorithm 2
is subsequently cast into a canonical tokenization by invoking the $\mathtt{canonize}$ function.
It is then assigned an importance weight of 0 0, and assigned zero probability in the resampling distribution
on line 9 in Algorithm 2.

During the resampling step, the set of candidate samples are only those sampled from $p_{\bm{y}}(\cdot\mid\alpha)$

We will now show that we can always construct $p_{\bm{y}}(\cdot\mid\alpha)$ given a constraint $\alpha$ defined over
variables $\{Y_{11},\ldots,Y_{nk}\}$ and a contextualized psuedolikelihood distribution $\tilde{p}_{\bm{y}}(\cdot)$.
Recall from Section 3.1 that the contextualized pseudolikelihood distribution is fully-factorized.
We can therefore construct a deterministic and decomposable circuit representing the contextualized pseudolikelihood
distribution where with a slight abuse of notation, we use $\tilde{p}_{\bm{y}}(\cdot)$ to refer to both the distribution
as well as its circuit representation.
Such a construction proceeds by introducing a Bernoulli distribution unit for each variable, and connecting the Bernoulli
distribution units using a singular product node.

Given a constraint $\alpha$, we can compile it into a constraint circuit $c_{\alpha}$.
The simplest construction is as follows.
Order the variables lexicographically.
Alternate OR and AND nodes.
An OR node branches on the current variable being true or false, and has two children: a left (right) AND node whose children
are the positive (negative) literal and the subtree corresponding to substituting the positive (negative) literal into the constraint.
Repeat the above process till exhausting all the variables.

Given a constraint circuit $c_{\alpha}$, a deterministic and omnicompatible circuit (Vergari et al., ) $\tilde{p}_{\bm{y}}(\cdot)$, we can compute the product of the two circuits $\tilde{p}_{\bm{y}}(\cdot,\alpha)$ in time $\mathcal{O}(|p||c|)$, following
from Theorem 3.2 in Vergari et al. (). Furthermore, the resulting product circuit $\tilde{p}_{\bm{y}}(\cdot,\alpha)$ can be normalized in time $\mathcal{O}(|\tilde{p}|)$ to obtain $\tilde{p}_{\bm{y}}(\cdot\mid\alpha)$, following from Proposition 2.1 in Vergari et al. ()

∎

###### Proof.

## Appendix B Language Detoxification

The experiments were run on a server with an AMD EPYC 7313P 16-Core Processor @ 3.7GHz, 3 NVIDIA RTX A6000, and 252 GB RAM.
Our LLM detoxification experiments utilized both GPUs using the Huggingface Accelerate (Gugger et al., ) library.

In order to construct our constraint, we start with the list of bad words(^3^33List downloaded from [here](https://github.com/LDNOOBW/List-of-Dirty-Naughty-Obscene-and-Otherwise-Bad-Words).) and their
space-prefixed variants(^4^44A word will be encoded differently whether it is space-prefixed or not.).
We then tokenize this list of augment bad words, yielding $871$ unique possibly-bad tokens (some tokens are only bad when considered in context with other tokens), in addition to an extra catch-all good token to which remaining tokens map to.
Our constraint then disallows all sentences containing any of the words on the augmented list, starting at any of the sentence
locations 0 0 through len(sentence) - len(word).
The code to process the list of words, the code to create the constraint as well as the constraint itself will be
made publicly available upon paper acceptance.

We use a batch size of $10$ during generation, and only sample every sentence $5$ times.
The model sentence $\bm{y}$ was generated using nucleus sampling with $p=0.9$ and a temperature of $1$.
We experimented with tempering the contextualized pseudo-likelihood distribution on a random set of prompts of size $1000$
using $\tau=\{0.1,0.3,0.5,0.7,0.9,1.0\}$.
Our final results are reported on a random subset of the RealToxicityPrompts dataset of size $10$k, average over $5$ different
runs using $5$ different seeds.
For only this task, our implementation makes use of top-$k$ to construct the pseudo-likelihood
distribution (lines $7$-$12$ in Algorithm 1) due to the lack of computational resources.
Generations from all methods were limited to a maximum of $20$ new tokens.

## Appendix C Sudoku

The experiments were run on a server with an AMD EPYC 7313P 16-Core Processor @ 3.7GHz, 2 NVIDIA RTX A6000, and 252 GB RAM.
We use the dataset provided by Wang et al. (), consisting of 10K Sudoku puzzles,
split into 9K training examples, and 1K test samples, all puzzles having 10 missing entries.
Our constraint disallows any solution in which the rows, columns and square are not unique.

## Appendix D Warcraft Shortest Path

The experiments were run on a server with an AMD EPYC 7313P 16-Core Processor @ 3.7GHz, 2 NVIDIA RTX A6000, and 252 GB RAM.
We used the best model trained by (Ahmed et al., ).
The model uses a CNN-LSTM model for this task.
Precisely, a ResNet-18 encodes the map to an embedding of dimension 128.
An LSTM with $1$ layer, and a hidden size of $512$ then predicts the next edge in the shortest path
conditioned on the input map and all previous edges.
The constraint disallows any prediction not a valid path connecting the upper left and lower right vertices.

## Appendix E Broader Impact

The work presented in this paper has a significant potential for positive
societal impact.
Neuro-symbolic AI moves us closer to models whose behavior is trustworthy, explainable and fair.
This extends to critical domains such as autonomous driving, medical diagnosis and financial planning to name a few.
Large language models have recently seen an exponential increase in popularity, crossing the threshold of being mere
research tools into products that are utilized by the general public.
Unfortunately, the same expressivity that renders these models so powerful also makes it hard to reason about their
behavior.
We believe our proposed approach is a step in right direction: it expands the class of logical constraints we can
tackle while account for and acknowledging the underlying probability distribution.
And we have shown the merits of our approach when applied to LLM detoxification.
We must, however, also be cognizant of the potential negative societal impacts:
In very much the same way that our approach can be used to output non-toxic generations, it can be used to output
toxic and harmful generations.

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 3
presentation: 3
questions: Please see "weaknesses" above.

Minor:
- Headings: There is not always consistent capitalisation (e.g., 3.1) and I don't understand the use of ellipsis in 3.4.
- L225 "structured" -> "structure"
- The name of the algorithm (GEN-C) does not appear until Section 5 (experiments). I suggest to introduce it earlier.
soundness: 3
strengths: - Relevance/significance: As the authors write in the introduction, conditioning LMs with logical constraints is important but difficult. This work proposes a method that is guaranteed to generate samples that satisfy constraints and, unlike others, requires no Monte Carlo or model training.
- Clarity:
  - The presentation of Sections 1-4 is, in my opinion, very good. The reviewer is familiar with circuits and graphical models, which certainly helps (a simple diagram appearing earlier in the paper than current Figure 2 would probably help readers who are not). The didactic style and organisation make the motivation of the algorithm clear.
  - Thanks also for introducing notations in 2.1 but not overburdening the reader with excessive rigour.
summary: This paper studies the problem of sampling from the distribution given by a pretrained language model subject to logical constraints (which could be expressed as lexical constraints, automata, etc.). 

It is proposed to compile a constraint into a circuit, so that conditioning a distribution that factorises fully over positions on the constraint computed by the circuit is tractable. To approximately sample a LM subject to constraints, we first draw unconditional samples, then build a fully factorised proposal distribution using the LM's next-token probabilities and constrain it by the constraint circuit; this procedure yields a collection of samples that satisfy the constraints, together with importance weights relative to the true target distribution.

This method is evaluated on two combinatorial/planning tasks and on a LLM detoxification task, achieving a high rate of constraint satisfcation.
weaknesses: - Experiments:
  - Presentation: It would be good to see examples of the input and desired/undesired output for each task in the main text. It is hard to understand what is being done from text descriptions alone.
  - I do not find the results very convincing for a few reasons:
    - Error bars are not reported => impossible to assess significance.
    - Comparison with methods from prior work: only a trivial baseline is compared with for LLM detoxification, and only cold-prompted LLMs for Sudoku.
  - The LM application is quite basic. Toxicity is much more subtle than banning the forbidden words (note that the forbidden word list is not very comprehensive!). There should be evaluations involving the constraints that were actually imposed -- currently only scores from an auxiliary model (the Perspective API) are reported. 
    - On this subject, imposing intractable constraints such as those given by a toxicity model is outside the range of applicability of GEN-C. But could GEN-C with more basic constraints (banned words?) perhaps be used as a proposal distribution for approximately sampling a distribution constrained by an intractable classifier?
  - Some questions on experiments:
    - What is the typical variance of importance weights at the resampling step? Do you have any estimates of mode coverage? Current results don't illustrate well that the procedure gets a good approximation to the constrained distribution. 
    - How big are the constraint circuits in each of the experiments? (Relatedly, is there a nontrivial computation cost of running the proposed algorithm on top of regular decoding?)
- Description of related work in L350-352 does not seem quite accurate. While it is correct that these three methods (Qin et al., Hu et al, Lew et al.) do not guarantee constraint satisfaction, they study the problem of "soft" conditioning, i.e., sampling an intractable but full-support posterior. As for variance:
  - Qin et al. runs Langevin in a continuous relaxation and I am unsure what is meant by "high variance".
  - Hu et al. is not even an approximate inference method, but an RL-based amortisation method (so asymptotically -- at convergence -- it is unbiased). Of note, the training objective used there happens to have zero gradient variance at the optimum. So what is meant by "high variance"?
  - Lew et al. proposes a sequential Monte Carlo approach, which is asymptotically unbiased in a different sense: with enough particles and sampling steps, it will give correct samples. Does "variance" refer to that of the annealed importance weights?
  - By the way, there are hybrid SMC+amortisation approaches, e.g., [Zhao et al., ICML'24](https://arxiv.org/abs/2404.17546), which could be worth mentioning.

Overall, the idea is very interesting and the paper has promise, but I cannot recommend acceptance without more thorough experiments and more difficult problem domains.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: * How does the method handle cases where constraints are mutually exclusive or when no valid solution exists?
* Could you provide more details about the choice of temperature parameter in the resampling step and its impact on generation quality?
* What is the impact of the size of the initial sample set on the quality of the final generations?
* How robust is the method to different types of logical constraints, particularly those that require long-range dependencies?
* Could you elaborate on how the approach might be extended to handle soft constraints or preferences rather than just hard logical constraints?
soundness: 3
strengths: * The probabilistic circuits formulation moves beyond greedy token-by-step constraint enforcement. It is an interesting application of probabilistic circuits to a broadly applicable problem of constrained sampling in LLMs. 
* The logical circuits also proivde a more expressive and efficient constraint representation compared to traditional DFAs which are typically used in constrained sampling in LLMs. 
* The paper is quite well written, with easy to follow explanations for the idea, along with examples (Figure 1). 
* The results are promising and indicate potential applicability to a variety of problems.
summary: This paper introduces Gen-C, a novel probabilistic approach for controlled text generation with large language models (LLMs) that ensures outputs satisfy logical constraints while maintaining natural language fluency. The key idea is to use a tractable approximation of the LLM's distribution through locally constrained resampling: starting from an initial model sample, the method induces a local factorized distribution that can be efficiently conditioned on constraints using logical circuits. The approach addresses limitations of current greedy constraint enforcement methods by performing proper Bayesian conditioning across the entire sequence. The authors demonstrate Gen-C's effectiveness on several tasks, including LLM detoxification, Sudoku puzzle solving, and shortest path prediction, showing significant improvements over baseline approaches.
weaknesses: * A key aspect for sampling algorithms is the runtime, but from what I can tell there is no discussion of the runtime of the approach and how it compares to the baselines. Another aspect is the memory usage (which is also a challenge for large models), Another aspect which is unclear just from the results is how the method scales with the sequence length. 
* While results are promising as initial proof-of-concept, the experiments are mainly about relatively small-scale tasks. There is a limited exploration of more complex logical constraints and thus it is unclear how well the method can handle multiple competing constraints. 
* There are no ablations to inform the choice of the sampling parameters chosen. Without that it is hard to understand how to apply the method to a new problem. 
* There are no theoretical results on approximation quality obtained with Gen-C and there is limited discussion of failure cases or limitations in the paper.

---

confidence: 4
contribution: 4
initial_rating: 5
presentation: 2
questions: Sec 3.2: 
- What is the difference between DFA and RegExp? Also, as DFA is more efficient, are there any downsides to using it? In particular, are all constraints expressible in that fashion? And, are all constraints expressible with a constraint circuit that is deterministic, smooth and decomposable?

Sec 3.3:
- X and Y in Eq 6 should be bolded.
- What is the "contextualised probability?"

Sec 3.4: 
- Shouldn't p_\tilde y(y) in Eq 7 also depend on alpha?

In terms of the experiments, it would be good to give some indication of how the different methods fare in terms of computing cost.
soundness: 3
strengths: originality:
- The method originally builds upon existing techniques in Bayesian inference and constraint circuits to tackle constrained generation with LLMs.
- The presented approach seems to be a step change with respect to simpler greedy methods.

quality:
- The method is effective, leading to great performance.

significance:
- Constrained generation is a central problem with LLMs, so addressing it is essential.
summary: The paper presents a novel method to sample from LLMs while satisfying constraints. The approach is based on sampling a preliminary sequence in the traditional (autoregressive) fashion, from which a tractable distribution approximating the target one (i.e., the autoregressive distribution conditioned on the constraint) is obtained. Then, samples from this distribution (which then satisfy the constraints) can be easily obtained and importance sampling can be used to renormalise them using the probabilities assigned to them by the autoregressive model. The local approximation is obtained by using constraint circuits, which the paper argues are more efficient than using regular expressions to check for constraints. The method provides exact samples from the target distribution (the autoregressive one conditioned on the constraints), which simpler greedy approaches are incapable of. The experimental results show the method allows perfect consistency with the constraints and very high performance.
weaknesses: The major issue with the paper is the lack of clarity in the notation and in presenting the method. In particular:
- First, I don't find myself fully convinced that the greedy sampling approach leads to samples that are not exact, due to the following reasons: 
	- it seems to me that greedy sampling is effectively identical (even though not operationally identical) to rejection sampling of full completions, by which I mean sampling multiple completions until they do not satisfy the constraint because the constraint is "hard" (you either satisfy it or not).
	- I believe rejection sampling of full completions targets the right conditional distribution 
	- It is correct that it is intractable to compute the normalizing constant of the conditional distribution, but that is generally not required for sampling from a distribution.
This amounts to saying that, actually, what the authors call the "myopic" distribution is identical to the exact one. Is there any fault with my reasoning here? I believe it would be useful for the authors to explain this carefully; for instance, it would be helpful, in Section 2.3, to give concrete example differ for specific choices of constraints.
- As I am not familiar with the topic, I found the discussion of logical circuits, DFA and related arguments in the second paragraph of the introduction and Sec 3.2 to be interpretable. After reading that, I am unsure about what is the difference between DFA and RegExp, and how constrain circuits can implement the former but not the latter. 
- The notation for the probabilistic quantities must be made more rigorous. For instance, 
	- from time to time new notations are introduced without being defined; for instance, the beginning of Sec 3 talks about $q(y)$ but Eq 3 uses $q(y,\tilde y)$, without explaining what it is; similarly for $p_y(\tilde y|\alpha)$ in Eq 8.
	- Strictly speaking, the right-hand side of Eq 5 is identical to the one of Eq 4 but evaluated in $\tilde y$ rather than $y$, but these two are used to define two different quantities. I assume the authors are abusing notation there, by assuming $p$ indicates a different distribution according to whether the argument has a tilde or not.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Could you provide a complete end-to-end algorithm that shows the full pipeline from initial model distribution $p_\theta$ to final constrained distribution $p^*$? The current split between Algorithms 1 and 2 leaves several implementation details unclear.

2. What is the computational cost of GEN-C compared to simpler approaches like word banning? Could the complexity be reduced using techniques similar to those in recent work on coordinate descent for language models?

3. In the Sudoku experiments, is the 100% accuracy rate an artifact of the constraint construction? How many samples are typically needed to achieve a valid solution, and how does it compare if you give the same number of samples to gemini or gpt4o?
soundness: 3
strengths: 1. The theoretical foundation is well-motivated, combining probabilistic sampling with logical constraints in a principled way.
2. The implementation leverages efficient logical circuits for marginal computation, which is novel as far as I am aware.
3. The experimental validation covers both practical (toxicity reduction) and formal (Sudoku) tasks
4. The approach approximately maintains the model's distributional properties while enforcing constraints, unlike simpler masking approaches which do not attempt to preserve the distribution.
summary: The paper presents GEN-C, a method for controllable generation that samples from a constrained subset of an LLM's distribution while maintaining the model's underlying probabilistic structure. The approach uses logical circuits for efficient marginal computation and importance sampling, while using a 1-Hamming-distance exhaustive proposal distribution.
weaknesses: 1. Clarity of exposition. The paper introduces multiple similar variables $(p_y, \tilde{p}_y)$ without clear distinctions. The probabilistic notation lacks consistency, making it difficult to track relationships between distributions. It would be useful to have a glossary in the appendix. It is hard to decipher what the full combined algorithm is, especially since algorithm 1 produces ${\tilde p}_y (y|\alpha)$ but ${p}_y (y|\alpha)$ is used in algorithm 2, which is presumably not the same. The paper would benefit hugely from a consolidated algorithm which shows the whole procedure.

2. Computational Complexity. As far as I can tell:
- The basic algorithm requires O(sequence_length × vocabulary_size) forward passes through the model
- For typical parameters (vocab size ~128K, sequence length 8), this amounts to approximately one million forward passes. This is quite a lot! But this doesn't seem to be discussed anywhere. In particular, it seems like there could be potential optimizations like those used in the paper [Universal and Transferable Adversarial Attacks on Aligned Language Models, Zou et al] which estimate one-hot deltas with a gradient-based approach. The computational overhead compared to simpler approaches like word banning is not adequately analyzed or justified. For instance, it's not clear if only one forward pass is used for the baselines while several hundred thousand are used for Gen-C.

3. Experimental Methodology:
As far as I can tell, the Sudoku experiments appear to guarantee 100% accuracy by construction, since any samples that are not valid are rejected, making comparisons with baseline methods potentially misleading. Shouldn't you also sample them until you get a valid sudoku? A fairer comparison would allocate equal sampling budgets to baseline methods like GPT-4 and Gemini. The improvements over word banning in toxicity reduction (Table 3) are modest given the substantially higher computational cost.

4. Novelty and Attribution:
- Section 3.2 appears to substantially reproduce content from the previous work [Neuro-Symbolic Entropy Regularization, UAI 2022] without appropriate attribution or differentiation.

Meta-review: This paper focuses on sampling from a language model subject to a constraint, i.e. from a distribution proportional to LM(x) * constraint(x). The authors propose using importance sampling where the proposal distribution is constructed via “knowledge compilation” which makes the sample satisfy a logical constraint. This sample is not necessarily distributed according to the target distribution of interest and is corrected via importance weighting and resampling. Constraint sampling from language models is an important problem and this paper is a nice contribution.

Decision: Accept (Poster)