Adaptable Logical Control for Large Language Models

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

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.

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? In 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). In 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. Since 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? The 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.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

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.

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.

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

Questions

See weakness.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors discuss limitations in the experiment sections but do not discuss potential negative societal impact.

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.

Strengths

1. The paper presented an interesting method on logically-controlled text generation. 2. 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. 3. The paper is well-written and presented.

Weaknesses

There are no major weaknesses.

Questions

1. Can the framework potentially handle highly creative tasks that might require more fluid and less structured outputs? 2. 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.

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

Yes, the authors adequately addressed the limitations

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. The 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. A 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.

Strengths

1. A method for constrained generation that always follows the constraints, by construction 2. 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 3. 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) 2. 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) 3. 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).

Questions

questions/comments: 0. 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! 1. figure 2 never referenced in main text 2. lines 38-39 unfinished/mangled sentence 3. 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. 4. 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 5. 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? 6. 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? 7. 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 8. line 121 typo: "fo" 9. line 125 consider making it clearer that q0 here is "the" q0 10. 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. 11. line 138 is this DFA only partial? if not, surely m=k * |\Sigma| - why not just write that? 12. 146 what subscript? 13. 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 14. thrm 3.2 - give some justificution. did you compute this? (if so, prove). is it taken from a paper? if so, refer. 15. 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 16. 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). 17. 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 18. line 226 "inflection of keywords" - huh? 19. 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. 20. line 231: "dead states" not been defined 21. 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 22. line 300 "word range" - maybe you mean sentence length range? word count range? 23. 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. 24. line 339-341 hard to understand what being compared to what, rephrase 25. 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.

Rating

5

Confidence

3

Soundness

2

Presentation

1

Contribution

3

Limitations

weak eval - missing comparisons and results

thank you

thank you for your comments and for sharing some missing results. i am surprised by how much faster ctrl-g is than gelato, this was not at all clear to me from the original manuscript! i raise my score. please do make all the changes needed for clarity as mentioned in my review. regarding latency, please clarify why ctrl-g can use the gpu but gelato cannot (if indeed it cannot. if it can, and just hasn't been implemented to take advantage of the gpu, please share this fact).