💬 NLP

Deductive Logic in Language Models: Horizontal vs Vertical Reasoning

This paper investigates how small transformer models trained on synthetic deductive tasks implement reasoning through distinct horizontal (autoregressive) and vertical (implicit) mechanisms, revealing that Chain-of-Thought supervision fosters genuine rule-based inference in horizontal settings while acting as curriculum learning to develop complex reasoning patterns in vertical settings.

Original authors: Davide Maltoni, Matteo Ferrara

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Davide Maltoni, Matteo Ferrara

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a tiny, blank-slate robot brain (a small language model) that knows nothing about the world. You want to teach it how to solve logic puzzles. This paper is like a detective story where the researchers peek inside this robot's brain to see how it figures things out. They discovered that the robot can solve these puzzles in two very different ways, depending on how you teach it.

Here is the breakdown of their findings using simple analogies:

The Two Ways of Thinking: "Walking" vs. "Teleporting"

The researchers tested the robot on two types of puzzles:

The Chain Puzzle: Connecting dots (e.g., if A leads to B, and B leads to C, does A lead to C?).
The Tree Maze: Finding a path from the top of a tree to a specific leaf at the bottom.

They found the robot uses two distinct modes of thinking:

1. Horizontal Reasoning: The "Step-by-Step Walker"

The Analogy: Imagine you are walking through a dark forest. You can only see the next step in front of you. To get to the end, you must take one step, look around, take the next step, and so on. You can't jump ahead.

How it works: This happens when the robot is taught using Chain-of-Thought (CoT). This is like giving the robot a notebook where it has to write down every single step of its journey before it gives the final answer.
What the robot learns: The robot learns to act like a detective following a trail. It finds a rule (A leads to B), writes it down, then uses that result to find the next rule (B leads to C).
The Secret Mechanism: Inside the robot's brain, there are tiny "search engines" (called Induction Heads) that act like a "copy-paste" function. They look back at what was just written, find a matching piece of information, and copy the next piece of the puzzle forward. It's a very clear, mechanical process of "Find A, get B, then find C."

2. Vertical Reasoning: The "Teleporting Thinker"

The Analogy: Imagine you are standing at the bottom of a tall tower, but you need to know what's at the very top before you can even take your first step up. You can't walk up step-by-step because you don't know which stairs are safe yet. Instead, you have to mentally "teleport" all the way to the top, figure out the whole path in your head, and then start speaking.

How it works: This happens when the robot has to solve the Tree Maze without being allowed to write down intermediate steps. It has to solve the whole problem inside its layers of neurons before it outputs the first word.
The Secret Mechanism: The robot doesn't "walk" the path; it builds the path vertically through its layers. It's like a stack of transparent sheets. The bottom sheet holds the starting point, the next sheet holds the next step, and so on, all the way up. By the time the information reaches the top layer, the whole path is assembled.
The Role of Teaching: Surprisingly, even though the robot isn't writing down steps, giving it a "Chain-of-Thought" example helps it learn. The researchers call this Curriculum Learning. It's like a teacher showing a student easy puzzles first (short paths) and gradually giving harder ones (long paths). The robot learns the simple patterns first and then uses that knowledge to tackle the complex ones, all happening "silently" inside its brain.

The Trap: "Cheating" Without a Teacher

The researchers tried to teach the robot without the step-by-step notes (Chain-of-Thought).

The Result: The robot mostly failed to learn the actual logic. Instead, it started "cheating."
The Analogy: Imagine a student taking a test. If the teacher doesn't ask for the work, the student might just memorize that "questions with 5 numbers usually get a 'Yes' answer" instead of actually doing the math.
The Finding: Without the step-by-step guidance, the robot memorized patterns in the test data (biases) rather than learning the rules of logic. It could get high scores on the practice test but would fail completely on new, tricky questions.

The Big Takeaway

The paper shows that how you teach a robot matters more than just the robot itself.

If you force the robot to speak its thoughts (Horizontal), it builds a clear, mechanical chain of logic that we can easily understand and trace.
If you force the robot to think silently (Vertical), it can still learn, but it does so by gradually building up complexity, almost like a student mastering a skill through practice rather than a manual.
If you don't give it any guidance at all, it tends to cheat by memorizing shortcuts, which makes it unreliable when the rules change.

In short, the "Chain-of-Thought" isn't just a fancy trick to get better answers; it's a fundamental tool that changes how the robot's brain is wired to solve problems, turning it from a memorizer into a logical thinker.

Technical Summary: Deductive Logic in Language Models: Horizontal vs. Vertical Reasoning

Problem Statement

Recent Large Language Models (LLMs) demonstrate significant logical reasoning capabilities, yet the low-level computational mechanisms supporting deductive inference remain poorly understood. While existing literature focuses on benchmark performance or high-level circuit descriptions in pretrained models, there is a gap in understanding how transformers implement multi-step deductive reasoning from first principles. Specifically, the paper investigates the distinction between two reasoning paradigms:

Horizontal Reasoning: An autoregressive process where intermediate steps are generated token-by-token, leveraging previously generated tokens for subsequent steps (typically elicited via Chain-of-Thought, or CoT).
Vertical Reasoning: An implicit process where inference unfolds across the layer hierarchy before the first output token is produced. This is necessary when the first token requires solving a non-trivial part of the problem (e.g., determining a root-to-leaf path in a binary tree) without the aid of autoregressive intermediate steps.

The study addresses whether small, non-pretrained transformers can learn explicit logical rules rather than statistical shortcuts, and how CoT supervision influences these distinct reasoning modes.

Methodology

The authors employ a mechanistic interpretability approach using small, decoder-only transformer models trained from scratch on two synthetic tasks designed to eliminate natural language ambiguity and reliance on pretraining knowledge.

Tasks

Task 1 (Logical Consequence): A propositional logic inference task involving chains of implications (Horn clauses). The model must decide if a query ( $q_0 \to q_1$ $q_{0} \to q_{1}$ ) is a logical consequence of five given rules.
- CoT Setting: The model generates the intermediate chain of implications leading to the conclusion before outputting a final decision token (1 or 0).
- Non-CoT Setting: The model outputs only the final decision token.
Task 2 (Root-to-Leaf Navigation): A task requiring the model to navigate a binary tree from the root to a specified leaf node, given an unordered list of parent-child pairs.
- CoT Setting: The model generates the full sequence of nodes in the path.
- Non-CoT Setting: The model outputs a binary token indicating reachability.

Model Architecture and Training

Architecture: GPT-2-style "NanoGPT" models (decoder-only) trained from scratch. Experiments utilized simplified configurations (e.g., 2 layers, 1 head) for interpretability and standard configurations (6 layers, 8 heads) for performance.
Training: Models were trained on synthetic datasets (4K to 150K examples) with and without CoT supervision.
Interpretability Tools:
- LogitLens: Decoding residual stream content into vocabulary space at intermediate layers.
- Attention Visualization: Analyzing attention patterns and filtering by strength.
- Truncated Pseudoinverse: A novel technique introduced to decode the information carried by Query, Key, and Value vectors back into token space, disentangling the specific information extracted by attention heads.
- Averaging: Computing average attention strengths across datasets to isolate token-independent (positional) attention links.

Key Contributions

Mechanistic Account of Horizontal Reasoning: The paper provides a low-level explanation of how a shallow (2-layer) model trained with CoT solves Task 1. It identifies specific, interpretable circuits:
- Rule Completion: Induction-head-like mechanisms that search for a rule antecedent matching the current token and retrieve the consequent.
- Rule Chaining: Mechanisms that connect the tail of one rule to the head of the next.
- Decision Making: Circuits that verify the final chain against the query.
Analysis of Vertical Reasoning: The study demonstrates that Task 2 (root-to-leaf navigation) requires vertical reasoning. The model learns to compute the entire backward path (leaf to root) internally across layers before generating the forward path. This involves "register tokens" in the prompt acting as working memory.
Role of CoT as Curriculum Learning: The paper reveals that in vertical reasoning, CoT does not merely provide step-by-step guidance (as in horizontal reasoning) but acts as a form of Curriculum Learning. It allows the model to first master simpler sub-problems (e.g., shorter paths or nodes closer to the target) and progressively generalize to complex cases.
Novel Interpretability Technique: The introduction of a truncated pseudoinverse method to decode Query, Key, and Value vectors, offering a new tool for inspecting the information flow in attention mechanisms.
Failure Modes without CoT: The study shows that without CoT, models fail to learn the intended logical algorithms for complex tasks, instead resorting to memorization or exploiting dataset biases (e.g., counting distinct literals) when such biases exist.

Results

Horizontal Reasoning (Task 1): A simple 2-layer model trained with CoT achieves ~100% accuracy and generalizes perfectly. Mechanistic analysis confirms the emergence of induction heads that perform "copy-search-retrieve" operations to chain rules. Without CoT, the model fails to converge to a generalizing solution, often memorizing the training set or exploiting statistical shortcuts (e.g., counting literals) if dataset biases are present.
Vertical Reasoning (Task 2): A 6-layer model trained with CoT successfully solves the root-to-leaf navigation task. The model implicitly learns to traverse the tree backward (leaf to root) within the residual stream of the last prompt token, storing intermediate nodes in "register" positions, and then generates the path forward.
- Without CoT, the model fails to learn the navigation logic unless a specific generation bias (exploitable statistical feature) is present. Once the bias is removed, performance drops to near-random levels.
- CoT facilitates this learning by enabling a curriculum effect: the model learns to predict tokens closer to the target leaf first, then extends this competence to the root.
Induction Heads: Induction heads are identified as central components in both reasoning modes, facilitating the matching of rule antecedents and the retrieval of consequents in horizontal reasoning, and enabling the backward chaining in vertical reasoning.

Significance and Claims

The paper claims to provide a low-level account of how transformers implement deductive reasoning, contrasting with previous works that offer high-level descriptions or focus on statistical shortcuts.

Distinction in Reasoning Modes: The work clarifies that CoT serves different functions depending on the reasoning paradigm: it enables explicit step-by-step decomposition in horizontal reasoning, while it acts as a curriculum scaffold for implicit, layer-wise computation in vertical reasoning.
Necessity of Supervision: The results suggest that for complex deductive tasks, explicit intermediate supervision (CoT) is crucial for learning the underlying logical algorithms. Without it, models tend to memorize or exploit biases rather than learning generalizable reasoning rules.
Generalizability of Mechanisms: The findings support the view that language models may rely on different computational strategies (symbolic rule-based vs. sub-symbolic numerical) depending on the task nature. The study highlights that induction heads, previously associated primarily with in-context learning, are fundamental to implementing logical inference circuits.
Limitations: The authors modestly note that their low-level analysis relies on simplified architectures (shallow models, shared embeddings) and symbolic syntax. While the mechanisms are clear in this setting, they may not directly transfer to larger, pretrained models or naturalistic settings. Furthermore, the specific mechanisms for merging partial paths in vertical reasoning when path length exceeds model depth remain partially unexplained.

In summary, the paper argues that understanding the specific computational circuits (like induction heads) and the role of supervision (CoT) is essential for designing robust models capable of genuine deductive reasoning, rather than mere statistical approximation.