# Propositional Logic for Probing Generalization in Neural Networks

arXiv: https://arxiv.org/abs/2506.08978 · HTML: https://mlsanity.com/paper/2506.08978/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 38 references that are in the map.
- First posted on arXiv 10 Jun 2025.

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Similarity of Neural Network Representations Revisited](https://mlsanity.com/paper/1905.00414/) (2019)
- [Right for the Wrong Reasons: Diagnosing Syntactic Heuristics in Natural Language Inference](https://mlsanity.com/paper/1902.01007/) (2019)
- [Towards Automated Circuit Discovery for Mechanistic Interpretability](https://mlsanity.com/paper/2304.14997/) (2023)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Negated and Misprimed Probes for Pretrained Language Models: Birds Can Talk, But Cannot Fly](https://mlsanity.com/paper/1911.03343/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [Scaling Laws vs Model Architectures: How does Inductive Bias Influence Scaling?](https://mlsanity.com/paper/2207.10551/) (2022)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Beyond Accuracy: Evaluating the Reasoning Behavior of Large Language Models -- A Survey](https://mlsanity.com/paper/2404.01869/) (2024)
- [Language models are not naysayers: An analysis of language models on negation benchmarks](https://mlsanity.com/paper/2306.08189/) (2023)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Teaching Temporal Logics to Neural Networks](https://mlsanity.com/paper/2003.04218/) (2020)
- [SynLogic: Synthesizing Verifiable Reasoning Data at Scale for Learning Logical Reasoning and Beyond](https://mlsanity.com/paper/2505.19641/) (2025)
- [Transferring Inductive Biases through Knowledge Distillation](https://mlsanity.com/paper/2006.00555/) (2020)
- [Symbolic Brittleness in Sequence Models: on Systematic Generalization in Symbolic Mathematics](https://mlsanity.com/paper/2109.13986/) (2021)
- [Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability](https://mlsanity.com/paper/2112.09054/) (2021)
- [ScoNe: Benchmarking Negation Reasoning in Language Models With Fine-Tuning and In-Context Learning](https://mlsanity.com/paper/2305.19426/) (2023)
- [Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition](https://mlsanity.com/paper/2504.03930/) (2025)
- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [Transparency at the Source: Evaluating and Interpreting Language Models With Access to the True Distribution](https://mlsanity.com/paper/2310.14840/) (2023)

## Built on by (most cited first, 1 of 1)

- [Transformer See, Transformer Do: Copying as an Intermediate Step in Learning Analogical Reasoning](https://mlsanity.com/paper/2604.06501/) (2026)

## Abstract (arXiv)

The extent to which neural networks are able to acquire and represent symbolic rules remains a key topic of research and debate. Much current work focuses on the impressive capabilities of large language models, as well as their often ill-understood failures on a wide range of reasoning tasks. In this paper, in contrast, we investigate the generalization behavior of three key neural architectures (Transformers, Graph Convolution Networks and LSTMs) in a controlled task rooted in propositional logic. The task requires models to generate satisfying assignments for logical formulas, making it a structured and interpretable setting for studying compositionality. We introduce a balanced extension of an existing dataset to eliminate superficial patterns and enable testing on unseen operator combinations. Using this dataset, we evaluate the ability of the three architectures to generalize beyond the training distribution. While all models perform well in-distribution, we find that generalization to unseen patterns, particularly those involving negation, remains a significant challenge. Transformers fail to apply negation compositionally, unless structural biases are introduced. Our findings highlight persistent limitations in the ability of standard architectures to learn systematic representations of logical operators, suggesting the need for stronger inductive biases to support robust rule-based reasoning.