# Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 62 references that are in the map.
- First posted on arXiv 16 Dec 2021.

## Builds on (most cited first, 30 of 35)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [SuperGLUE: A Stickier Benchmark for General-Purpose Language Understanding Systems](https://mlsanity.com/paper/1905.00537/) (2019)
- [Beyond Accuracy: Behavioral Testing of NLP models with CheckList](https://mlsanity.com/paper/2005.04118/) (2020)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Annotation Artifacts in Natural Language Inference Data](https://mlsanity.com/paper/1803.02324/) (2018)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [AllenNLP: A Deep Semantic Natural Language Processing Platform](https://mlsanity.com/paper/1803.07640/) (2018)
- [ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language](https://mlsanity.com/paper/2012.13048/) (2020)
- [Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks](https://mlsanity.com/paper/1502.05698/) (2015)
- [CLUE: A Chinese Language Understanding Evaluation Benchmark](https://mlsanity.com/paper/2004.05986/) (2020)
- [Transformers as Soft Reasoners over Language](https://mlsanity.com/paper/2002.05867/) (2020)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019)
- [oLMpics -- On what Language Model Pre-training Captures](https://mlsanity.com/paper/1912.13283/) (2019)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Learning to Compose Neural Networks for Question Answering](https://mlsanity.com/paper/1601.01705/) (2016)
- [Text Modular Networks: Learning to Decompose Tasks in the Language of Existing Models](https://mlsanity.com/paper/2009.00751/) (2020)
- [Probing Natural Language Inference Models through Semantic Fragments](https://mlsanity.com/paper/1909.07521/) (2019)
- [PRover: Proof Generation for Interpretable Reasoning over Rules](https://mlsanity.com/paper/2010.02830/) (2020)
- [Measuring Systematic Generalization in Neural Proof Generation with Transformers](https://mlsanity.com/paper/2009.14786/) (2020)
- [Making Neural Programming Architectures Generalize via Recursion](https://mlsanity.com/paper/1704.06611/) (2017)
- [Critical Thinking for Language Models](https://mlsanity.com/paper/2009.07185/) (2020)
- [Do Neural Models Learn Systematicity of Monotonicity Inference in Natural Language?](https://mlsanity.com/paper/2004.14839/) (2020)
- [Sensitivity as a Complexity Measure for Sequence Classification Tasks](https://mlsanity.com/paper/2104.10343/) (2021)
- [Can Neural Networks Understand Logical Entailment?](https://mlsanity.com/paper/1802.08535/) (2018)

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

- [Complexity-Based Prompting for Multi-Step Reasoning](https://mlsanity.com/paper/2210.00720/) (2022)
- [ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning](https://mlsanity.com/paper/2502.01100/) (2025)
- [Progressive-Hint Prompting Improves Reasoning in Large Language Models](https://mlsanity.com/paper/2304.09797/) (2023)
- [A Comprehensive Survey on Applications of Transformers for Deep Learning Tasks](https://mlsanity.com/paper/2306.07303/) (2023)
- [Natural Language Reasoning, A Survey](https://mlsanity.com/paper/2303.14725/) (2023)
- [Towards LogiGLUE: A Brief Survey and A Benchmark for Analyzing Logical Reasoning Capabilities of Language Models](https://mlsanity.com/paper/2310.00836/) (2023)
- [How are Prompts Different in Terms of Sensitivity?](https://mlsanity.com/paper/2311.07230/) (2023)
- [MindGames: Targeting Theory of Mind in Large Language Models with Dynamic Epistemic Modal Logic](https://mlsanity.com/paper/2305.03353/) (2023)
- [RECKONING: Reasoning through Dynamic Knowledge Encoding](https://mlsanity.com/paper/2305.06349/) (2023)
- [Quantifying and Attributing the Hallucination of Large Language Models via Association Analysis](https://mlsanity.com/paper/2309.05217/) (2023)
- [What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment](https://mlsanity.com/paper/2204.09148/) (2022)
- [GPT-in-the-Loop: Adaptive Decision-Making for Multiagent Systems](https://mlsanity.com/paper/2308.10435/) (2023)
- [A Survey on Symbolic Knowledge Distillation of Large Language Models](https://mlsanity.com/paper/2408.10210/) (2024)
- [Can Transformers Reason in Fragments of Natural Language?](https://mlsanity.com/paper/2211.05417/) (2022)
- [Explainable Verbal Reasoner Plus (EVR+): A Natural Language Reasoning Framework that Supports Diverse Compositional Reasoning](https://mlsanity.com/paper/2305.00061/) (2023)
- [Propositional Logic for Probing Generalization in Neural Networks](https://mlsanity.com/paper/2506.08978/) (2025)
- [Evaluating Robustness of Reasoning Models on Parameterized Logical Problems](https://mlsanity.com/paper/2602.12665/) (2026)
- [Natural Language Satisfiability: Exploring the Problem Distribution and Evaluating Transformer-based Language Models](https://mlsanity.com/paper/2508.17153/) (2025)

## Abstract (arXiv)

Investigating the reasoning abilities of transformer models, and discovering new challenging tasks for them, has been a topic of much interest. Recent studies have found these models to be surprisingly strong at performing deductive reasoning over formal logical theories expressed in natural language. A shortcoming of these studies, however, is that they do not take into account that logical theories, when sampled uniformly at random, do not necessarily lead to hard instances. We propose a new methodology for creating challenging algorithmic reasoning datasets that focus on natural language satisfiability (NLSat) problems. The key idea is to draw insights from empirical sampling of hard propositional SAT problems and from complexity-theoretic studies of language. This methodology allows us to distinguish easy from hard instances, and to systematically increase the complexity of existing reasoning benchmarks such as RuleTaker. We find that current transformers, given sufficient training data, are surprisingly robust at solving the resulting NLSat problems of substantially increased difficulty. They also exhibit some degree of scale-invariance - the ability to generalize to problems of larger size and scope. Our results, however, reveal important limitations too: a careful sampling of training data is crucial for building models that generalize to larger problems, and transformer models' limited scale-invariance suggests they are far from learning robust deductive reasoning algorithms.