Adaptable Logical Control for Large Language Models

Thank you for your feedback and questions.

We 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 $p_{ctrlg}(x_{t} | x_{<t}, \alpha) \propto p_{lm}(x_{t} | x_{<t}) p_{hmm} (\alpha | x_{\leq t})$, where 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.

Choice of baselines:

For 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.

For 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.

Quality of the distilled HMMs:

By 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.

Generalize to larger LLMs:

Though 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:

• 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.

• 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.

• 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.

We will add a more detailed discussion to the paper.

Thank you for following up with our discussion. Here are some further clarifications to your questions.

---

Ctrl-G vs. GPT4.

We would like to first clarify that Ctrl-G (with TULU2-7B and HMM-2B) actually beats GPT4 by large margins. Please refer to the pdf shared in our global response for details: the Overall section of Table 3 measures the percentange of examples where the models' outputs (1) satsifies the given constraints (keyphrase inclusion, word count range) and (2) attains an average quality score higher than 3 (out of 5) in human evaluation. Here Ctrl-G beats GPT4 by 30% - 70% in Overall Satisfaction rate in all settings.

---

Why do we need an HMM?

Thank you for mentioning [1]. To the best of our understanding, [1] mainly leverages SCFGs to prune away the next-token that would violate the constraints. From this perspective, [1] is actually similar to Outlines [2] and guidance [3], which also use CFGs/DFAs to prune away the next-tokens.

As discussed in Sec. 3.3, [1, 2, 3] is subsumed by Ctrl-G in the sense that [1, 2, 3] only decide whether $p_{hmm}(\alpha | x_{\leq t})$ is 0 or not. [1, 2, 3] would not work for many applications because they do not have any probabilistic information. We added the following example to Sec. 3.3 to illustrate the distinction: consider the task of generating a sentence that ends with the phrase " in the park", where we compare Ctrl-G with guidance, both applied to the same model.

guidance: silhouette of suspected ... an heavily secured.in the park 
Ctrl-G: A man and a woman are walking in the park

Even though both generations end with " in the park", it is clear that the output from guidance is not desirable as it unnaturally appends the phrase to some irrelevant text. The reason is that guidance, by performing pure logical reasoning over the DFA, only discard the next tokens that would make the constraint unsatisfiable, while the probabilities of the other next tokens remain unchanged; in contrast, Ctrl-G performs probabilistic reasoning by estimating $p_{lm}(\alpha | x_{\leq t})$; i.e., we estimate how likely each next token would eventually lead to $\alpha$ being satisfied.

Hopefully this would answer your question why an HMM is needed. We have added [1] as a reference to Sec. 3.3. Thank you for your suggestion.

---

HMM training details:

The goal of the HMM training is to minimize $D_{KL}(p_{lm} || p_{hmm}) = E_{x_{\leq n} \sim p_{lm}} \log p_{lm}(x_{\leq n}) - E_{x_{\leq n} \sim p_{lm}} \log p_{hmm}(x_{\leq n})$, which is equivlant to maximizing the second term (log-likelihood of the data sampled from the LM) because the first term (entropy of the LM) is a constant. We will add a more detaile discussion to the methodology section. Thank you for your suggestion.

---

Ctrl-G significantly generalizes GeLaTo:

GeLaTo proposes the idea of using a distilled HMM to approximate $p_{lm}(\alpha | x_{\leq t})$ via $p_{hmm}(\alpha | x_{\leq t})$, which is indeed significant, but GeLaTo is not applicable to many down-stream applications: it only derived the algorithm for computing the marginal probability $p_{hmm}(\alpha | x_{\leq t})$ for $\alpha$ being the keyword constraints. i.e., GeLaTo could not handle the keyword exclusion, text infilling or word count control because the algorithm for computing such marginal probability in general is not known in existing literature.

Compared to Ctrl-G, the main technical contribution of Ctrl-G is deriving a polynomial-time and GPU-parallelizable algorithm for computing $p_{hmm}(\alpha | x_{\leq t})$, as long as $\alpha$ can be represented as a DFA (see Sec. 3.2). This contribution is not trivial. We will add more technical details (e.g., deriviation of Eq. 4) and show how the algorithm is tensorized in the revised paper. Besides, we have also cut down the DFA content by over a half to highlight our technical contribution here. Thank you for your suggestion.

In summary, GeLaTo only supports the down-stream application of keyword-constrained generation, and Ctrl-G significantly generalizes GeLaTo by allowing this approach to be applicable to arbitrary constraints that can be represented as DFAs.

We will add a more comprehensive comparison between GeLaTo and Ctrl-G to the methodology section. Thank you for your suggestion. Please let us know if you have further questions or concerns.

---

[1] Shin, Richard, et al. "Constrained Language Models Yield Few-Shot Semantic Parsers." Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. 2021.

[2] Brandon T Willard and Rémi Louf. Efficient guided generation for large language models. arXiv e-prints, pages arXiv–2307, 2023.

[3] Scott Lundberg, Marco Ribeiro, Richard Edgar, and Harsha-Nori. Guidance: a guidance language for controlling large language models., 2024.

Thank you for your feedback and questions.

• 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.

• 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:

field stand look: a woman stands in a field looking at flowers
kid room dance: The kids are dancing in the living room.
pet couch cat: A pet cat sleeping on the couch.
climb side building: A man climbs up the side of a building.
talk climb wall: A man climbs a wall while talking on a cell phone
snow car drive: A car drives through the snow.
phone talk wear: A man wearing sunglasses talks on a cell phone.
rink hockey team: hockey player on rink during team practice
surfer surf ocean: surfers surf in the ocean off the coast
flight stair jump: A dog jumps down a flight of stairs.

We 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.

• 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.
• 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.
• 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.

Thank you for your feedback and questions.

• 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.
• 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.

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.

• 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.
• 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.

Efficiency of Ctrl-G:

Despite 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.

Comparison between GeLaTo and Ctrl-G:

GeLaTo 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.

Both 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$.

We revised line 87 - 93 as:

• 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.
• 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.

(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.

Derivation of Eq. (4) and Theorem 3.2:

The 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:

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|)$.

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)$.

The total time complexity is $O(nmh^2 + mh|\Sigma|)$, which simplifies to $O(nmh^2)$ given that $|\Sigma| < nh$ in practice.

Comparison with ILM:

For 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.

Answers to Other Questions:

Line 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.

Line 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.

Line 146. Changed to “we omit the subscript “hmm” for simplicity.”

Line 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”

Line 202-204. “one epoch” is actually “one step of EM parameter update;” we will rephrase to avoid confusion.

Line 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.

Line 231. Dead states now defined in Sec. 3.1.

Line 300. Changed to “word count range”

Line 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, …”

Line 350 - 352. “we can” changed to “In future work, it is possible to”

Authors may not submit revisions of their paper or supplemental material, but may post their responses as a discussion in OpenReview. This is to reduce the burden on authors to have to revise their paper in a rush during the short rebuttal period.