Propositional Logic for Probing Generalization in Neural Networks DOI: 10.1613/jair.1.xxxxx

Anna Langedijk, Jaap Jumelet, Willem Zuidema · 2025

Read Propositional Logic for Probing Generalization in Neural Networks DOI: 10.1613/jair.1.xxxxx by Anna Langedijk, Jaap Jumelet, Willem Zuidema (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08978.txt.

Introduction

Anna Langedijk, Jaap Jumelet, and Willem Zuidema probe in 2025 how well three network types generalize on a logic task. Models must find value sets that satisfy logic formulas, a clean test of rule learning. A balanced data set removes shallow patterns and adds unseen operator mixes.

All three types do well on training-like cases, yet unseen patterns trip them in clear ways. Negation poses the top hurdle, above all for transformer models. Adding built-in structure helps transformers apply negation in steps. The finds point to a need for stronger built-in bias when true rule use is the goal.

Catalog record

CREATORAnna Langedijk, Jaap Jumelet, Willem Zuidema
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-08978

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Propositional Logic for Probing Generalization in Neural Networks DOI: 10.1613/jair.1.xxxxx Anna Langedijk, Jaap Jumelet, Willem Zuidema Abstract . 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. 1. Introduction The relation between neural networks and symbolic logic has been a topic of debate for decades, centered around the question whether sub-symbolic systems are able to build up robust representations of symbolic rules by learning from data. With the recent advances in deep learning, and specifically the successes of ‘Large Reasoning Models’ such as OpenAI-O3 and DeepSeek-R1 ( DeepSeek-AI et al. 2025 ) , the debate is shifting. When reasoning capabilities of state-of-the-art language models are rigorously evaluated, researchers report both impressive generalization beyond the training data and unexpected failure models, where the models seem to rely on heuristics and spurious correlations instead of learning generalizable rules ( McCoy et al. 2019 ; Hossain et al. 2020 ; Helwe et al. 2021 ; Mondorf and Plank 2024 ; Wan et al. 2024 ) . These unexpected failures highlight the fact that, at a fundamental level, the reasoning abilities of large neural models remain insufficiently understood. While numerous efforts have been made to study reasoning abilities in the context of LLMs ( Zhang et al. 2022 ; Parmar et al. 2024 ; Liu et al. 2025 ; Hazra et al. 2025 ) , we suspect that a rigorous understanding of reasoning and generalization abilities can only be gained in a fully controlled setting. Similar questions about the intrinsic generalization capacity of neural models have been addressed by testing them on simple synthetic tasks, where one has full control over the training data ( Hupkes and Zuidema 2018 ; Hao et al. 2022 ; Jumelet and Zuidema 2023 ) . Evaluating the behaviour of the model on structurally different (out-of-distribution) test sets can then lead to insights about its systematic capabilities. Furthermore, evaluating model behaviour in such a controlled setting also allows us to investigate the inductive biases of different model architectures ( Abnar et al. 2020 ; Tay et al. 2023 ) . In this paper, we aim to contribute a small step in this research program, with an in-depth case study that uses synthetic training and testing data from the domain of propositional logic. This domain is very restricted, but fundamental within symbolic logic and useful in practice through SAT solving, as well as helpful in revealing the methodological challenges when combining logic and deep learning. More specifically, we study models trained on a sequence-to-sequence task, in which models must generate a possible world that satisfies an input formula in propositional logic. Propositional logic is a well-defined task that requires systematic understanding: propositional variables and operators must be recursively combined to form the meaning of the logical formula. Previous research shows that Transformer models generalize to out-of-distribution data with varying rates of success ( Richardson and Sabharwal 2021 ; Zhang et al. 2022 , e.g.) . As a starting point to our study, we analyze and extend the dataset of propositional logic created by Hahn et al. 2021 . We identify various shortcomings in this dataset and, balance it to avoid learning shortcuts based on the direction of branching. This yields a partitioning of the dataset that allows for systematic investigating of the generalization behavior to unseen categories of formulas. We then use this dataset to analyze the solutions learned by three popular generative deep learning architectures: a Transformer encoder-decoder (with and without tree-position embeddings), a Graph Convolutional Network and a Long-Short Term Memory Network, and compare their performance. Our results show that all architectures can learn to generate highly accurate predictions of variable assignments that satisfy a given logic formula: all setups score \geq 87% correct on the standard test set. However, we also show that such results hide great variation between the three architectures in their abilities to generalize not just to novel formulas, but to novel categories of formulas. More specifically, we examine whether the models can systematically apply their knowledge of seen logical operators to unseen combinations of operators. We rewrite the data in such a way that certain patterns no longer occur, while the output distribution of variable distributions remains the same, which gives the models better chances of succeeding. For example, some models never see the xor -operator applied to the not -operator, and some models never see the not -operator applied to the or -operator. We evaluate their performance on such unseen patterns. We find that all models trained on limited training sets can in most cases generalize to unseen patterns, suggesting that their learned logical representations are at least partially systematic. However, when the unseen combination consists of a negation ( not -operator) applied to another operator, vanilla Transformers fail to generalize to even the simplest sentences containing this combination, demonstrating that specialized negation operators have to be learned for every logical operator. Generalization of the negation operator improves in 2 out of 3 cases when explicit structure is added to the model architecture, in the form of tree-based encodings, recurrence, or graphs. However, unlike for other patterns, their performance on the unseen patterns even in simple sentences still lags behind significantly. These findings cast doubt on whether Transformer-based models can learn systematic representations of negation, a crucial logical operator, from data alone. 2. Related Work Learning logic using neural networks Using neural networks to solve exact problems differs fundamentally from using classical solvers. Neural networks often require large amounts of training data to learn a task, and even then, their outputs are not guaranteed to be correct. Therefore, a practical way to use neural methods for logic is to use them in combination with symbolic solvers. For instance, deep neural networks can be used as a variable selection heuristic ( Yolcu and Póczos [n. d.] , e.g.) . Neurosymbolic methods combine reasoning with learning ( d’Avila Garcez et al. 2022 ) , leveraging the ability of neural networks to find complex statistical patterns, without incorporating their noisy behaviour into the output. In the current paper, however, we focus on attempts to train

Read the complete text