Controllable Generation via Locally Constrained Resampling

We would like to thank the reviewer for their detailed feedback. We are happy to see they find that the method is principled and theoretically motivated, that the proposed approach is novel, and that the experiential evaluation covers a spectrum of tasks. We will now address their concerns.

“Clarity of exposition”

• “The paper introduces multiple similar variables (py,p~y) without clear distinctions.” In our submission, $p_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$ was used interchangeably with $\tilde{p}_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$. We have revised our submission to use only the former. We have also revised our algorithms to make them clearer. Algorithm 2 calls Algorithm 1 on line 4.

“Computational Complexity”

• To construct the approximate distribution which we can condition on the constraint, we need to query the model for all sentences that are 1-Hamming distance away from the model sample. As an approximation, we use top-p/top-k as one would when decoding from an LLM distribution. In our case, we found that k=5 was sufficient for our purposes i.e. for a generation of length 10, we would need to evaluate 50 extra sentences. This of course incurs a slight overhead compared to word banning, but it also comes with an upside: this particular setting was inspired by a HuggingFace github issue [1] regarding banning words, which to the best of our knowledge was unsolved until our work. Simply put, we did not have any approach that 1) could guarantee that a set of banned words would not appear, as there are exponentially many tokenizations of a word, and therefore, exponentially many ways in which it can be generated [2] , and 2) attempted to move beyond greedy decoding towards proper bayesian conditioning, thereby avoiding getting stuck in toxic trajectories. We attempted to answer the second point empirically, by showing that proper conditioning leads to lower toxicity while retaining the same perplexity. And in our revised submission we prove that our approach is guaranteed to produce generations that satisfy the constraint. We thank the reviewer for the suggested ways in which this can be made more efficient, and we’re excited to explore these directions.

“As far as I can tell, the Sudoku experiments appear to guarantee 100% accuracy by construction, since any samples that are not valid are rejected, making comparisons with baseline methods potentially misleading”

• We thank the reviewer for the great question. *We emphasize that a key aspect of our approach is that we are guaranteed to sample only valid configurations without having to perform any rejection sampling (Please see Theorem 1 in the revised submission). Therefore, in the case of Sudoku, a single sample suffices to obtain the solution to the Sudoku puzzle, which is the exact same number of samples used by (the more powerful) baselines.

“Section 3.2 appears to substantially reproduce content from the previous work”

• We are happy to acknowledge the Neuro-Symbolic Entropy Regularization paper, although we would like to point out that these are basic structural properties that apply to circuits, and therefore some resemblance is unavoidable, although we would argue that the exposition is sufficiently different.

“Could you provide a complete end-to-end algorithm that shows the full pipeline”

• If we replace line 4 in Algorithm 2 with Algorithm 1, then we have our complete end-to-end algorithm. As shown in Figure 2, starting from the probabilities given by the LLM distribution, we use Algorithm 1 to compute the probability of every token conditioned on the rest of the sentence. Once we have these probabilities, we are going to input them at their corresponding literals in the circuit. We can them do an upward pass followed by a down pass of the circuit to obtain constrained samples. We then reweight these samples by the importance weights, and sample again to obtain our final constrained sample.

References:

[1] https://github.com/huggingface/transformers/issues/17504

[2] Renato Lui Geh, Honghua Zhang, Kareem Ahmed, Benjie Wang, and Guy Van den Broeck. Where is the signal in tokenization space? In EMNLP 2024.

Thanks for your reply. I'm afraid I still don't entirely understand, but I appreciate you helping me get a better understanding.

Consider a case of 'mini-sudoku' where there are only three entries and the rule is simply that the three entries must consist of items 1, 2, 3, each exactly once. So valid mini-sudokus are [1 2 3], [2 1 3], etc. Now, let's say your model generates the sample $y$ which is [1 1 1]. If I understand what you mean by 1-Hamming distance away, the samples that are 1-Hamming distance away (and are in your proposal distribution given $y$) are [2 1 1], [3 1 1], [1 2 1], [1 3 1], [1 1 2], [1 1 3]. Obviously none of these are valid mini-sudokus, and so the probability mass on each of these is zero, (as it should be). Now, of course if we sample a new $y \sim p$, we will eventually hit on a sample $y$ which is a 1-Hamming distance from a valid sudoku (assuming such a sudoku has support over $p(\cdot | \alpha)$.

So just to be clear, I agree that your method is consistent and will recover $p(\cdot | \alpha)$, but may require a lot of samples $y \sim p$ (in that respect, not that different from PICARD?) However, it's very possible I am misunderstanding something.

Thanks for continuing to engage with us.

"if you take enough samples" We're afraid the part relating to having "enough samples" is not entirely right. Going back to the example that the reviewer gave above RE: the mini Sudoku, let's revise the example so that what we're given a valid sudoku puzzle as input, for instance [ 3 _ 2 ]. Let's say we sample [ 3 2 2 ] from the model, because it doesn't know any better. Now, we're going to construct our pseudolikelihood distribution as above, we're going to evaluate the likelihood (no further model samples) of many samples, specifically all the ones that are 1-Hamming distance away to be able to construct our distribution. So now we have $p_{[3 2 2]}(\mathbf{y})$ defined *for all configurations $\mathbf{y}$. Now we're going to condition $p_{[3 2 2]}(\mathbf{y})$ on the fact that the first entry is a 3 and the last entry is a 2, and that the numbers need to be unique i.e. $p_{[3 2 2]}(\mathbf{y} | \text{entries unique} \land X1 = 3 \land X3 = 2)$. The only configuration you can sample from this conditional distribution is [ 3 1 2 ]. You can sample 10 times, or 100 times, and all the samples are going to be [3 1 2].

Another way to think about it is that in the revised paper we proved that given a constraint $\alpha$, any samples we draw using Gen-C provably satisfy the constraint (please see Theorem 1). Given the constraints $\text{entries unique} \land X1 = 3 \land X3 = 2$ there is only one sample possibility that satisfies the constraint, and it is [3 1 2]. This is very similar to using a SAT-solver to solve a Sudoku puzzle. You do not need many samples, you're just pruning away any configurations that violate the constraint. Given that a valid Sudoku puzzle has a unique solution, if you prune away all the configurations that violate the constraint, you're left with the single correct Sudoku solution.

We are still happy to compare against PICARD, which we can perhaps implement are best-of-N sampling for Sudoku. But we really want to make sure to drive the following point home: Using Gen-C, a single sample is provably guaranteed to satisfy the constraint. All the importance-weighted samples drawn in algorithm 2 line 4 (we can draw many at a time, batched, without any loops) are guaranteed to satisfy the constraint. The importance weights in algorithm 2 are used merely to make sure that we approximate the true conditional distribution e.g. that we do not output nonsensical sentences when detoxifying a sentence. In the case of Sudoku, by definition, we only have a single possible valid solution for a given puzzle, and we do not even need to use importance-weighting. That is, it would suffice to return the output of line 4 in algorithm 2.

Please let us know if this makes sense, this is a core contribution of the paper, and we want to ensure it gets across.

Thanks for clarifying. I didn't twig that the conditioning on $\alpha$ happens in algorithm 1, I thought it was happening in algorithm 2 line 6. I think you could make this clearer by adding a line in algorithm 1 which says something like $P_{\tilde y}(\cdot | \alpha) = `construct-circuit`(P_{\tilde y}, \alpha)$ or something.

And the key point is that since your conditioning is implemented via the probabilistic circuit mechanism, you can essentially sample via a version of ancestral sampling which is obviously quite efficient, while still guaranteeing that the resulting sample satisfies the constraint. I can see how this would be more efficient than PICARD now -- since you are essentially doing importance sampling where you have an effective proposal distribution and you can sample efficiently from it, with no need for rejection sampling.

After all this discussion, I will raise my score to 8, as I'm convinced there is an interesting method here with good reasons for believing it works. However, the paper is still written quite confusingly, and should be revised, perhaps with a more complete worked example than the one in the paper, in order to illustrate the idea more comprehensively and clearly.

We would like to thank the reviewer for their thorough feedback, and we are happy to see they find the contribution original, and the presented approach effective at solving a timely and important problem. We will now address their concerns.

“First, I don't find myself fully convinced that the greedy sampling approach leads to samples that are not exact”

• As a counterexample, consider the following setting. Consider the setting where we train an LLM to have a uniform distribution over all binary strings with length 4. Then we have 2^4 = 16 possible generations, each with probability 1/16. Now let’s say that we’re given a constraint specifying that, if we have a generation starting with 0, then all the subsequent characters need to be 0. That is, conditioned on the constraint, the possible generations are now {0000, 1000, 1001 1010, 1011, 1100, 1101, 1110, 1111}, and we would expect the LLM to generate each string with a probability of 1/9. Since the LLM is trained to generate each of the possible 16 strings with equal probability, it must generate a string starting with 0 or 1 with equal probability, which means that the string 0000 will be generated 50% of the time under greedy decoding.

“I am unsure about what is the difference between DFA and RegExp, and how constrain circuits can implement the former but not the latter.”

• The idea behind DFAs and RegExps is that they recognized languages. We can think of them as Boolean functions that return 1 if a given string is in the language and 0 otherwise. Let’s consider the constraint where we want to output binary strings of length 4 where exactly 2 of them are true. A simple regexp for this language would look like {011|101|110}. On the other hand, a DFA would look something like ((X1) & ((X2 & -X3) | (-X2 & X3))) | ((-X1) & (X2 & X3)). Logical circuits subsume DFAs on bounded-length strings since they can branch on arbitrary logical sentences instead of a single variable as is the case in DFAs.

“The notation for the probabilistic quantities must be made more rigorous”

• We have revised the notation and the methodology section to clarify the notation.

Please note that below, we denote by $\mathbf{y}$ the constrained model sample, and by $\tilde{\mathbf{y}}$ the unconstrained model sample.

We associate with a constrained sample $\mathbf{y}$ an unconstrained sample $\tilde{\mathbf{y}}$, where $\mathbf{y}$ can be understood as a projection of $\tilde{\mathbf{y}}$ onto $\alpha$ s.t. $\mathbf{y} \models \alpha$. We can therefore define our proposal distribution as

$

q(y) = \sum_{\tilde{\mathbf{y}}} p(\tilde{\mathbf{y}}) \cdot p_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)

$

where $p(\tilde{\mathbf{y}})$ is the autoregressive distribution, and $p_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$ is a distribution over projections $\mathbf{y}$ of the unconstrained $\tilde{\mathbf{y}}$ given the constraint $\alpha$. The above definition outlines a two-step procedure for sampling a sentence $\mathbf{y}$ that satisfies a given constraint $\alpha$. We sample a sentence $\tilde{\mathbf{y}}$ autoregressively from $p(\tilde{\mathbf{y}})$, followed by sampling $\mathbf{y}$ from the distribution conditioned on $\tilde{\mathbf{y}}$ and the constraint $\alpha$, $p_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$. By incorporating the autoregressive distribution $p(\tilde{\mathbf{y}})$, we ensure that we can potentially generate any sentence. $p_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$ then refines $\tilde{\mathbf{y}}$ by projecting it to satisfy the constraint $\alpha$.

“similarly for eqn 8”

• In our submission, $p_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$ was used interchangeably with $\tilde{p}_{\tilde{\mathbf{y}}}(\mathbf{y} | \alpha)$. We have revised our submission to use only the former.

“Strictly speaking, the right-hand side of Eq 5 is identical to the one of Eq 4… What is contextualized probability”

• The idea behind equation 5 is to further approximate equation 4. Intuitively, we want to turn our intractable LLM distribution into a fully-factorized distribution that is easier to manipulate. To do so, we move from conditioning each word $\mathbf{y_{i}}$ on all the other words on the same sentence $\mathbf{y_{-i}}$ , to conditioning on all the other words in a fixed model sample $\mathbf{\tilde{y}_{-i}}$. That is how we define contextualized probability.

“Shouldn't p_\tilde y(y) in eqn 7 also depend on alpha”

• We have revised equation 7 to be more clear. Equation 7 defines the true conditional distribution

$

p(\mathbf{y} | \alpha) \propto \sum_{\tilde{\mathbf{y}}} p(\mathbf{y}, \alpha) \cdot p_{\mathbf{y}}(\tilde{\mathbf{y}})

$

This factorization reflects the process of first generating a constrained sentence y, and marginalizing over all the unconstrained sentences \tilde{\mathbf{y}} that could have given rise to \mathbf{y}

As a counterexample, consider the following setting. Consider the setting where we train an LLM to have a uniform distribution over all binary strings with length 4. Then we have 2^4 = 16 possible generations, each with probability 1/16. Now let’s say that we’re given a constraint specifying that, if we have a generation starting with 0, then all the subsequent characters need to be 0. That is, conditioned on the constraint, the possible generations are now {0000, 1000, 1001 1010, 1011, 1100, 1101, 1110, 1111}, and we would expect the LLM to generate each string with a probability of 1/9. Since the LLM is trained to generate each of the possible 16 strings with equal probability, it must generate a string starting with 0 or 1 with equal probability, which means that the string 0000 will be generated 50% of the time under greedy decoding.

Ok, this example clarifies things. I misinterpreted what "greedy decoding" meant. I assumed greedy decoding consisted in verifying the constraints after the generation of each token and, if the constraint was not satisfied, reject the completion and discard. However, I now see that greedy decoding consists of discarding the last token and trying other tokens in place of that. Maybe this could be clarified in the text.

I also thank the authors for the further clarifications. I've changes my score following the clarifications, however I think the presentation (particularly the notation) could still be made easier to access (for instance including the example they provided in their response in the paper as well).

Thanks again for engaging with us, we are grateful for the clarifying questions and discussion. We have just added the example clarifying the pitfalls of greedy constrained decoding to lines 145-157 of our revised submission. We also hope that our revised notation aids with the exposition of our work. Consequently, It is our hope that the reviewer votes for acceptance.

We would like to thank the author for their thorough feedback and interesting questions. Below is our response to their concerns and questions.

“from what I can tell there is no discussion of the runtime of the approach and how it compares to the baselines”

• To construct the approximate distribution which we can condition on the constraint, we need to query the model for all sentences that are 1-Hamming distance away from the model sample. As an approximation, we use top-p/top-k as one would when decoding from an LLM distribution. In our case, we found that k=5 was sufficient for our purposes i.e. for a generation of length 10, we would need to evaluate 50 extra sentences. Reviewer y7mC suggested ways in which this can be made more efficient, which we’re excited to explore.

“the experiments are mainly about relatively small-scale tasks.”

• We would argue that the constraints considered in this paper are hard: whether we’re representing a distribution over paths, over valid Sudoku puzzles or sentences without a list of specified expressions, we’re representing a distribution over a combinatorial number of configurations. For instance, there are ~10^10 valid paths, ~10^21 valid sudokus and ~10^102 valid sentences for a vocabulary of size 128000 and sequence length of size 20. This is combined with us using Llama3 as our LLM, the SoTA open source LLM.

“it is unclear how well the method can handle multiple competing constraints.”

• If Gen-C is supplied with more than 1 constraint, it conditions on their conjunction e.g. “generate sentences containing dog”, “generate sentences not containing hate” becomes “generate sentences containing dog and not containing hate”. If, however, the constraints are “generate sentences containing hate”, “generate sentences not containing hate” then the output is an empty sentence, because the constraint is unsatisfiable

“choice of the sampling parameters chosen”

• Our approach is parameter free, and so does not require tuning any parameters. We did experiment with temperature scaling the LLM distribution in the language detoxification experiment (as one would while sampling) on a random set of prompts of size 1000 using τ = {0.1, 0.3, 0.5, 0.7, 0.9, 1.0} but found that a temperature of 1.0 worked best across all settings. Please see Section B in the appendix of the updated manuscript.

“There are no theoretical results on approximation quality obtained with Gen-C and there is limited discussion of failure cases or limitations in the paper.”

• While we do not prove any theoretical results regarding the quality of the approximation, we revised our paper adding a theorem stating that Gen-C produces generations that provably satisfy the constraint. Furthermore, the contextualised probability was empirically shown by [1] to have a low KL-divergence from the GPT2 distribution (albeit with a low entropy)

“What is the impact of the size of the initial sample set on the quality of the final generations?”

• In our LLM detoxification experiment, we used a sample size of 4 sentences per sample in the batch. We did not perform an ablation study due limited computational resources, but rather that number was chosen to allow for sufficiently large batch sizes and therefore a short evaluation time. {TODO maybe}

“How robust is the method to different types of logical constraints, particularly those that require long-range dependencies?”

• An advantage of our approach is that it is agnostic to the logical constraint, in the sense that, regardless of the constraint, we’re guaranteed to sample a generation that satisfies it (see Theorem 1 in the revised submission). So, the logical reasoning is sound. One question we might ask is, just how good are the samples that we obtain. For instance, in the case of LLM detoxification, we don’t just want samples that are less toxic, but that are also fluent. We show that this is the case by measuring the perplexity, and showing that the perplexity of samples generated using Gen-C are as fluent as the baseline.

“Could you elaborate on how the approach might be extended to handle soft constraints or preferences rather than just hard logical constraints?”

• One could simply integrate the scores output from a toxicity classifier with the importance weights to get a posterior distribution over the samples conditioned on their toxicity. We plan to explore this in future work.

References:

[1] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. A pseudo-semantic loss for deep autoregressive models with logical constraints. In NeurIPS 2023.

Thank you for continuing to engage with us!

"Are the samples expected to satisfy the constraints even under the approximations used?"

• Yes! For a given constraint $\alpha$, any sample $\mathbf{y}$ returned by Algorithm 2 is guaranteed to satisfy the constraint. Theorem 1 in the revised submission formalizes this claim. Essentially, when conditioning on a logical constraint there are two prongs at play: the logical reasoning prong (my distribution allows for and the probabilistic reasoning prong.

• The logical reasoning prong asks does my distribution allow only for generations that follow from the constraint? The probabilistic reasoning prong asks is a given generation as likely under my distribution as it is under the target distribution?

• In Gen-C, the logical reasoning is exact, meaning our approximate distribution will only ever admit as part of its support generations that satisfy the constraint, and consequently, we will only ever sample generations that sample the constraint. On the other hand, the probabilistic reasoning is approximate, meaning if we do not draw enough samples, we might return a sample that is not very likely under the true distribution. This approximation, however, converges asymptotically to the true distribution as we state in lines 350-360.

"I think adding the runtime numbers would still be quite helpful."

• A single iteration of the baseline with a single samples runs in 1.65 seconds, averaged over 9 runs after a warmup run. If we take as many samples using the baseline as we do using Gen-C, we get an average runtime of 2.50. A single iteration of our approach on the other hand runs in 5.11 seconds, averaged over 9 runs after a warmup run, a 2x slow down compared to the baseline. We are happy to add these numbers to the paper, and are excited to explore future ideas to speed up our approach.

"I still think an ablation on k would be helpful for the reader."

• Thank you for the suggestion, we are currently working on an ablation study and will be adding it to the camera ready.

We would like to thank the reviewer for their thorough feedback, and we are happy to see the reviewer finds the paper interesting and promising. We will now address their concerns.

“It would be good to see examples of the input and desired output”

• Thanks for the suggestion, we’ve added example inputs with their desired outputs to the appendix.

“I do not find the results very convincing”

• We would like to point out that, for LLM detoxification, it is customary to report the expected maximum toxicity and the percentage toxicity over several random seeds as we do here. Also, please see the updated results in the paper for the mean and standard deviation for Sudoku.

“The LM application is quite basic.”

• We do not disagree with the reviewer that toxicity is more subtle than banning expressions, and are aware of the many works that leverage classifiers to guide the LLMs towards less toxic generations. This particular setting was inspired by a HuggingFace github issue [1] regarding banning words, which to the best of our knowledge was unsolved until our work. Simply put, we did not have any approach that 1) could guarantee that a set of banned words would not appear, as there are exponentially many tokenizations of a word, and therefore, exponentially many ways in which it can be generated [2] , and 2) attempted to move beyond greedy decoding towards proper bayesian conditioning, thereby avoiding getting stuck in toxic trajectories. We attempted to answer the second point empirically, by showing that proper conditioning leads to lower toxicity while retaining the same perplexity. And in our revised submission we prove that our approach is guaranteed to produce generations that satisfy the constraint.

• “There should be evaluations involving the constraints that were actually imposed” Could you please clarify what you mean by the previous statement?

• “could GEN-C with more basic constraints (banned words?) perhaps be used as a proposal distribution for approximately sampling a distribution constrained by an intractable classifier?” One could simply integrate the scores output from a toxicity classifier with the importance weights to get a posterior distribution over the samples conditioned on their toxicity. We plan to explore this in future work.

• Regarding Sudoku, we are not aware of any constrained decoding approaches that support it. Frameworks like Outlines and Guidance require that the Sudoku constraint be expressed as a regular expression, and it’s unclear how to do so in a succinct manner. The only non-constrained approach we’re aware of that tackles Sudoku puzzles is Tree-of-Thought [3], where the authors do not evaluate on 9x9 Sudoku Puzzles, and the maximum accuracy attained on 5x5 Sudoku Puzzles in 80%.

“Some questions on experiments”

• “What is the typical variance of importance weights at the resampling step” The variance of the normalized importance weights averaged across 5 different prompts is 0.1167. We do not have concrete estimates of mode coverage aside from the asymptotic unbiasedness of importance sampling, but [4] have empirically shown the approximate non-constrained distribution we used here to have a low KL-divergence from the GPT2 distribution.

• “How big are the constraint circuits in each of the experiments?” The biggest circuit was the toxic expressions circuit coming in at 655MB. The Warcraft paths circuit is almost ~13MB. The Sudoku circuit is dynamically compiled for each puzzle (as it is conditioned on the entries in each input Sudoku), and is in the order of MBs.

• “is there a nontrivial computation cost of running the proposed algorithm on top of regular decoding” To construct the approximate distribution which we can condition on the constraint, we need to query the model for all sentences that are 1-Hamming distance away from the model sample. As an approximation, we use top-p/top-k as one would when decoding from an LLM distribution. In our case, we found that k=5 was sufficient for our purposes i.e. for a generation of length 10, we would need to evaluate 50 extra sentences. Reviewer y7mC suggested ways in which this can be made more efficient, which we’re excited to explore.

"Description of related work in L350-352 does not seem quite accurate."

• We do concede that the term variance in the related work is a bit overloaded. In the case of Hu et al. we mean variance in the context of training the policy as pointed out here multiple times (https://openreview.net/forum?id=Ouj6p4ca60). In the case of Lew et al., it refers to the importance weights, as one would have to contend with running SMC, which is notorious for particle degeneration. Lastly, we agree since Qin et. al run stochastic gradient Langevin dynamics on a single sample, it would not make sense to group them with the first two works. We are happy to revise the wording of that sentence to clarify the confusion, and will add the suggested related work.

"more difficult problem domains"

We would argue that the constraints considered in this paper are hard: whether we’re representing a distribution over paths, over valid Sudoku puzzles or sentences without a list of specified expressions, we’re representing a distribution over a combinatorial number of configurations. For instance, there are ~10^10 valid paths, ~10^21 valid sudokus and ~10^102 valid sentences for a vocabulary of size 128000 and sequence length of size 20. This is combined with us using Llama3 as our LLM, the SoTA open source LLM. Most other controllable generation works with lexical constraints focus on a singular application, keyword generation. We were therefore excited about the novelty, and difficulty, of the proposed experimental settings. We would be curious what other difficult domain problems the reviewer would recommend.

"Minor"

• Thank you for pointing those out. We will make sure to address them.

References:

[1] https://github.com/huggingface/transformers/issues/17504

[2] Renato Lui Geh, Honghua Zhang, Kareem Ahmed, Benjie Wang, and Guy Van den Broeck. Where is the signal in tokenization space? In EMNLP 2024.

[3] Jieyi Long. Large Language Model Guided Tree-of-Thought. 2023 Preprint

[4] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. A pseudo-semantic loss for deep autoregressive models with logical constraints. In NeurIPS 2023.