A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints
Authors: Kareem Ahmed
Kai-Wei Chang
Guy Van den Broeck
Venue: NeurIPS 2023 poster (2023)
Keywords: Neuro-Symbolic
Tractable Models
Learning with Constraints
TL;DR: We propose a tractable, local approximation with high fidelity for learning with constraints in auto-regressive models, a task which is in general #P-hard.

Abstract: 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 auto-regressive 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 likelihood distribution, we propose to do so on a random, local approximation thereof. More precisely, we approximate the likelihood of the constraint with the pseudolikelihood of the constraint centered around a model sample. Our approach is factorizable, allowing us to reuse solutions to sub-problems---a main tenet for the efficient computation of neuro-symbolic losses. It also provides a local, high fidelity approximation of the likelihood: it exhibits low entropy and KL-divergence around the model sample. We tested our approach on Sudoku and shortest-path prediction cast as auto-regressive generation, and observe that we greatly improve upon the base model's ability to predict logically-consistent outputs. We also tested our approach on the task of detoxifying large language models. We observe that 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 compared to previous approaches.

A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints
Kareem Ahmed
Kai-Wei Chang
Department of Computer Science University of California, Los Angeles ahmedk@cs ucla.edu
Department of Computer Science
University of California, Los Angeles kwchang&cs ucla. edu
Guy Van den Broeck Department of Computer Science University of California, Los Angeles guyvdbêcs ucla. edl
Abstract
Neuro-symbolic AI bridges the gap between purely symbolic and neural approaches to learning. This often requires maximizing the likelihood of symbolic constraint w.r.t. the neural network's 's output distribution. Such output distributions are typi- cally assumed to be facto-.ac.o This limits the applicability of neuro-symbolic learning to the more expressive autoregressive distributions, e.g., transformers. Un- der such distributions, computing the likelihood of even simple constraints is #P-hard. Instead of attempting to enforce the constraint on the entire output dis- tribution, we propose to do so on random, local approximation thereof. More precisely, we optimize the likelihood the constraint under a pseudolikelihood- based approximation centered around model sample. Our approximation is factorized, allowing the reuse of solutions to sub-problems a main tenet for ef- ficiently 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 Sudoku and shortest-pati predic- tion cast as autoregressive generation, and observe that we greatly improve upon the base model's ability to predict logically-consiseent outputs. We also evaluate the task of detoxifying large language models. Using simple constraint disallowing list of toxic words, we able steer the model's outputs away from toxic generations, achieving SoTA detoxification compared to previous approaches.
Introduction
Neuro-syme ceuro-symbolic AI aims to consolidate purely statistical approaches, chiefly using neural networks, with purely symbolic approaches for learning and reasoning. It has thus far shown great promise in ad- dressing many of the shortcomings of both paradigms, developing scalable approaches that learn from unstructured data while leveraging domain knowledge ensure the explainability, trusted behavior as well as reduce the amount of labeled data required by typically data-hungry deep neural networks.
More specifically, common approach to neuro-symbolic learning consists in injecting knowledge regarding the underlying problem domain into the training process as an auxiliary form supervision. Such knowledge typically takes the form of sentence in logic, and relates the outputs of the neural network, delineating assignments to the output variables that constitute a valid object from those that do not. For instance, only assignment to the cells of Sudoku puzzle such that each row, column, and x 3 square contain all of the digits from to constitutes a valid Sudoku solution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Injecting such knowledge into training is typically achieved by maximizing the probability of the constraint-a sum product of probabilities of the solutions to the constraint w.r.t. the network's distribution. There the outputs are assumed to be conditionally independent given the learned features, and therefore the distribution over the solutions of the constraint assumed to be fally-factorized.
In this paper we move beyond fully-factorized output distributions and towards autoregressive ones, including those induced by large language models such as GPT [35]. where the output at any given time step depends on the outputs at all previous time steps. Computing the probability of an arbitrary constraint under fully-factorized output distributions is #P-hard. Intuitively, the hardness of the problem can be attributed to the possibly exponentially-mang solutions of the constraint. Under an autoregressive distribution, however, computing the probability of even single literal as constraint is #P-hard [37]. That is, under autoregressive distributions, the hard- ness of computing the probability of an arbitrary constraint is now due to two distinct factors: the hardness of the logical constraint well as the hardness of the distribution. Throughout this paper, we will assume the inherent hardness of the constraint can be sidestepped: for many applications, we can come up with compact representations of the constraint's solutions that are amenable to computing its probability under the fully- fully-faccorized distribution efficiently (cf. Section 3.1). For problems where such compact representations are unavailable, we can fall back to approximate representations of the constraint [4].
p x))
y
-m(()
Figure I: Our approach in a nutshell. Given a data point 2; we approximate the likelihood of the constraint a (area shaded in pink) with the pseu- dolikelihood (shown in gray) of the constraint in the neighborhood of a sample (denoted x), where m(a) denotes the region of the constraint support.
Unlike previous works that are only able to approximately handle simple constraints under relaxations of autoregressive distributions [14, 50, 21, 48]. our approach injects non-trivial constraints, that don't 't easily factorize, as part of the training process, computing the probability of the constraint exactly w.r.t. an approximate distribution. Concretely, we approximate the likelihood of the constraint w.r.t. the autoregressive distribution with its probability in a local pseudolikelihood distribution- a product of conditionals- centered around a model sample. This leads to a factorizable objective which allows us efficiently compute the probability of constraints by reusing solutions to common nub-problems. Experiments show our approximation is low-entropy, allocating most of its mass around the sample, and has low KL- divergence from the true distribution. Intuitively, we want stay close to the sample to ensure high fidelity, while retaining a distribution to ensure differentiability and maximum generality within tractability bounds. An overview of our proposed approach depicted in Figure 1.
Empirically, we start by evaluating our approach on the tasks of solving a Sudoku puzzle and generating a shortest path in given Warcraft map where, conditioned the input puzzle (map, resp.), the neural network autoregressively generates a Sudoku solution (shortest path, resp.). taking into account generations at previous time steps. We observe that our autoregressive models improve upon the non-autoregressive baselines, and that our approach leads to models whose predictions are even more accurate, and even more likely to satisfy the constraint. Lastly, we evaluated our approach on the challenging task of detoxifying pretrained large language models where the aim is to move the model's distribution away from toxic generations and towards nontoxic ones without sacrificing the model's overall language modeling abilities. We show that, perhaps surprisingly, using only simple constraint disallowing a list of toxic words, the model exhibits a great reduction in the toxicity of the generated sentences, as measured using the perspective API', at almost no cost in terms of the model's language modeling capabilities, measured in perplexity; to our knowledge the first use of logical constraints in such task. Our code is available at gi thub. com/UCLA- Stt.t-trAArIPeaaae
Contribution In summary, we propose approximating the likelihood of the constraint w.r.t. the model parameters with the pseudolikelihood of the constraint centered around a model sample. Our approach can be thought of as penalizing the neural network for all the probability mass allocates to the local perturbations of a model sample that volate the logical constraint. We empirically demonstrate that our approach leads to models that are more consistent with the constraint.
htteps:/www.pereee http://wwww.rrrpptieppp...co
2

---

2 Background
2.1 Notation
We write upperease letters (X, Y) for Boolean variables and lowercase letters (x. y) for their instantiation (Y or Y =). Sets of variables are written in bold uppercase (X, Y), and their joint instantiation in bold lowercase (æ, y). A literal is a variable (Y) or its negation (-Y). A logical sentence (a or () is constructed from variables and logical connectives (A, V, etc.), and is also called (logical) formula constraint. A state or world y is instantiation to all variables Y. A state y satisfies a sentence a, denoted y - a, if the sentence evaluates to true that world. state y that satisfies a sentence is also said to be model of a. We denote by m(()) the set of all models of a. The notation for states y is used to refer to an assignment, the logical sentence enforcing the assignment, or the binary output vector capturing the assignment, these are all equivalent notions.
sentence a entails another sentence 3, denoted a += B, if all worlds that satisfy a also satisfy 3.
2.2 A Probability Distribution over Possible Structures
Let be logical sentence defined over Boolean variables Y = (Yi1...... Yuk), where denotes the number of time steps in the sequence, and k denotes the number of possible classes at each step.
The neural network's 's outputs induce a probability distribution p(-) over possible states y. However, the neural network will ensure that, for each time step i, there is exactly one class being predicted in each possible state. That is, exactly one Boolean variable .Y...... Yuk ) can be set to true for each time step i. We will use y, to denote that variable Y, is set to true in state y. More precisely, we let y: E {0, 13*h be the one-hot encoding of Yúj being set to 1 among {Yi,,.., }. By the chain rule, the probability assigned by the autoregressive neural network to state is then defined as
ply) = II ply ye.), 1=1
(1)
where yo: denotes the prefix y...... -: The most common approaches [30, 46, 16] to neuro- symbolic learning assume the conditional independence of the network outputs given the learned embeddings. More precisely, let f be a neural network that maps inputs x to M -ddimensional embeddings fz) Under such assumption, we obtain the fulloy-actorized distribution
p 2) = II plu: 2).
(2)
We no longer have notion of ordering under the fully-factorized distribution-ann and each possible p(y; 2) is computed as ow. 2) where w; E R is vector of parameters and (xx) is the softmax function. The appeal of such distribution is that it enables the tractability of many reasoning tasks, but the downside that it dismisses any correlation between the output labels. As we will show in our experimental section (cf. Section 5), using autoregressive distributions, even simple ones such as LSTMs, already outperforms neural network where the labels are assumed to be independent.
2.3 Neuro-Symbolic Losses
In neuro-symbolic learning, we often assume access to symbolic knowledge connecting the different outputs of neural network, typically the form of a constraint (or sentence) a in Boolean logic. We are concerned with maximizing the likelihood of the constraint w.r.t. the network's 's parameters O:
argmax pa (a) = argmax Ey-pe {1 - a3]] = argmax Σ po(y),
y
where, with slight abuse of notation, we omit the inputs æ. The expectation in Equation (3) quantifies how close the neural network comes to satisfying the constraint. It does so by reducing the problem of probability computation to weighted model counting (WMC): summing up the models of a, each weighted by its likelihood under p. The negative logarithm of this expectation yields loss function called semantic loss [46). Depending on how one chooses to compute said expectation, we recover different approaches. T-norms [28] make various assumptions, for instance, that the clauses of the
3

---

constraint are independent [36]. Ahmed et al. [1] estimate the expectation by sampling, using various gradient estimators for learning. Xu al. [46] compute the objective exactly, leveraging knowledge compilation techniques that exploit the structure embedded in the solution space. They obtain target representation (a circuit) which computing the expectation in Equation (3) using dynamic programming is linear in the size of the target representation (the number of circuit edges). We note that computing this expectation is, for arbitrary constraints, #P-hard [39, 40]. Indeed the size of the compiled circuit can grow exponentially in the constraint. In practice, we can obtain compact circuits for many constraints of interest, or effectively decompose the constraints as an approximation [4].
3 Pseudo-Semanti Loss
Unfortunately, as previously mentioned, moving beyond the fully-factorized distribution, we are faced with another source of intractability: the hardness of the distribution w.r.t which the expectation in Equation (3) is being computed. Assuming deep generative model whose distribution can capture Bayesian network distribution, the problem of computing even a single marginal-i.e., the marginal probability of single variable- is known to be #P-hard [37]. This class of models includes the autoregressive distribution. Intuitively, a constraint might have exponentially-mant lend itself nicely to reusing of solutions to sub-proble sub-problems, and therefore a tractable calculation of the expectation in Equation
solutions, yet
(3). An example being the n choose & constraint [5], where the expectation in Equation (3) can be computed in quadratic time under the factorfact distribution, despite having a coamally-poohibiiiee number of solutions. Moving away from the fully-factorized distribution, however, entails that in the worst case, we would need to compute a sub-problem combinatorial number of times-for all possible sequences-For the exponentially many solutions of the constraint.
To sidestep the intractability of the expectation in Equation (3), as a first step, we consider the pseu- dolikelihood p()) of set of parameters given an assignment [6], as a surrogate for its likelihood i.e..
p(y) ~ p(y) Il p y-:),
where y_; denotes yi..... 1 1 Yn. Consequently, we can consider the pseudolikelihood of a set of parameters given logical constraint a as a surrogate for its true likelihood i.e.,
p(a) 2 p(a) En [1 { F at) = Σ ply).
y//
Intuitively, the pseudolikelihodd objective aims to measure our ability to predict the value of each variable given a full observation of all other variables. The pseudolikelihood objective is attempting to match all of the model's conditional distributions to the conditional distributions computed from the data. If it succeeds in matching them exactly, then Gibbs sampler run the model's conditional distributions attains the same invariant distribution as Gibbs sampler run on the true data distribution.
On its own, the above would still not be sufficient to ensure the tractability of the expectation in Equation (3). Intuitively, different solutions depend on different sets conditionals, meaning we would have to compute the probabilities of many of the solutions of the constraint from scratch.
Instead, we compute the pseudolikelihood of the constraint in the neighborhood of a model sample*
p(a)= = Ey-p [1 {y F= az} R Ky-p E [1 F aa)] = Egyp (a( = Byy-p Σ Py Pv(
(6)
DFa
where By (g)
II p P(ū 9-
which can be seen as the pseudolikclihood p(-) of an assignment in the neighborhood of a sample y. Crucially this distribution is fully factorized, making it amenable to neuro-symbolic loss functions. Definition 3.1 (Pseudo-Semantic Loss). Let be sentence in Boolean logic, and let p be the pseudolikelihood function parameterized by 0 and centered around state as defined in Equation (7). Then, define the pseudo-semantic loss between and 0 to be
CSL Co (ce, po) = - log Eyyp (a)) = - log Hynp
(8)
"e sample y1 conditioned on the beginning of sentence token, then 82 conditioned on the sampled yr. followed by ys conditioned both y1 and y2 and on until we the ond-of-sentence token is sampled.

---

Intuitively, our semantis loss between a and pe can be thought of as penalizing the neural network for all the local perturbations ÿ of the model sample y that violate the logical constraint a.
3.1 Tractable Expectation Computations
We appeal to knowledge compilation techniques- class of methods that transform, or compile, a logical theory into a tractable circuit target form, which represents functions as parameterized computational graphs. By imposing certain structural properties on these computational graphs, we enable the tractable computation of certain classes of probabilistic queries over the encoded functions. As such, circuits provide a language for building and reasoning about tractable representations.
Logical Circuits More formally, logical circuit is a directed, acyclic computational graph repre- senting a logical formula. Each node n in the DAG encodes a logical sub-formula, denoted [r|. Each inner node in the graph is either an AND or an OR gate, and each Ieaf node encodes a Boolean literal (Y' or -Y). We denote by in(n) the set of n's children, that is, the operands of its logical gate.
As already alluded to, circuits enable the tractable computation of certain classes of queries over encoded functions granted that a set of structural properties are enforced.
Structural Properties
A circuit is decomposable if the inputs of every AND gate depend on disjoint sets of variables i.e. for a = 33 A', var)( (Tvar(?)) = Ø. Intuitively, decomposable AND nodes encode local factorizations over variables of the function. For simplicity, we assume that decomposable AND gates always have two inputs, a condition enforceable on any circuit in exchange for a polynomial size increase [41, 32].
A second useful property is smoothness. A circuit is smooth if the children of every OR gate depend on the same set of variables i.e. for a V, we have that (Br) var) Vi, Decomposability and smoothness are sufficient and necessary condition for tractable integration over arbitrary sets of variables in a single pass, as they allow larger integrals to decompose into smaller ones [8].
Furthermore, a circuit is said to be deterministic if, for any input, at most one child of every OR node has non-zero output i.e. for a V Br we have that 3; {3 1 for all i * j. Similar to decomposability, determinism induces a recursive partitioning of the function, but over the support, i.c. satisfying assignments, of the function, rather than the variables. Determinism, taken together with smoothness and decomposability, allows us to tractably compute constraint probability [10]. Given a smooth, deterministic and decomposable logical circuit ca encoding a constraint a² we can compute the probability p(a) w.r.t. a distribution that factorizes by feeding the probability of each literal at the corresponding leaf node and evaluating the circuit upwards, taking sums at OR nodes and products at AND nodes. Figure 2 shows an example of computing the probability of such a circuit.
3.2
The Algorithm
Algorithm 1 psoudo (a:pe)
We will now give a walk through of comput- ing our sseudo-semantic loss. We note that our algorithm
1: Input: Logical constraint a and model pg.
implemented in log-space
2: Output: Pseudo-semantic loss of w.r.t. 0
to preserve numerical stability and uses Py-
3: // Obtain sample from pa
Torch [31]. Our full algorithm is shown in Al- gorithm 1. We sample assignment y pe from the model (line 4). We now need to com- pute the pscudolikelihood of the sample
4: y ~ Po
5: // Get sequence length and num. of categories
6: seq, cats = shappe(
7: Expand the batch to contain all perturbations
8: of y that are a Hamming distance of away
log (3)) =
Σ log Log v
9: y = s.expand cats)
10: y range(seq), i, range(see)]] = rango(cats)
= =Σ log v- LSE
SoElogp(ue peupp(u.. U. v.
11: Evaluate expanded samples through model
12: log pe = pe (y) wolog_soooaaaaaooo (dim= - 1)
13: // Compute the conditional probabilities:
where LSE is the logsumexp function. That is, for every element in the sequence, we need to marginalize over all categories y/- This entails, for every element in the sampled sequence, we need to substitute each of the categories (lines
14: log [J]]]]] log pe (y) (3
15: logão = log Po log Po logsumexp (dim= 1)
16: // Compute the probability of a under Py
17: // by propagating the conditionals through ca
18: return log (a(a)
2 Such circuit can always be constructed, (Appendix A) although can grow exponentially in the worst case.
5

---

0.71
0.38
0.33
Po ~ abe abc
eapand
abc
abc
-bb a -bc
ab
0.84
1.0
00.33
C7 0.45
eval.
p(-abe) 0.15
p(abc) = 0.13
p plabe) = 0.13
p(a-be) 0.21
p(ab-c) 0.16
p(abe) = 0.13
0.38
0.46
T
0.33
1.0
plalbe) 0.46
p(blac) 0.38
p(clab) 0.45
1.0
p(-albe) = 0.54
p(-blac) 0.62
p(-clab) 0.55
-4
0.46 0.54
0.38
Figure 2: An example of our pipeline. (Left) We start by sampling an assignment from the model Po. Our goal is to compute the pseudolikelihood of the model sample- the product of the sample's conditionals. We start by expanding the model sample to include all samples that are Hamming distance of away from the sample. We proceed by (batch) evaluating the samples through the model, obtaining the joint probability of each sample. We then normalize along each column, obtaining the conditionals. (Right) logical circuit encoding constraint (Cat = Animal) (Dog = Animal), with variable A mapping to Cat, variable / mapping to dog and variable C' mapping to Animal. To compute the pseudolikelihood of the constraint in the neighborhood of the sample abc, we feed the computed conditional at the corresponding literals. We push the probabilities upwards, taking products at AND nodes and sums at OR nodes. The number accumulated at the root of the circuit is the pseudolikelihood of the constraint in the neighborhood of the sample abc.
9-10) and compute the probability of the sample under the model (line 12). obtaining sequence length x number of categories sequences. Now we can compute the log-conditional probabilities log p(y; y 9=:). We marginalize over the categories y', to obtain the log-marginal log ply LSE (log p(o', y...)-.),, We then condition the probability of every sequence by subtracting the log-marginals i.e., log y y))) logp(y-> (line 15). We use these conditionals to compute the pseudolikelihood assigned by the neural network to local perturbations of the model sample that satisfy the constraint (line 18). As per Section 3.1, we can compute the pseudolikelihood of constraint locally around the sample by pushing the computed conditionals at the respective input nodes of Ca. propagating them through the circuit, taking sums and products, and reading the value at the circuit root. Figure 2 shows toy example run of our algorithm in non-log space.
4 Related Work
In an acknowledgment to the need for both symbolic as well as sub-symbolic reasoning, there has been a plethora of recent works studying how to best combine neural networks and logical reasoning, dubbed neuro-symbolic AI. The focus such approaches is typically making probabilistic reasoning tractable through first-order approximations, and differentiable, through reducing logical formulas into arithmetic objectives, replacing logical operators with their fuzzy t-norms, and implications with inequalities [22, 36, 13].
Another class of neuro-symbolic approaches have their roots in logic programming. Deep- ProbLog [27] extends ProbLog, a probabilistic logic programming language, with the capacity to process neural predicates, whereby the network's 's outputs are construed as the probabilities of the corresponding predicates. This simple idea retains all essential components of ProbLog: the semantics, inference mechanism, and the implementation. domain knowledge specified as purely logical Prolog rules with the output of neural networks, dealing with the network's 's uncertainty through revising the hypothesis by iteratively replacing the output of the neural network with anonymous variables until consistent hypothesis can be formed. Bošnjak et al. [7] present a framework combining prior procedural knowledge, as a Forth program, with neural functions learned through data. The resulting neural programs are consistent with specified prior knowledge and optimized with respect to data.
similar vein, Dai et al. [9] combine
Diligenti et al. [11] and Donadello et al. [12] use first-order logic to specify constraints on outputs of a neural network. They employ fuzzy logic to reduce logical formulas into differential, arithmetic objectives denoting the extent to which neural network outputs violate the constraints, thereby supporting end-to-end learning under constraints. Xu et al. [46] introduced semantic loss, which circumvents the shortcomings of fuzzy approaches, while still supporting end-to-end learning under

---

7 000000000 67
3
2
4
0 00304000 003040022 153 6 64
O 4 040005/34 9246942800
236
1 D 100030090
26
994
3 30 804446600
39448
Ô 00/0906060 99
7 699594
2
5 7 0 0000000000
52
O 2 9 5 2 0
4 9
0
0
7
Figure 3: Example inputs and groundtruth labels for two of the three tasks considered in our experimental evaluation. (Left) Example Warcraft terrain map and a possible (non-unique) minimum-cost shortest path. (Right) Example Sudoku puzzle and its corresponding (unique) solution.
constraints. More precisely, fuzzy reasoning is replaced with exact probabilistic reasoning, made possible by compiling logical formulae into structures supporting efficient probabilistic queries.
There has recently been a plethora of approaches ensuring consistency by embedding the constraints as predictive layers, including semantic probabilistic layers (SPLs) [2], MultiplexNet [20] and C- HMCNN [16]. Much like semantic loss [46], SPLs maintain sound probabilistic semantics, and while displaying impressive scalability to real world problems, but might struggle with encoding harder constraints. MultiplexNet able to encode only constraints disjunctive normal form, which is problematic for generality and efficiency neuro-symbolit tasks often involve an intractably large number of clauses. HMCCN encodes label dependencies as fuzzy relaxation and the current state- of-the-art art model for hierarchical multi-label classification [16], but, similar to its recent extension [17], restricted to a certain family of constraints.
A related line of research focuses on constrained text generation, modifying the decoding algorithm to inject lexical constraints into the beam search process. Such methods include constrained beam search [34], NeuroLogic Decoding [25] and A *esque NeuroLogic Decoding [26]. And although they can be easily applied to various language models without training, these search-based methods can be inefficient they suffer from large search spaces. Recent works like NADO [29] and FUDGE [47] train auxiliary neural models to provide token-level guidance for autoregressive generation. In similar vein, GeLaTo [49] augments large language model with guidance from tractable probabilistic model to guarantee the keyword tokens are part of the generated sentence while retaining its fluency. Another family of approaches that enforce keyword-type constraints are insertion-based language models [24, 38), where the initial sequences only consist of the desired keywords and the transition phrases are repeatedly inserted to complete the sentences.
Throughout this paper, we assumed that the constructing logical circuit from a logical formula was easy. This is, in general, not the case. Ahmed et al. [4] offer an approach, by assuming the sub-problems are independent, and iteratively relaxing the independence assumption according to the sub-problems that most violate that assumption measured using the conditional mutual information.
5 Experimental Evaluation
We evaluate our pseudo-semantic loss on several tasks, spanning number of domains. We start by evaluating on Warcraft shortest-path finding, where we are given an image of Warcraft tilemap, and are tasked with autoregressivell generating one of the potentially many minimum-cost paths between two end points conditioned on the map, where the cost is determined by the underlying cost of the tiles spanned by the path. We move on to evaluating on the classic, yet challenging, task of solving 9 x Sudoku puzzle where, once again, the generation proceeds autoregressively. conditioned on the input Sudoku puzzle. It is worth noting that such tasks have been considered as test bed for other neuro-symbolic approaches before, but never from an autoregressive generation perspective.
We also evaluate on the task of large language models (LLMs) detoxification. In this task, we are interested the generations produced by an LLM when presented by a prompt input by the user. More specifically, we are interested not only in how good these models are at the modeling aspect, but also how toxic their outputs might be, measure which includes sexual explicitness, identity attacks, and profanity, among others. Our goal in this task is then to shift the model's distribution
7

---

Table Our experimental results on Sudoku,
Table 2: Our experimental results on Warcraft.
Test accuracy %
Exact
Consistent
Test accuracy %
Exact
Consistent
ConvNet
16.80
16.80
R8 ResNet- 18 + SL
55.00
56.90
ConvNet + SL
22.10
22.10
59.40
61.20
RNN
22.40
22.40
CNN-LSTM
62.00
76.60
RNN + PSEUDOSL
28.20
28.20
CNN-LSTM + PSEUDOSL
66.00
79.00
away from toxic generations, and toward nontoxic ones, all while maintaining its original ability to model text. We believe this to be a timely and important problem due to their recent prevalence and widespread usage coupled with the fact that previous work [15] has found non-negligible amounts of toxic, harmful, and abusive text in the corpora used to train LLMs.
Lastly, we evaluated our approximation's fidelity by comparing the entropy of our local approximation against that of the GPT-2 distribution, as well as how close our approximation is to the true likelihood in the proximity of the sampled data point as measured by the KL-divergence between the two. All experimental details, hardware specifications, as well as training details are provided in the appendix.
Warcraft Shortest Path For this task, we follow the experimental setting set forth by [33], where training set consists of 10, 000 terrain maps curated using Warcraft II tileset. Each map encodes 12 x 12 grid superimposed on a Warcraft terrain map, where each vertex is weighted according to the cost of the tile, which in turn depends on type of terrain it represents e.g., earth has lower cost than water. These costs are nol presented to the network. The task is then to generate a minimum-cost path from the upper left to the lower right vertices, where the cost of a path is defined as the sum of costs of the vertices visted by the edges along the path, and the minimum-com path is not unique, i.c., there exists many paths with the minimum cost, and are all considered correct. The minimum cost path between the top left and bottom right vertices is encoded as an indicator matrix, and serves as label, Figure shows an example input to the network, and the input annotated with a possible path.
We use a CNN-LSTM model, where, presented with an image of a terrain map, we use a ResNet1 8 [19] to obtain a 128 image embedding, which is then passed on an LSTM with single layer, hidden dim of size 512, and at every time step predicts the next edge in the path conditioned on the image embedding and previous edges. The constraint being maximized by pseudo-semantic loss in this task is that the predicted edges form a valid path.
As has been established in previous work [46, 3, 2]. the accuracy of predicting individual labels is often a poor indicator of the performance of the neural network in neuro-symbolic settings, where are rather more interested in the accuracy of our predicted structure object exactly matching the groundtruth label, e.g., is the prediction a shortest path?, a metric which we denote "Exact" in our experiments, as well the accuracy of predicting objects that are consistent with the constraint, e.g.. is the prediction a valid path?, a metric denoted "Consistent". Our results are shown in Table 2.
As alluded to repeatedly throughout the course of the paper, the first observation is that using an autoregressive model to predict the shortest path in the grid, even a simple single layer LSTM outperforms both ResNet- 18, well as ResNet- 18 trained with semantic loss, improving the exact match from 55.00% and 59.40% to 62.00%, and greatly improving the consistency of the predicted paths to 76.00%, improvement by almost 15%. We also see that using pseudo-semantic loss, denoted PL we improve the exact and consistent accuracies to 66.00% and 79.00%, resp.
Sudoku Next, we consider the task of predicting a solution to a given Sudoku puzzle. Here the task is, given a 9 partially-filedd grid of numbers to fill in the remaining cells such that the entries each row, column, and 3 x 3 square are unique i.e., each number from to 9 appears exactly once. We use the dataset provided by Wang et [43], consisting of 10K Sudoku puzzles, split into 9K training examples, and 1K test samples, all puzzles having 10 missing entries. As our baseline, we use a 5-layer RNN with a hidden dimension of 128, lanh non-linearity and a dropout of 0.2. At each time step, the RNN predicts the next cell given as input a one-hot encoding of the previous cell, and conditioned on the partially filled Sudoku. The constraint being maximized by pseudo-semantic loss is that entries in each row, column, and 3 x 3 squares are unique. Our results are shown in Table 1.
8

---

Table 3: Evaluation of LLM toxicity and quality across different detoxification methods on GPT-2 with 124 million parameters, Model toxicity is evaluated on the REALTONICITYPROE through Perspective API. Full, Toxic and Nontoxic refer to the full, toxic and nontoxic subsets of the prompts, respectively. PPL refers to the model perplexity on the WebText validation set. PPL of word banning evaluated on the 50% nontoxic portion of the WebText validation set. In line with previous work [15, 42], we characterize toxicity using two metrics: the Expected Maximum Toxicity over 25 generations, and the Toxicity Probability of a completion at least once over 25 generations. Setting the probabilities of toxic words to zero sending the perplexity of to infinity. We, therefore, report the perplexity on the 50% least toxic prompts dataset for Word Banning variants.
benchmark
Exp. Max. Toxicity (4)
Toxicity Prob. (L)
Models
PPL (L)
Full
Toxic
Nontoxic
Full
Toxic
Nontoxic
GPT-2
0.44
0.62
0.39
31.11%
67.27%
24.85%
25.85
Domain-
SGEAT [42]
0.32
0.46
0.28
14.05%
35.72%
7.99%
28.72
Adaptive
PseudoSL. (ours)
0.29
0.38
0.27
9.80%
20.07%
6.93%
28.14
GPT-2
0.40
0.55
0.36
27.92%
57.86%
19.56%
22.24
Word
SGEAT [42]
0.30
0.41
0.27
10.73%
27.05%
6.17%
24.91
Banning
PseudoSI. (ours)
0.29
0.37
0.27
9.20%
18.71%
6.55%
24.19
In line with our previous experiment, we observe that, once again, simple RNN outperforms the non-autoreerresiive model, as well as the same model augmented with semantic loss, although the difference is not that big with regards to semantic loss. Augmenting that same autoregressive model with pseudo-semantee loss, however, increases the gap to a convolutional network, and the same convolutional network augmented with semantic loss to 11.40 and 7.10, respectively.
LLM detoxification Lastly, we consider the task of LLM detoxification. That is, we investigate the effectiveness of logical constraints, enforced using pseudo-semantic loss, at steering the model away from toxic pseudo-semanti loss throughout this task, namely we minimize the probability that any of a list of profanity, slurs, and swear words* appear as part of the model generations. Following previous work [15, 42], we evaluate on the REALTOXICITY PROMPIT dataset of almost 100k prompts ranging from nontoxic, assigned a toxicity score of 0, to very toxic, assigned a toxicity score of 1. We focus on GPT-2 [35] as a base model for detoxification. As is customary, [15, 42], we use Perspective API, an online automated model for toxic language and hate speech detection, to score the toxicity of our predictions. It returns scores in the range 0 to 1.0, corresponding to nontoxic on the one end, and extremely toxic on the other. Though not without limitations, studics [42, 44] have shown that the toxicity scores from Perspective API are strongly correlated with human evaluations.
We choose a very simple constraint to be minimized by
We compare GPT-2 against SGEAT [42]-which finetunes GPT-2 on the nontoxic portion of its self generation, performing unconditional text generation and retaining only generations with toxicity < 0.5 and against SGEAT augmented with -eeudo-semantic loss. We report the Expected Maximum Toxicity and the Toxicity Probubility. The Expected Maximum Toxicity measures the worst- case toxicity by calculating the maximum toxicity over 25 generations under the same prompt with different random seeds, and averaging the maximum toxicity over all prompts. Toxicity Probubility estimates the empirical probability of generating toxic language by evaluating the fraction of times toxic continuation is generated at least once over 25 generations with different random seeds for all prompts. To understand the impact of detoxification, we evaluate the quality of the LLM using perplexity on the validation split of WebText, used to train GPT-2. Our results are shown in Table 3.
Addaiie Training It was previously shown that SGEAT lowers the toxicity of the generations produced by GPT-2, albeit at a slight cost in terms of perplexity. This is confirmed by our numbers, where we see that SGEAT reduces the average worst-case toxicity as well as the probability of producing a toxic generation when prompted with either toxic or nontoxic prompts. We also observe that using PseudoSL loss alongside SGEAT further reduces the overall average worst-case toxicity as well as the probability of producing toxic generation, while producing a better language model compared to SGEAT. Much of this reduction in toxicity appears to stem primarily from a reduction in the average worst-case toxicity well as toxicity probability given toxic prompts.
List downloaded from here.

---

Decoding- Timee Methods We also compared GPT-2. SGEAT and PseudoSL with variants thereof obtained through augmentation with a decoding-time algorithm. Word Banning [15]. Word Banning sets the probability of generating any of the words from the aforementioned list of profanity, slurs and swearwords to zero during decoding. We also attempted to compare against NouroLogic decoding, search-based decoding algorithm utilizing look-ahead heuristics to optimize for not only the probability of the generated sentence but also the lexical constraints being satisfied. However, attempting to run NouroLogic decoding on the entire dataset of prompts (100k) using the maximum batch size we could fit on a 48GB GPU yielded an estimated time of 165 hours. Considering a obtained empty generations for at least 30% of the
subset of the prompts, prompts. The PPL of word banning goes to infinity as the probabilities of some banned words are set to zero. We, therefore, report the perplexity the 50% least toxic portion of the prompts dataset. We observe that augmenting all of the domain-adaptive training baselines with Word Banning reduces their average worst-case toxicity as well the their toxicity probability. SGEAT augmented with Word Banning exhibits lower toxicity, both average worst-case toxicity and toxicity probability, than all other Lon-Pseu variants. Interestingly, even augmented with Word Banning, SGEAT exhibits higher toxicity than the base PseudoSL model. PSeudoSL augmented with Word Banning exhibits the lowest overall toxicity, both average worst-case toxicity and toxicity probability, with the gap to the second best in terms of toxicity probability being particularly stark on the toxic prompts. We also note that, in our evaluation of PPL for Word Banning, having discarded the toxic sentences, assigned a lower probability under our model, the perplexity of our model is now closer to that of GPT-2.
uudooll-samplee
Fidelity evaluation Lastly, we evaluated the fidelity of our approximation. We start comparing the entropy of our approximate distribution to the true distribution. We want this quantity to be low, as it would mean our approximation only considers assignments centered around the model sample. We also evaluate the KL-divergence of our approximate distribution from the true distribution in the neighborhood of model sample. We want this quantity to be low as well, as corresponds to how faithful our approximation is to the true distribution in the neighborhood of the model sample. Intuitively, the Kl.-divergence measures how many extra bits are needed to encode samples from our approximation using a code optimized for GPT-2, and is zero when the two distributions coincide. We find the entropy of GPT-2 80.89 bits while the entropy of our approximation is, on average, 35.08 bits. We also find the KL-divergence DKL (py, || PP) is on average 4.8 bits. That is we only need 4 extra bits, on average, to encode the true distribution w.r.t. our approximation distribution. Intuitively, we want to stay close to the sample to ensure high fidelity, while retaining a distribution to ensure differentiability and maximum generality within tractability bounds.
Conclusion
In conclusion, we proposed pseudo-semantic loss, neuro-symbolic loss for learning with logical constraints in deep generative models. Instead of attempting to enforce the constraint on the entire distribution, our approach does intuition to our approach is that it is analogous to a first-order approximation of a discrete functions with analytical form. As such, our approach makes use of first-order information to approximate the value of the discrete function about a given point, in our case the model sample. Our approach factorizes, allowing us efficiently compute the probability of the constraint under such approx- imate distribution using the language of tractable logical circuits. Our approach is able to greatly improve the accuracy and consistency of the baselines on structured-output prediction tasks, and is more effective at reducing the toxicity of GPT-2 compared to SoTA adaptive training approaches.
local distribution centered around model sample. One
Acknowledgments
We would like to thank Honghua Zhang for helpful discussions throughout the course of the project, and for providing the initial GPT sampling code. We also thank Tao Meng for the discussions that inspired the LLM detoxification experiment. The authors would like to thank the reviewers for their insightful feedback towards improving the paper. This work was funded in part by the DARPA Perceptually-enabled Task Guidance (PTG) Program under contract number HR001 12220005, DARPA Assured Neuro Symbolic Learning and Reasoning (ANSR) Program under contract num- ber FA8750-23-2-0004 ONR grant N00014-23-1-27800 NSF grants #IIS- 1943641, MITS-1956441 #CCF-1887129 129, and gift from RelationalAI. GVdB discloses financial interest in RelationalAI.
10

---

References
[1] Kareem Ahmed, Tao Li, Thy Ton, Quan Guo, Kai-Wei Chang, Parisa Kordjamshidi, Vivek Srikumar, Guy Van den Broeck, and Sameer Singh. Pylon: A pytorch framework for learning with constraints. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Demo Track), feb 2022.
[2] Kareem Ahmed, Stefano Teso Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In NeurlPS, 2022.
[3] Kareem Ahmed, Eric Wang, Kai- Wei Chang, and Guy Van den Broeck. Neuro-symbolit entropy regularization. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
[4] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. Semantic strengthening of neuro- symbolic learning. In Proceedings of the 26th International Conference Artificial Intelligence and Statistics (AISTATS), apr 2023.
[5] Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. Simple: gradient estimator for k-subset sampling. In Proceedings of the International Conference on Learning Representations (ICLR), may 2023.
[6] Julian Besag. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society. Series D (The Statistician), pages pp. 179-195, 1975.
[7] Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In Proceedings of the 34th ICML, 2017.
[8] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: unifying framework for tractable probabilistic modeling. 2020.
[9] Wang-Zhou Dai, Qiu-Ling Xu, Yang Yu, and Zhi-Hua Zhou. Tunneling neural perception and logic reasoning through abductive learning, 2018.
[10] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. JAIR, 2002.
[11] Michelangelo Diligenti, Marco Gori, and Claudio Saccà. Semantic-based regularization for learning and inference. Artificial Intelligence, 2017.
[12] Ivan Donadello, Luciano Serafini, and Artur d' Avila Garcez. Logic tensor networks for semantic image interpretation. In IJCAI, 2017.
[13] Mare Fischer, Mislav Balunovie, Dana Drachsler- Cohen, Timon Gehr, Ce Zhang, and Martin Vechev. DL2: Training and querying neural networks with logic. In ICML, 2019.
[14] Kuzman Ganchev, Joao Graça, Jennifer Gillenwater, and Ben Taskar. Posterior regularization for structured latent variable models. Journal of Machine Learning Research, 2010.
[15] Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. Realtoxic- ityprompts: Evaluating neural toxic degeneration in language models. ArXiv, abs/20009.11662 2020.
[16] Eleonora Giunchiglia and Thomas Lukasiewicz. Coherent hierarchical multi-label classification networks. Advances in Neural Information Processing Systems, 33:9662-960 -9633, 2020.
[17] Eleonora Giunchiglia and Thomas Lukasiewicz. Multi-label classification neural networks with hard logical constraints. Journal of Artificial Intelligence Research, 72:759-88 818. 2021.
[18] Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, and Sourab Mangrulkar. Accelerate: Training and inference at scale made simple, efficient and adaptable., 2022.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, June 2016.
[20] Nicholas Hoernle, Bafael-Michad Karampatsis, Vaishak Belle, and Ya'ake Ya'akov Gal. Multiplexnet: Towards fully satisfied logical constraints in neural networks. In AAAI, 2022.
11

---

[21] Zhiting Hu, Zichao Yang, Russ R Salakhutdinov, LIANHUI Qin, Xiaodan Liang, Haoye Dong. and Eric P Xing. Deep generative models with learnable knowledge constraints, In Advances in Neural Information Processing Systems, 2018.
[22] Angelika Kimmig, Stephen Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. A short introduction to probabilistic soft logic. In Proceedings of the NIPS Workshop on Probabilistic Programming: Foundations and Applications, 2012.
[23] Nya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2017.
[24] Sidi Lu, Tao Meng, and Nanyun Peng. Insnet: An efficient, flexible, and performant insertion- based text generation model. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022.
[25] Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Neurologic (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 (NAACL), 2021.
[26] Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. NeuroLogic asesque decoding: Constrained text generation with lookahead heuristics. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies (NAACL), 2022.
[27] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In NeurlPS, 2018.
(28) Mattia Medina Grespan, Ashim Gupta, and Vivek Srikumar. Evaluating relaxations of logic for neural networks: comprehensive study. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 281 2812-2811 8 2021.
[29] 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.
[30] James Mullenbach, Sarah Wiegreffe, Jon Duke, Jimeng Sun, and Jacob Eisenstein. Explainable prediction of medical codes from clinical text. arXiv preprint arXiv:1802.05660 2018.
[31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[32] Robert Peharz, Steven Lang. Antonio Vergari. Karl Stelzner, Alejandro Molina, Martin Trapp. Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference of Machine Learning, 2020.
[33] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In ICLR, 2020.
[34] Matt Post and David Vilar. Fast lexically constrained decoding with dynamic beam allocation for neural machine translation. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL) (Long Papers), 2018.
[35] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. 2019.
12

---

[36] Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge into embeddings for relation extraction. In Proceedings of the 2015 Conference of the NAACL, 2015.
[37] Dan Roth. On the hardness of approximate reasoning. In IJCAI, pages 613-619, Morgan Kaufmann, 1993.
[38] Raymond Hendy Susanto, Shamil Chollampatt, and Liling Tan. Lexically constrained neural machine translation with levenshtein transformer. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL), 2020.
[39] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 1979.
[40] L.G. Valiant, The complexity of computing the permanent. Theoretical Computer Science, 1979.
[41] Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthening sum-product network structure learning. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 343-358. Springer, 2015.
[42] Boxin Wang, Wei Ping. Chaowei Xiao, Peng Xu, Mostofa Patwary, Mohammad Shoeybi, Bo Li, Anima Anandkumar, and Bryan Catanzaro. Exploring the limits of domain-adaptive training for detoxifying large-scale language models. In Neurips, 2022.
[43] Po- Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 6545-65555 PMLR, 2019.
[44] Johannes Welbl, Amelia Glaese, Jonathan Uesato, Sumanth Dathathri, John F, J. Mellor, Lisa Anne Hendricks, Kinsty Anderson, Pushmeet Kohli, Ben Coppin, and Po-Sen Huang. Challenges in detoxifying language models. ArXiv, abs/2109.074453 2021.
[45] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the- art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, Association for Computational Linguistics, 2020.
[46] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. International conference on machine learning, pages 5502-5511. PMLR, 2018.
[47] 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.
[48] Wenhao Yu, Chenguang Zhu, Zaitang Li, Zhiting Hu, Qingyun Wang, Heng Ji, and Meng Jiang. survey of knowledge-enhancee text generation. ACM Comput. Surv., 2022.
[49] Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In Proceedings of the 40th International Conference on Machine Learning (ICML), jul 2023.
[50] Jiacheng Zhang, Yang Liu, Huanbo Luan, Jingfang Xu, and Maosong Sun. Prior knowledge integration for neural machine translation using posterior regularization. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), 2017
13

---

A Circuit Construction
Any logical formula can be compiled into a smooth, deterministic and decomposable logical cir- cuit: every disjunction factorizes the solution space into mutually exclusive events whereas every conjunction factorizes the function into two sub-function ffnctiontioss over disjoint sets of variables. Here is simple albeit potentially sub-optimal recipe: order variables lexicographically. Alternte OR and AND nodes. An OR node branches on the current variable being true or false, and has two children: a left (right) AND node whose children are the positive (negative) literal and the subtree corresponding to substituting the positive (negative) literal into the formula. Repeat while variables remain. We use the PySDD compiler which outputs circuits satisfying the above properties, addition to structured- decomposability, which asserts that functions, or constraints, over the same variables decompose in the same manner. We say the above recipe is potentially sub-optimal as we use a fixed variable order. In general, there can be an exponential gap in the size of the logical circuit obtained using the worst and best variable order. Finding the best such order is, in general, NP-hard. However, in practice, compilers (PySDD included) use search heuristics that yield demonstrably good orders.
B Language Detoxification
The experiments were run server with an AMD EPYC 7313P 16-Core Processor @ 3.7GHz, 2 NVIDIA RTX A6000, and 252 GB RAM. Our LLM detoxification experiments utilized both GPUs using the Huggingface Accelerate [18] library.
In order to construct our constraint, we start with the list of bad words and their space-prette preefxee variants". We then tokenize this list of augment bad words, yielding 871 unique possibly-bar tokens (some tokens are only bad when considered in context with other tokens), in addition an extra catch-all good token to which remaining tokens map to. Our constraint then disallows all sentences containing any of the words on the augmented list, starting at any of the sentence locations 0 through len (enstenenc len(word). The code to process the list of words, the code to create the constraint as well as the constraint itself will be released as part of our code.
Similar to SGEAT [42]. the SoTA domain-adaptive training approach to detoxification, we finetune our model self-generations as opposed any external dataset. More specifically, we unpromptedly generate 100k samples using GPT-2 through Hugging Face [45]. which are then filtered through Perspective API, keeping only the 50% most nontoxic portion of the generations. We leverage the curated nontoxic corpus to further fine-tune the pre-trained LLM with standard log-likelihood loss and adapt it to the nontoxic data domain. Unlike the two other tasks where we use model samples, we use the toxic portion of the corpus to which we apply our newly proposed pseudo-semantic loss. The intuition here is that the local perturbations of toxic sentence are also toxie, and these are exactly the assignments whose probability we would like to penalize.
Our training script is adapted from that provided by Hugging Face?. We use batch size of 16, a learning rate of le-5 with the Adam optimizer [23] with otherwise de- fault parameters. We did grid search over the pseudo-semantic loss weight in the values {0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1, 4, 8}. All other hyperparameters were left unchanged. Simi- lar to [42], we use use nucleus sampling with p = 0.9 and temperature of during generation. A randomized 10k portion of the RcalToxicityPromee
dataset was used to determine early stopping.
For only this task, our implementation of the pseudo-semanti loss makes pseudo- likulo-- distribution (lines 7-12 in Algorithm 1) due to the lack of computational resources. We constructed our distribution using only the top-10 good words and the top-470 toxic words.
of top-k construct the
C
Sudoku
The experiments were run server with an AMD EPYC 731 16-Core Processor @ 3.7GHz, 2 NVIDIA RTX A6000, and 252 GB RAM. Training utilized only one of the two GPUs.
List downloaded from here.
'A word will be encoded differently whether it is space- or not. Downloaded from here.
14

---

We follow the experimental setting and dataset provided by Wang et al. [43], consisting of 10K Sudoku puzzles, split into 9K training examples, and 1K test samples, all puzzles having 10 missing entries. Our model consists of an RNN with an input size of 9, a hidden dimension of 128, 5 layers, tanh nonlinearity and dropout of 0.2. We used Adam with default Py PyTorch parameters and learning rate of 3e-4. We did a grid search over the pseudo-semanti loss weight in the values {0.01, 0.05). Our constraint disallows any solution in which the rows, columns and square are not unique.
D Warcraft Shortest Path
The experiments were run server with AMD EPYC 7313P 16-Core Processor @ 3.7GHz, NVIDIA RTX A6000, and 252 GB RAM. Training utilized only one of the two GPUs. We follow the experimental setting and dataset provided by [33]. Our training set consists of 10, 000 terrain maps curated using Warcraft II tileset. We use a CNN-LSTM model for this task. Precisely, a ResNet-18 encodes the map an embedding of dimension 128. An LSTM with layer, and hidden size of 512 then predicts the next edge in the shortest path conditioned on the input map and all previous edges. We used Adam with the default Py parameters and a learning rate of 5e-4. We did grid search over the pseudo-semantic loss weight in the values {0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1}. Our constraint disallows any prediction not a valid path connecting the upper left and lower right vertices.
E Broader Impact
The work presented in this paper, pseudo-semantic loss, has significant potential for positive socictal impact. Neuro-symbolic learning moves us closer to models whose behavior is trustworthy, explainable and fair. This extends critical domains such autonomous driving, medical diagnosis and financial planning to name a few. Large language models have recently seen an exponential increase in popularity, crossing the threshold of being mere research tools into products that are utilized by the general public. Unfortunately, the same expressivity that renders these models so powerful also puts them outside the reach of current neuro-symbolic approaches. Our proposed approach, aseudo-semantic loss, tackles exactly this problem, and does so efficiently. Namely, brings neuro-symbolic learning, and the promise of trustworthy, explainable and fair models to LLMs. And we have shown the merits of our approach when applied to L.LM detoxification. We must, however, also be cognizant of the potential negative societal impacts. More precisely, in very much the same way that our approach can be used to steer the model away from toxic, or generally inconsistent, outputs can also be used steer the model towards toxic and harmful generations.
F
Limitations
Our approach assumes access to hard symbolic knowledge. Such knowledge is not always available, and is not always easy to capture and express symbolically. Our approach also currently only supports hard symbolic knowledge, whereas often times we might be interested in distributional soft constraints that only hold in expectation. Our approach, while tractable, requires a sufficient amount of memory in order to construct the local distribution centered around the model sample. Lastly, our approach approximates the distribution of the model locally, and although we have empirically shown it's effectiveness on three different tasks, ''s not clear what guarantees can derive in general. We view addressing all of the above limitations as very interesting and impactful future endeavors.
15

---

G Example Generations
Warning! The following contains explicit and/or triggering content.
Example prompted generations of all the approaches considered can be found at https: //ghthub. caan/UULA-SSarrrL/sadddSlS. TaaerA///souddSS//oo/mmaiiiiii htt.l///aiinggneratiis... generations pdf
16


Reviews:
[{"review_id": "nhsSxNvxMD", "reviewer": "Reviewer_sCK6", "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.", "questions": "I don't have a question in this stage.", "limitations": "I don't see the discussion of limitations in this paper.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 1, "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.\n* 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.\n\n[1] NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints (NAACL 2021)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response.\n\n[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.]\n\nThe figure is just meant to convey our approach in broad strokes. An autoregressive model defines a distribution over the output space, shown in black. It places probability mass on sentences that both violate (white area under curve) as well as those that satisfy the constraint (pink area under curve). Our aim throughout the paper is to shift the distribution, so the autoregressive model places all its mass only on sentences that satisfy the constraint. Typically, we can achieve this by simply maximizing the probability of the constraint w.r.t the output distribution. The problem is computing the probability of the constraint w.r.t the output distribution is intractable when the distribution is autoregressive. What we propose is a local, tractable approximation of the original distribution (shown in grey) under which we can approximate the probability of the constraint. It is local in the sense of being correct within a neighborhood of a sample (the red cross). This is similar to how we compute a linear approximation of a function about a point, except here we have a discrete function with no analytical form.\n\n[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.]\n\nThere has indeed been numerous work on controllable text generation which we’re happy to acknowledge in the related works section of our camera-ready.  We would like to point out, however, that when specifying “learning with constraints”, we mean so in the specific sense of learning to maximize the training data likelihood, through cross-entropy, subject to some constraint. This can be achieved through the addition of a *regularization* or *penalty* term that *also* ensures the network's outputs satisfy the constraint. In such a setting, all the work that we are aware of only considers fully-factorized distributions. Please see the general response regarding how learning with constraints relates to constrained generation.\n\n[“I don't see the discussion of limitations in this paper.”]\n\nPlease see section F of the appendix for some potential limitations of our proposed approach.\n\nWe are happy to engage with the reviewer regarding any misunderstandings regarding\nthe paper's contribution as well as the presentation. Our hope is that this paper is accessible to a wide audience"}, {"review_id": "9gep27jRSL", "reviewer": "Reviewer_5z8g", "summary": "The method proposes as new neuro-symbolic loss for autoregressive models. \n\nThe proposed method approximates the ture expectation of the constraint satisfaction using a pseudo likelihood term computed only in a neighbourhood of the node.", "questions": "1) How is the LSTM used to model p(y_i | y_{<i})?\n2) Do you have any intuition / experiment on how an RNN/LSTM behaves with pure semantic loss?\n3) How is the proposed method linked to the use of pseudolikelihoods in statistical relational models (e.g. MLN learning with pseudolikehood?)", "limitations": "No explicit limitations are mentioned in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the paper proposes an interesting extension of neurosymbolic methods on auto-regressive models addressing some tractability problems. \n\nMoreover, 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.\n\n\nMy 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the valuable feedback and for engaging with our work. We are particularly happy with their appreciation for the language detoxification experiment, which we believe has great potential for real-life impact.\n\n[\"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\"]\n\nIt is true that the outputs $y_i$ are \\emph{conditionally independent} given the hidden states $h_i$. This, however, does not imply that $p(y_1, \\ldots, y_n) \\neq \\prod_i p(y_i | y_{<i})$.\nIt also does not buy us much since we do not have oracle access to the hidden states $h_i$ ahead of time. Rather, for some weight matrices $\\mathbf{U}, \\mathbf{W}$ and $\\mathbf{V}$ we can only obtain $\\mathbf{h_i} = g(\\mathbf{U} \\mathbf{h_{i-1}} + \\mathbf{W} \\mathbf{e_i})$ and consequently $p(y_{i} | y_{t-1}) = \\mathsf{Softmax}(\\mathbf{V} \\mathbf{h_i})$ only having processed $h_{i-1}$, and inductively, the entire prefix. Intuitively, the main computational hurdle remains: the probability $y_i$ is dependent on the entire prefix \n$y_0, \\ldots, y_{i-1}$. Computing the probability of a Boolean constraint constituting of even a single term asserting e.g. $y_i$ = dog, which reduces to computing the \\emph{marginal} probability $p(y_i=\\text{dog})$ requires summing over all $50256^{i-1}$ prefixes ($50256$ being the number of possible tokens at every time step) , a summation which is highly intractable even for a prefix of size $10$.\n\n[\"How is the LSTM used to model $p(y_i | y_{<i})$?\"]\n\nConsequently, the RNN/LSTM is trained in precisely the same manner as you would train an autoregressive model i.e. we simply train the model to minimize the error in predicting the true next word in the training sequence given the prefix, using cross-entropy as the loss function (see e.g. https://web.stanford.edu/~jurafsky/slp3/9.pdf, section 9.2 for a treatment of RNNs as language models). The only modification is that we also condition on the input (Warcraft map image and the input Sudoku puzzle in the shortest path and Sudoku tasks, respectively) in a fashion very similar to CNN-BiLSTM models, throughout the entire sequence.\n\n[\"Do you have any intuition / experiment on how an RNN/LSTM behaves with pure semantic loss?\"]\n\nOne intuition to our approach is that it is the analog of a first-order approximation to discrete functions with no analytical form. As such, our approach makes use of first-order information to approximate the value of the discrete function about a given point, in our case the model sample. One naïve approach to employing semantic loss would be to assume the distribution is a fully-factorized one and use the the conditional probabilities of the model sample $p(y_i | y_{<i})$ as marginal probabilities $p(y_i)$. It is unclear, however, what the semantics of the loss would be in this case, or in what way the number it yields relates to the original quantity. Nonetheless, on attempting to train with semantic loss, we achieved an exact match of $63$% and a consistency of $75$%, the former metric being slightly better than the baseline and the latter being slightly worse (see numbers in paper)\n\n[How is the proposed method linked to the use of pseudolikelihoods in statistical relational models]\n\nOur approach was inspired by such methods, although the end goal is at odds in a sense.\nPrecisely, in statistical relational learning, maximizing the pseudolikelihood in place of the likelihood sidesteps the computation of the, very often intractable, partition function.\nIn our case, however, the partition function *is* precisely what we're interested in computing, or at the very least estimating. Towards that end, the role of pseudolikelihood is as a stepping stone to help “massage” the autoregressive distribution into a form that is amenable to the reuse of computations, in a fashion similar to dynamic programming. To see what we mean by reuse of computations, consider e.g. in the easiest case, when we have a fully-factorized distribution, the probability of every sentence where $y_i$ is true depends on the same probability $p(y_i)$.\n\n[“No explicit limitations are mentioned in the paper.”]\n\nPlease see section F of the appendix for some potential limitations of our proposed approach.\n"}, {"review_id": "Ee6mfVCUDQ", "reviewer": "Reviewer_FKar", "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: \n\n1. Warcraft shortest path: the task is to generate a minimum-cost path from the upper left to the lower right vertices.\n\n2. Sudoku: the task is to generate a solution to a given partially filled sudoku \n\n3. LLM detoxification: the task is to steer away the LLM model from toxic prompted-generations.  ", "questions": "- I found the entire paper very clear. However, I have a doubt about this step at equation 7. Why can you write: \n$\\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)]$?\nCan you give some more details about this step? \n\n- 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.  \n\n- 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?\n\n- 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. \n\n- Minor: in the related work it shouldn't be HMCCN but C-HMCNN\n\nP.S. I really like the paper, if all the questions can be answered well, then I will increase the score. ", "limitations": "See weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is very well written and easy to follow. \n\n- The introduced approach is very interesting and presents improvements in the experiments. \n\n- 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. \n\n- On this note, it might be interesting to see how their method performs against such methods in the LLM detoxification task. \n\n- 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\".\n\nReferences:\n\n[1] Meng et al. Controllable text-generation with neurally-decomposed oracle, NeurIPS 2022. \n\n[2] Lu et al. NeuroLogic Decoding: (Un)supervised Neural Text generation with predicate logic constraints. ACL 2022\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments.\n\nWe are delighted they found the paper easy to follow, the problem to be timely, and the approach to be interesting.\n\n[\"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.\"]\n\nThere has indeed been numerous work on controllable text generation which we’re happy to acknowledge in the related works section of our camera-ready.  We would like to point out, however, that when specifying “learning with constraints”, we mean so in the specific sense of learning to maximize the training data likelihood, through cross-entropy, subject to some constraint. This can be achieved through the addition of a *regularization* or *penalty* term that *also* ensures the network's outputs satisfy the constraint. In such a setting, all the work that we are aware of only considers fully-factorized distributions. Please see the general response regarding how learning with constraints relates to constrained generation.\n\n\n[“I think that the current title is a bit misleading. Not all deep generative models are auto-regressive.\"]\n\nIt is true that not all deep generative models are auto-regressive. Our intention was to hint at the fact that our approach is applicable to any likelihood-based model where the output distribution is not fully-factorized. However, we agree that maybe “auto-regressive” would be more befitting, especially given our experiments.\n\n[“However, I have a doubt about this step at equation 7”]\n\nThis step can be understood as performing the analogous of a first-order Taylor series expansion of a discrete function with no analytical form about a point of interest, the point here being a model sample.\n\n[“In the example, suppose that instead of having generated abc, the model 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?”]\n\nThey would be all possible completions of \"_ love dogs\", \"I _ dogs\" and \"I love _\", where _ denotes a blank to be filled in. We can, however, save some computations by only considering the tokens of interest. More specifically, in the detoxification experiment, only the ~800 possibly-toxic tokens in addition to a single ``non-toxic'' token to fill in each blank.\n\n[“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.”]\n\nThese are unfortunate typos that will be corrected in the camera-ready. We will map seq_len and num_cats to seq and cats, respectively.\n\nRegarding expand, you are absolutely correct, it does only operate on singleton dimensions, meaning our code would require unsqueezing the last two dimensions before calling expand, which we elected to omit for brevity's sake. But we do agree that it makes sense to present working PyTorch code, and will modify the code accordingly.\n\n[“Again in the example, you use a constraint with Cat, Dog and Animal as variables. Can you rewrite it using a,b,c”]\n\nVariable A maps to Cat, variable B maps to dog and variable C maps to Animal. We will make the mapping clear and/or modify the example accordingly.\n\n[“Also, in appendix A, it would be nice to have the step by step guide showing how the circuit is built from the constraint.”]\n\nThank you for the suggestion. We will add it to the camera-ready.\n\n[“Minor: in the related work it shouldn't be HMCCN but C-HMCNN”]\n\nWill make sure to fix it in the camera-ready.\n\nWe are happy to answer any more questions or concerns you might have.\n"}, {"review_id": "Nu2aLq8uvP", "reviewer": "Reviewer_P5zX", "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.\n\n", "questions": "Q1: Not sure I understood how your approach reuses sub-problems. Could you give examples from the tasks you use? \n\nQ2: Could you give examples of reducing toxicity by looking at samples from the GPT model?\n\n", "limitations": "the authors adequately addressed the limitations", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: The problem of adding constraints with semantic losses is important, and has a clear impact on relevant problems, such as reducing toxicity.\n\nS2: The approximations in the paper are sound and seem to be of good fidelity and low deviation from the ground truth. \n\nS3: 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.\n\nW2: 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?\n\nW3: 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. \n\nMinor: \n\nM1: line 115 - do you mean $\\mathbf{w}_i$ in the softmax? I do not see where the index $j$ comes from.\n\nM2: line 9 in Algorithm 1 - I think you mean \"seq\" vs, \"seq_len\" and \"cats\" vs. \"num_cat\"?\n\nM3: line 323: one again <- once again.\n\nM4: line 508: generate 100k <- generate 100k samples (or generations)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for engaging with our work and their valuable feedback. \n\nWe are happy to see them acknowledge the importance of the problem tackled and the value of both the proposed approximation and experimental evaluation.\n\n[“ It's not clear how one relates A, B, and C to the constraint with Cat, Animal, and Dog.“]\n\nWe agree that a mapping from the variable A, B and C to Cat, Animal and Dog is missing.\nWe will modify the example to either make the mapping explicit, or only use one or the other.\nThe implied mapping is that variable A maps to Cat, variable B maps to dog and variable C maps to Animal. We will make the mapping clear and/or modify the example accordingly.\n\n[“The authors need to give more examples of constraints, logical circuits”]\n\nA logical constraint is simply any sentence in Boolean logic. For instance, a very simple constraint might be $y_3, = \\text{dog}$ which simply states that all sentences must have as their third token “dog”. In the example we presented, our constraint simply asserts that if I predict an “cat” or “dog”, I necessarily need to predict an animal (every “cat” is an animal, and every “dog” is an animal; If I acknowledge the existence of either in an image, logic necessitates that I also acknowledge the existence of an animal in the image.\n\nA logical circuit is  a computational graph for compactly representing solutions of  a constraint, that is all possible assignments where the constraint holds true. There every AND node represents a (partial) solution to the constraint and every OR node represents a distribution over mutually exclusive and exhaustive (partial) solutions. More concretely, focusing on the upper-right AND node, we can see that it represents the Boolean function $$(\\text{Animal} \\lor \\lnot \\text{Animal}) \\land (\\lnot \\text{Cat} \\lnot \\text{Dog})$$, meaning if we predict neither a dog nor a cat, then we're free to predict or not predict an animal.\n\n[“how the loss encourages the reuse of sub-problems”]\n\nWe simply mean the solution of a problem depends on already-computed solutions to other subproblems in a dynamic-programming fashion. Take for example the problem of choosing $k$ out of $n$ elements which has a simple structurethe probability of selecting $k$ out of $n$ elements is simply the probability of selecting $k-1$ out of $n-1$ elements AND selecting the current element OR selecting $k$ out of $n-1$  elements AND NOT selecting the current element.\n\n[“The choice of numbers at the leaves is arbitrary (should be discussed). The computation of the probabilities on the left is not clear”]\n\nBack to our example, the numbers on the second row on the left, denoted by an arrow \"eval\" are the likelihood assigned by the auto-regressive model to these joint assignments i.e. they are the output of a neural network. The row below that, denoted by an arrow \"norm\" refers to the conditional probabilities, obtained through normalizing the joint by the marginal e.g. $p(a|b,c) = p(a,b,c) / p(b,c)$ on the right, the only numbers we supply are those at the leaves $A, \\lnot A, B, \\lnot B, C$ and $\\lnot C$ .These correspond exactly to the conditionals obtained on the last row on the left.\n\n[“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?”]\n\nThe size of the logical circuit can indeed worst-case grow exponentially in the size of the constraint. That being said, there are some problems that exhibit a surprising amount of structure theoretically guaranteeing compact circuit representations, examples of which are the $k$-subset constraint and perfect matching on planar graphs. For many other problems, we can obtain compact logical circuits for many instances of interest e.g. entity-relation extraction, NLI transitivity, MNIST addition, and many many more. There are cases in practice, of course, when the circuits grow too much beyond what is computational feasible, in which case we can resort to approximating the logical circuit [1, 2] which should work seamlessly with our distributional approximation.\n\n[“What more complicated problems should we expect to solve by using the proposed pseudo-semantic loss?”]\n\nWe expect pseudo-semantic loss to be of use in any task where we have domain knowledge relating the outputs of a classifier (also known as structured-prediction problems), and where we have that the output distribution induced by the classifier goes beyond the fully-factorized distribution.\n\n[“other constraints for toxicity? \"]\n\nWe have not explored other constraints for toxicity. It is generally not easy to capture toxicity using a logical constraint as the trait of being toxic can be attributed to latent factors beyond just the presence of certain keywords e.g. a condescending tone. Instead, our hope was that steering the model's distribution from sentences containing toxic words would serve to steer it away from toxic sentences in general as both are typically correlated. This is a direction that we hope to explore in future work.\n\n[“examples of reducing toxicity”]\n\nPlease see the PDF included in the general response.\n\n[“Typos”]\n\nThank you for pointing out the typos. We will be sure to correct them in the camera-ready.\n\nReferences:\n\n[1] Kareem Ahmed, Kai-Wei Chang and Guy Van den Broeck. 2023. Semantic Strengthening of Neuro-Symbolic Learning. In Proceedings of International Conference on Artificial Intelligence and Statistics (2023).\n\n[2] Robin Manhaeve, Giuseppe Marra, Luc De Raedt. 2021. Approximate Inference for Neural Probabilistic Logic Programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning.\n"}]

Author rebuttal:
We would like to thank all the reviewers for their valuable feedback towards improving our paper.

We are happy to see the reviewers' excitement regarding the posed problem, the proposed solution as well as the empirical evaluation, with an emphasis on the LLM detoxification experiment.

There have been several comments regarding controllable language generation and its relevance to our approach. There has indeed been a lot of work on controllable text generation which we’re happy to acknowledge and discuss in our camera-ready. We would like to point out, however, that both approaches are not at odds. Indeed, they have been shown to be *complementary* by previous work, both old [1] and new [2] [3], theoretically and empirically, with methods combining both paradigms attaining the highest performance. In the specific context of language detoxification, [4] has shown complementing domain-adaptive training, such as our approach, with decoding-time constraints to yield the best results.
It is, however, non-trivial to generalize such decoding methods beyond *non-lexical constraints* e.g. Sudoku or Warcraft, which seem to be the focus of all such approaches.

Reviewers have also suggested adding a step-by-step construction of the logical circuit in our examples, which we are happy to add in the camera-ready.

We will now address each reviewer's individual concerns.

References

[1] Ming-Wei Chang, Lev Ratinov, and Dan Roth. 2007. Guiding Semi-Supervision with Constraint-Driven Learning. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics.

[2] Kareem Ahmed, , Eric Wang, Guy Van den Broeck and Kai-Wei Chang. 2021. Leveraging Unlabeled Data for Entity-Relation Extraction through Probabilistic Constraint Satisfaction. ArXiv abs/2103.11062.

[3] Kaifu Wang, Hangfeng He, Tin D. Nguyen, Piyush Kumar and Dan Roth. 2023. On Regularization and Inference with Label Constraints. In Proceedings of the 40th International Conference on Machine Learning.

[4] Boxin Wang, Wei Ping, Chaowei Xiao, Peng Xu, Mostofa Patwary, Mohammad Shoeybi, Bo Li, Anima Anandkumar and Bryan Catanzaro. 2022. Exploring the Limits of Domain-Adaptive Training for Detoxifying Large-Scale Language Models. ArXiv abs/2202.04173.

Meta-review: This paper proposes a new approach for training auto-regressive models (e.g., language models) with logical constraints. A new neuro-symbolic loss is developed with various approximations to make the loss tractable and efficient for training. Evaluated on three tasks (Warcraft shortest path, Sudoku, and LM detoxification), the approach shows improvements. The reviewers acknowledged the problem of adding constraints into auto-regressive model training is important, and the proposed loss and approximations are sound. 

A major concern is that the paper claimed itself to be “*the first approach to learning with constraints under auto-regressive generative models*”, which is probably not true as pointed out by the reviewers. There are previous general approaches of learning with constraints, such as posterior regularization [1-4] (e.g., [4] applied non-factorizable constraints on training auto-regressive text generation models). Additionally, as again pointed out by the reviewers, there are also a bunch of works of inference-time control of language model generations, such as [5, 6], where [5] studies specific logical constraints and [6] studies general forms of constraints, both applying to auto-regressive LMs. Though these works focus on adding constraints during inference instead of training, they are very relevant to the submission and worth thorough discussion.



[1] Posterior Regularization for Structured Latent Variable Models (JMLR 2010)

[2] Prior Knowledge Integration for Neural Machine Translation using Posterior Regularization (ACL 2017)

[3] A Survey of Knowledge-Enhanced Text Generation (ACM Computing Survey, 2022)

[4] Deep Generative Models with Learnable Knowledge Constraints (NeurIPS 2018)

[5] NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints (NAACL 2021)

[6] COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics
Decision: Accept (poster)