Adaptable Logical Control for Large Language Models
Authors: Honghua Zhang
Po-Nien Kung
Masahiro Yoshida
Guy Van den Broeck
Nanyun Peng
Venue: NeurIPS 2024 poster (2024)
Keywords: Language Generation
Probabilistic Models
Probabilistic Methods
Large Language Models
Primary area: natural_language_processing

Abstract: Despite the success of Large Language Models (LLMs) on various tasks following human instructions, controlling model generation to follow strict constraints at inference time poses a persistent challenge. In this paper, we introduce Ctrl-G, a neuro-symbolic framework that enables tractable and adaptable control of LLM generation to follow logical constraints reliably. Ctrl-G combines any production-ready LLM with a Hidden Markov Model (HMM), guiding LLM outputs to adhere to logical constraints represented as deterministic finite automata. We show that Ctrl-G, when a TULU2-7B model is coupled with a 2B-parameter HMM, outperforms GPT4 in text editing: on the task of generating text insertions/continuations following logical constraints, our approach achieves over 30% higher satisfaction rate in human evaluation. When applied to medium-size language models (e.g., GPT2-large), Ctrl-G also beats its counterparts on standard benchmarks by large margins. Additionally, as a proof-of-concept study, we use Ctrl-G to assist LLM reasoning on the GSM benchmark, foreshadowing the application of Ctrl-G, as well as other constrained generation approaches, beyond traditional language generation tasks.

Adaptable Logical Control for Large Language Models
Honghua Zhang"
Po-Nien Kung" UCLA
Masahiro Yoshida UCLA Sony Group Corporation
UCLA #zhangg96ccs www.. edu
ponienkung@cs wuw.angg.s....l......e ucla.edu
masahhroyyoshhdbuuclla. edu
Guy Van den Broeck UCLA guyvdbêcs ucla. edu
Nanyun Peng
UCLA
violetpeng@es ucla.edaaee
Abstract
Despite the success of Large Language Models (LLMs) on various tasks following human instructions, controlling model generation to follow strict constraints inference time poses persistent challenge. In this paper, introduce Ctrl-G, a neuro-symbolic framework that enables tractable and adaptable control LLM gen- eration to follow logical constraints reliably. Ctrl-G combines any production-ready LLM with a Hidden Markov Model (HMM), guiding LLM outputs to adhere to logical constraints represented as deterministic finite automata. We show that Ctrl- G, when TULU2-7B model coupled with 2B 2B-parameter HMM, outperforms GPT4 in text editing: the task of generating text insertionn/cconiinutions follow- ing logical constraints, our approach achieves over 30% higher satisfaction rate human evaluation. When applied to medium-size language models (e.g., GPT2- large), Ctrl-G also beats its counterparts on standard benchmarks by large margins. Additionally, as a proof-of-concept study, use Ctrl-G assist LLM reasoning on the GSM benchmark, foreshadowing the application of Ctrl-G, as well as other constrained generation approaches, beyond traditional language generation tasks.
Introduction
Large language models (LLMs) have achieved remarkable performance on wide range of challenging language gen- eration tasks including translation [4, 48, 41], summariza- tion [49], and open-domain creative generation [45, 38), Nevertheless, many downstream applications benefit from fine-grained control of LLMs to follow logical constraints, e.g., avoid using bad words for detoxification [9, 1] or inserting text that is coherent with contexts for document revision [16]. Despite the recent advancement of LLM finetuning techniques such as instruction-tuming [5, 42, 35] and preference optimization [28, 33), LLMs still fail to reliably follow logical constraints [37, 20).
conditioning on logical constraints...
2. constraint specification)
distill
LLM
HMM
DFA
3. inference-time guidance
outputs satisfying the constraints
Figure Ctrl-G pipeline; both the LLM and the HMM are frozen once trained.
The major difficulty achieving constrained generation from LLMs lies the intractability of conditioning LLMs on logical constraints [34]. One recently proposed framework called GeLaTo [47] uses tractable generative models, which can be conditioned on logical constraints efficiently, to guide autoregressive generation from LLMs. Though GeL.aTo guarantees that the logical constraints
Egqual contributions.
Work done at UCLA visiting scholar.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

code!
User: given the following context, generate infilling text for [BLANK] using key phrases "alien mathership", "far from over"; generated oeerrrgeeeeaee text must contain 25 25--3 30 words.
from CtrlG inport
"First they' defeated small squad of aliens, then larger fleet of their ships. Eventually they's 've even managed to take down the alien mothership. But their problems are from over There are humans left, and despite their magical power, their numbers are getting fewer."
prefix "First they defeated suffix "are few hunons left
dfa_list = "far from over"), DFA.word_count(25, 30),
of nothership",
"First they've defeated small squad (BLAM [BLA are few humans left, and despite their magical power, thair numbers are getting fewer."
]
dfa DFA.
(tri@logitsProcessor(
dfa, hmn, prefix, suffix) Lun.generateClogits. htapee/coottssppceesoo-pppp processor-1p)
Figure 2: An example usage of Ctrl-G for text insertion with multiple constraints.
will be satisfied, it only works for the keyword-inclusion constraint. Significantly generalizing the GelaaTo framework, we propose Ctrl-G (shorthand for controllable generation while mimicking the keyboard shortcuts Ctrl-C and Ctrl-V) for reliable, scalable and adaptable control of LLMs to follow logical constraints. Ctrl-G consists of three major steps (see Fig. 1): (1) distillation: given LLM, we distill a Hidden Markov Model as its white-box approximation; (2) constraint specification: we construct a deterministic finite automaton (DFA) to (compactly) represent the desired logical constraint; (3) inference: we condition the HMM on the DFA-specified constraint and compute this conditional probability to steer LLM generation towards satisfying the constraint.
Ctrl-G² has three major advantages compared to its counterparts: (1) the desired logical constraints guaranteed to be satisfied [47]; (2) once have the distilled HMM, it can be applied arbitrary constraints without retraining; (3) Ctrl-G works for any constraints specified as DFAs, which can be casily constructed for various applications by leveraging existing algorithms.
We evaluate Ctrl-G on the task of text editing: in the domain of story writing, we evaluate models' ability to generate suggestions for text insertions/contiiuation under combinations of logical con- straints (e.g. keyphrase inclusion and length control; see Fig. 2). Human evaluation shows that Ctrl-G, where a TULU2-7B model [13] is combined with 2B 2B-parameter HMM, outperforms prominent LLMs including GPT3.5 and GPT4 [27] by over 30% in overall satisfaction rate (i.e., percentage of the generated text that not only fluent but also satisfies the constraints). We note that as the constraints become more complex, while the generation quality of GPT4 declines, Ctrl-G consistently produces high-quality text, highlighting its strong generalizability complex constraints. Even when no constraint is present, Ctrl-G still matches with the generation quality of GPT4 in text insertion.
In addition, we demonstrate the extensive adaptability of Ctrl-G on two commonly used benchmarks: commonsense generation [18] and text infilling [7]. When applied to variants of the GPT2 models, Ctrl-G outperforms prior constrained generation approaches by producing outputs of substantially higher quality while achieving 100% constraint satisfaction.
To further explore the potential of Ctrl-G, proof-of-concept, we conduct an empirical study on the Grade School Math (GSM) benchmark [6]: here, we use Ctrl-G to assist the L.LM reasoning process by enforcing keyphrase-inclusion constraints. Performance improvement suggests the potential of Ctrl-G in applications of a scope broader than the traditional constrained generation tasks.
2 Preliminaries
In this section, we briefly summarize the background for basics for Hidden Markov Models. Notations introduced here will be used throughout the paper.
generation and the
Constrained generation For simplicity, we assume that the lengths of token sequences generated by LLMs are always bounded by some number n and denote the LLM distribution as Pmo (0 1mm) Given
Coode availahle at https: hatt::///itttt comm/joehuannf/Crr)) 'Sequences padded to the length of n tokens.
2

---

logical constraint a, our goal is to generate from (1m aa), which decomposes autoregressively:
Pim (1 a) = II pim(1s (ee,,) where pan(ar (ee,, a) x Pan [x))) Pin(ex Wt, T<t);
that is, given that we have generated the first ( - tokens Zet., want to generate the next token 2t from (in( (ee)) Pim [e, Tet). The first term Pim( (ic)) is just the next-token distribution of the LLM, but the marginal probability Pm Zt; Z<t), which characterizes how likely the constraint
a will be satisfied in the future, cannot be efficiently computed; specifically,
Pm ze, 21) E min satisfies p( It, F<t);
that is, we need to marginalize over all possible future sequences Zyz such that, together with r<t. satisfy a. For example, say a is the constraint that the phrase "in the park" must appear at the end of the generated text; to compute the desired marginal probability, need to enumerate over all future token sequences with this phrase at the end, and there are exponentially many of them.
Prior work To solve the problem of constrained generation, one line of work proposes search- based decoding algorithms like NeuroLogic Decoding [22, 21J, which explicitly performs heuristic search to find hroh-probbbblityy token sequences that would (partially) satisfy the logical constraint; however such methods scale poorly because the search space grows exponentially with respect to the sequence length. The other line of works including GeDi [15], FUDGE [44] and NADO [25] train auxiliary neural classifiers to approximate the intractable term Pim (a Øt, T<ee); however, they do not guarantee that the constraints will be satisfied and the classifiers need to be retrained for different constraints.
Some other methods use approximate inference techniques (c.g., sequential Monte Carlo sampling) to approximate the intractable conditional distributions [30, 11, 17], which provide guarantee the convergence rate and often suffer from the high-varianc" of sampling.
From GeLaTT to Ctrl-G A recent framework called GeLaTo [47] uses tractable generative models, particular, Hidden Markov Models (HMMs), to guide LLM generation to satisfy the given logical constraints. Specifically, GeLaTo first (1) distills an HMM Phmm (1)m) to approximate the LLM distribution Pin 11nn) and then (2) computes Phmm (a [t; T<t() as an approximation for Pim (a (x, x Compared to its counterparts, GeLaTo guarantees that the constraints will be satisfied. Nevertheless, two major questions remain unanswered, limiting its downstream applications:
GeLaTo only handles the keyword deyword-inclusion constraint and it is unclear whether Phmm (al z++1, T1:a) can be tractably computed for other logical constraints; despite the success of GeLa'To unclear whether the assumption Panm (a I=ge)= R Pim(cx (a xge)) would still hold for the more recent LLMs (e.g., Llama2), which have over 100 times more parameters.
language models at the scale of 0.1 billion parameters, it is
We propose Ctrl-G as a generalization of GeLaTo and give positive answers to both questions.
Hidden Markov Models A Hidden Markov Model (HMM) [32] represents joint probability distribution over n observed variables ii.n and n hidden variables = Specifically, for language modeling, 24 represents the token at position and is the corresponding hidden state; 2, takes values in (1,2.... h), where h is the number of hidden states. An HMM models the joint distribution:
p(I 21:n) p(x1 21) p(21) II 2.) p(2, 24-1);
in particular, the parameters of an HMM are given by the initial probability p( p(21), the emission matrix p(z, (æz) and the transition matrix p(*++1 kz);: the number of parameters of HMMs grows quadratically with respect to h. To perform inference on HMMs efficiently, we leverage the Markov property: p(Z>11 x<t) =p{2 24). For example, we can efficiently compute p(xre:) Σ,, p(x 21) by the following recurrence relation, referred as the forward algorithm [32]:
p(Eg),)) -ei)=Enss Eis p( 2)) p((e 2--1) ((
3 Tractable probabilistie reasoning over logical constraints
The Ctrl-G pipeline consists of three steps (Fig. 1): (1) distillation: we train an HMM on samples drawn from the LLM to minimize their KL-divergenee; (2) constraint specification: construct
3

---

initial state
accept state(s)
Accepted by the DFA:
dfa_graph "edges": [ f"gets"),
the weather (ett cold in winter
ge "gets"
"gets"
IA, "gets"),
A
B
cc
[B, A, *"gets" or "cold"), IB, "gets"), IB, C, "cold"),
"gets"
"cold"
B
Rejected by the DFA: the weather gets warm in wnnter
IC, C s),
initial state": "accept_states"" (C),
# "gets" or "cold"
A
(a) DFA graph.
(b) Examples of DFA state transition.
(c) Specifying DEA for Ctrl-G
Figure 3: Example of a DFA representing the logical constraint that the phrase "gets cold" must appear in the generated text along with pseudo-code for representing this DFA in Ctrl-G.
(compact) deterministic finite automaton (DFA) M representing the desired logical constraint a (i.e., MM accepts 2m.m if and only if 21.m satisfies o);; (3) inference: for each step of the autoregressive generation from the LLM,, we compute Phmm Fe, (eet) as an approximation for Pmn Ty, vet) and then sample the next token from
geat-g V< a:) Pim( xiee) Pumm (a It, Fct);
here, given that a is represented as M,
Pa Te; Fett)
Σ Bot s.t. M accepts mim
Phmm (Tzt Ft, Tet)
For step (1) (distillation) we follow the procedure proposed by [47], and we describe step (2) and step (3) in Sec. 3.1 and See. 3.2, respectively. In the end of this section, we briefly discuss the distinction between pure logical reasoning and probabilistic reasoning over constraints.
3.1 Logical constraints as DFAS
Deterministic finite automata (DFAs) [24, 31, 10] are computation models that accept reject some given strings. Figure 3a shows an example DFA encoding the constraint that the phrase "gets cold" must appear: accepts all strings containing this phrase and rejects the others. The DFA consists of 3 different states labeled A, B and C,, where A is the initial state and C' an accept state. The states are connected by edges marked with sets of words (tokens, to be precise), which fully specify the transition function of the DFA. A DFA decides whether given string satisfies the constraint by consuming it left-to-right while transitioning from state to state accordingly; in the end, the DFA accepts the string if it is in accept state. See Figure 3b for example.
Definition 3.1. A deterministic finite automaton (DFA) is a tuple M= (Q, Σ, 8, go. F). where Q is a finite set of states, Σ finite set of symbols (i.e., tokens of an LLM), 8 :Qx2i - Q transition function, Yu an initial state, and F C Q a set of accept states. A string of tokens w1 W/2 Wn, is accepted by M if there exists a sequence of states qo: 91 ... In s.t. 8(9;, W;-1) 9-11 for 1 < n. In F.
One question naturally arises: how can we come up with DFA representations for logical constraints? We first note that in the real world, we can always assume that the lengths of the generated token sequences are bounded by a constant; hence DFAS can represent any logical constraints defined on this bounded set and the important question is whether we can do this efficiently. For many common logical constraints, we can efficiently construct their DFA representations via existing algorithms. For example, given string consisting of n tokens, to encode the constraint that the string must appear, we can construct a DFA size O(n) by adapting the well-known
Morris-Pratt Pratt (KMP) algorithm [14] for string matching (e.g., Fig. 3a). One can also easily specify compositional logical constraints via DFAs by taking their intersection (logical and), union (logical or). complement (logical negation) concatenation, which we illustrate throughout the rest of this paper.
3.2
An efficient algorithm for marginalizing HMMs over DFAS
Now assume that we have a constraint a encoded as DFA M with k states (1,,,, and m edges, and we are given distilled HMM with h hidden states. To sample the next token from Eq. 1, we need to compute Phmm (ax Fe, Fic)), which the marginal probability over all strings accepted by M (see Eq. 2). In the following, we describe tractable algorithm for computing this probability.

---

In autoregressive generation, M starts from the initial state and transitions according to the transition function as each new token generated; we denote the state of M after sampling the first tokens J.st 8t- In addition, we use the uppercase S. to denote the random variable representing the state of M after sampling the first tokens: e.g., Sn E F denotes the event that the token sequence 1im accepted by M. Dropping the subscript "hmm" from Phmm (a: Fe, Feat), we compute
p(a (e) p(S,, E F<i) p(S,, F
The denominator x<z), can be easily computed by the forward algorithm [32]; so we compute
p(S, F,a, xe() = Σ p(S, E Ze, Tea) p(zz, (<c))
(3)
Σ p(S. 8t) ((,,, Ie, Xet)
the first step follows from the law of total probability and the second step follows from the Markov properties of HMMs and DFAs, well as the fact that is fully determined by zig-- Again, the term p(2,, Ft, Tc)) can be computed by the forward algorithm and we reduce the problem to computing the boxed term. We compute pSS, E following recurrence relation:
F Ze, 8t) for all 1 I S n, S 2 S h and 1 S 8, Sh via the
p(S, EF Ze, 8t)
= Σ p(20+1 2x)
Σ Re41
p(Sn EF
24 21,188411
Σ p(1+41 2o41); (4) (edge((().))))
1
here edge(#t; &t; 8++1):= (w 5(t, = denotes the of tokens wo that transition M from 8t to 8t-1- The base case of the recurrence relation is given by p(S,, F 12,8,)) 11 if 8 E F and O otherwise. We refer readers the appendix for its derivation. Algorithm shows the pseudo-code for sampling from Peut-g (Zim) a) autoregressively, using the recurrence relations above.
Runtime analysis of Algorithm 1. To sample from Ctrl-G, the computation overhead (i.e. in addition to the LLM inference cost) is dominated by the computation of p(S,, F Zt; 8t) for all 4, 2 and 8 shown in Eq. 4. Since Ex..; Eodge(s.. p(z++1 2441) does not depend on and cache their values, resulting one-time cost of Ommh[1]) Then, note that for 8t, we only need to consider the 8t+1 where edge(s;, $t+1) A 0. Hence, fixing t and 2t, when we compute p(S, F 2t, st) for all 1 15 S, we only need to (1) enumerate through S 24+1 S Kh and (2) for each 2141, we only need to go through each edge exactly once. There are m edges in total, so it follows that the cost (n h m) = O(nmh²)) The total time complexity is (mmmh++mhps which simplifies to O (mmhh? given that [ < nh in practice.
precompute
Theorem 3.2. Given a constraint a represented as a DFA with m edges and an HMM with h hidden states, the time complexity for sampling a sequence of tokens from Penrtg (Fimm (
| a.) is (nmh²).
3.3 Logical reasoning vs. probabilistic reasoning
Some recent work well as open source projects have proposed to use regular expressions (regex) to achieve structured generation from LLMs [23, 43, 50]. Regex are equivalent to DFAs in terms of the logical constraints they represent, but the aforementioned approaches only perform pure logical reasoning over regex, which is not suitable for many constrained generation tasks. For example, consider the task of generating sentence that ends with the phrase in the park":
Algorithm 1: Ctrl-G: sampling tokens
Input: DFA M = (Q, Σ, do.0.
HMM qı LLM q2.
for from to 1 do pre-compute (a | by Eq. 4. end for
initialize su : Qu. 21.u := for from 1 to n do
compute qı (ax (.),, m by Eq. 3.
sample x, X q
(t) qa (Ir see)
guidance [23] (logical reasoning): silhouette of suspected ... heavily secured.in the park
update Ig := @ d
transition M from s to 8 80:=0(0)11
end for return Fi.m
Ctrl-G (probabilistic reasoning): man and woman are walking in the park
5

---

Table CommonGen results. All methods are applied to the GPT2-large model.
BLEU-4
ROUGE-L
CIDEr
SPICE
Constraint
dev
test
dev
Test
dev
test
dev
test
dev
test
supervised base models trained with full supervision
FUDGE
24.6
40.4
47.0%
A A
28.2
43.4
15.2
30.8
98.8%
NADO
30.8
44.4
16.1
32.0
88.8%
GeLaToo 34.0
34.1
46.2
45.9
17.2
17.5
32.2
33.5
100.0%
100.0% %
CtrlGG
35.1
34,4
46.7
46.4
17.4
17.6
32.7
33.3
100.0%
100.0%
unsupervised base models not trained with keywords as supervision
A
28.6
44.3
15.6
29.6
NADO
26.2
GeLaTo
30.3
29.0
44.3
43.8
15.6
15.5
30.2
30.3
100.0%
100.0%
Ctrl-G 32.1
31.5
45.2
44.8
16.0
16.2
30.8
31.2
100.0%
100.0%
Even though both generations end with " "in the park", is clear that the output from guidance is desirable as it forcefully appends the phrase to some irrelevant text. The reason that guidance, by performing pure logical reasoning, only discard the next tokens z; that would make a unsatisfiable, while the probabilities of the other next tokens remain unchanged; in contrast, Ctrl-G performs probabilistic reasoning by estimating Pim (a Zt, (xx)) i.c., we estimate how likely each next token Ie would eventually lead to being satisfied. Ctrl-G subsumes the other approaches in the sense that if we set Pumm (a Ze; x<te) 1 for all non-zero values, that is, we remove all probabilistic information, then it degenerates to pure logical reasoning.
Evaluating Ctrl-G on constrained generation benchmarks
4.1 Commonsense Generation
Following prior work [21, 25], we first evaluate Ctrl-G on the Commonsene Generation (Common- Gen) benchmark [18]. Each test example of CommonGen provides 3 to 5 concepts (keywords) as input and the goal is to generate a natural sentence that incorporates all keywords, allowing for any of their inflections. For example, given "car", "snow" and "drive" as concepts, both "a man drives car on snow covered road" and "the car drove through the snow" are considered acceptable.
DFA construction For CommonGen, given one keyword, say, "snow", we adapt the Aho- Corasick algorithm [2] construct DFA enforcing the constraint that least one of its inflections (e.g.. "snow", "snowing" or "snowy") must appear. To encode the constraint that multiple keywords must appear, we can simply take the intersection of the individual DFAS [10]; see appendix for example.
Experiments & results We use the GPT2-large checkpoint (only finetuned for domain adaptation) released by [47] our base model and we follow the same pipeline distill an HMM with 32768 hidden states: we sample 4M examples from the base model and train the HMM for 40 EM steps, each consisting of 100K examples. We compare Ctrl-G against FUDGE [44], NADO [25], NeuroLogic A *esque decoding [21] and GeLaTo [47]; GeLaTo uses the same base model as Ctrl-G. The results are summarized in Table 1, where the Constraint column shows the percentage of the outputs containing all concepts. Compared to all baselines, Ctrl-G achieves not only 100% constraint satisfaction rate but also substantially higher generation quality measured by automatic evaluation metrics [29, 19, 40, 3].
Runtime comparison From an algorithmic perspective, GeLaTo only handles keyword constraints hence it is special case of Ctrl-G. Nevertheless, Ctrl-G also runs significantly faster than GoL as shown in Table 2. The GeLaTo implementation only tensorizes the HMM inference component, while the component that reasons about the constraints runs sequentially representing DFAS as (weighted) adjacency matrices, Ctrl-G tensorizes the inference procedure for both HMMs and DFAs and runs GPUs with full parallelization. Besides, both GeLaTo and Ctrl-G runs significantly faster than A *esque, which explicitly performs heuristic search.
CPU. In contrast, by
Generalization to more keywords To evaluate the generalization performance of Ctrl-G, we construct test examples containing 6 to 9 concepts (CommonGen+):: we randomly select 100 examples with 5 concepts from the dev split of CommonGen, and then augment them with additional keywords

---

Table Time (seconds) of generating one example on CommonGen (dev); # of HMM hidden states shown in brackets. Beam sizes used by A Aeeqque GeLaTo and Ctrl-G are 20, 128 and 128.
unsupervised
supervised
of concepts
5
Pesque
472.9
542.5
613.9
8.5
11.4
GeLaTo [4096]
69.8+32.3
37.9
143.0=4444
49.8
127.6=+30.4 30.7
Ctrl-G [4096]
1.1
1.9+
1.6
1.2+00.4
2.3
5.7
Ctrl-G [32768]
4.1
9.0+22.0
22.3+5.4
4.7
11.0
27.6++8.3
45
100
ROUGE-L
Constraint
75
BLFU4
50
RUDGE
Neurol ogic
25
7
concepts
concepts
concepts
(a) BLEU-4
(b) ROUGE-L
(c) Constraint satisfaction rate
Figure 4: CommonGen+ results; Ctrl-G generalizes well on test examples with more than 5 concepts.
sampled from their reference sentences. As shown in Fig. 4, Ctrl-G achieves 100% constraint satisfaction rate while preserving high generation quality across all settings.
4.2
Text infilling
We also evaluate Ctrl-G on a text infilling benchmark [7] constructed from the ROC stories corpus [26]. Each test example consists of a short story with some fragments masked out, each of a specified granularity; the goal to fill the masks. Here an example: "Jill wanted knit her [WORD] sweater. [SENTENCE] She finished [NGRAM] for her boyfriend's 's birthday. Jill was [WORD]."
DFA construction CommmonGen. We can view the non-masked parts, e.g., "Jill wanted to knit her" and "a sweater." from the example above, keyphrases, and the task reduces to generating piece of text such that all keyphrases appear in the given order. In this setting, given text fragments, we first construct Mi, ................................ Mr using the KMP algorithm [14]; then, we concatenate them represent the constraint that they must appear in the given order. Though DFA concatenation is intractable in general [46], we observe that the KMP DFAS can actually be concatenated in linear time. See appendix for details.
The underlying logical constraint for the task of text infilling is similar that of
Table 3: Text infilling results (BLEU--)ROUF--L) across different masking ratios.
BLEU-4
ROUGE-L
mask ratio
13%
13%
21%
32%
ILM
85.2:10.1
76.3=
64.3:10.1
53.8=10.1
90.9-10.2
84.9:10.3
76.3:10.4
68.4:10.5
Ctrl-G
85.4
77.5
66.5
57.2
90.6
85.2
77.0
69.8
diff'
+0.2
+1.2
+2.2
+3.4
0.3
+0.3
+0.7
+1.4
Experiments & results We use the GPT2-small checkpoint (only finetuned for domain adaptation with no supervision on the task of text infilling) released by [7] as the base model for Ctrl-G and compare against the ILM model, which a GPT2-small model trained on this text infilling benchmark with full supervision. By applying the mask function from [7], we construct 4 test sets with different masking ratios (i.e., different percentage of masked characters) by changing the hyper-parameters. We measure the BLEU and ROUGE scores of the completed stories (i.e., including both the masked and unmasked parts) with respect to the original stories. The ILM model adopts sampling for decoding, so we run the ILM inference for 10 times to report the means and standard deviations. The results are summarized Table 3. Based on [7], ILM trained on distribution with masking ratio of approximately 15%, explaining why it achieves the best performance on the test set with 13% masking
7

---

ratio. Note that the performance gap between Ctrl-G and ILM improves almost monotonically as the masking ratio mereases, again illustrating the strong generalization performance of Ctrl-G.
5 Scaling up Ctrl-G for interactive text editing
Human-AI collaborative writing has been a long studied topic in the Human- Cluman-Computer Interac- tion (HCI) community [12, 36]. One prior work [16] proposed CoAuthor, graphical user interface for querying LLMs to generate continuationn/msertion suggestions in arbitrary positions of doc- ument. However, when using CoAuthor to ask for LLM suggestions, users are unable to specify their preferences. We propose to extend the CoAuthor system by allowing users to have fine-grained control over the suggestions generated by L.LMs: for example, users control the topie of the generated content by instructing L.MMs to incorporate certain keyphrases, and they can also ask for more concise/detailed suggestions by controlling their lengths. For this application, apply Ctrl-G to the TULU2-7B model and compare against prominent LLMs including GPT3.5 and GPT4.
5.1 Experiment setup
Dataset construction We construct an evaluation dataset consisting of 800 test examples, each based on one story passage extracted from the CoAuthor dataset [16]. These stories are jointly written by humans and the -11..5tturb--istruee model, falling under ten different topics. For each story, we randomly split it into prefix, infix and suffix; we mask out the infix and view it as a gold reference. We consider two scenarios when evaluating the models: continuation and insertion. For continuation, we only provide prefix to the model, and the model is supposed to generate one suggestion for continuation; for insertion, we provide both prefix and suffix to the model and the model is required to generate a piece text that is coherent with both prefix and suffix. Additionally, we consider imposing combinations of the following two constraints:
Keyphrase: suggestions should include one to three given keyphrases. Word Count: suggestions should contain a to words where 1 I 3b3
We consider all combinations of the following settings: insertion or continuation, w/ or w/o keyphrase constraint, w/ or w/o word-count constraint, resulting in 8 different settings. For cach setting, sample 100 stories from the CoAuthor dataset and create 100 test examples (e.g., Fig. 2).
Scaling up Ctrl-G We adopt the TULU2-7B [13] model, which is an instruction-tuned variant of the Llama2 [39] model with 7 billion parameters, as the base model for Ctrl-G. We further finetune the base model on 3000 examples extracted from the WritingPrompt dataset [8] for the task of text continuation, following the prompt "Continue the given text:" along with a story prefix. After finetuning, we use the same prompt to sample 5 million examples from the base model and train an HMM with 32768 hidden states (approx. billion parameters). Note that for the task of text insertion, the base model only sees the prefix, while the suffix is incorporated i... the HMM is fully responsible for guiding the base model to generate a piece of text that will be coherent with the suffix. For generation, sample 128 examples from Petr-g with temperature 0.7 and pick the one with the highest likelihood given by the base model as the final output.
part of the constraint a;
Baselines We compare Ctrl-G against prominent LLMs including the GPT3.5 model and the GPT4 model. To generate output from the GPT models, we adopt the prompt provided by the OpenAl docu- mentation for text insertion/continuation with constraints specified in the instructions. See appendix for the specific prompt templates. In addition to the GPT models, we also compare Ctrl-G against pure instruction-tuning specifically, we construct 1000 training examples for the task of text insertion based on the WritingPrompt datasct and further finetune the TULU2-7B model for text insertion, TEXT][
following the prompt "Generate the text at /INSERT TEXT] tag/Vn[prefix/[NSS For all baselines, for the purpose of fair comparison, we generate 128 samples for each test example and select the one with the highest probability as the final output.
Human evaluation To evaluate the quality of the generated outputs, we conduct human evaluation through the Amazon Mechanical Turk (MTurkk platform. For each test example, we generate the outputs from TULU2 (prompt only), GPT3.5, GPT4 and Ctrl-G respectively, and ask annotators to rate their quality on scale from I to 5. For each test example, we present the generated outputs from all models, along with their original context, to the annotators side-by-side and ask them to evaluate their quality; specifically, we ask the annotators to answer the following questions:
8

---

Table 4: Evaluation results of interactive text editing. K&W indicates that the model should adhere to both keyphrase (K) and word count (W) constraints simultaneously. We present the human evaluation score (Quality), constraint success rate (Success), and overall satisfaction rate (Overall), which represents the proportion of examples meeting logical constraints with Quality score above 3.
Continuation
Insertion
None
K&W
Arg.
None
W
K& W
Avg.
Quality
TULU2
3.80
3.77
3.87
3.88
3.83
2.68
2.64
2.78
2.74
2.71
GPT3.5
4.40
4.32
4.44
4.36
4.38
2.27
2.22
2.27
2.31
2.27
GPT4
4.48
4.44
4.44
4.26
4.40
3.79
3.33
3.53
3,10
3,44
CurlGG
4.13
3.98
4.27
3.96
4.08
3.77
3.56
3.73
3,59
3.67
Success
TULU2
35%
33%
1%
23%
12%
20%
3%
12%
GPT3.5
36%
62%
31%
43%
22%
54%
10%
29%
GPT4
56%
55%
59%
57%
20%
27%
36%
Cul-G
100%
100%
100%
100%
100%
100 %
100 %
100%
Overall
TULU2
30%
31%
1%
21% %
7%
10%
1%
6%
GPT3.5
36%
62%
31%
43%
0%
5%
2%
2%
GPT4
56%
55%
57%
56%
41%
17%
14%
24%
Ctrl-G
89%
97%
90%
92 %
76%
78%
82 %
79%
Ql. is the paragraph coherent and grammatically correct?
Q2. is the paragraph consistent and semantically reasonable?
Q3. based your answers Q1&Q2, what your rating for the overall quality?
Note that we only ask human annotators to evaluate the coherency and fluency the generated text and they are not aware of the required logical constraints. We ask three annotators to evaluate each output and compute their inter-annotator agreement score. See appendix for more details.
5.2 Results
The evaluation results are summarized in Table 4, showing the quality score, constraint satisfaction rate, and overall satisfaction rate. In particular, the overall satisfaction rate denotes the percentage of test examples that (1) satisfy the constraint and (2) attain average quality scores > 3. For continuation, in terms of generation quality, GPT4 beats all other models; this is no surprise, as gigantic models like GPT3.5 (with 175B parameters) and GPT4 have significant advantage generating high quality text continuations. However, despite the high generation quality, the success rates for GPT3.5 and GPT4 are relatively low (the highest 59%) while Ctrl-G always satisfy the specified constraints; hence in terms of the overall satisfaction rate, Ctrl-G beats all baselines by large margins when constraints are present. For the case of insertion, the "implicit" soft constraint here is that the generated parts need to be coherent with the given suffix, which is challenging for autoregressive models; in this case, in terms of pure generation quality, Ctrl-G beats/matches with the performance of GPT4 in all settings; for insertion, the success rate of all baselines becomes even lower compared to continuation, while Ctrl-G achieves 100% success rate in all settings. again beats all baselines. The other observation is that the generation quality of GPT4 decreases as the logical constraints become more complex, while the generation quality of Ctrl-G stays relatively consistent across all settings, demonstrating strong generalization performance.
terms of overall satisfaction rate, Ctrl-G
5.3 Runtime analysis
We provide an empirical analysis on the runtime of Ctrl-G, with TULU2-7B as the base model. In addition to the computation cost of the base LLM, the major cost of Ctrl-G lies in the computation of Phom (ax < 1), with a time complexity of O(nmh²) (Thm. 3.2); here n is the maximum sequence length, is the size (i.e. # of edges) of the DFA, and h is the number HMM hidden states. First, fixing the sequence length we change the size of the DFA and verify that the time for generating each token scales roughly linearly with respect to the DFA size (Fig. left). Then, fixing a DFA of
averaage ratings given to Q3 in human evaluation; appendix for complete results.

---

1/100
1/100
Cti-G (HMM--086)
TULU2-78
time/token (seconds)
CtriGG (HMM-332
time/token //ok//kkennnn (seconds)
Ctrl-G (HMM-32768 TULU2-7B)
3/400
Jamanin
3/400
1|
1/200
1/200
1/400
1/400
0
450
900
1350
1800
0 120 240 360
480
600
DFA size
sequence length
Figure 5: Runtime analysis of Ctrl-G; Left: the generation time per token scales linearly w/ respect to DFA size. Right: the generation time per token stays constant w/ respect to sequence length.
size 900, we change the sequence length n and measure the time for generating each token from Ctrl-G and the base L.M respectively. The gap between the two lines in Fig. 5 (right) shows the computation overhead introduced by Ctrl-G, which stays constant with respect the sequence length. On the other hand, however, due to the attention mechanism, the time for generating each token from the base LLM scales linearly with respect to n. Hence, the computation cost will be dominated by the base model when generating long sequences. The runtime measurements are conducted on an NVIDIA-A100 GPU with 80GB memory.
Perspectives: improving LLM reasoning abilities via logical constraints
In this section, we explore the use of Ctrl-G on a non-traditional constrained generation application. As a case study, we apply Ctrl-G assist the reasoning process of the TULU2-7B model on the grade school math (GSM) benchmark. As we naively apply chain-of-thougee prompting, we observe that for 293 out of the 1319 test examples, the model fails to use all numbers provided in the problem statement; this leads to much lower accuracy on the 293 examples compare to that on the complete test set. For such 293 test examples, we apply Ctrl-G to the TULU2-7B model to enforce the constraint that all numbers from the problem statement must be generated as part of the chain-of of-thhught reasoning process. We sample 16 outputs from the TULU2-78 7B model and do majority vote; with Ctrl-G, the model achieves 28.3% % accuracy, which is 3.4% higher than the marjoity-vote accuracy without Ctrl-G.
Our proof-off-concee study on the GSM benchmark illustrates one potential use case of Ctrl-G beyond traditional language generation tasks. Specifically, we demonstrate the possibility of "approximating" soft control (i.c., better reasoning ability in this setting) via logical constraints. For future work, we motivate the application of Ctrl-G, as well other constrained generation approaches, on broader scope of downstream tasks: e.g., helping LLM detoxification by conditioning on set of bad words/phrases not appearing, improving the reasoning ability of LLMs by conditioning on generating longer reasoning sequences, and controlling the topic of the generated content by conditioning on the occurrence of certain keyphrases.
7 Conclusion
We propose Ctrl-G, a versatile framework that enables reliable and flexible inference-ting time control of LLMs; given any production-ready LLM, Ctrl-G distills an HMM as its approximation and uses it to guide the LLM to generate outputs that comply with any logical constraints specified as DFAs. We show that Ctrl-G, where a 1B-parameter TÚLU2 model is combined with a 2B 2B-parameter HMM, beats significantly larger LLMs like GPT4 on the task of generating text insertions/continuatio with logical constraints. On commonly used constrained generation benchmarks like CommonGen Ctrl-G beats other constrained generation approaches, as well as supervised training, by large margins. In addition to the dominant paradigm of prompt engineering, our work opens up new avenues for achieving tractable, reliable and fine-graines inference-time control of LLMs.
10

---

Acknowledgments
This work was funded in part by the DARPA ANSR program under award FA8750-23-2-0004 the DARPA PTG Program under award HROOI 12220005, NSF grant #1I8-1943641, NSF CAREER Award #2339766, and AFOSR MURI via grant #FA9550-22-1-0386
References
[1] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. A pseudo-semantic loss for autoregressive models with logical constraints. Advances in Neural Information Processing Systems, 36, 2024.
[2] Alfred V Aho and Margaret J Corasick. Efficient string matching: aid bibliographic search. Communications of the ACM, 18(6))333-340, 1975.
[3] Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. Spice: Semantic propositional image caption evaluation. In European Conference on Computer Vision (ECCV). Springer, 2016.
[4] Yujin Back, Koanho Lee, Dayeon Ki, Hyoung-Gyu Lee, Cheonbok Park, and Jaegul Choo. Towards accurate translation via semantically appropriate application of lexical constraints. arXiv preprint arXiv:2306. 0003306.22000 /0089, 2023.
[5] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. Scaling instruction-finetuee language models, 2022.
[6] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jeny Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers solve math word problems, 2021.
[7] Chris Donahue, Mina Lee, and Percy Liang. Enabling language models fill in the blanks. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2492 2492-2501, 2020.
[8] Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation, 2018
[9] Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. RealToxi- cityPrompts: Evaluating neural toxic degeneration in language models. In Trevor Cohn, Yulan He, and Yang Liu, editors, Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3356-3369, Online, November 2020. Association for Computational Linguistics.
[10] John Hopcroft, Rajeev Motwani, Rotwani, and Jeffrey D Ullman. Introduction to automata theory. languages and computability, 2000.
[11] Edward 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.
[12] Daphne Ippolito, Ann Yuan, Andy Coenen, and Sehmon Burnam. Creative writing with an pi-powered writing assistant: Perspectives from professional writers. arXiv preprint vrXiv:2211.05030 2022.
[13] Hamish Ivison, Yizhong Wang, Valentina Pyatkin, Nathan Lambert, Matthew Peters, Pradeep Dasigi, Joel Jang, David Wadden, Noah A Smith, Iz Beltagy, et al. Camels in changing climate: Enhancing Im adaptation with tulu arXiv preprint arXiv:2311.10702 2023.
[14] Donald E Knuth, James H Morris, Jr, and Vaughan Pratt. Fast pattern matching in strings. SIAM journal computing, 6(2):323-350) 1977.

---

[15] 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, pages 4952, 2021.
[16] Mina Lee, Percy Liang, and Qian Yang. Coauthor: Designing human-ai collaborative writing dataset for exploring language model capabilities. In CHI Conference on Human Factors in Computing Systems, CHI 22. ACM, April 2022.
[17] Alexander Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash K Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs. arXiv preprint arXiv:2306.03300 2023.
[18] Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. CommonGen: A constrained text generation challenge for generative commonsense reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1823 1840, Online, November 2020. Association for Computational Linguistics.
[19] Chin- Lin and Eduard Hovy. Automatic evaluation of summaries using n-gram co- occurrence statistics. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL), 2003,
[20] Albert Lu, Hongxin Zhang, Yanzhe Zhang, Xuezhi Wang, and Diyi Yang. Bounding the capabilities of large language models in open text generation with prompt constraints, 2023.
[21] Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu. Rowan Zellers, et al. Neurologic a* esque decoding: Constrained text generation with lookahead heuristics. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 780-799, 2022.
[22] Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Neurologic decoding: (un)supervised neural text generation with predicate logic constraints. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4288 4299, Online, June 2021. Association for Computational Linguistics.
[23] Scott Lundberg, Marco Ribeiro, Richard Edgar, and Harsha-Nori. Guidance: guidance language for controlling large language models., 2024.
[24] Warren S McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 5:115-133, 1943.
[25] 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 (NeurlPS), 2022.
[26] Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. A corpus and cloze evaluation for deeper understanding of commonsense stories. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, pages 839-849, 2016
[27] OpenAl, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Flo- rencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett- Bernadett-Shapirg Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, An- drew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis. Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decarcaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve
12

---

Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao. Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider. Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Knueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Man- ning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk. David Mély, Ashvin Nair, Rejichiro Nakano, Rajeev Nayak. Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O' Keefe. Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pan- tuliano. Giambatisst Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shich, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Kata- rina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalic Staudacher, Felipe Petroski Such, Natalie Summers. Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng. Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang. Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024.
[28]
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback, 2022.
[29] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics (ACL), 2002.
[30] Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. Cold decoding: Ehergy-based constrained text generation with langevin dynamics. Advances in Neural Information Processing Systems, 35:9538-9555 2022.
[31] Michael O Rabin and Dana Scott. Finite automata and their decision problems. IBM journal of research and development, 3(2):114-125 1959.
[32] Lawrence Rabiner and Biinghwang Juang. An introduction to hidden markov models. IEEE ASSP Magazine, (1), 1986.
[33] Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model, 2023.
13

---

[34]
Dan Roth. On the hardness of upproximate reasoning. Artificial Intelligence, 1996.
[35]
Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szezechla, Taewoon Kim. Gunjan Chhablani, Nihal Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Mattco Manica, Sheng Shen, Zheng Xin Yong. Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Fevry, Jason Alan Fries, Ryan Teehan, Tali Bers, Stella Biderman, Leo Gao, Thomas Wolf, and Alexander M. Rush. Multitask prompted training enables zero-shot task generalization, 2022.
[36] Shuming Shi, Enbo Zhao, Wei Bi, Deng Cai, Leyang Cui, Xinting Huang, Haiyun Jiang, Duyu Tang, Kaiqiang Song, Longyue Wang, et al. Effidit: An assistant for improving writing efficiency. In Proceedings of the 61st Anmual Meeting of the Association for Computational Linguistics (Volume 3: System Demonstrations), pages
2023.
[37] Jiao Sun, Yufei Tian, Wangchunshu Zhou, Nan Xu, Qian Hu, Rahul Gupta, John Frederick Wieting, Nanyun Peng, and Xuezhe Ma. Evaluating large language models on controlled generation tasks, 2023.
[38] Yufei Tian and Nanyun Peng. Zero-shot sonnet generation with discourse-level planning and aesthetics features. arXiv preprint arXiv:2205.01822 2022.
[39] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint (t..i::23070992600 2023.
[40] Ramakrishna Vedantam, Lawrence Zitnick, and Devi Parikh. Cider:
Consensus-bard image description evaluation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2015.
[41] Ke Wang, Xin Ge, Jiayi Wang. Yu Zhao, and Yuqi Zhang. Easy guided decoding in providing suggestions for interactive machine translation. arXiv preprint Sitiv:2211.00992 2022.
[42] Yizhong Wang. Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Anjana Arunkumar, Arjun Ashok, Arut Selvan Dhanasekaran, Atharva Naik, David Stap, Eshaan Pathak, Giannis Karamanolakis, Haizhi Gary Lai, Ishan Purohit, Ishani Mondal, Jacob Anderson, Kirby Kuznia, Krima Doshi, Maitreya Patel, Kuntal Kumar Pal, Mehrad Moradshahi, Mihir Parmar, Mirali Purohit, Neeraj Varshney, Phani Rohitha Kaza, Pulkit Verma, Ravsehaj Singh Puri, Rushang Karia, Shailaja Keyur Sampat, Savan Doshi, Siddhartha Mishra, Sujan Reddy, Sumanta Patro, Tanay Dixit, Xudong Shen, Chitta Baral, Yejin Choi, Noah A. Smith, Hannanch Hajishirzi, and Daniel Khashabi. Super=-aturalinsttuuctons:: Generalization via declarative instructions on 1600+ nlp tasks, 2022.
[43] Brandon T Willard and Rémi Louf. Efficient guided generation for large language models. arXiv e-prints, pages arXiv-2307, 2023.
[44] Kevin Yang and Dan Klein. Fudge: Controlled text generation with future discriminators. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL), 2021.
[45] L Yao, N Peng, W Ralph, K Knight, D Zhao, and R Yan. Plan-and-wric Towards better automatic storytelling, association for the advancement of artificial intelligence. Cited on, page 92, 2019.
[46] Sheng Yu, Qingyu Zhuang, and Kai Salomaa. The state complexities of some basic operations on regular languages. Theoretical Computer Science, 125(2):315 1994.
[47] Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In International Conference on Machine Learning, pages 40932-40945. PMLR, 2023.
14

---

[48] Jinpeng Zhang, Nini Xiao, Ke Wang, Chuanqi Dong, Xiangyu Duan, Yuqi Zhang. and Min Zhang. Disambiguated lexically constrained neural machine translation. arXiv preprint arXiv:2305.1333 17351, 2023.
[49] Yusen Zhang, Yang Liu, Ziyi Yang, Yuwei Fang. Yulong Chen, Dragomir Radev, Chenguang Zhu, Michael Zeng, and Rui Zhang. Macsum: Controllable summarization with mixed attributes. Transactions of the Association for Computational Linguistics, 1:787-803, 2023.
[50] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, lon Stoica, Joseph E Gonzalez, et al. Sglang: Efficient execution of structured language model programs. arXiv preprint arXiv:2312.077104 2023.
15

---

A Derivation of Eq. (4)
p(Sn EF 2t, 8t)
E E Fi 21, st)
Σ
p(Sn EFI F+41 244 2c, 9t) p( 2441 8x)
+141
E 1411
p(S,
EF
Si+1 = 0(8 Fe+ 2411) p( 24+1) p(=+41 =x)
ΣΣ
Σ
p(S, EF (041; p(1e+1 Ze+1) p(=0+1 (x))
2441 8441 P6 (011
Σ p(2+1 2x)
Σ
p(Sn EF 244188411
Σ
p( I (x+1)-
Re+1
11+1
B DEA operations
"ets"" "
"gets"
*
"gets"
* gets"
"gets"
"gets"
"cold"
"gets"
"cold"
"gets" "
B
AD
BD
CD
B
Mj # "get"" or "cold"
"winter
"winter"
"cold"
# "winter"
"gets"
# "winter"
"winter"
"gets"
"cold"
"winter"
E
AE
BE
(a) Two DFAs Mi and M2 Figure 6: An example showing the intersection (logical and) and concatenation of two DFAs.
(b) Intersection of Mj and M2 (c) Concatenation Mr and M2
Proposition B.1. Let M1 be a DFA such that for each accept state s, 8(s, w) goes dead state for all w E E. Then Mi can be concatenated with any other DFA M2 by merging the accept states of M1 with the initial state of M2:
here dead state denotes DFA state that is (1) not accept state and (2) only transitions to itself. Instead of formally defining what means by "merging" the initial state M2 with the accept states of MM, we refer readers to Figure 3c for such example.
C Human evaluation
Table 5 presents the aggregated results for all questions from the Human Evaluation. Each question was answered by three workers, and compute their inter-annotator agreement. Each worker evaluated the outputs generated by four different models for the same prefix (and suffix) within each batch. We converted these evaluations for each batch into rankings and then used the Kendall Coefficient of Concordance to assess the correlation between the rankings assigned by each worker. The average coefficient was 0.449, indicating a moderate level of agreement among the annotators.
16

---

You will be presented with short paragraphs (A, B, and DJ extracted from some stories. Read each paragraph and rate them by answering the following questions.
Paragraph
Based dad's judge Juny, being judged. their needs and desires aside stroke
Fluency: Paragraph
Yes, well formed and fluent.
dad's a ago? it high time dad's it high time dad's brainatorm new approach to handle this growing frend judgment, idea how handle this growing judgement.
Between
Somewhatt, there few interuptions, but understandable.
Between and
No, the writing completely broken.
(2)
Paragraph
logical?
Yes, 8 consistent and logical.
Between and
Somewhat, there few rough transitions, but overall
consistent.
Between and
No, the story makes no sense.
Based
written logical?
Perfect, it well-ritten and logical.
Between 3 and
Okay, 8 has some issues, but overall acceptable.
Between 1 and
Poor, writing broken and the story makes no sense.
Paragraph
Questions
judged. Based dad's valuee? Of course nott Why would anyone put their own needs and desires aside stroke dad a ego? it high time dadd's a values be judgedd? idea how to handle this growing trand of judgement
Dad, uttimate
Paragraph B well-fommd fluent?
Yes, tt well- rell-formed and fluent.
Between 3 and
Somewhatt, there are few interuptions, but underatandablle
Between 1 and
No, the writing completely broken.
logical?
Yes, & consistent and logical.
Between 3 and
Somewhhat, there are few rough transitions, but overall
consistent.
Between
No, the story makes no sense.
(3) Overall: Based on answers and Paragraph overall well writtan and logical?
wall-written logical.
Okay, some issues, overall acceptable.
Between
writing
story sense.
Figure 7: Human evaluation interface on Amazon Mechanical Turk.
Table Full human evaluation results.
Continuation
Insertion
None
K
L
K&L
None
K
L
K&L
Q1. Fluency
TULU2
4.06
3.99
4.20
4.22
2.77
2.77
2.87
2.89
GPT3.5
4.52
4.45
4.58
4.50
2.33
2.34
2.37
GPT4
4.58
4.50
4.57
4.44
3.91
3.51
3.66
3.23
Ctrl-G
4.31
4.23
4.42
4.22
4.00
3,80
4.02
3.90
Q2. Coherency
TULU2
3.92
3.89
3.95
3.96
2.82
2.84
2.96
GPT3.5
4.54
4.43
4.55
4.46
2.60
2.48
2.57
GPT4
4.59
4.54
4.53
4.37
3,90
3.49
3.75
3.32
Ctrl-G
4.23
4.04
4.38
4.05
3.88
3,68
3.78
3.67
Q3. Overall Quality
TULU2
3.80
3.77
3.87
3.88
2.68
2.64
2.78
GPT3.5
4.40
4.32
4.44
4.36
2.27
2.22
2.27
2,31
GPT4
4.48
4.44
4.44
4.26
3.79
3.33
3.53
3.10
Ctrl-G
4.13
3.98
4.27
3.96
3.77
3.56
3.73
3.59
17

---

Table 6: Prompt templates for querying the GPT3.5 and GPT4 models the task of text editing.
Continuation:
Below is the opening of story. Continue the narrative by writing the next few sentences that includes the specified keywords. Your continuation should naturally follow the themes, tone, and setting established the opening. Aim to write compelling and coherent continuation that could lead the story forward. Your answer must consist of at least (WordRangeStart) words and no more than (WordRangeEnd) words. Please make sure to incorporate the given keywords in to your answer. Keywords: (Keyword).
Story: (Prefix)
Insertion:
the text the [INSERT] the following story with an appropriate sentence that includes the specified keywords. Feel free to use your knowledge, guesses, or interpretations to craft your answer, but ensure it is relevant to the context provided by the prefix and suffix. Your answer must consist of least (WordRangeStart) words and more than (WordRangeEnd) words. Please make sure incorporate the given keywords your answer. Keywords: (Keyword). Story: (Prefx)[INSERT((Suffi)
18

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract accurately summarize the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: It clearly stated that our proposed method only works for constraints that can be specified as DFAs.
19

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Proof for Theorem 3.2. is given in the main paper and the full derivation of Equation (4) is presented in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code for reproducing the main results is released on github and the model checkpoints are released on huggingface hub.
Guidelines:
The answer NA means that the paper does not include experiments.
20

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code for reproducing the main results is released on github and the model checkpoints are released on huggingface hub.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /twpps.cc/publcc//eecpcp/ httpliic/guieesee /CodeSubmiii
httpa////giieee//eeeuuubiii ssi ssionoolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
21

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
All sypeerparameetee are given in the released code repository.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For human evaluation, we computed inter-annotator agreement scores. For the text infilling experiments, which involve sampling, we reported standard deviation of the evaluation results over multiple runs.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The spec of the GPUs used for running experiments is given.
Guidelines:
The answer NA means that the paper does not include experiments.
22

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics betps://neurrig
(ppuulic/ttiisttiii ines?
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our application has non-trivial societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
23

---

Justification:
We do not release risky models or data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The creators or original owners of assets used in the paper are properly credited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcoee.ee......oooeeooooooooeeee com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
The released code repository is well-documentedd
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?

---

Answer: [Yes]
Justification:
See appendix for screenshots.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: We did not collect any personal information about the human annotators and they have never been exposed to any form of risks.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "QzwBqsGExB", "reviewer": "Reviewer_N2WB", "summary": "The paper tackles the problem of generating sequences from llms while following a constraint \\alpha, providing a solution for the case where \\alpha can be represented as a regular language (e.g., a constraint on containing certain substrings).  The method allows application of any regular-language constraint, and is somewhat similar to/inspired by a previously proposed method, Gelato, in which the LLM is distilled into an HMM.\n\nThe method is evaluated with domain-finetuned TULU-7B language models, and compared to some other constrained sequence generation methods, FUDGE and Neurologic A* esque decoding: these results are favourable. It is also compared to baselines such as directly using very large language models (e.g. GPT4), with the constraint given simply as part of the input. These results are unfortunately missing (the appendix is missing), but apparently GPT4 struggles to follow constraints (whereas ctrl-G always follows the constraints, by design). It is not clear to me whether the method was compared to Gelato.\n\nA small investigation is done to see whether constrained decoding can help when solving math problems, specifically by forcing the solution to contain all numbers from the question, and the method is deployed on the GSM benchmark. The performance is improved relative to not using the method, but not compared to other methods.", "questions": "questions/comments:\n\n0. several references made to materials in appendix, but no appendix! even if it were there, main materials should not be in appendix - pseudo code and greater description of ctrl g would be much more appreciated in main, as well as several results referred to from main text!\n1. figure 2 never referenced in main text\n2. lines 38-39 unfinished/mangled sentence\n3. line 39-40: possibly unclear sentence? it reads like gelato provides multiple algorithms in general, but for the case of keyword constraints it only provides one, in which case it is unclear what this alg is, what the situation is for other types of constraints, and whether ctrl-G covers the same or a larger set of constraints as can be represented with gelato. generally, the comparison between ctrl-g and gelato is not clear enough on the similarities and differences and in fact on what gelato is exactly. end of this sentence (in line 41) also unclear.\n4. lines 87-91: it seems (also from lines 39-41) that the paper faults Gelato for only providing one algorithm for handling certain constraints. but doesn't this paper also have only one algorithm? this criticism doesnt make sense\n5. lines 87-91: gelato is critiqued for possibly not being efficiently computable, but my impression is that this is true for ctrl-g too (with complexity nmh^2, where h is the distilled HMM size and reaches 32k even in this paper). can you compare the two explicitly?\n6. lines 87-91: the claim that it is unclear whether gelato would scale - why is that? is it because of the distillation to an hmm, and an assumption that this will become a worse approximation as the original model grows larger? if so, does that drawback not hold also for this method?\n7. lines 99-111: the description says a DFA is used to encode the constraint, but the DFA does not seem to appear in the equations, and it is not clear how it factors in\n8. line 121 typo: \"fo\"\n9. line 125 consider making it clearer that q0 here is \"the\" q0\n10. 127-135 this feels overly mystical for the problem of designing a dfa to express simple constraints. Unless I am missing something (in which case I would appreciate explanation), I think the whole discussion of designing DFAs for the constraints does not need more details than: \"this method allows for any constraint that can be expressed with a DFA\", with maybe a reference to textbooks on dfas if someone is not experienced. similarly figs 3 and 4 are not necessary.\n11. line 138 is this DFA only partial? if not, surely m=k * |\\Sigma| - why not just write that?\n12. 146 what subscript?\n13. 146-151 here i could do with being walked through what is happening in simpler terms/more detail/justifications/something - this bit is harder for me\n14. thrm 3.2 - give some justificution. did you compute this? (if so, prove). is it taken from a paper? if so, refer.\n15. line 166: \"we set\": i get what youre saying but rephrase because you cant set this distribution as you please. maybe you mean used 0/1 or only evaluated whether or not phmm(a|..)>0\n16. section 4 again bewildering amount of space dedicated to design of dfas for ultimately very simple constraints. line 170, and then lines 176-196 (also, 186-189 seem to be a definition not a theorem), all for this simple task. Also, if must refer to various algorithms (e.g. Aho-Corasick, line 182), then need to also provide relevant sources (ie cite).\n17. lines 202-204 im a bit confused: if each epoch has its own samples, what separates epochs? i dont understand. i see similar phrasing used in gelato but i dont follow this. are you changing anything between epochs? if not, this sounds like 1 epoch over 4m samples? if yes, explain what is being changed\n18. line 226 \"inflection of keywords\" - huh?\n19. 222-235 (and 235-241 kind of): more space spent on needless discussion of dfa operations. i respect that maybe sometimes these operations are computationally expensive but it seems all constraints considered in this paper do not bump against this anyway. it would make more sense to mention this only if it somehow limited the experiments or practical applications of the method.\n20. line 231: \"dead states\" not been defined\n21. line 259: seems like a fairer comparison against ILM would have it trained with the right percentage of masked out tokens each time, or even a varying percentage if want to see how it performs when only allowed one model\n22. line 300 \"word range\" -  maybe you mean sentence length range? word count range?\n23. line 331: saying ctrl-G is a 7B param model: you are ignoring the parameter count of the distilled HMM, which seems to me quite large (32k states!). What is the vocabulary size of Tulu2? If I assume 50k (i.e. similar to GPT2), that's 32 * 50M = 1.6B parameters for the emission matrix, and another 32 * 32 M = ~1B parameters for the transition matrix.\n24. line 339-341 hard to understand what being compared to what, rephrase\n25. 350-352: everything following \"we can\" - it is possible, but this is speculation, and not backed by the results, so be more careful in presentation.", "limitations": "weak eval - missing comparisons and results", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. A method for constrained generation that always follows the constraints, by construction\n2. The method possibly allows richer constraints than a previous one? Unfortunately I am not entirely sure about this, it is not clearly enough stated in the work\n3. Comparison with some previous methods", "weaknesses": "1. Weak evaluation (see questions/comments), in particular no comparison to gelato (?), no inference time comparison ( I get the impression that inference with this method is very slow), key results put in appendix, GSM experiment more a demonstration of usefulness of constrained decoding than of ctrl-G in particular (no comparison to other other constrained decoders)\n2. Some hard to follow details and overview. Missing in particular: 1) a complete description of how inference is done in this framework, and 2) more detailed description of differences and similarities between this method and Gelato (both use an HMM distilled from the LLM, but Gelato then uses only that while this method still uses the LLM as well - why does this method have both an LLM and its distilled HMM - I will appreciate more intuition on what is happening here). Also, it is not clear how/whether this method differs from gelato with respect to inference complexity (time) or potential constraint space (i.e. type of constraints that can be encoded)\n3. Confusing amount of attention given to problem of expressing \"regular\" constraints (e.g., contains/doesnt contain substring, has maximum length 3) as DFAs, I would expect this is trivial, but somehow the authors treat it as not, referencing multiple algorithms and dedicating several paragraphs and figures (e.g. 3: example of a DFA, 4: operations on DFAs) to it. 2 figures and over 40 lines (127-135, 176-196, 222-235) dedicated to question of creating DFAs for rather simple constraints, all would be better spent on describing main alg and bringing in main results (which are currently in missing appendix).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback. Following some prior years’ tradition, our appendix was mistakenly uploaded as the supplementary material and we apologize for the confusion. We have greatly improved the presentation of the paper and would love to share the revision upon AC’s approval.\n- We cut down the DFA content by more than a half and we will further move Fig. 3 & 4 to the appendix as you suggested. \n- The pseudocode, the main experiment results and the runtime analysis is moved from the appendix to the main text. **Please see the global response for the main results.**\n\n### **Efficiency of Ctrl-G:**\n\nDespite the time complexity result $O(nmh^2)$ from Theorem 3.2., Ctrl-G is actually quite fast due to its GPU-based implementation, where the $mh^2$ part is fully tensorized. For example, on the task of interactive text editing, Ctrl-G, when applied to the TULU2-7B model, is able to generate infillings under multiple constraints within a few seconds, enabling a user interface for real-time interaction. On the CommonGen benchmark, in the unsupervised setting, Ctrl-G not only generates outputs of higher quality but also runs 30 - 100 times faster than NeuroLogic A\\*esque and 6 - 16 times faster than GeLaTo. **Please refer to the global response for details.**\n\n### **Comparison between GeLaTo and Ctrl-G:**\n\nGeLaTo is really a special case of Ctrl-G. GeLaTo is much more limited in the sense that it only supports the keyword constraint, that is, no support for text infilling, word count control or arbitrary DFAs. \n\nBoth GeLaTo and Ctrl-G follow the same formulation for controllable autoregressive generation: they sample from $p_{ctrlg}(x_{t} | x_{<t}, \\alpha) \\propto p_{lm}(x_{t} | x_{<t}) p_{hmm} (\\alpha | x_{\\leq t})$, where $p_{hmm} (\\alpha | x_{\\leq t})$ approximates $p_{lm} (\\alpha | x_{\\leq t})$; specifically, *both GeLaTo and Ctrl-G use the base LM and the distilled HMM*. The intuition is that $p_{lm}(x_{t} | x_{<t})$ is responsible generating fluent text while $p_{hmm}(\\alpha | x_{\\leq t})$ is responsible for guiding the LM to satisfy the constraint $\\alpha$.\n\nWe revised line 87 - 93 as:\n\n> - To control LM generation with an HMM, we need to compute $p_{hmm}(\\alpha | x_{\\leq t})$. GeLaTo only shows how to compute it for $\\alpha$ being the keyword constraint. A polynomial-time algorithm for computing this probability for logical constraints in general is not known.\n> - GeLaTo assumes that $p_{hmm}(\\alpha | x_{\\leq t}) \\approx p_{lm}(\\alpha | x_{\\leq t})$ and have verified its effectiveness on GPT2-large. It remains to be explored whether this assumption would hold for the more recent LLMs (e.g. Llama2) with over 10 times more parameters.\n\n> (1) In Ctrl-G, we propose a polynomial-time algorithm that computes $p_{hmm}(\\alpha | x_{\\leq t})$ **for any $\\alpha$ that can be represented as a DFA.** (2) In addition to LMs on the scale of GPT2-large, we further verify the effectiveness of Ctrl-G in controlling LLMs with 7B parameters, demonstrating its scalability to even larger models.\n\n### **Derivation of Eq. (4) and Theorem 3.2:**\n\nThe derivation of Eq. (3) and (4) relies on the Markov property of HMMs and DFAs, and the fact that s_{t} is determined by x_{\\leq  t}. We derived Theorem 3.2 and here is a sketch analysis: \n\n> The computation cost of Ctrl-G is dominated by the computation of $p(S_{n} \\in F | z_{t}, s_{t})$ for all $t$, $z_t$ and $s_t$ following Eq. (4). Since $\\sum_{x_{t+1} \\in \\text{edge}(s_{t}, s_{t+1})} p(x_{t+1} | z_{t+1})$ does not depend on t, we can precompute and cache it, resulting a cost of $O(mh|\\Sigma|)$. \n\n> Then, note that for $s_{t}$, we only need to consider the $s_{t+1}$ where $\\text{edge}(s_t, s_{t+1}) \\neq \\emptyset$. Hence, fixing $t$ and $z_t$, when we compute $p(S_{n} \\in F | z_{t}, s_{t})$ for all $1 \\leq s_t \\leq k$, we only need to (1) enumerate through $1 \\leq z_{t+1} \\leq h$ and (2) for each $z_{t+1}$, we only need to visit each edge exactly once; there are $m$ edges in total, so it follows that cost is $O(n\\cdot h\\cdot h \\cdot m) = O(nmh^2)$.\n\n> The total time complexity is $O(nmh^2 + mh|\\Sigma|)$, which simplifies to $O(nmh^2)$ given that $|\\Sigma| < nh$ in practice.\n\n### **Comparison with ILM:**\n\nFor the task of text infilling, the base LM used by Ctrl-G is not finetuned with any supervision on this task; it is only finetuned to adapt to the style of ROC stories. In contrast, the ILM baseline is explicitly trained with full supervision on text infilling. Hence, it is remarkable for Ctrl-G to match the performance of ILM on the training distribution of ILM (13% ratio). The evaluation on other masking ratios is meant to show that Ctrl-G is able to generalize well to different distributions.\n\n### **Answers to Other Questions:**\n\nLine 99 - 111. We assume that $\\alpha$ can be represented as a DFA so that $p_{hmm} (\\alpha | x_{\\leq t})$ can be computed by the algorithm proposed in Sec. 3.2.\n\nLine 138. We merge all transitions from one state to the other into one edge and the edges of a DFA denote the pair of states $(s_1, s_2)$ connected by transitions. Definition added to Sec. 3.1.\n\nLine 146. Changed to “we omit the subscript “hmm” for simplicity.”\n\nLine 166. Changed to “the other approaches are subsumed by Ctrl-G in the sense that they only evaluate whether $p_{hmm}(\\alpha | x_{\\leq t})$ is 0 or not”\n\nLine 202-204. “one epoch” is actually “one step of EM parameter update;” we will rephrase to avoid confusion. \n\nLine 226. “Inflections of keywords” refers to CommonGen where “swims” “swimming” are inflections of “swim”; for the task of text infilling we don’t need to handle such cases. We will remove this reference.\n\nLine 231. Dead states now defined in Sec. 3.1.\n\nLine 300. Changed to “word count range”\n\nLine 331. The vocab size of TULU2-7B is 32K; changed to “we show that Ctrl-G, where a 7B-parameter model is coupled with a 2B-parameter HMM, …”\n\nLine 350 - 352. “we can” changed to “In future work, it is possible to”", "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": "KEfxmORviV", "reviewer": "Reviewer_GDqt", "summary": "It is a challenge to control LLMs' generation to adhere to logical constraints. Ctrl-G integrates LLMs with a Hidden Markov Model (HMM) and deterministic finite automata (DFAs) for flexible and tractable control, such as keyword and length constraints. Ctrl-G combined with TULU-2-7B model outperforms GPT-3.5 and GPT-4 in human evaluations for interactive text editing, achieving a 30% higher satisfaction rate and 100% constraint satisfaction. Additionally, Ctrl-G improves performance on the Grade School Math (GSM) dataset by guiding the reasoning process with logical constraints.", "questions": "1. Can the framework potentially handle highly creative tasks that might require more fluid and less structured outputs?\n2. Can Ctrl-G potentially generalize to domains outside of those tested, such as scientific text generation or code synthesis? No need to provide results, but insights on this would be helpful.", "limitations": "Yes, the authors adequately addressed the limitations", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper presented an interesting method on logically-controlled text generation.\n2. Comprehensive experimental results and analysis are provided. The results are strong and the findings are backed by well-designed human evaluation. Runtime analysis on efficiency of the method is provided. \n3. The paper is well-written and presented.", "weaknesses": "There are no major weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and questions.\n\n- We believe that better control in general will substantially benefit creative tasks. For example, according to the experience of our collaborators, when LLMs are asked to generate generic lyrics, they often tend to generate lyrics for love songs even when they are instructed not to do so. We can potentially avoid such a phenomenon by using Ctrl-G to prevent the phrases commonly used by love songs from appearing.\n- The effectiveness of Ctrl-G mainly relies on how well the assumption $p_{hmm}(\\alpha | x_{\\leq t}) \\approx p_{lm}(\\alpha | x_{\\leq t})$ holds. Distributions over scientific writing or code could be potentially harder to approximate but there should not be a fundamental difference compared to generic writing: for the more challenging domains we can always further scale up the HMMs.", "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": "2sEvJMOaUq", "reviewer": "Reviewer_Uqfm", "summary": "This paper proposes Ctrl-G to enable flexible lexically constrained generation with high accuracy and efficiency. Ctrl-G first distills an HMM from an unconditioned language model and then formulates the lexical/logical constraints with deterministic finite automata (DFAs). The inference algorithm takes both the HMM and the DFA as input and computes the desired conditional probability for guiding 48 LLM generation towards satisfying the given constraints. Experiments in keyphrase generation, text infilling, interactive text editing, and mathematical reasoning indicate that Ctrl-G achieves competitive performances for various sizes of LMs.", "questions": "See weakness.", "limitations": "The authors discuss limitations in the experiment sections but do not discuss potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed method is flexible and manageable for constrained generation. It achieves competitive performance on various tasks, and it can scale up to control larger models with high efficiency.\n2. The proposed method is theoretically sound and is clearly presented. The illustrations help in understanding the DFA formulation.", "weaknesses": "1. The experimental comparison for small model tasks is relatively weak. The paper discussed several related works in the introduction and method part (e.g., GeLaTo and NADO), but the works are not included in the experiments. The evaluation metrics BLEU and ROUGE-L measure text overlaps and cannot comprehensively represent the generation quality. Qualitative results are not provided.\n2. The experiment part of the paper is a little bit hard to follow. Section 5 and 6 represent key improvements, but the experimental results are displayed in the appendix (Table 4 and 5). Some sentences/sections are not finished.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and questions.\n\n- For the CommonGen benchmark, we did not include NADO because they only published results on the dev set and their released code is not reproducible due to lack of documentation; In the revised paper, we have added the results from NADO and GeLaTo on both dev & test sets, along with more evaluation metrics, for a direct comparison. **Please see the global response for the updated results.** \n\n- Regarding qualitative examples, for a quick reference, here are the outputs of Ctrl-G on the first 10 examples of the dev set of CommonGen; each line is a list of concepts followed by the output:\n```\nfield stand look: a woman stands in a field looking at flowers\nkid room dance: The kids are dancing in the living room.\npet couch cat: A pet cat sleeping on the couch.\nclimb side building: A man climbs up the side of a building.\ntalk climb wall: A man climbs a wall while talking on a cell phone\nsnow car drive: A car drives through the snow.\nphone talk wear: A man wearing sunglasses talks on a cell phone.\nrink hockey team: hockey player on rink during team practice\nsurfer surf ocean: surfers surf in the ocean off the coast\nflight stair jump: A dog jumps down a flight of stairs.\n```\nWe have further released the outputs of Ctrl-G for all three tasks, i.e., CommonGen, Text Infilling and Interactive Text Editing. **Following the instructions for authors, we uploaded them to an anonymous link and shared the link with the AC.**\n\n- For the text infilling task, ILM, as a model trained with full supervision, is already a very strong baseline for Ctrl-G, which is not trained with any supervision on infilling. Furthermore, all baselines for CommonGen cannot be adapted to this task. In addition, to the best of our knowledge, the diffusion-based LMs cannot be used to fill in multiple blanks of unknown length thus cannot be adapted to this task either.\n- In the revised paper, we cut down the contents about DFAs by more than a half and moved all main results, pseudocode for the algorithm, and the runtime analysis from the appendix back to the main paper. We have also cleaned up the unfinished sentences and greatly improved the writing. We would be more than happy to share the revised version upon AC’s approval.\n- Potential social impact: as we discussed in Sec. 6, Ctrl-G could potentially be used to detoxify language models by preventing inappropriate phrases from appearing. At the same time, it is also possible that people can use Ctrl-G to make LM generate toxic contents by enforcing the occurrence of inappropriate contents. The ability to control the generation from LMs is indeed a double-edged sword and we will add a more detailed discussion on the potential social impact of our work.", "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": "ob83TXjsld", "reviewer": "Reviewer_eXgv", "summary": "This paper proposes an approach called Ctrl-G to control LLM generation, specifically, constraining LLM’s output to deterministically follow certain logical constraints, such as maintaining a certain keyword in the generated text.\nThe approach has two main parts, the first is a Hidden Markov Model (HMM) that serves as a “prediction” model to guide the generation. The data used to train the HMM is sampled from the LLM. Essentially, the HMM is like a distillation model of the LLM that tries to capture the next-token generation “search space” of the LLM on a specific task. The second part is a series of deterministic finite automata (DFAs), each designed to represent a certain logical constraint $\\alpha$. The DFAs serves as a “checker” to determine the acceptance or rejection of an output from LLM. Combining the HMM and the DFAs, the proposed approach computes the conditional probability $P_hmm(\\alpha | x_t, x_<t)$, i.e., how likely $x_t$ is leading to $\\alpha$ being satisfied, to sample the next token.", "questions": "In section 4, the proposed approach is compared with FUDGE [Yang and Klein, 2021], NeuroLogic A*esque decoding [Lu et al., 2022], and ILM model [Donahue et al. 2020]. The background and motivation of comparing with these baseline methods is not clear. Why choose these models for comparison? \n\nIn section 5, the proposed approach is compared with plain GPT-3.5-Turbo and GPT4-Turbo. The comparison should also be made using GPT models and the proposed DFAs method as an output checking method. In fact, there are other simpler constrained parsing techniques, for example, the method used in [Constrained Language Models Yield Few-Shot Semantic Parsers](https://aclanthology.org/2021.emnlp-main.608) (Shin et al., EMNLP 2021). \n\nIn section 5, the HMM is distilled from TULU-2-7B model. Is there a specific reason for choosing this model? A 7B model seems relatively small. The llama-2 series and Google Gemma has open-sourced models with larger (> 20B) parameter sizes. \n\nSince distillation of a HMM is the key in this approach, the HMM’s training quality should be a concern. The paper mentioned that the HMM was trained on millions of samples generated from a baseline LLM (not fine-tuned on the task-specific data), but if those samples are of bad-quality, how can the quality of the obtained HMM be assured? \n\nThe paper claimed a 100% constraint satisfaction achieved with the proposed approach. Following the previous three questions, it is unclear if this 100% is achieved with the HMM model or the constrained parsing with DFAs. The proposed approach would be more valuable if the author can demonstrate the contribution is mainly from the HMM.", "limitations": "As mentioned in the questions, the experiment only shows the HMM being trained on a 7B model. Is it possible to generalize the approach to larger models, eventually to be used with models with trillions of parameter like GPT? For example, is the sampling amount a barrier for distillation from larger models? If so, what is the size limit here? More discussion should be made on the benefits of the proposed approach.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of using a HMM model to approximate a white-box model for exploring the LLM’s token generation space is novel. Despite that the idea of using HMM was published in a previous work [Zhang et al. Tractable control for autoregressive language generation], this paper proposes to improve by using DFAs for modeling various other task-specific logical constraints.", "weaknesses": "The evaluation requires more details and/or more experimental results to justify the contribution of the proposed approach. The limitation of the proposed approach is not clearly laid out and requries more discussions. Please see questions and limitations below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and questions.\n\nWe would like to clarify that Ctrl-G does not use DFAs to post-check the generated text; instead, the generated text is always guaranteed to satisfy the constraint. Specifically, Ctrl-G achieves constrained generation by generating from\n\t$p_{ctrlg}(x_{t} | x_{<t}, \\alpha) \\propto p_{lm}(x_{t} | x_{<t}) p_{hmm} (\\alpha | x_{\\leq t})$,\nwhere the LM $p_{lm}(x_{t} | x_{<t})$ is responsible for generating high-quality text while the HMM $p_{hmm} (\\alpha | x_{\\leq t})$ is responsible for guiding the LM to satisfy the constraint $\\alpha$. Here, we assume that $\\alpha$ can be represented as a DFA so this marginal probability $p_{hmm} (\\alpha | x_{\\leq t})$ can be computed by the algorithm proposed in Sec. 3.2.\n\n### **Choice of baselines:**\n\nFor the CommonGen benchmark, we chose FUDGE as a representative for the classifier-guided constrained generation methods; we chose NeuroLogic A\\*esque as a representative for the search-based decoding methods. We have further included NADO and GeLaTo as the baselines and we show that Ctrl-G beats them by large margins. **Please refer to the global response for more details.** We have also released the outputs of Ctrl-G via an anonymous link shared to the AC.\n\nFor the task of text infilling, ILM is the only available baseline that can generate infillings for multiple masks of arbitrary length; all baselines for CommonGen cannot be immediately adapted to this particular task. Nevertheless, given that Ctrl-G is an unsupervised approach, ILM, which is finetuned with full supervision on the task of text infilling, is a very strong baseline.\n\n\n### **Quality of the distilled HMMs:**\n\nBy training an HMM on examples sampled from the base LM, our goal is to effectively minimize the KL-divergence between $p_{hmm}$ and $p_{lm}$ and the actual quality of the samples should not matter. In the ideal case, we would have $p_{hmm} = p_{lm}$ and using Ctrl-G would be equivalent to sampling from $p_{lm} (x_{1:n} | \\alpha)$. Note that Ctrl-G controls the generation from the base LM by approximating $p_{lm} (x_{t} | \\alpha, x_{< t})$ but is not expected to extrapolate beyond the distribution of the base LM. Luckily, given the recent advancement of LLMs, the quality of the base LM should not be a bottleneck.\n\n### **Generalize to larger LLMs:**\n\nThough there are larger open-source LLMs, we chose a 7B-parameter model due to the limit of computation. However, this is not a weakness of this work:\n\n- Note that prior controllable generation approaches like NADO, FUDGE, GeLaTo and NeuroLogic A*esque were only evaluated on LMs with < 0.7B parameters; by demonstrating the effectiveness of Ctrl-G on a 7B-parameter LLM, we have provided strong evidence for scaling it up to even larger models with potentially hundreds of Billions of parameters. \n\n- It would be more computationaly expensive to distill an HMM from larger LLMs but it would not be a bottleneck. (1) The distillation process is independent from the constraints: once the HMM is trained, it can be used to enforce whatever constraints that can be represented as DFAS. (2) According to our experience with GPT2-large and TULU2-7B, it turns out that we don't really need to sample a lot more examples from larger LLMs: 128 million tokens for GPT2-large and 320 million tokens for TULU2-7B are good enough.\n\n- We show that Ctrl-G allows an LLM with *only 7B parameters* (coupled with a 2B-parameter HMM) to beat GPT3.5 and GPT4. This constitute an even stronger argument demonstrating the effectiveness of our approach, compared to showing that Ctrl-G allows a 70B-parameter LLM to beat the GPT models.\n\nWe will add a more detailed discussion to the paper.", "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:
Thank you all for your feedback. Please refer to the attached PDF for some of our main evaluation results as well as an additional runtime comparison: (1) Evaluation results on CommonGen (dev & test) for FUDGE, NADO, NeuroLogic A\*esque, GeLaTo and Ctrl-G. (2) Runtime analysis on CommonGen (dev) for NeuroLogic A\*esque, GeLaTo and Ctrl-G. (3) Evaluation results on Interactive Text Editing for TULU2-7B, GPT3.5, GPT4 and Ctrl-G. (4) Runtime analysis on Interactive Text Editing for TULU2-7B and Ctrl-G.

Upon your request, we have also released the output of Ctrl-G via an anonymous link. The link contains the output files as well as an html-based data visualization tool for you to browse the outputs. The link is sent to the AC following the instrutions for authors.

Meta-review: The study proposes an inference-time method based on HMMs and finite state automata to constrain the output of an LLM. The study presents encouraging results in terms of human evaluation and quality of the generated output.

The problem is interesting and important. However, the contribution could be seen as somewhat incremental. The reviewers also voiced concerns about clarity and appropriate comparison with baselines. These concerns were largely addressed in the author/reviewer discussion.
Decision: Accept (poster)