A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints

Kareem Ahmed, Kai-Wei Chang, Guy Van den Broeck

Introduction

Neuro-symbolic AI represents a promising frontier in machine learning, aiming to synthesize the pattern-recognition capabilities of neural networks with the rigorous, rule-based reasoning of symbolic logic. A common approach to this integration is the use of a Semantic Loss (SL), which penalizes a model when its output distribution violates predefined logical constraints. However, a significant computational barrier has historically limited the application of Semantic Loss: it typically assumes that model outputs are fully factorized (independent).

Modern state-of-the-art architectures, such as Transformers and LSTMs, are autoregressive, meaning each output step is conditioned on previous steps. In these dependent models, calculating the probability that a complex logical constraint is satisfied is a #P-hard problem. This complexity has effectively excluded autoregressive models from many neuro-symbolic training techniques. This paper, presented at NeurIPS 2023, introduces Pseudo-Semantic Loss (PseudoSL), a novel training objective designed to overcome this bottleneck.

The Challenge: Autoregression and #P-Hardness

In a standard Semantic Loss framework, the objective is to maximize the probability that a model's output satisfies a constraint. If the outputs are independent, this probability is easy to compute. However, in an autoregressive model, the joint probability distribution is a complex chain of conditional probabilities. To determine if a constraint (e.g., "no two numbers in a Sudoku row can be the same") is satisfied across the entire distribution, one must sum over an exponential number of possible sequences. This makes the gradient of the loss function computationally infeasible to calculate for any non-trivial constraint.

Methodology: The Pseudo-Semantic Loss

The authors propose bypassing the global complexity of the autoregressive distribution by focusing on a local, factorized approximation. The PseudoSL framework operates through five key stages:

  1. Sampling: The model generates a candidate output (e.g., a sequence of moves or a string of text).
  2. Local Perturbation: The algorithm examines the "neighborhood" of this sample, specifically looking at outputs that differ by only a single element (a Hamming distance of 1).
  3. Pseudolikelihood Approximation: The complex autoregressive distribution is approximated using a pseudolikelihood distribution centered on the generated sample. Crucially, this approximation is factorized, meaning the individual components are treated as independent within this local window.
  4. Tractable Logical Circuits: The logical constraints are compiled into tractable symbolic representations, such as Sentential Decision Diagrams (SDDs). Because the local approximation is factorized, the probability of constraint satisfaction can be computed in linear time relative to the size of the circuit.
  5. Optimization: The model is penalized if the probability mass in this local "cloud" violates the symbolic logic. By steering the local neighborhood toward consistency, the entire distribution is effectively guided toward satisfying the constraints.

Experimental Evaluation

The researchers evaluated PseudoSL across three diverse domains to test its versatility and effectiveness.

1. Sudoku

Using a dataset of 10,000 puzzles, the task required an RNN to fill in 10 missing entries autoregressively. While a standard RNN achieved 22.4% exact match accuracy, the PseudoSL-augmented RNN reached 28.2%, outperforming both the baseline and specialized convolutional architectures.

2. Warcraft Shortest Path

In this task, a model predicts a minimum-cost path across a terrain map. The logical constraint is structural: the predicted edges must form a continuous, valid path. PseudoSL improved the consistency of a CNN-LSTM from 76.6% to 79.0%, while simultaneously improving the accuracy of the shortest path prediction.

3. LLM Detoxification

To test the method on large-scale language modeling, the authors applied PseudoSL to GPT-2 using the REALTOXICITYPROMPTS dataset. By treating a list of toxic words as a hard logical constraint ("do not generate these words"), PseudoSL reduced the toxicity probability from 34.11% to 9.20%. Notably, it maintained higher fluency (lower perplexity) than existing state-of-the-art detoxification methods like SGEAT.

Key Insights

The success of PseudoSL rests on the insight that locality is sufficient. One does not need to solve the #P-hard problem of the entire probability space to improve a model's logical consistency. By enforcing logic in the immediate vicinity of the model's own samples, the training process provides a clear signal for the model to move away from inconsistent regions of the latent space. Furthermore, the use of pseudolikelihood acts as a mathematical bridge, allowing researchers to apply tools designed for independent models to the more powerful dependent models used in modern AI.

Limitations and Future Directions

While PseudoSL represents a major step forward, several challenges remain:

  • Constraint Type: The current framework is optimized for "hard" symbolic constraints (True/False) and does not yet support probabilistic or "soft" logic.
  • Computational Overhead: Evaluating multiple perturbations for each sample increases memory usage. In the LLM experiments, the authors mitigated this by using a "top-k" approach to limit the number of perturbations.
  • Circuit Compilation: Compiling complex logic into SDDs can still be a bottleneck, as the compilation process itself can be exponential in the worst case.

Future research may explore applying this local approximation technique to other generative architectures beyond autoregressive models or extending the framework to handle more nuanced, non-binary distributional constraints.

Summary updated

BibTeX
@inproceedings{ahmed2023pseudo,
  author = {Kareem Ahmed and Kai-Wei Chang and Guy Van den Broeck},
  title = {{A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=hVAla2O73O},
}
Figure