A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints

Neuro-symbolic AI bridges the gap between purely symbolic and neural approaches to learning. This often requires maximizing the likelihood of a symbolic constraint w.r.t the neural network's output distribution. Such output distributions are typically assumed to be fully-factorized. This limits the applicability of neuro-symbolic learning to the more expressive autoregressive distributions, e.g., transformers. Under such distributions, computing the likelihood of even simple constraints is #P-hard. Instead of attempting to enforce the constraint on the entire output distribution, we propose to do so on a random, local approximation thereof. More precisely, we optimize the likelihood of the constraint under a pseudolikelihood-based approximation centered around a model sample. Our approximation is factorized, allowing the reuse of solutions to sub-problems, a main tenet for efficiently computing neuro-symbolic losses. Moreover, it is a local, high-fidelity approximation of the likelihood, exhibiting low entropy and KL-divergence around the model sample. We evaluate our approach on Sudoku and shortest-path prediction cast as autoregressive generation, and observe that we greatly improve upon the base model's ability to predict logically-consistent outputs. We also evaluate on the task of detoxifying large language models. Using a simple constraint disallowing a list of toxic words, we are able to steer the model's outputs away from toxic generations, achieving SoTA detoxification compared to previous approaches.

Paper

References (51)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer P5zX7/10 · confidence 3/52023-06-26

Summary

The authors propose a pseudo-semantic loss for deep generative models with logical constraints. The authors consider autoregressive generative distributions (modeled by RNNs, Transformers, etc.), which are more expressive, and go beyond the standard approach of enforcing the constraints on fully-factorized distributions. However, the likelihood of the constraint is hard for auto-regressive distributions, so the authors propose an approximation at a random, local point, yielding a "pseudolikelihood". Then they show the utility of that pseudolikelihood in constructing a pseudo-semantic loss, which improves standard tasks such as finding the shortest path on Warcraft maps and solving partially solved 9x9 Sudokus. As a "killer app," the authors propose to use their method on detoxifying generations from LLMs. They show results on detoxifying GPT-2.

Strengths

S1: The problem of adding constraints with semantic losses is important, and has a clear impact on relevant problems, such as reducing toxicity. S2: The approximations in the paper are sound and seem to be of good fidelity and low deviation from the ground truth. S3: The experiments are performed on a variety of tasks, showing the promise of the method.

Weaknesses

W1: The authors need to give more examples of constraints, logical circuits, and how the loss encourages the reuse of sub-problems. See my questions below for more concrete suggestions for improvement. Furthermore, I do not think that Figure 2 is a good example. The choice of numbers at the leaves is arbitrary (should be discussed). The computation of the probabilities on the left is not clear. It's not clear how one relates A, B, and C to the constraint with Cat, Animal, and Dog. Some simplification and/ or explanation of the steps are necessary. W2: The reader does not get a sense of how scalable the approach is. It is acknowledged in the paper that the circuits' complexity is a bottleneck (260-263). I would expect more discussion on the circuits used in the paper, and how they could scale. What more complicated problems should we expect to solve by using the proposed pseudo-semantic loss? W3: Have you tried other constraints for toxicity? Was the avoiding tokens from the list the first thing you tried? Why not try more stuff to check for more gains? Again, it's important to discuss the circuits design and the issues that arise. Minor: M1: line 115 - do you mean $\mathbf{w}_i$ in the softmax? I do not see where the index $j$ comes from. M2: line 9 in Algorithm 1 - I think you mean "seq" vs, "seq_len" and "cats" vs. "num_cat"? M3: line 323: one again <- once again. M4: line 508: generate 100k <- generate 100k samples (or generations)?

Questions

Q1: Not sure I understood how your approach reuses sub-problems. Could you give examples from the tasks you use? Q2: Could you give examples of reducing toxicity by looking at samples from the GPT model?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

the authors adequately addressed the limitations

Reviewer FKar6/10 · confidence 4/52023-07-01

Summary

The paper presents a new way of computing a loss function measuring the degree of satisfaction of logical constraints for autoregressive models. This is an important task, as autoregressive models are now more and more used and calculating the degree of satisfaction of even simple constraints made of a single literal is #P-hard (due to the fact that different solutions depend on different conditionals). The proposed solution has been evaluated on 3 different tasks: 1. Warcraft shortest path: the task is to generate a minimum-cost path from the upper left to the lower right vertices. 2. Sudoku: the task is to generate a solution to a given partially filled sudoku 3. LLM detoxification: the task is to steer away the LLM model from toxic prompted-generations.

Strengths

- The paper is very well written and easy to follow. - The introduced approach is very interesting and presents improvements in the experiments. - The problem solved is very important as auto-regressive models are becoming more and more important (mostly due to the spread of LLMs)

Weaknesses

- The authors claim that they are the first to learn with constraints under auto-regressive generative models. While this might be true, there has been a lot of work on steering the generation of auto-regressive LLMs at inference time (see, e.g., [1,2]). I think that discussing the pros and cons of learning to satisfy the constraints during training vs steering the generation during inference might be very beneficial for the community. Especially given the fact that the authors have a NLP task in their experiments. - On this note, it might be interesting to see how their method performs against such methods in the LLM detoxification task. - I think that the current title is a bit misleading. Not all deep generative models are auto-regressive. So I would change the title from "A Pseudo-Semantic Loss for DGM with Logical Constraints" to "A Pseudo-Semantic Loss for auto-regressive models with Logical Constraints". References: [1] Meng et al. Controllable text-generation with neurally-decomposed oracle, NeurIPS 2022. [2] Lu et al. NeuroLogic Decoding: (Un)supervised Neural Text generation with predicate logic constraints. ACL 2022

Questions

- I found the entire paper very clear. However, I have a doubt about this step at equation 7. Why can you write: $\mathbb{E}_{y \sim \tilde p}[\mathbb{1}(y \models \alpha)] \approx \mathbb{E}_{y\sim p} \mathbb{E}_{\tilde y \sim \tilde p_y}[\mathbb{1}(\tilde y \models \alpha)]$? Can you give some more details about this step? - Algorithm 1: what is the difference between seq and seq\_len? In the same way, what is the difference between cats and num\_cat? Also, expand works on non-singleton dimensions. Since you're having python code in the paper then it needs to be as you'd write it. - In the example, suppose that instead of having generated $abc$, the models has generated the phrase "I love dogs", the samples that are 1 hamming distance away then would be "love dogs", "I dogs" and "love dogs"? Or something else? - Again in the example, you use a constraint with Cat, Dog and Animal as variables. Can you rewrite it using $a,b,c$. Also, in appendix A, it would be nice to have the step by step guide showing how the circuit is built from the constraint. - Minor: in the related work it shouldn't be HMCCN but C-HMCNN P.S. I really like the paper, if all the questions can be answered well, then I will increase the score.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weaknesses.

Reviewer 5z8g6/10 · confidence 3/52023-07-06

Summary

The method proposes as new neuro-symbolic loss for autoregressive models. The proposed method approximates the ture expectation of the constraint satisfaction using a pseudo likelihood term computed only in a neighbourhood of the node.

Strengths

I think the paper proposes an interesting extension of neurosymbolic methods on auto-regressive models addressing some tractability problems. Moreover, I really appreciated the toxic language experiment and it really shows an important application of neurosymbolic in the current AI scenario

Weaknesses

My first concern/doubt is about the exploitation of RNNs as auto-regressive probabilistic model (i.e. p(y_i | y_{<i})). While RNNs have an autoregressive nature in the latent space, they do not model an auto-regressive probabilistic model. What I mean is that, in terms of the y random variables (i.e. output variables), RNNs are fully factorised models conditioned on the parameters and the inputs, which have to be considered as observed variables in a PGM sense. Therefore it is not clear to me whether and how an LSTM is used for modelling p(y_i | y_{<i})), and whether many of the approximations are needed for an LSTM classifier. This question is also related to the baselines of the experiments, as one would be interested in knowing how pure semantic loss would behave on an RNN/LSTM. My second doubt/question is about the fact that peudolikelihood approximations have been quite standard in statistical relational learning (e.g. MLNs/PSL inference based on pseudolikelihood) and it is not clear to me how the proposed approximations are positioned/inspired/different w.r.t. these methods.

Questions

1) How is the LSTM used to model p(y_i | y_{<i})? 2) Do you have any intuition / experiment on how an RNN/LSTM behaves with pure semantic loss? 3) How is the proposed method linked to the use of pseudolikelihoods in statistical relational models (e.g. MLN learning with pseudolikehood?)

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

No explicit limitations are mentioned in the paper.

Authorsrebuttal2023-08-16

We wanted to ensure we've satisfactorily addressed the reviewers concerns. To that end, we wanted to emphasize that, just like the output distribution defined by GPT, the output distribution defined by an RNN is auto-regressive. Simply put, to obtain the hidden state at time $t$, the RNN needs to have processed the entire prefix up to time $t-1$. $h_t$, and consequently $y_t$, is then a function of the current token $x_t$ and the prefix through $h_{t-1}$. This is very similar to the way in which, in GPT, $y_t$ is a function of the current token and the prefix through the attention at time $t$.

Reviewer 5z8g2023-08-21

I think this depends on how the RNN is designed, and this was my main question. If the output at time (t-1) is fed as input to timestep (t), then, yes, I agree that there exist a conditional dependence of the variable y_t on y_{t-1}. This is indeed what you would do for text generation. But, this is not a general property of recurrent networks. As for general definition, when the x and y space are disjoint, the only dependence of the output is on the state h_{t-1} and the history input x_{0:t}, not on the previous output y, which would make it autoregressive on this space. Reading the answer of the authors it seems this is the way it is implemented. I missed this detail in the paper and I think it is fundamental to give credit to the experimental campaign. I will therefore change my score accordingly.

Reviewer sCK63/10 · confidence 4/52023-07-27

Summary

This paper proposes adding a pseudo-semantic loss into the training of autoregressive models, so that the model can learn logical constraints. Specifically, this approach includes a data augmentation by perturbation (e.g., by Hamming distance), and then adding a penalty loss for generation steps that are not following given constraints.

Strengths

I don't see obvious strengths.

Weaknesses

* The writing of this paper is of low quality. For example, the meaning of Figure 1 is vague. As a front-page figure, it is even harder to understand than the algorithm pseudo-code. * The most important claim of this paper, "the first approach to learning with constraints under auto-regressive generative models", is actually not true. Instead, there is already a bunch of previous work on the topic of "generation with constraints", such as [1] and its followup work. [1] NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints (NAACL 2021)

Questions

I don't have a question in this stage.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

1 poor

Presentation

1 poor

Contribution

1 poor

Limitations

I don't see the discussion of limitations in this paper.

Authorsrebuttal2023-08-16

We wanted to re-emphasize the key difference between our work and "generation with constraints" works such as NeuroLogic. Our proposed approach is a **training time** approach that biases the function learnt from the data to respect certain constraints by adding a regularization term to the cross-entropy loss. It **does not** interfere with the generation process at test time. "generation with constraints" approaches on the other hand **do not interfere with the training process**, and only modify an **already trained** model's predictions at test time.

Reviewer sCK62023-08-20

Re: Official Comment by Authors

Thanks for your clarification on the difference between your work and NeuroLogic. However, I would like to insist my score for now, because I am still not convinced regarding the validation of the big claim "the first approach to learning with constraints under auto-regressive generative models": * "Learning" is a rather high-level concept, and people don't always understand it as "training", especially when it doesn't appear together with "inference", so it might be better to claim it as "training generative models with constraints". * Even considering training-time approaches only, there are still a bunch of work closely related, especially [1] and its following work. After a quick reading of [1], I even feel the proposed approach in this paper can be seen as a special case of [1]. Specifically, [1] adapts a posterior regularization formulation to text generation. It has a search space approximation and a regularization term in its objective function, corresponding to the purturbation of y and the penalty loss term in this paper, respectively. There are more related work mentioned in [2], such as [3]. * Missing discussion and citation for all the above closely related work, including NeuroLogic, raises an overall concern on the thoroughness of the background introduction in this paper. [1] Prior Knowledge Integration for Neural Machine Translation using Posterior Regularization (ACL 2017) \ [2] A Survey of Knowledge-Enhanced Text Generation (ACM Computing Survey, 2022) \ [3] Deep Generative Models with Learnable Knowledge Constraints (NeurIPS 2018)

Authorsrebuttal2023-08-21

Thank you for your response and help towards improving the paper. ["might be better to claim it as "training generative models with constraints""] Thank you for your suggestion. We will make sure to clarify it in the paper. ["considering training-time approaches only, there are still a bunch of work closely related…, I even feel the proposed approach in this paper can be seen as a special case of [1]. "] Thank you for pointing out this related work. We are happy to discuss it in our related works section. It is unclear, however, how applicable it is to our setting. The approach in [1] rests upon the framework of posterior regularization [4], which requires that we design feature functions encoding the constraint. Such feature functions need to *factorize* over the tokens of the sentence (see section 2.5 in [4]). That might be doable for very simple constraints such as those considered in [1], but not in general. Setting aside that issue, the approach in [1] minimizes an extra KL-divergence between the autoregressive distribution and a log-linear variational distribution. For the constraints considered, computing such KL-divergence is intractable. Even approximating the KL-divergence is hard, due to the computational hardness of sampling the constraint ([1] sample from the autoregressive distribution and threshold using the feature function, which does not sample from the correct distribution). There is also no notion of perturbations; these are simply samples from the distribution. We would also argue that log-linear models defined by a set of linear constraints as variational distributions have been in use since posterior regularization was first introduced. [1] is simply an instantiation of such a framework. In our case, however, our distributional approximation is novel: it is a first-order approximation of the true autoregressive distribution. Consequently, we are **exactly computing the probability of the constraint being satisfied w.r.t. our proposed approximate distribution**. ["Missing discussion and citation"] We are happy to cite any and all related work. We were of course aware of neurologic and other inference time approaches, but felt they might be orthogonal to approach proposed here. Having discussed it with the reviewers, however, we will happily include a discussion with such works. Moreover, our work tends to focus on developing methodology for *general* constraints. And despite our best efforts, due to the massive number of works, it can be easy to miss methods geared towards very specific tasks from other communities. We greatly appreciate the reviewer bringing these to our attention. ["Claims"] Having said all of the above, fundamentally, the issue at hand seems to be the reviewer's disagreement with our overarching claim. We are happy to relax our claim to something along the lines of "Unlike previous works that are only able to approximately handle simple constraints under relaxations of autoregressive distributions, our approach injects non-trivial constraints, that don't easily factorize, as part of the training process, computing the probability of the constraint exactly w.r.t an approximate distribution". Thanks again for engaging with us, and we hope this convinces the reviewer to push their scores towards an accept. [References]: [4] Posterior Regularization for Structured Latent Variable Models (JMLR 2010)

Reviewer FKar2023-08-13

I would like to thank the authors for their answers. However, I still do not understand why they cannot compare against approaches (e.g., neurologic decoding) proposed for controllable text generation in the LLM detoxification example. Actually, I think it would be very interesting to: 1. compare the approaches, and 2. try to see what happens when used together. This should be possible because the LLM detoxification example includes only the simple constraint "a list of profanity, slurs, and swear words should not appear as part of the model generations", which can also be dealt with methods such as NeuroLogic decoding. Also, in the general answer to all reviewers, the authors write that they can deal with non-lexical constraints. Can the authors give an example of non-lexical constraint that they can deal with in the *text generation* domain? Finally, will the authors change the title? If so, how?

Authorsrebuttal2023-08-14

Thanks again for your response. [neurologic decoding] Here are the numbers comparing against neurologic, after painstakingly getting the code to work (the code base was quite outdated). Results that are not significantly worse than the competition, as determined by a t-test, are boldfaced. | Method | Full | Toxic | Non-toxic | |-------------------------|---------------|----------------|--------------------| | GPT-2 | 0.11 +- 0.15 | 0.69 +- 0.13 | 0.09 +- 0.19 | | GPT-2 + neurologic | 0.08 +- 0.14 | 0.66 +- 0.13 | **0.06 +- 0.08** | | GPT-2 + word banning | 0.12 +- 0.16 | 0.69 +- 0.13 | 0.09 +- 0.11 | | PseudoSL | **0.06 +- 0.09** | 0.59 +- 0.04 | **0.06 +- 0.08** | | PseudoSL + neurologic | **0.05 +- 0.10** | 0.68 +- 0.15 | **0.05 +- 0.07** | | PseudoSL + word banning | **0.06 +- 0.09** | **0.58 +- 0.01** | **0.06 +- 0.08** | We observe that while neurologic does improve the toxicity of the GPT-2 model, it fails when used in conjunction with our trained fine-tuned model. We do, however, show that a simple decoding method, where we set the probabilities of toxic words to 0 at decoding time, improves upon our results which is in line with our expectations given previous work. As a side note, these results are reported on a random subset of size 1k of the dataset. Attempting to run neurologic decoding on the entire dataset, 100k, using the maximum batch size we could fit on a 48GB GPU yielded an estimated time of 165 hours. [Title] We will be changing the title to "A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints". [Constraints] If we restrict ourselves to the definition in the neurologic paper "lexical constraints i.e. which words should or shouldn’t be included in the output text.", then we can specify more general constraints on the generated sentences such as "every fourth word has to be the same" or "every sentence needs to start with a noun". Essentially, any constraint that can be expressed in propositional logic can be dealt with. Thanks again for continuing to engage with us, and we hope this convinces the reviewer to push their scores towards an accept.

Authorsrebuttal2023-08-15

Update: Added comparison to neurologic decoding and word banning

Here are the numbers comparing against neurologic and word banning. Results that are not significantly worse than the competition, as determined by a t-test, are boldfaced. | Method | Full | Toxic | Non-toxic | |-------------------------|---------------|----------------|--------------------| | GPT-2 | 0.11 +- 0.15 | 0.69 +- 0.13 | 0.09 +- 0.19 | | GPT-2 + neurologic | 0.08 +- 0.14 | 0.66 +- 0.13 | **0.06 +- 0.08** | | GPT-2 + word banning | 0.12 +- 0.16 | 0.69 +- 0.13 | 0.09 +- 0.11 | | PseudoSL | **0.06 +- 0.09** | 0.59 +- 0.04 | **0.06 +- 0.08** | | PseudoSL + neurologic | **0.05 +- 0.10** | 0.68 +- 0.15 | **0.05 +- 0.07** | | PseudoSL + word banning | **0.06 +- 0.09** | **0.58 +- 0.01** | **0.06 +- 0.08** | We observe that while neurologic does improve the toxicity of the GPT-2 model, it fails when used in conjunction with our trained fine-tuned model. We do, however, show that a simple decoding method, where we set the probabilities of toxic words to 0 at decoding time (through HuggingFace), improves upon our results which is in line with our expectations given previous work. As a side note, these results are reported on a random subset of size 1k of the dataset. Attempting to run neurologic decoding on the entire dataset, 100k, using the maximum batch size we could fit on a 48GB GPU yielded an estimated time of 165 hours.

Reviewer P5zX2023-08-19

Thanks for the clarifications.

The authors have addressed my questions and comments well. I am maintaining my positive score. Regarding the discussion with the other reviewers, there was a question of whether RNNs/ LSTMs are autoregressive. Yes, they are. I think the reviewers responded well to that.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC