PaperlayerView exact revision on arXiv

Source-linked AI summary

The Scaling Properties of Implicit Deductive Reasoning in Transformers

Enrico Vompa, Tanel Tammet

arXiv:2605.04330v2cs.AIcs.CCcs.LOcs.SC

TL;DR

The paper asks how depth-bounded Transformers can perform implicit Horn-clause deduction without relying on spurious features. It decorrelates provability from shortcuts and aligns training with deduction algorithms, finding that sufficiently deep models approach explicit CoT performance across graph topologies and widths, although CoT remains necessary for depth extrapolation.

  • Problem

    Depth-bounded Transformers often learn spurious features instead of faithfully executing deductive algorithms, while their limiting factors for Horn-clause reasoning remain unclear.

  • Method

    The study decorrelates shortcut features from labels and uses the r2 heuristic, bidirectional prefix masking, corrective training, and controllable Horn-clause datasets to enforce algorithmic alignment.

  • Results

    Increasing model depth allows implicit reasoning to approach explicit CoT performance across graph topologies and problem widths.

  • Takeaways & Limitations

    Within the studied setting, sufficient depth improves robust implicit deductive reasoning, but CoT remains necessary for depth extrapolation.

  • Takeaways & Limitations

    The findings come from a toy model on synthetic data in a controlled Horn-clause setting, and learned strategies are interpretations based on empirical evidence.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies why Transformers rely on spurious shortcuts instead of faithfully executing deductive algorithms, and examines how depth and training design affect robust implicit reasoning. It finds that corrective training makes direct prediction tractable, while increasing depth narrows the gap with explicit CoT across graph topologies and widths.

  • Transformers often exploit spurious features or parallelizable computations rather than faithfully executing the sequential structure of logical deduction.
  • Depth-bounded models cannot perfectly solve Horn satisfiability or AI planning under standard complexity assumptions, but the limiting factors remain unclear.
  • Scaling model depth is essential for robust generalization to unseen distributions, while the corrective objective makes direct prediction optimization tractable.
  • The study identifies empirical scaling trends for faithful approximation of Horn-clause deduction in depth-bounded Transformers.
  • The r2 heuristic, bidirectional prefix masking, and corrective objective systematically mitigate shortcut-inducing biases and improve out-of-distribution performance.
  • Increasing model depth closes the implicit–explicit reasoning gap across graph topologies and problem widths, although CoT remains necessary for depth extrapolation.

2 Related work

Related work frames this study around implicit versus externally delegated deduction, causal and non-causal decoding, joint training of reasoning modes, and probing representations across depth. The paper positions its approach as improving direct deductive competence while reducing shortcut and representation-analysis problems.

  • External theorem provers can improve effectiveness by delegating deduction, but they do not directly improve a model’s implicit deductive competence.
  • Decorrelating spurious features from labels is presented as a way to make near-collisions compete with standard regularization.
  • A bidirectional prefix mask can outperform causal decoding after masked-language-model pretraining and multitask fine-tuning, while this study finds autoregressive training sufficient in its setting.
  • The proposed single-sequence formulation unifies implicit and explicit reasoning while mitigating information leakage and reducing embedding collapse.
  • A Procrustes-based alignment method addresses the failure of standard probes to generalize across continuously transformed representations at adjacent layers.

3 Methodology

The methodology constructs controllable Horn-clause datasets whose graph complexity, topology, and forward-chaining depth can be independently varied. It balances depth-related distributions and evaluates models beyond training bounds to test logical generalization.

  • The dataset environment is designed to manipulate graph complexity and topology independently, enabling robustness evaluation under distribution shifts.
  • A Llama 3-based decoder-only Transformer is trained with compositional type embeddings that separate logical roles from token identity.
  • RP generates entangled graphs through random facts, rules, and queries, whereas LP uses a hierarchical backbone with distractor rules; LP* adds cyclic dependencies.
  • In RP, proof depth δ is the forward breadth-first-search layer where the query is first derived, while LP’s hierarchical backbone determines the shortest path.
  • Random rule generation favors shallow paths, so datasets are balanced by depth to reduce this distributional bias and maintain balanced classes.
  • Backward-chaining depth balancing can leave forward BFS depth skewed toward shallow values, enabling graph depth to act as a shortcut for truth.
  • Evaluation uses unified logical depth δ as the required forward BFS horizon, including the layer where reachable graphs are exhausted for unprovable samples.
  • Training uses Npred ≤30 and δ ≤6, while out-of-distribution tests extend to Npred ≤60 and δ ≤12.

4 Complexity- and Information-theoretic scaling properties

The paper frames Transformer deductive reasoning through parallel depth, retrieval, synthesis, and representational bandwidth. Faithful approximation is constrained by logical depth, graph width, and the dimension needed to store and linearly decode active premises.

  • Reasoning primitives: Reasoning steps combine rule synthesis and forward-chaining primitives rather than simply following a single inference direction.Rule synthesis derives new rules after rule retrieval, while forward-chaining derives new facts after fact retrieval.
  • Retrieval limits: FFN memory cannot dynamically retrieve across arbitrary problem lengths, so retrieval analysis focuses primarily on attention.The text distinguishes retrieval limits from synthesis and derivation, which need not be localized to one complete reasoning step.
  • Depth scaling: Depthwise complexity λ(δ) is the minimum layer count required to solve a problem of logical depth δ.Increasing input size expands computational width but does not add sequential depth capacity.
  • Depth scaling: Θ(log δ) parallel time for path-like chains motivates a lower bound λ(δ) = Ω(log δ) for faithful parallel approximation.The same discussion connects graph reachability with polylog-depth parallel algorithms.
  • Depth scaling: P-completeness makes Horn deduction difficult to parallelize efficiently, so depth-bounded models cannot consistently solve instances when δ > L under sequential retrieval assumptions.The limitation arises when attention provides only one sequential retrieval step per layer.
  • Representational alignment: Procrustes alignment factors out orthogonal transformations across layers to recover linearly accessible information from evolving representation subspaces.The method is grounded in the superposition and linear representation hypotheses.
  • Representational bandwidth: Linear accessibility imposes a stronger feature-space requirement than nonlinear recovery: d = Ω_ε(s^2 log s log(n/s)) in the stated worst-case bound.The bound reflects low pairwise interference among active premises, with a nearly matching upper bound for exponential feature superposition.

5 Architectural alignment

The paper addresses shortcut learning by decorrelating provability from superficial and structural features, then aligns model computation with logical reasoning through masking and corrective training.

  • 5.1 Shortcut learning: Non-faithful shortcuts exploit superficial or structural features with unintended semantics instead of faithfully executing deduction.Decorrelating these features from provability reduces their predictive power.
  • 5.2 The r2 heuristic: The r2 heuristic constructs minimally different opposite-label pairs with nearly identical superficial statistics, increasing pressure to use structural features.Linearly separating such near-collisions requires a large weight norm that conflicts with standard regularization.
  • 5.2 The r2 heuristic: Adversarial balancing via r2 diminishes aggregate feature-label correlations and weakens individual feature predictability.Nonlinear models may still exploit higher-order features or artifacts.
  • 5.3 Bidirectional masking: A bidirectional prefix mask enables all-to-all attention within the problem statement, mitigating premise-ordering bias in causally masked models.Error analysis reports uniform reductions in hallucinations and missed deductions, with hallucinations dominant until r2 is introduced.
  • 5.4 Corrective objective: The corrective objective imposes a step-by-step algorithmic bias on direct prediction to align it with reasoning primitives used by CoT.CoT explicitly unrolls the computational graph and can bypass shortcuts exploited during direct generation.
  • 5.4 Corrective objective: A mixed curriculum degrades performance relative to individual baselines because conflicting direct and CoT signals can collapse task-token embeddings.The proposed interpretation attributes this degradation potentially to gradient conflicts.

6 Experimental results

Experiments show that depth, corrective alignment, and bidirectional visibility govern robust implicit deduction more strongly than width alone. Sufficiently deep models perform well across topologies, while rule synthesis creates a harder width-scaling regime.

  • Component ablations: The corrective objective is the strongest direct-mode component, but its benefit requires sufficient depth for faithful forward-chaining.For shallow models with L < δ, its marginal contribution is statistically indistinguishable, although convergence is more stable.
  • Component ablations: Bidirectional masking is a robust contributor across reasoning modes through global visibility, whereas ffn provides no systematic baseline benefit.A Universal Transformer’s recursive bias can make ffn useful by mirroring logical recursion.
  • Scaling properties: For logical depth δ = 5, L = 8 models achieved high, stable accuracy across rule premise counts, consistent with sequential forward-chaining.Once simultaneously active features are recoverable, increasing attention-head dimensionality yields no meaningful improvement.
  • Scaling properties: Rule synthesis requires at least λ(δ) = Ω(log δ) layers, while increasing premise counts expands the search space and makes attention-width scaling increasingly costly.Maintaining log-time execution would require exponentially growing head count and dimensionality to approximate a faithful algorithm.
  • Scaling properties: Implicit reasoning reliability scales primarily with layer count, while width-scaling is inefficient for depth-bounded Transformers solving P-complete problems in the worst case.The experiments report this pattern despite keeping dataset size fixed.
  • Representation analysis: Procrustes alignment and a training-free linear probe identify the layer at which provability becomes decodable from intermediate representations.The probe projects hidden states into output space and evaluates predictions against ground-truth provability.

7 Discussion

The discussion interprets direct reasoning as an efficient, redundant approximation that can resemble CoT while highlighting limits on causal credit assignment and real-world transfer. The authors therefore frame the findings as empirical and bounded by synthetic, controlled experiments.

  • Discussion: Direct reasoning resembles CoT by computing one novel reasoning step per N layers, but causal CoT cannot retroactively update preceding-token representations.The authors present the broader connection as speculative and call for further investigation.
  • Discussion: Improved faithfulness and robustness could reduce shortcut-driven failures and overconfident errors, while stronger implicit reasoning may make internal decisions harder to audit.The passage presents these as competing implications of more capable automated systems.
  • Limitations: The study uses a toy model and synthetic short-context Horn-clause tasks, so extrapolation to real-world domains requires care.The authors also state that learned strategies are empirical interpretations and that probing may not identify a single algorithm.
  • Future work: Future work includes formalizing CoT limits, characterizing reasoning primitives, extending the principles to richer logics and natural language, and studying unbounded-state architectures.The listed directions also include optimization biases that better promote learning reasoning steps.

A Dataset generation methodologies

The dataset generators create controlled logical graphs with varied topology, depth, noise, and rule counts, while shuffling presentation order to reduce positional shortcuts. Inputs also receive compositional semantic type embeddings that encode each token’s logical role.

  • Graph generators: RP generates entangled graphs by sampling facts, rules, and queries uniformly from a predicate set.Rules use 1–3 premises and duplicate rules are rejected.
  • Graph generators: LP generates hierarchical graphs by partitioning predicates into ordered levels and constructing a backbone whose rules connect adjacent levels.Noise rules are sampled separately from all levels.
  • Graph generators: LP* increases cyclic dependencies by allowing broader premise and noise-rule connections across levels while retaining LP’s fact and query construction.False-labeled conclusions reject all-true premises, and noise rules target intermediate levels.
  • Dataset controls: Datasets are balanced by logical depth, so actual instances lean toward the maximum rule bound rather than the sampler mean, with sequences capped at 1024 tokens.The appendix reports expected and maximum rule counts for each generator.
  • Input representation: Each token receives compositional semantic role embeddings summed with its vocabulary embedding, allowing the model to encode overlapping logical roles before processing.The type vocabulary describes token functions such as facts, premises, and conclusions.
  • Input representation: A serialized example concatenates facts and rules with a task token and query to form the model’s input sequence.The example uses facts {0, 1}, rule 1 →2, and query 3.

C Open source baselines

Open-source models show a pronounced gap between direct and explicit deductive reasoning: direct accuracy deteriorates with logical depth, whereas Qwen 3 remains above 90% with CoT. The section also introduces the evaluation and probing setup used to study these behaviors.

  • Evaluation setup: The benchmark evaluates approximately 30B-parameter open-source models on LP and RP with one-shot prompts, logical depth δ ≤6, and a 10,000-token generation budget.Figure A.1 compares direct and CoT evaluation, while Figure A.2 shows exponential decay in proof-depth counts.
  • Baseline results: Direct evaluation collapses to approximately 50% on LP for depths ≥2 and falls below 70% on RP beyond depth 2.These results indicate that standard pre-training does not naturally produce the state transitions needed for implicit deduction.
  • Baseline results: Qwen 3 (30B) achieves consistent >90% accuracy across LP and RP when reasoning is explicitly unrolled with CoT.The comparison frames the limitation as compressing reasoning into one forward pass rather than lacking logical knowledge.
  • Evaluation setup: CoT evaluation prompts the model to show forward-chaining steps and stop once the query is proved or no additional rules apply.Direct evaluation instead requests only the final provable or unprovable label.
  • Internal analysis: The probing analysis aligns intermediate states to a target layer with an orthogonal transformation, then projects them into output space to estimate provability confidence.Scores are computed for tokens and layers to visualize evidence accumulation.
  • Evaluation controls: The r2 transformation breaks provable LP instances by pruning a necessary rule and adding a logically irrelevant distractor, with fallback query alteration when pruning is unavailable.Some structures cannot be made unprovable, so balancing operations may fail and leave the original instance unchanged.

I Mitigating superficial and structural features

The r2 heuristic targets both superficial and structural label correlations by constructing near-collisions, pushing models toward structural representations. However, low aggregate correlations do not rule out nonlinear shortcut exploitation.

  • Feature correlations: Original datasets correlate labels with both superficial and structural features, including num_rules at 0.416 and ratio_rules_facts at 0.437.These correlations provide potential non-causal predictors for shortcut learning.
  • Limitation: A low Pearson correlation after augmentation does not prevent a Transformer from learning nonlinear compositional shortcuts from the same features.The model could identify augmented samples and conditionally reuse original statistics.
  • Heuristic mechanism: The r2 heuristic constructs oppositely labeled examples with nearly matched superficial statistics, making simple linear separation require large weight norms.This creates tension with regularization and encourages reliance on structural differences.
  • Heuristic mechanism: Separating r2 pairs using only superficial features produces brittle decision boundaries, motivating representations that encode underlying structural differences.After structural features move counterfactual pairs apart, a simple linear head can suffice.
  • Implementation context: The implementation uses a Llama 3 decoder-only Transformer with type embeddings and custom masking, while applying weight decay to RMSNorm parameters.Training uses 50k samples per depth-label bucket, and r2 augmentation doubles the effective dataset size.

L Normalization ablation

Normalization methods perform comparably when normalization parameters receive weight decay, but disabling that decay prevents convergence. The mixed curriculum also degrades both direct and CoT performance, whereas the corrective format keeps task signals disentangled.

  • Normalization: RMSNorm and LayerNorm perform comparably on RP-to-LP evaluation, with RMSNorm slightly ahead in out-of-distribution direct evaluation when FFN is enabled.Models were trained on RP and evaluated on RP and LP with Npred ≤30 and δ ≤6.
  • Normalization: Disabling weight decay on normalization parameters prevents convergence, leaving accuracies near random chance at approximately 50%.These runs used r2, corrective, and bidirectional components.
  • Data format: The mixed curriculum causes substantial degradation, with direct and CoT accuracies becoming nearly identical and falling below corrective baselines.The result suggests that the model fails to disentangle τdirect and τcot task instructions.
  • Data format: In the degraded mixed model, the CoT task token τcot collapses to zero magnitude, explaining the identical performance reported for direct and CoT tasks.Figure A.6 presents cosine-similarity heatmaps alongside L2 norms.

N Factorial ablation

The factorial ablation evaluates corrective, bidirectional, r2, and FFN components across expanded problem spaces and distribution shifts. Corrective objectives are most useful when models have enough depth, while width and reinforcement-learning effects are narrower or can degrade extrapolation.

  • Evaluation setup: Models trained on RP with Npred ≤30 and δ ≤6 are evaluated on expanded problems reaching Npred ≤60 and δ ≤12.Table A.11 isolates component contributions using average percentage-point differences.
  • Factorial ablation: Corrective objective benefits direct reasoning most, but its marginal contribution is indistinguishable in shallow models that cannot faithfully execute forward-chaining.It nevertheless provides more stable convergence in shallow models.
  • Width scaling: Scaling attention head dimensionality improves performance significantly only for L = 4 models on δ = 5 and δ = 6 problems.The number of attention heads is fixed to H = 4 in this comparison.
  • Error decomposition: The bidirectional mask uniformly reduces total CoT error volume under RP-to-LP shift, while the r2 heuristic balances the error distribution.Errors are categorized as hallucinated or missed deductions.
  • Reinforcement learning: GRPO matches the baseline without meaningfully improving out-of-distribution generalization, whereas FlowRL degrades systematically as logical depth increases.FlowRL degradation is attributed to missed deductions and persists across sparse, dense, token-level, and sequence-level rewards.
  • Reinforcement learning: FlowRL shifts toward missed deductions, while GRPO maintains a balanced hallucinated-versus-missed error profile resembling the baseline.Figures A.9 and A.10 visualize these contrasting profiles.

S Architecture as inductive bias

A Universal Transformer supplies a recursive inductive bias by repeatedly applying one weight-tied layer, aligning computation with logical recursion. Out-of-distribution convergence occurs only after matching the proof depth, while increasing layers—not heads—closes the implicit–explicit gap.

  • Recursive architecture: A Universal Transformer applies one weight-tied layer recursively for K = 8 iterations, biasing computation toward a graph-traversal next-step operator.This architecture mirrors recursive application of the same rules in logical deduction.
  • Direct evaluation: The Universal Transformer significantly outperforms the baseline under direct evaluation only when the FFN component is present.Both architectures include corrective, bidirectional, and r2 components in the comparison.
  • Out-of-distribution generalization: On out-of-distribution LP problems, Universal Transformer convergence is delayed until recurrent iterations match logical depth, k ≥ δ.In-distribution evaluation instead shows early convergence at k < δ, consistent with shortcut learning.
  • Scaling trends: Scaling attention heads does not close the implicit–explicit gap within the training horizon, whereas increasing layer count is required.Figure A.12 compares parameter-matched models, and Table A.17 reports the minimum layers needed for sustained non-inferiority to CoT.
  • Scaling trends: Scaling trends are evaluated with corrective, bidirectional, and r2 components on RP training samples, including test problems up to Npred ≤60 and depth 12.The scaling runs omit the FFN component and evaluate both direct and CoT modes.
Loading 2605.04330v2…