Controllable Generation via Locally Constrained Resampling
Authors: Kareem Ahmed
Kai-Wei Chang
Guy Van den Broeck
Venue: ICLR 2025 Poster (2025)
Keywords: Neuro-symbolic
LLMs
Controllable Generation
Constraints
Probabilistic Methods
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

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. By factoring in information about the entire sequence, our approach offers better contextual awareness during constrained generation compared to current greedy approaches. 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 sample weights, 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 also show that our approach achieves a perfect accuracy on Sudoku, compared to less than $50\%$ for GPT4-o and Gemini 1.5.

Published as a conference paper at ICLR 2025
CONTROLLABLE GENERATION VIA LOCALLY CONSTRAINED RESAMPLING
Kareem Ahmed; Kai-Wei Chang & Guy Van den Broeck
Department of Computer Science University of California, Los Angeles {ahmedk, kwchang, guyvdb) @ us.ucl..edu
ABSTRACT
Autoregressive models have demonstrated an unprecedented ability at modeling the intricacies of natural language. However, they continue to struggle with gen- erating complex outputs that adhere to logical constraints. Sampling from a fully- independent distribution subject constraint is hard. Sampling from an autore- gressive distribution subject to constraint is doubly hard: We have to contend not only with the hardness of the constraint but also the distribution's 's lack of structure. We propose a tractable probabilistic approach that performs Bayesian condition- ing draw samples subject to 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 dis- tribution 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 several tasks, including LLM detoxification and solving Sudoku puz- zles. We show that by disallowing a list toxic expressions our approach able steer the model's 's outputs away from toxic generations, outperforming similar approaches to detoxification. We conclude by showing that our approach achieves perfect accuracy on Sudoku compared < 50% for GPT4-o and Gemini 1.5.
INTRODUCTION
The advent of large language models (LLMs) has brought about paradigm shift towards generating sequences of tokens that jointly constitute the desired output. Such multi-token outputs exhibit an amount of structure paragraphs; in question answering, it is expected to provide answers to the posed questions; and in summarization, is expected to condense lengthy documents into concise summaries. And while current LLMs are remarkably apt generating fluent sentences, there is need for generations that go beyond that, exhibiting more intricate structure (Liu et al., 2024b). Such structure includes, e.g., API calls and code snippets (Wang et al., 2023), JSON schemas (OpenAI, 2023), logical puz- zles (Mittal et al., 2024; Pan et al., 2023), all of which LLMs struggle with (Sun et al., 2023).
them: in free-form generation, the model is expected to generate coherent
Consequently, several approaches to constraining LLMs were developed, all bolstering similar underlying idea: at every generation step greedily mask the L.M outputs that could lead to the constraint being violated. That is, the "defacto" recipe (Deutsch et al., 2019; Lundherg al., 2024; Willard & Louf, 2023; Koo et al., 2024) for applying constraints to LLMS consists of the following:
1. Based the current state of the constraint, build 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 number of ways. First, the masking process is myopic (Shih al., 2023), as the constraint is enforced greedily on a per-token basis rather than jointly across the entire
"Latter portions of this research were conducted while affiliated with University of California, Irvine.

---

Published as a conference paper at ICLR 2025
p())))
p(y
P(yla)
[Be's, s, .uul, Jof, ssh!tl
[Je' rull, .oI, -satt]
[Hles Iuul, time, .employed]
1In dist.
uu apprex, dies.
y
y
y
Ma
ma
mo
Figure 1: An illustration of our proposed approach. (left) An LLM induces distribution over all possible sentences. Autoregressively sampling from the LLM distribution, we obtain a sentence ÿ [He' s, .ffull, .of, .. This sentence ÿ violates constraint that disal- lows toxic words, including the word "sh! !t. The subset of sentences that satisfy the constraint a (I)) are denoted by + m, -t (center) The sentence ÿ induces local, tractable approximation of the true distribution centered around ÿ. (right) We can efficiently condition this tractable approxi- mation on the constraint a, trimming away portions of its support that do not satisfy the constraint. Sampling from the LLM distribution subject to the constraint then corresponds to sampling from the conditional approximate distribution and adjusting the sample weights using importance weight- y [He' s, fulll time, _employed] that satisfies a.
ing. This yields a sentence
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 signifi- cantly more verbose than their target compilation forms, deterministic finite automata (DFAs) (Gru- ber & Holzer, 2009; 2014; Koo et al., 2024). 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 con- straining LLMs, tackling all the aforementioned shortcomings in the process. Our approach starts with the observation that an LIM sample induces a local, factorized distribution p. We use a tractable compilation form, constraint circuits (Darwiche, 201 1), that subsume DFAs bounded- length strings while being more expressive efficient (Choi et al., 2020). That is, there are classes of functions that we can represent using constraint circuits that could not otherwise as effi- ciently represent using DFAs (Bova, 2016). Such constraint circuits can be specified as Boolean python functions, alleviating the need for writing regular expressions or other domain specific lan- guages. We show that we can leverage logical circuits to tractably condition p. drawing samples that are biased yet provably satisfy the constraint. Sampling from the LLM subject to a constraint a then entails conditioning on a, drawing biased samples from ç(- a)), 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 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 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 perfect accuracy on Sudoku puzzles, compared to an almost 26% and 45% accuracy achieved by Gemini 1.5 Flash and GPT4-o models, respectively.
2 BACKGROUND
2.1 NOTATION AND PRELIMINARIES
We write uppercase letters (X, Y) for Boolean variables and lowercase letters (2. y) for their instan- tiation (Y = 0 or Y = 1). Sets of variables are written in bold uppercase (X, Y), and their joint instantiation in bold lowercase (æ, y). A literal is variable (Y) or its negation (-Y). A logical
2

---

Published as a conference paper at ICLR 2025
sentence (a or () is constructed from variables and logical connectives (A, V, -, and is also called a (logical) formula or constraint. A state or world y is an instantiation to all variables Y. A state y satisfies constraint a, denoted y }= a, if the sentence evaluates to true in that world. A state satisfying a constraint a is said to be a model of a. We denote by m(() the set of a'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, 1992).
2.2 A PROBABILITY DISTRIBUTION OVER POSSIBLE SENTENCES
Let a be a logical constraint defined over Boolean variables Y (YII...., Yn where n denotes the number of time steps in the sentence, and & denotes the size of the vocabulary, i.e., the number of possible tokens each time step. An autoregressive model induces probability distribution p(-) over all possible sentences y. At every time step i, the autoregressive model ensures that exactly one token is predicted; i.e., exactly one Boolean variable {Yi,,.... Yu } can be set to true for each time step i. We will write y; to denote that variable Yıy is set true in sentence y. More precisely, let y: {0,, 1)sh be the one-hot encoding of Y3 being set to 1 among {Yi....., Y.k). The probability assigned by the autoregressive model to a sentence y is then defined as
p(y) II p(y yer):
(1)
where yeu denotes the sentence prefix, yl.-.... 1--1-
2.3 THE STATE OF CONDITIONAL AUTOREGRESSIN SAMPLING
Sampling from an autoregressive distribution conditioned on a logical constraint a constitutes major challenge: computing the exact conditional distribution p(y a) p(v.a) is intractable even for the simplest constraints (Roth, 1993), e-g., asserting that the word "dog" appears at the end of the sentence. Intuitively, conditioning on a requires that we compute the marginal probability of the constraint p(a),, in turn requiring that we enumerate all sentences ending with the word "dog".
p(a)
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., 2019; Lundberg et al., 2024; Willard & Louf, 2023; Koo et al., 2024). Let the conditioning of the constraint a on the prefix Yeu, which we write as 0lyee be a subconsiraint defined on Y.m. that results from setting the variables Y to their values in YKs- Semantically, dlys. denotes the set of yen that, taken together with the prefix yeu- would satisfy the constraint. Moreover, let & == Bys Olyc, denote the set of tokens allowed the i-th position such that there exists some completion Y of the sentence that satisfies the constraint a, given the current prefix Yci. Then we can define the above greedy, or myopic, distribution
p B, yei) Σ, P(u, B y2.)
p(y y I + 31
P myopic
II
II
P(U.) v<t) Mh 3.1'
Of note here is that since the approximate distribution is modeling the joint probability of the sen- tence and the constraint, in principle, the logical reasoning is sound, i.e., the constraint guaranteed to hold. Rather, the shortcoming is in the way the probabilistic reasoming is performed: instead of normalizing the joint distribution by the marginal probability of the constraint, we are perform- ing it token-wise steering us towards sampling sequences that are locally likely rather than globally likely. To see this, consider an LLM trained to generate one of the eight sentences from the set (Adam, Poorva)
{loves, hates) x (dogs, cats} uniformly at random. If we condi- tion the L.M on the fact that Adam loves cats, we reduce the possible outputs to five: Adam loves cats and all generations starting with Poorva, each now generated with an equal proba- bility of 1/5. However, since the LLM initially generates each of the eight possible sentences with equal probability, it must generate a string starting with Adam Poorva with equal probability and therefore greedy decoding mistakenly generates the string Adam loves cats half the time.
The second issue lies with the logical constraint along two different axes. First is the lack of concise- ness of the constraint specification language. The most common language for specifying constraints is regular expressions which can be significantly more verbose (Gruber & Holzer, 2009; 2014; Koo
3

---

Published as a conference paper at ICLR 2025
et al., 2024) compared to the equivalent logical form. This is due to the inability reference and reuse sub-expressions without introducing additional features such as lookaround operations which can cause exponential blowup in the size of the target representations (Mamouras & Chattopad- hyay, 2024), or backreferences that allow us to describe non-regular languages at the expense of an exponential runtime due backtracking. Second is the lack of succinctness of the target rep- resentation. All of the current approaches compile the specified regular expressions into DFAs. DFAs represent Boolean functions by recursively performing Shannon-decomposition on the func- tion: 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, but rather that of an entire sentence (Darwiche, 2011). This class of target representations, which we shall henceforth denote as constraint circuits are not only more succinct than DFAs in practice, but provably exponentially more succinct: there are classes of functions with exponentially-sizee DFAs but polynomially-sizee constraint circuits (Bova, 2016).
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(y) using a local, tractable distribution p(y). The distribution p(y) is amenable to exact and efficient probabilistic reasoning, allowing us efficiently condition on the constraint a and draw samples from the distribution p(y a). We can transform the biased samples drawn from p(y | a)) into samples from p(y a) 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(y a) p(y.a) p(a)
(2)
which is intractable. Instead, we design a tractable proposal distribution q such that ((y) > 0 whenever p(y a) > O. We associate with constrained sample y an unconstrained sample ÿ. where y can be understood as projection of ÿ onto a s.t. y } a. We define our proposal as
((y) = Σ p(ū) po a))
where p(ğ) is the autoregressive distribution, and (y at) is distribution over projections y of the unconstrained ÿ given the constraint a. The above definition outlines a two-step procedure for sampling a sentence that satisfies a given constraint We sample a sentence ÿ autoregressively from p()). followed by sampling y from the distribution conditioned on ÿ and the constraint a, Py Py(y [y] a.. By incorporating the autoregressive distribution p(ğ), we ensure that can potentially generate any sentence. Py(y | a) then refines ÿ by projecting it to satisfy the constraint a. It is straightforward sample from p(ū), but what exactly is Pý Py()), and how do condition it a? 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 probability distribution p5 a) that is first, tractable for conditioning on the constraint a 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 sample-efficient approximation of the true distribution (Koller & Friedman, 2009).
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-man 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 exam- ple being the n choose l constraint (Ahmed et al., 2023b), where the conditional distribution can be computed in quadratic time under the falto-factorized distribution, despite having combinato- rially many solutions. Moving away from fully- factoriad distribution and towards autoregressive distributions, however, requires that we enumerate all sentences, even for very simple constraints.
4

---

Published as a conference paper at ICLR 2025
To sidestep the hardness of the autoregressive distribution, attempt to move towards the tractabil- ity of cully-factoriz distributions, while retaining as much of the contextual information. To that end, consider the pseudolikelihood p(-) of sentence y (Besag, 1975; Ahmed et al., 2023a), i..,,
p = p(O) = II p(U Ø-1),
(4)
where ÿ-: denotes .i..... 11 1i+1. yn- Unfortunately, Equation (4) above would still not ensure the tractability of Equation (2) since different solutions depend on different sets of condition- als. Instead, we define the pseudolikelihood of a sentence y in the neighborhood of a sentence y
Py(y)=
II ply: Ø-
(5)
which can be understood as the contextualized probability of a sentence y given the context ý. We will next show how, given the structure of the contextualized pseudolikelihood distribution, we are able to efficiently condition it on a constraint a. Furthermore, Ahmed et al. (2023a) have shown the contextualized pseudolikelihood distribution to be 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--divegeence meaning that our approximation is faithful the true distribution in the neighhorhood of the model sample.
3.2 CONSTRAINT COMPILATION AND TRACTABLE OPERATIONS
We appeal to knowledge compilation, class of methods that transform, or compile, 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, 2017) or Py PyTorch functions (Ahmed et al., 2022a) from which they construct cir- cuits. 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 PyTorch function which gets compiled into constraint circuit is shown in the bottom left of Figure 2 with the corresponding circuit in Figure 2, right.
Formally, logical circuit is directed, acyclic computational graph representing a logical formula over variables X. Each node n in the DAG encodes a logical sub-formula, denoted [n]. Each inner node in the graph is AND or OR gate, and each leaf node encodes a Boolean literal (Y or -Y)).. We denote by in(n) the set of a node n''s 's children. We associate with every node n a scope function <(-) such that ((n) X evaluates to the subset of variables the subfunction
is defined over.
A circuit is decomposable if the inputs of every AND gate depend on disjoint sets of variables i.e. for a B A 7. vars(3) vars(7) Ø. A circuit is said be structured-ddccooposabb 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 cireuit in exchange for polynomial size increase (Vergari et al., 2015; Peharz et al., 2020).
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 a = V we have that vars(33) = vars( Vi,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, 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 a = V, B,, we have that 8, A B, -i for all i * j. Similar to decomposability, determinism induces 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,
V.(B,A7%), the 3, 's are mutually exclusive i.e., 33 A 33 = 1 for any + j. Ensuring they are also exhaustive i.c., V; S = T, along with structured- decomposability, we recover sentential decision diagrams (Darwiche, 201 )), or constraint circuits.
5

---

Published as a conference paper at ICLR 2025
Algorithm Compute Py Q)
Algorithm 2 Locally Constrained Resampling
1: Input: Constraint a,, LLM distribution p(.)
1: Input: Constraint o, LLM distribution p(-)
2: Output: P ax) defined in Equation (5)
2: Output: drawn approximately from p(y a))
3: ÿ ~ p<p(.)
D Sample y and ÿ from p(y) and Py aa) resp.
>. Expand the batch to contain all perturbations
3: y p(-)
> of y that are a Hamming distance of I away
4: y ~ Pp a)) & From Algorithm
4: ý = "..expand(nn vocab)
D. Compute importance weights
5: gf. range(n); range(n)] = range(vocab)
5: q_w = p()) Po (3) |
> Evaluate expanded samples through model
6: p-w p(y) [[canonize(y) - a] Py (t)
6: log p .og sof tmax softmax(dim
-1)
7: p-w/q_w
> Compute log Po [ = log po y y yー1)
7: log log p log p.logsumexpp xp (dim -1)
Resample distribution according weights
>> A vector of conditional marginals by (14) a)
8: p" Categorical =w
8: return P at)
9: return p* .sampee
Given a constraint circuit ca that encodes a logical constraint a we can compute the pseudolikeli- hood (()) 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 distribu- tion (ÿ a). To sample from the distribution, starting from the root node, we trace the circuit top-down, sampling a child at every OR Og-gate encountered. Figure 2 (center) shows example of computing such distribution, and Figure 2 (right) demonstrates the process of sampling from it.
3.3 INTERMEZZO: CONSTRAINT CIRCUITS AND DFAS
Constraint circuits can implement decisions of the form
m
V
(6)
at OR gates, where X and Y are disjoint sets of variables, as opposed to DFAs that are restricted to Binary (or Shannon) decisions and therefore boil down very special decisions of the form
(~xA v 72())
where the variable X is not in the variable set Y. Therefore, constraint circuits are exponen- tially more succinct than DFAs, i.e., there are families of functions can only be represented by exponentially-sizee DFAs, but have polynomially-sinn such families of functions, constraint circuits are also empirically more succinct than DFAs (Xue et al., 2012). In practice, this also allows to construct shallower (i.c., less layers) and wider (i.e., units per layer) constraint circuits that are more amenable to GPU parallelization (Liu et al., 2024a), and can therefore exhibit much lower vectorized computational complexity (Ahmed et al., 2023b).
constraint circuit (Bova, 2016). Barring
3.4 CORRECTING SAMPLE BIAS: IMPORTANCE SAMPLING... RESAMPLING
We have now sampled y from our proposal distribution y(y), where is a projection of some latent unconstrained sample y. and satisfies the constraint a. However, our proposal distribution g might not align perfectly with our target distribution p(y a). We therefore need to account for the mismatch between the two distributions, which we can do by defining importance weights that are function of the original y. and its projection ÿ. We start by defining the true augmented distribution
ply a)
Σ p(y. a)) Py (v)
This factorization reflects the process of first generating constrained sentence y. and marginalizing over all the unconstrained sentences ý that could have given rise to y. and can be therefore be thought of as reversing the proposal distribution. We calculate the self-normalized importance weights
p(y, a) Py (g(
w
p(ū) Pg ( a)
(8)

---

Published as a conference paper at ICLR 2025
0.60
0.60
p(v) ~M I: 0.3
hate:
0.3 doga: 0.4
0.25
love:
0.5 cats:
0.36
0.12
0.12
She:
0.25
adore:
0.2
rats: 0.2
0.12
0.12
P(T): 0.6
;[hate):
0.4 1 ((dogs):
0.3
Atee:: 0.2
plloee]:
0.5 p(cass:
0.3
0.6
p[She): 0.2
Madore)
0.1 p(zats):
0.2
Ho
Shc 0.2
Hc 0-2
Shc 0.2
0.6
0.6
0.3
0.1
0.5
0.1
idx Tokenizer, aakenizer.tokenize tokeniza (* hate")
True
loves 0.5
adores 0.1
loves 0.5
adores
for 1 in sange [eqgless]:
0.1
and tckens (i, 1dx)
return
dogs 0.3
rats 0.2
cats
dogs
cats
0.3
Figure 2: Constructing and sampling the proposal distribution. (Top left) We start by sampling sentence ÿ from the model p. Our goal is compute the full conditional probability of every word in the vocab i.e., P(Dss) == p(ūe ÿ=:). We start by expanding the sampled sentence y. including all sentences that
Hamming distance of away from the sample 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(yt)) (Bottom left) We can easily specify a logical constraint that prevents the word hate" from appearing as simple python function that gets compiled the constraint circuit on the right. (Center) A logical circuit encoding constraint -hates, with a simplified vocab is shown in the figure. To construct the distribution Py (y a²), 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 distribution Pt (3/ at). (Right) To sample a from this distribution, we start at the root the circuit, sampling a child of every OR gate according to the logits of the distribution, and concatenating every AND gate. In this case, we sample the sentence "He loves dogs" satisfying the constraint.
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(y at), only set of weighted particles. Rather, to transform our weighted particles into samples drawn from p(y | (x) we need to apply a resampling step ac- cording the importance weights. That is, given particles 8; with their corresponding importance weights wy, if we resample 8, with replacement from the importance weights i.c..
8n} with probabilities proportional
Wi
(s{)
2j=1 Wj
then s; is drawn from the true the distribution in the limit of large sample size n. Our full algorithm shown in Algorithm 2. and follows Py Torch syntax (Paszke et al., 2019). One thing to note the use of the canonize function on line 6 in Algorithm 2, where canonize returns the canonical tokenization of an expression (Geh et al., 2024). This ensures that, e.g., in the case of language banning all the possible ways of generating given expression. We can now prove that Algorithm is guaranteed to return samples that satisfy the constraint a. Our algorithm implemented in log-space to preserve numerical stability while handling very small probabilities.
detoxification,
Theorem 1. LOCALLY CONSTRAINED RESAMPLING in Algorithm 2 returns a sample y s.t. y }= a.
4 RELATED WORK
There has been long line of work tackling constrained generation with LLMs. One of the car- lier approaches was to use search-based decoding algorithms, such as NeuroLogic Decoding (Lu et al., 2021; 2022). While these methods explicitly search for high-probability sequences that sat- isfy the constraint, they face scalability issues due the exponential growth of the search space as the sequence length increases. Another set of techniques that include GeDi (Krause et al., 2021),
'This issue has received an amount of attention in the past https: / /gg thub. www.//oo.//ooeeeeeoeoooo wgw.nugggignnnnege trans forme rs/ ssues/ 4
7

---

Published as a conference paper at ICLR 2025
Test accuracy %
Exact
Consistent
Test accuracy %
Exact
Consistent
CNN-LSTM
62.00
76.60
Gemini 1.5 Flash
31.00% + 4.19
31.00% + 4.19
GPT-4o mini
40.90% + 7.90
40.90% = 7.90
+ oversampling
69.10%
84.50% 100%
GRN-C (Ours)
78. 13%
GEN-C (Ours)
100%
100%
Table 1: Experimental results on Warcraft.
Table 2: Results on Sudoku across 3 runs.
FUDGE (Yang & Klein, 2021), and NADO (Meng al., 2022) employ auxiliary neural classifiers to approximate the intractable conditional distribution, but do not guarantee that the constraint is sat- isfied and require that classifier be trained for every new constraint type. Approximate inference methods attempt to approximate the intractable conditional distributions (Qin et al., 2022; Hu et al., 2023; Lew et al., 2023) but suffer from high variance and do not guarantee constraint satisfaction.
Recently Outlines (Willard & Louf, 2023) and Guidance (Lundberg et al., 2024), and along similar lines SGLang (Zheng et al., 2024), were proposed, also guaranteeing that the constraint is satisfied. Outlines employs precompilation step where constraints specified in regular expressions are com- piled into DFAs that are "indexed" create token-based overlay. This overlay guides the decoding process, ensuring adherence to the constraints. Koo et al. (2024) recently recast the entire process an automata-theoretie framework. Similar to Outlines, Guidance utilizes trie to efficiently store and search through valid token continuations based on the grammar. This allows for dynamic vo- cabulary matching at each decoding step, offering flexibility potentially at the cost of impacting efficiency. These approaches considered the "defacto" approaches for constrained generation.
More recently, GeLaTo (Zhang et al., 2023) and subsequently CTRL-G (Zhang et al., 2024) 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., 2024) aims to debias the greedy approach through repeated sampling and discov- ery of mass assigned to non- non-grammatical completions, reducing each overapproximation to make it more accurate. While similar in intention, our approach relies on closed-form tractable approxi- mation of the target distribution to correct for the bias, avoiding the need to oversample the LLM.
Finally, some other approaches longer predictively mask logits, but instead sample unconstrained continuations and reject invalid ones post-hoc. For example. PICARD (Scholak et al., 2021) 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 very low probability tokens.
5 EXPERIMENTAL EVALUATION
We evaluate our approach GEN-C on several tasks spanning a number of domains. We start by evaluating Warcraft shortest-path finding, where and are tasked with autoregressively generating one of the potentially many minimum-cost paths between two end points conditioned 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 9 x 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, 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., 2020) has found non- negligibee amounts of toxic, harmful, and abusive text in the corpora used to train LLMs. Experimental details, hardware specifications, and training details provided in the appendix. The implementation of approach will be made publicly available.
given an image of a Warcraft tilemap,
8

---

Published as a conference paper at ICLR 2025
Table Evaluation of LLM toxicity and quality across different detoxification methods on Llama3- 8b. Model toxicity is evaluated on the REALTOXICCTYPRMMP benchmark through Perspective API. Full, Toxic and Nontoxic refer to the full, toxic and nontoxic subsets of the prompts, respec- tively. PPL refers to the perplexity of Llama3-70B on the model generations using 5 different seeds. In line with Gehman et al. (2020); Wang et al. (2022), we characterize toxicity using two metries: the Expected Maximum Toxicity over generations, and the Toxicity Probability of completion at least once over generations.
How toxic is the model? (L)
How often it toxic? (L)
Models to toxic
PPL (4)
to nontoxic
to toxic
to nontoxic
LLAMA3-8B
0.43
0.20
38.30%
7.60%
14.45
Greedy Decoding
0.40
0.19
32.43%
6.93%
14.50
+ GEN-C (ours) 0.37
0.19
28.00%
6.35%
14.50
Warcraft Shortest Path For this task, we follow the experimental setting set forth by Pogančić et al. (2020), where our training set consists of 10, 000 terrain maps curated using Warcraft II tileset. Each map encodes a 12 x 12 grid superimposed on Warcraft terrain map, where each vertex is weighted according to the cost of the tile, which turn depends on type of terrain 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-com 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-com path is not unique, i.e., there exists many correct paths with the minimum cost.
We use CNN-LSTM model, where, presented with image of terrain map, (He et al., 2016) 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 valid simple path from the upper left vertex to the lower right corner of the map.
a ResNet18
As has been established in previous work (Xu et al., 2018; Ahmed et al., 2022b;c), the accuracy of predicting individual labels is often poor indicator of the performance of the neural network in seuro-symbolic settings, where we are rather more interested in the accuracy of our predicted structured object exactly matching the groundtruth label, e.g.. the prediction a shortest path?, 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 1. 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, 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 19% to 78. 13% while guaranteeing the sampled sequences of edges constitute valid paths, as
Sudoku Next, we consider the task of predicting solution to given Sudoku puzzle. Here the task is, given 9 x 9 partially-filed grid of numbers to fill in the remaining cells such that the entries each row, column, and 3 x 3 square are unique i.e., each number from to 9 appears exactly once. We use the dataset provided by Wang et al. (2019), 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 x 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, approach consistently manages to recover the correct Sudoku Puzzle solution.
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-gennrrations. We choose very simple constraint to be enforced by GEN-C through-

---

Published as a conference paper at ICLR 2025
out this task, namely we ban any of list of "bad words", including profanity, slurs, and swear words from appearing as part of the model's generations. Similar to previous work (Gehman et al,, 2020: Wang et al., 2022), we evaluate on the REALTOXICITYPRRMPPE prompts ranging from nontoxic, assigned a toxicity score of O, to very toxic, assigned a toxicity score of 1. We foeus LLAMA3-8B (Radford et al., 2019) as base model for detoxification. As customary (Gehman et al., 2020; Wang et al., 2022), we use Perspective API, an API for toxic language and hate speech detection, to score the toxicity of our predictions. It returns scores in the range 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 the text being perceived as toxic and have been shown to be strongly correlated with human evaluations (Wang et al., 2022; Welbl et al., 2021).
a dataset of almost 100k
We compare LLAMA3-8B against WORD BANNING, which for this simple constraint functions very similarly to Outlines (Willard & Louf, 2023) and Guidance (Lundberg et al., 2024). It keeps track of the words generated so far, and prevents the banned expression from appearing by setting its probability to O. 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 sentence associated with 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 toxic- ity 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 toxic continuation is generated at least once over 25 generations with different random seeds for all prompts. This metric can be seen as 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 detoxifica- tion, 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 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 modest 1 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 constraining our LLAMA3-8B with our approach GEN-C attains the same perplexity as using word banning, but greatly reduces the toxicity of LLA M-388, especially on toxic prompts where 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 logical con- straint, GEN-C guarantees that an autoregressive model's generations satisfy the constraint. GEN-C C is probabilistically sound, while providing concise constraint specification language as well as an exponentially more succinet 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 basclines on the tasks of minimum-coss paths pre- diction, language as well solving Sudoku puzzles, where achieved a perfect accuracy, heating both GPT-4o and Gemini 1.5 by a large margin. We have also shown that by virtue of its proba- bilistic nature, GEN-C is able outperform current approaches for constrained generation on LLM detoxification using only a list of toxic expressions as a constraint, relying on probabilistic inference.
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., 2024a) 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.
2 downloaded from here.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The work is supported by the DARPA ANSR program FA8750-23-2-0004. The views and conclu- sions are those of the authors and should not reflect the official policy position of DARPA or the U.S. Government.
REFERENCES
Kareem Ahmed, Tao Li, Thy Ton, Quan Guo, Kai Chang, Parisa Kordjamshidi, Vivek Sriku- mar, Guy Van den Broeck, and Sameer Singh. Pylon: A pytorch framework for learning with constraints. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Demo Track), feb 2022a.
Kareem Ahmed, Stefano Teso Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Seman- tic probabilistic layers for neuro-symbolic learning. In NeurIPS, 2022b.
Kareem Ahmed, Eric Wang, Kai-Wei Chang, and Guy Van den Broeck. Neuro-symbolic entropy regularization. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022c.
Kareem Ahmed, Kei Chang, and Guy Van den Broeck. A pseudo-semantic loss for deep gen- erative models with logical constraints. NeurIPS, 2023a.
Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. Simple: A gradient estimator for k-subset sampling. In Proceedings of the International Conference Learning Representa- tions (ICLR), may 2023b.
Julian Besag. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society, Series D (The Statistician), pp. pp. 179-195, 1975.
Simone Bova. Sdds are exponentially more succinet than obdds. In AAAI Conference on Artificial Intelligence, 2016.
Randal E. Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys, 1992.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying frame- work for tractable probabilistic modeling. 2020.
Adnan Darwiche, Sdd: A new canonical representation of propositional knowledge bases. In IJCAI, 2011.
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A general-purposs algorithm for constrained sequential inference. Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), 2019.
Renato Lui Geh, Honghua Zhang. Kareem Ahmed, Benjie Wang, and Guy Van den Broeck. Where is the signal in tokenization space? In Empirical Methods in Natural Language Processing 2024, 2024.
Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. Realtoxic- ityprompts: Evaluating neural toxic degeneration in language models. ArXiv, abs/2009, 1442, 2020.
Hermann Gruber and Markus Holzer. Tight bounds on the descriptional complexity of reg- ular expressions. In Proceedings of the 13th International Conference on Developments in Language Theory, DLT '09, pp. 276-287, Berlin, Heidelberg, 2009. Springer- Springer-Verlag. ISBN 9783642027369, doi:
0-179978---622-0777-6222
Hermann Gruber and Markus Holzer. From finite automata to regular expressions and back-a sum- mary on descriptional complexity. Electronic Proceedings in Theoretical Computer Science, 151, 05 2014. doi: 10.4204/EPTCS.155.1
11

---

Published as a conference paper at ICLR 2025
Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, and Sourab Man- grulkar. Accelerate: Training and inference at scale made simple, efficient and adaptable., 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, June 2016.
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. 2023.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Teryy Koo, Frederick Liu, and Luheng He. Automata-based constraints for language model decod- ing, 2024.
Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq Joty, Richard Socher, and Nazneen Fatema Rajani. Gedi: Generative discriminator guided sequence generation. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 4929-4952, 2021.
Alexander K Lew, Tan Zuan, Gabriel Grand, and Vikash K Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs. arXiv preprini arXiv:2306.03081, 2023.
Anji Liu, Kareem Ahmed, and Guy Van den Broeck. Scaling tractable probabilistic circuits: A sys- tems perspective. In International Conference Machine Learning (ICML), July 2024, 2024a.
Michael Xieyang Liu, Frederick Liu, Alex Fiannaca, Terry Koo, Lucas Dixon, Michael Terry, and Carrie Cai. "we need structured output"": Towards user-centered constraints on large language model output. pp. 2024b.
Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Neurologic (ecoding:(un) supervised neural text generation with predicate logic constraints. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Com- putational Linguistics; Human Language Technologies (NAACL), 2021.
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 heuristies. In Proceedings of the 2022 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 780-799, 2022.
Scott Lundberg, Marco Ribeiro, Richard Edgar, and Harsha-Nori. Guidance: guidance language for controlling large language models., 2024.
Konstantinos Mamouras and Agnishom Chattopadhyay. determining the validity of a given isbn matching of regular expressions with lookaround assertions. Proc. ACM Program, Lang., 2024.
Wannes Meert. Pysdd. In Recent Trends in Knowledge Compilation, sep 2017.
Tao Meng, Sidi Lu, Nanyun Peng, and Kai-Wei Chang. Controllable text generation with neurally- decomposed oracle. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022.
Chinmay Mittal, Krishna Kartik, Mausam, and Parag Singla. Puzzlebench: Can Ilms solve chal- lenging first-order combinatorial reasoning problems?, 2024.
OpenAl. Introducing structured outputs in the api. https://openaa com. indx// introodrdn---srruuuuree--- wtw.:sstttttuuudooourrtoee soteeddoottttt--inn ieces--in-tee thetheeapppt /, June 2023. Accessed: 2023-09-
24.
Liangming Pan, Alon Albalak, Xinyi Wang, and William Wang. Logic-LM: Empowering large lan- guage models with symbolic solvers for faithful logical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2023, 2023.
12

---

Published as a conference paper at ICLR 2025
Kanghee Park, Jiayu Wang. Taylor Berg- Kirkpatrick, Nadia Polikarpova, and Loris D' A'ttoni. coummar-aligned decoding. In NeurlPS, 2024.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, nigh-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference of Machine Learning, 2020.
Marin Vlastelica Pogančié, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differ- entiation of blackbox combinatorial solvers. In ICLR, 2020.
Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. Cold decoding: Energy-based con- strained text generation with langevin dynamics. Advances in Neural Information Processing Systems, 35:9538 115099551111 2022.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. 2019.
Dan Roth. On the hardness of approximate reasoning. IJCAI, pp. 613 619.619. Morgan Kaufmann, 1993.
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the 2021 Confer- ence on Empirical Methods in Natural Language Processing, 2021.
Andy Shih, Dorsa Sadigh, and Stefano Ermon. Long horizon temperature scaling. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Jiao Sun, Yufei Tian, Wangchunshu Zhou, Nan Xu, Qian Hu, Rahul Gupta, John Wieting, Nanyun Peng, and Xuezhe Ma. Evaluating large language models on controlled generation tasks. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthen- ing sum-product network structure learning. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 343-358. Springer, 2015.
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. Advances in Neural Information Processing Systems, 34, 2021.
Bailin Wang. Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. Grammar prompt- ing for domain-specific language generation with large language models. In Thirty-seventh Con- ference Neural Information Processing Systems, 2023.
Boxin Wang, Wei Ping, Chaowei Xiao, Peng Xu, Mostofa Patwary, Mohammad Shoeybi. Bo Li, Anima Anandkumar, and Bryan Catanzaro. Exploring the limits of domain-adaptiv training for detoxifying large-scale language models. In Neurips, 2022.
Re- Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6545 PMLR, 2019.
Johannes Welbl, Amelia Glaese, Jonathan Uesato, Sumanth Dathathri, John F. J. Mellor, Lisa Anne Hendricks, Kirsty Anderson, Pushmeet Kohli, Ben Coppin, and Po-Sen Huang. Challenges in detoxifying language models. ArXiv, abs/2109.07440 2021.
13

---

Published as a conference paper at ICLR 2025
Brandon T. Willard and Rémi Louf. Efficient guided generation for large language models. ArXiv, abs/2307.09 099002, 2023.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning, pp. 5502-5511, PMLR, 2018.
Yexiang Xue, Arthur Choi, and Adnan Darwiche. Basing decisions on sentences in decision dia- grams. Proceedings of the AAAI Conference on Artificial Intelligence, 2012.
Kevin Yang and Dan Klein. Fudge: Controlled text generation with future discriminators. In Pro- ceedings of the 2021 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies (NAACL), 2021.
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In Proceedings of the 40th International Conference Ma- chine Learning (ICML), jul 2023.
Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Nanyun Peng, and Guy Van den Broeck. Adaptable logical control for large language models. In NeurlPS, 2024.
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. Sglang: Efficient execution of structured language model programs. NewrIPS 2024, 2024.
14

---

Published as a conference paper at ICLR 2025
A PROOFS
Theorem 1. LOCALLY CONSTRAINED RESAMPLING in Algorithm 2 returns a sample y s.t. y F a.
Proof. Let y - (y),..., yn) denote a string. Let vocabulary V denote a set of subwords, or tokens.
tokenization of a string y w.r.t. a vocabulary V is sequence of tokens v (VI,..... Un) such that each 1; E V and the concatenation of all tokens constitutes the string y, i.c., vi 0.0 y.
An autoregressive distribution p(-) defines a conditional probability distribution over tokens, and therefore, induces a distribution over tokenizations of a given string (Geh et al., 2024)
[1 p (2% ................................ e2-1) if y.
p(u, y)
otherwise,
where e }= y denotes that e a tokenization of y.
We start by showing that, if the canonical tokenization of string does not satisfy a, then Al- gorithm precludes any non-canonical tokenizations of the string y. To see that, observe that non-canonical tokenization of a sentence y generated by Algorithm 2 is subsequently cast into canonical tokenization by invoking the canonize function. It is then assigned an importance weight of 0, and assigned zero probability in the resampling distribution on line 9 in Algorithm 2.
During the resampling step, the set candidate samples are only those sampled from Pn( (x)
We will now show that we can always construct (- | a:) given constraint defined over variables (Yi.....,Y., Y and a contextualized psuedolikelihood distribution (-).). 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 distribu- tion where with slight abuse of notation, we use Py (-) refer both the distribution well its circuit representation. Such a construction proceeds by introducing a Bernoulli distribution unit for each variable, and connecting the Bernoulli distribution units using singular product node.
Given a constraint a, we can compile it into a constraint circuit C... 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: left (right) AND node whose children are the positive (negative) literal and the subtree corresponding substituting the positive (negative) literal into the constraint. Repeat the above process till exhausting all the variables.
Given a constraint circuit Ca, a deterministic and omnicompatible circuit (Vergari et al., 2021) (.))). we can compute the product of the two circuits (- a) in time O(p]]c)) ([).]c]), following from Theorem 3.2 Vergari et al. (2021). Furthermore, the resulting product circuit (- ar) can be normalized in time ((p)) to obtain (- a.), following from Proposition 2.1 in Vergari et al. (2021)
B LANGUAGE DETOXIFICATION
The experiments were run 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 al., 2022) library.
In order to construct our constraint, we start with the list bad words and their space-prefixed v 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 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.
List downloaded from here.
A word will be encoded differently whether it space-prefixed or not.
15

---

Published as a conference paper at ICLR 2025
6 07 0 0
6
6
8
3
2
8
4 5
0 04 0000400020
1 6
9
2
O 4 0 04000033.
92449422 2
836
0 304406070 76
999
394490
0 0 00/0906000
7 8895944 6
5 0 9 0 000000000000
52
877
O 0 4 9 5 2
4 8
9 5
0 D 0
1 7
O
0
9 3
8
7727455 5 2
Figure 3: Example inputs and groundtruth labels for two of the three tasks considered in our experimental evaluation. (Left) Example Warcraft terrain map and possible (nonuniquee) minimum-cost shortest path. (Right) Example Sudoku puzzle and corresponding (unique) solution.
We use batch size of 10 during generation, and only sample every sentence 5 times. The model sentence was generated using nucleus sampling with p = 0.9 and a temperature 1. We experi- mented with tempering the contextualized beeudo-ikelihood distribution of size 1000 using = {0.1, 0.3, 0.5, 0.7, 0.9, 1.0). Our final results are reported on random sub- set of the SealToxxiityyPromps dataset of size 10k, average over different runs using different seeds. For only this task, our implementation makes use of top-k to construct the pseudo likulo-i distribution (lines 7-12 in Algorithm 1) due the lack of computational resources. Generations from all methods were limited to maximum of 20 new tokens.
random set of prompts
C
SUDOKU
The experiments were run on 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 al. (2019), 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 which the rows, columns and square are not unique.
D WARCRAFT SHORTEST PATH
The experiments were run server with an AMD EPYC 7313P 16-Core Processor @ 3.7GHz, NVIDIA RTX A6000, and 252 GB RAM. We used the best model trained by (Ahmed et al., 2023a). The model uses CNN-LSTM model for this task. Precisely, ResNet- 18 encodes the map to an embedding of dimension 128. An LSTM with 1 layer, and a hidden size 512 then predicts the next edge in the shortest path conditioned the input map and all previous edges. The constraint disallows any prediction not a valid path connecting the upper left and lower right vertices.
E BROADER IMPACT
The work presented in this paper has a significant potential for positive societal impact. Neuro- symbolic Al moves closer models whose behavior is trustworthy, explainable and fair. This extends to critical domains such as autonomous driving, medical diagnosis and financial planning 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 hard to reason about their behavior. We believe our proposed approach is step in right direction: 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 approach can be used to output non-toxic generations, can be used to output toxic and harmful generations.
16


Reviews:
[{"review_id": "QXeVfLxJ7D", "reviewer": "Reviewer_m1bs", "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.). \n\nIt 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.\n\nThis method is evaluated on two combinatorial/planning tasks and on a LLM detoxification task, achieving a high rate of constraint satisfcation.", "questions": "Please see \"weaknesses\" above.\n\nMinor:\n- Headings: There is not always consistent capitalisation (e.g., 3.1) and I don't understand the use of ellipsis in 3.4.\n- L225 \"structured\" -> \"structure\"\n- The name of the algorithm (GEN-C) does not appear until Section 5 (experiments). I suggest to introduce it earlier.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 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.\n- Clarity:\n  - 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.\n  - Thanks also for introducing notations in 2.1 but not overburdening the reader with excessive rigour.", "weaknesses": "- Experiments:\n  - 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.\n  - I do not find the results very convincing for a few reasons:\n    - Error bars are not reported => impossible to assess significance.\n    - Comparison with methods from prior work: only a trivial baseline is compared with for LLM detoxification, and only cold-prompted LLMs for Sudoku.\n  - 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. \n    - 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?\n  - Some questions on experiments:\n    - 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. \n    - 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?)\n- 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:\n  - Qin et al. runs Langevin in a continuous relaxation and I am unsure what is meant by \"high variance\".\n  - 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\"?\n  - 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?\n  - 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.\n\nOverall, the idea is very interesting and the paper has promise, but I cannot recommend acceptance without more thorough experiments and more difficult problem domains.", "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": "V8tMB2C4Wg", "reviewer": "Reviewer_6nQ2", "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.", "questions": "* How does the method handle cases where constraints are mutually exclusive or when no valid solution exists?\n* Could you provide more details about the choice of temperature parameter in the resampling step and its impact on generation quality?\n* What is the impact of the size of the initial sample set on the quality of the final generations?\n* How robust is the method to different types of logical constraints, particularly those that require long-range dependencies?\n* Could you elaborate on how the approach might be extended to handle soft constraints or preferences rather than just hard logical constraints?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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. \n* 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. \n* The paper is quite well written, with easy to follow explanations for the idea, along with examples (Figure 1). \n* The results are promising and indicate potential applicability to a variety of problems.", "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. \n* 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. \n* 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. \n* 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.", "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": "EcD9nOTZaI", "reviewer": "Reviewer_t2jb", "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.", "questions": "Sec 3.2: \n- 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?\n\nSec 3.3:\n- X and Y in Eq 6 should be bolded.\n- What is the \"contextualised probability?\"\n\nSec 3.4: \n- Shouldn't p_\\tilde y(y) in Eq 7 also depend on alpha?\n\nIn terms of the experiments, it would be good to give some indication of how the different methods fare in terms of computing cost.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "originality:\n- The method originally builds upon existing techniques in Bayesian inference and constraint circuits to tackle constrained generation with LLMs.\n- The presented approach seems to be a step change with respect to simpler greedy methods.\n\nquality:\n- The method is effective, leading to great performance.\n\nsignificance:\n- Constrained generation is a central problem with LLMs, so addressing it is essential.", "weaknesses": "The major issue with the paper is the lack of clarity in the notation and in presenting the method. In particular:\n- 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: \n\t- 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).\n\t- I believe rejection sampling of full completions targets the right conditional distribution \n\t- 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.\nThis 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.\n- 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. \n- The notation for the probabilistic quantities must be made more rigorous. For instance, \n\t- 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.\n\t- 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.", "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": "s8fOrkqTO5", "reviewer": "Reviewer_y7mC", "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.", "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.\n\n2. 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?\n\n3. 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical foundation is well-motivated, combining probabilistic sampling with logical constraints in a principled way.\n2. The implementation leverages efficient logical circuits for marginal computation, which is novel as far as I am aware.\n3. The experimental validation covers both practical (toxicity reduction) and formal (Sudoku) tasks\n4. The approach approximately maintains the model's distributional properties while enforcing constraints, unlike simpler masking approaches which do not attempt to preserve the 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.\n\n2. Computational Complexity. As far as I can tell:\n- The basic algorithm requires O(sequence_length × vocabulary_size) forward passes through the model\n- 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.\n\n3. Experimental Methodology:\nAs 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.\n\n4. Novelty and Attribution:\n- Section 3.2 appears to substantially reproduce content from the previous work [Neuro-Symbolic Entropy Regularization, UAI 2022] without appropriate attribution or differentiation.", "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)