The Scaling Properties of Implicit Deductive Reasoning in Transformers

2026/05/31 by Enrico Vompa, Tanel Tammet
#cs.AI #cs.CC #cs.LO #cs.SC

paper · pdf

Abstract

We investigate the scaling properties of implicit deductive reasoning over Horn clauses in depth-bounded Transformers. By systematically decorrelating provability from spurious features and enforcing algorithmic alignment, we find that in sufficiently deep models with a bidirectional prefix mask, implicit reasoning approaches explicit CoT performance across graph topologies and problem widths, though CoT remains necessary for depth extrapolation.

Citations

• How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?
• FlowRL: Matching Reward Distributions for LLM Reasoning
• Parallel-R1: Towards Parallel Thinking via Reinforcement Learning
• The Non-Linear Representation Dilemma: Is Causal Abstraction Enough for Mechanistic Interpretability?
• ProtoReasoning: Prototypes as the Foundation for Generalizable Reasoning in LLMs
• Magistral
• Qwen3 Technical Report
• Grokking in the Wild: Data Augmentation for Real-World Multi-Hop Reasoning with Transformers
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
• DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning
• On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery
• Do LLMs Overcome Shortcut Learning? An Evaluation of Shortcut Challenges in Large Language Models
• Transformers Provably Solve Parity Efficiently with Chain of Thought
• To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning
• The Llama 3 Herd of Models
• FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering
• Your Transformer is Secretly Linear
• The Illusion of State in State-Space Models
• How Transformers Learn Causal Structure with Gradient Descent
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
• Premise Order Matters in Reasoning with Large Language Models
• The Linear Representation Hypothesis and the Geometry of Large Language Models
• How do Language Models Bind Entities in Context?
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
• Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective
• Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning
• Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting
• On the Expressivity Role of LayerNorm in Transformers' Attention
• Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizes
• Eliciting Latent Predictions from Transformers with the Tuned Lens
• Looped Transformers as Programmable Computers
• Transformers Learn Shortcuts to Automata
• Governance Architecture for Neural Network Superposition: A Structural Solution to Hallucination via Routing and Interference Filtering
• Faithful Reasoning Using Large Language Models
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers
• On the Paradox of Learning to Reason from Data
• What Language Model Architecture and Pretraining Objective Work Best for Zero-Shot Generalization?
• Locating and Editing Factual Associations in GPT
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• Saturated Transformers are Constant-Depth Threshold Circuits
• RoFormer: Enhanced Transformer with Rotary Position Embedding
• ProofWriter: Generating Implications, Proofs, and Abductive Statements\n over Natural Language
• Measuring Association Between Labels and Free-Text Rationales
• WT5?! Training Text-to-Text Models to Explain their Predictions
• Shortcut learning in deep neural networks
• Gradient Surgery for Multi-Task Learning
• Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
• Learning the Difference that Makes a Difference with Counterfactually-Augmented Data
• SGD on Neural Networks Learns Functions of Increasing Complexity
• Universal Transformers
• Deep learning generalizes because the parameter-function map is biased towards simple functions
• Attention Is All You Need
• Understanding intermediate layers using linear classifier probes
• Lower Bounds for Sparse Recovery
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• Decoding by Linear Programming
• Hypertree Decompositions and Tractable Queries
• The Expressive Power of Transformers with Chain of Thought
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

Related

• Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
• How do Transformers Learn Implicit Reasoning?
• Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability
• Implicit Reasoning in Transformers is Reasoning through Shortcuts