Introduction
Deep learning models, particularly Transformers, have demonstrated remarkable performance across a variety of natural language tasks. However, it remains an open question whether these models are genuinely "reasoning" or merely relying on superficial pattern matching. A critical test for true reasoning is systematic generalization: the ability to take known components and combine them in novel, complex ways that were never encountered during training.
This paper investigates the systematic generalization abilities of Transformer language models on logical reasoning tasks. Specifically, the authors focus on "soft theorem-proving"—using natural language to describe logical steps. By forcing a model to generate an interpretable, step-by-step proof before answering a complex relational query, the researchers aim to understand how different logical strategies affect performance and whether explicit proof generation aids in generalization.
Methodology and Datasets
The researchers fine-tuned a Transformer decoder to treat reasoning as a sequence-to-sequence problem. The model receives a "story" (a set of facts) and a "query," and must generate a "proof" followed by the final "answer."
The study utilizes the CLUTRR (Compositional Language Understanding and Text-based Relational Reasoning) benchmark, which consists of stories detailing family relationships (e.g., "Alice is the daughter of Bob"). Tasks are categorized by complexity "levels" based on the number of reasoning steps required to deduce the answer.
The core experiment compares five distinct Proof Resolution Strategies:
- Short-proof (sp): Forward-chaining; starts from known facts and moves toward the answer using the minimum required steps.
- Short-proof-reversed (spr): Backward-chaining; starts with the target goal and works backward to the supporting facts.
- Long-proof (lp): Forward-chaining but exhaustive; the model generates all possible intermediate facts.
- Long-proof-reversed (lpr): Backward-chaining and exhaustive.
- No-proof (np): A baseline where the model is trained to output the answer directly without generating a proof.
Models were trained on complexity levels 2, 4, and 6. They were then tested on levels 3 and 5 to measure interpolation, and levels 7 through 10 to measure extrapolation (length generalization).
Key Findings
The Extrapolation Challenge
Models performed near-perfectly on unseen problems of the same or lesser complexity as the training set (Levels 2–6). However, performance dropped sharply when models were faced with Level 7+ problems, highlighting a significant struggle with length extrapolation.
Backward vs. Forward Chaining
The direction of reasoning significantly impacted performance. Models utilizing backward-chaining strategies (spr, lpr) generally achieved higher answer accuracy than their forward-chaining counterparts. The authors hypothesize this is because backward-chaining forces the model to generate the answer at the beginning of the proof, anchoring its subsequent reasoning. Conversely, while backward-chaining yielded better final answers, models found it easier to generate logically consistent (valid) proofs using forward-chaining, as it naturally follows the chronological flow of the provided story.
The Interpretability Trade-off
Surprisingly, the "No-proof" (np) baseline often generalized better to longer reasoning chains than models forced to generate their own proofs. This suggests an "interpretability trade-off": Transformers may develop highly efficient internal reasoning strategies that are actually hindered or bottlenecked when the model is forced to translate its internal state into a rigid, step-by-step natural language proof.
Exhaustive Training and Language Noise
The study also found that models trained on "long proofs" (inferring every possible relation in the story) generalized better than those trained only on the shortest path to the answer. Furthermore, performance was significantly lower on the "amt" dataset (noisy, human-written natural language) compared to the "facts" dataset (clean, templated sentences), indicating that parsing and de-noising natural language remains a major hurdle for logical reasoning.
Limitations and Future Directions
The primary limitation observed is length generalization. Transformers still struggle to maintain logical consistency over long sequences, often exhibiting a recency or primacy bias that suggests they are not yet reasoning in a truly abstract, position-independent manner. Interestingly, when the model was provided with a perfect, human-generated proof at test time, its accuracy on Level 10 problems jumped significantly. This proves the model can use logic to find an answer; the failure point is generating the long logic chain itself.
To bridge this gap in systematic generalization, the authors suggest future work should explore neuro-symbolic methods—combining the flexible pattern-matching strengths of neural networks with the rigid, reliable logic of symbolic AI.
Summary updated