Source-linked AI summary
Language models can learn implicit multi-hop reasoning, but only if they have lots of training data
Yuekun Yao, Yupei Du, Dawei Zhu, Michael Hahn, Alexander Koller
TL;DR
Prior implicit-reasoning studies largely focused on two-hop tasks, leaving models’ capacity for harder multi-hop reasoning uncertain. The paper trains GPT2-style models on controlled k-hop datasets and finds that they can learn this reasoning, but with exponentially increasing data needs and linearly increasing depth requirements; curriculum learning mitigates, but does not eliminate, data growth.
Problem
Prior implicit-reasoning work focused on two-hop tasks, leaving it unclear whether language models can handle harder k-hop reasoning; explicit chain-of-thought methods also incur long inference time and costly annotations.
Source: §1 · p. 1Method
The authors train GPT2-style language models on controlled synthetic k-hop reasoning datasets and examine their layer-wise processing of intermediate entities.
Source: §1 · p. 2, §3.2 · p. 3Results
Models learn k-hop reasoning, but data requirements grow exponentially and model depth grows linearly with k; curriculum learning reduces, but does not eliminate, data growth.
Source: §1 · p. 2Takeaways & Limitations
Curriculum learning is an effective mitigation for the data requirement, but the growth trend with k persists.
Source: §1 · p. 2The experiments use synthetic datasets and restrict tasks to k<5; analysis does not extend to models larger than GPT-2 large.
Source: §8 · p. 9
Abstract
from arXiv · showhide
Implicit reasoning is the ability of a language model to solve multi-hop reasoning tasks in a single forward pass, without chain of thought. We investigate this capability using GPT2-style language models trained from scratch on controlled $k$-hop reasoning datasets ($k = 2, 3, 4$). We show that while such models can indeed learn implicit $k$-hop reasoning, the required training data grows exponentially in $k$, and the required number of transformer layers grows linearly in $k$. We offer a theoretical explanation for why this depth growth is necessary. We further find that the data requirement can be mitigated, but not eliminated, through curriculum learning.
1 Introduction
The paper asks whether language models can handle implicit reasoning beyond the two-hop tasks emphasized in prior work, and studies GPT2-style models on controlled k-hop tasks. It finds that this capability comes with rapidly growing data needs and model-depth requirements, while curriculum learning reduces but does not eliminate the data growth.
1 Introduction
- Chain-of-thought methods generate intermediate steps, but incur long inference time and costly annotations.This motivates the paper’s question of whether language models can reason implicitly, without explicit chain of thought.Source: §1 · p. 1
- Earlier implicit-reasoning studies focused on two-hop questions, leaving models’ ability to handle harder k-hop questions unclear.The paper studies generalization to novel combinations of learned facts using GPT2-style models on k = 2, 3, and 4 tasks.Source: §1 · p. 1
- The authors attribute the exponential data requirement primarily to the explosion in the search space of fact combinations.They report that models with sufficient data derive intermediate hop entities layer by layer.Source: §1 · p. 2
- A theoretical lower bound suggests that transformer depth growing with k may be unavoidable under the stated attention-pattern condition.The condition is that the attention pattern does not depend on the query entity.Source: §1 · p. 2
- Curriculum learning significantly reduces required training data, whereas simply mixing easier m-hop tasks with k-hop tasks yields only modest gains.The curriculum introduces tasks in progressively harder order.Source: §1 · p. 2
- Models can learn k-hop reasoning, but training data grows exponentially and model depth must grow at least linearly as k increases.The paper characterizes curriculum learning as a mitigation, not a resolution, of the data-growth trend.Source: §1 · p. 2
2 Related work
Prior work on implicit reasoning mainly examined knowledge-based two-hop tasks, while this paper extends the investigation to more complex synthetic tasks. It also relates its data findings to work on memorization and generalization.
2 Related work
- Research on implicit reasoning includes knowledge-based and mathematical tasks, but the cited knowledge-based studies primarily evaluate two-hop question answering.Those studies assume the model knows individual facts and ask it to combine them.Source: §2 · p. 2
- Unlike studies relying on pretrained models’ single-hop knowledge, this work trains on synthetic data to control task complexity across 2-, 3-, and 4-hop reasoning.Wang et al. (2024) also use synthetic data, but study two-hop reasoning.Source: §2 · p. 2
- Work on grokking studies memorized and generalizable solutions, whereas this study argues training data must grow exponentially with task difficulty.The authors offer this data-growth finding as a possible explanation for LLM failures on complex implicit-reasoning tasks.Source: §2 · p. 2
3 Dataset
The paper constructs synthetic knowledge-based datasets to control the difficulty of multi-hop reasoning tasks. They represent facts as entity profiles and test questions that compose facts across increasingly long chains.
3 Dataset
- The dataset uses synthetic knowledge to support controlled study of task difficulty and model behavior.It focuses on knowledge-based multi-hop reasoning, where answers require combining known facts.Source: §3 · p. 2
3.1 Task description
- Facts are entity-relation-object triples, and k-hop queries compose k relations into chains with intermediate bridge entities.The datasets cover k = 2, 3, and 4, extending beyond the two-hop tasks common in prior work.Source: §3.1 · p. 3
- Each dataset contains entity profiles encoding facts and natural-language questions that query fact compositions.The reasoning questions use relation names and a queried entity, such as asking who is the teacher of the instructor of Jennifer.Source: §3.1 · p. 3
3.2 Data generation
- The small and large dataset variants differ in entity and relation counts: |E|=250, |R|=10 and |E|=500, |R|=20, respectively.For k-hoplarge 2-hop questions, up to 40,000 instances can be generated.Source: §3.1 · p. 3, §3.2 · p. 4
- Profile generation organizes entities into five hierarchical layers and links each entity to randomly selected entities in the layer above.The same profiles are reused across k values; questions are generated by traversing k relations from bottom-layer entities, and training includes all profiles plus sampled questions while held-out questions form the test set. Table 1 reports GPT-2 accuracy across dataset variants and training-data budgets.Source: §3.2 · pp. 3–4, §3.1 · p. 3, Table 1 · p. 4
4 LMs can learn k-hop reasoning, but at a large data cost
Randomly initialized GPT-2 models can learn 2- to 4-hop reasoning from input-output examples, but the required training budget grows rapidly with hop count. The study links this data inefficiency chiefly to the growth of relation combinations.
4.1 Experiment setup
- Training budgets scale the number of reasoning questions from the 2-hop training-set size, and larger budgets can also accelerate convergence.Figure 4 reports that ×20 reaches 100% accuracy at step 5,000 on 3-hoplarge, while ×10 reaches 10% at that step.Source: §4.1 · p. 4, §4.2 · p. 5, Figure 4 · p. 5
4.2 Results
- With sufficient training data, GPT-2 reaches 100% accuracy on 2-, 3-, and 4-hop tasks without explicit instructions for combining facts.The result supports learning from input-output pairs alone, even without explicit rationales.Source: §4.2 · p. 5
- On k-hoplarge, the minimum budget for above 80% accuracy rises from ×10 for 3-hop to ×100 for 4-hop tasks.The corresponding k-hopsmall thresholds are ×5 and ×20.Source: §4.2 · p. 5
4.3 Why data-hungry?
- When 1-hop and 2-hop relations are each restricted to a single relation, the model learns the 4-hop task at the base data budget (×1); increasing relation counts rapidly increases required budget.The case study attributes data inefficiency to exponential growth in relation combinations rather than individual facts.Source: Figure 5 · p. 5, §4.3 · p. 6
5 LMs reason through layer-wise lookup, incurring the cost of depth
Probing and interventions indicate that models solve multi-hop queries by retrieving bridge entities layer by layer. The paper's theoretical analysis shows that, under a query-independent attention assumption, the required model capacity must grow with hop count.
5.1 Experiment setup
- Probes find information about all bridge entities at the final whitespace token, while other token positions have low probe accuracy.The experiments use a 4-hoplarge model trained with a ×100 budget; intervention effects are measured by patching residual streams at the final token.Source: §5.1 · p. 6, §5.2 · p. 7, Figure 6 · p. 7
5.2 Results
- Causal interventions show that shallower layers handle lower-hop entities and deeper layers handle higher-hop entities, supporting a layer-wise lookup account of multi-hop reasoning.The analysis extends observations from earlier 2-hop tasks.Source: §5.2 · p. 7, Figure 7 · p. 7
5.3 Theoretical Analysis
- Under query-independent attention, the lower bound requires the product of layers, precision, width, and heads to grow linearly with k in the worst case.For fixed width, heads, and precision, the analysis predicts that more layers must participate as k increases; some relation sets may admit shallow shortcuts.Source: §5.3 · pp. 7–8
6 Curriculum learning mitigates the data requirement, but doesn’t solve it
The paper compares mixed learning with a staged curriculum that introduces harder reasoning tasks progressively. Curriculum learning substantially reduces the data budget needed for multi-hop reasoning, but does not eliminate its growth with hop count.
6.1 Experiment setup
- Curriculum training adds lower-hop tasks in stages, progressing from 2-hop questions to increasingly harder tasks up to k-hop.Mixed learning instead combines lower-hop and target k-hop questions in the training set.Source: §6.1 · p. 8
6.2 Results.
- Curriculum learning achieves perfect accuracy on 4-hop tasks with a ×5 budget, compared with ×100 for the target-task-only baseline; mixing lower-hop data provides only modest gains.The comparison holds total training steps equal across the mixed and curriculum strategies.Source: §6.2 · p. 8, §6.1 · p. 8
- The authors attribute curriculum learning's effectiveness to circuits building stepwise: lower-hop retrieval mechanisms emerge early, and later stages develop higher-hop circuits on top of them.The data-budget growth remains: curriculum learning requires ×2 for 3-hop and ×5 for 4-hop tasks.Source: §6.2 · pp. 8–9
7 Conclusion
Controlled k-hop datasets show that language models can learn implicit multi-hop reasoning through sequential, layer-by-layer retrieval of bridge entities. This capability requires exponentially more training data and linearly greater model depth as k grows; curriculum learning reduces, but does not eliminate, the data growth.
7 Conclusion
- As k increases, implicit k-hop reasoning requires exponentially growing training data and linearly growing model depth; curriculum learning mitigates but does not eliminate data growth.Models perform the reasoning through sequential lookup of intermediate bridge entities layer by layer.Source: §7 · p. 9
8 Limitations
The study is limited to synthetic, predefined-template implicit reasoning tasks and k-hop tasks with k < 5. Its experiments primarily use randomly initialized GPT-2 small models, although pretrained and larger models are also tested.
8 Limitations
- The study uses synthetic datasets generated from predefined templates, making extension to realistic datasets challenging because complex questions and corresponding facts are difficult to collect.The authors give 4-hop questions as an example of complex questions that are hard to collect.Source: §8 · p. 9
- Computational budget constraints restrict the experiments to k-hop tasks with k < 5.Source: §8 · p. 9
- Experiments primarily use randomly initialized GPT-2 small; pretrained GPT-2 and GPT-2 medium and large are also tested, but models beyond 770M parameters are not analyzed.Source: §8 · p. 9
A.1 Proof of Theoretical Bound
The proof bounds the information a causal transformer can convey about composed functions, then constructs a relation set with exponentially many distinct k-fold compositions. The discussion states the proof's attention-pattern assumption and reports empirical evidence that data-budget growth persists across model setups, while required depth rises with hop count.
A.1 Proof of Theoretical Bound
- With attention patterns independent of query entity e, the proof bounds composed-function information by transformer communication capacity, then constructs exponentially many distinct compositions.The communication argument uses 4LpdH bits; the constructed relations use f to cyclically shuffle non-sink entities and g to map the first entity to the sink.Source: §A.1 · pp. 11–12
A.2 Discussion
- The lower-bound proof assumes attention patterns do not depend on query entity e; relaxing that assumption remains open, and unrestricted multilayer lower bounds remain challenging.A related one-layer-transformer result is consistent with increasing layer requirements but does not bound how many layers are needed.Source: §A.2 · pp. 12–13
B.1 Finetuning
- On k-hoplarge, pretrained GPT-2 small requires ×10 budget for 3hoptask and ×100 for 4-hop; data-budget growth also persists for GPT-2 medium and large.The pretrained model reaches 100% accuracy on 3-hop k-hopsmall at ×10 budget.Source: §B.1 · p. 13
B.2 Scaling up the model size.
- GPT-2 medium and large retain the data-budget growth issue on k-hopsmall, despite scaling up model parameters.Source: §B.2 · p. 13
C Effect of model depth
- Test accuracy across varying depths shows that required model depth grows as the hop number increases, consistent with the theoretical analysis.Source: C Effect of model depth · p. 13
D.1 Datasets in Section 4
The appendix describes synthetic dataset construction for 2-, 3-, and 4-hop reasoning, then gives the auxiliary-data schedules for mixed and curriculum learning. It also specifies the baseline model and training configuration and the staged curriculum setup.
D.1 Datasets in Section 4
- Datasets use distinct single-token person and relation names; profiles are built across hierarchical entity layers, with training questions generated for a subset of target entities.The small setup uses 250 entity profiles and 10 relations, with 5,000 generated 2-hop questions.Source: §D.1 · p. 14
D.2 Datasets for mixed and curriculum learning
- Mixed learning adds lower-hop instances to higher-hop tasks, while curriculum learning uses the same auxiliary instances; auxiliary-data sizes were not specifically tuned.For small datasets, the setup adds 4k 2-hop instances for 3-hop and 4k 2-hop plus 20k 3-hop instances for 4-hop.Source: §D.2 · pp. 14–15
E.1 Baseline
- The baseline is GPT-2 small with 12 transformer layers and 12 attention heads, trained with AdamW and a warm-up followed by cosine learning-rate scheduling.Source: §E.1 · p. 15
E.2 Setup for mixed and curriculum learning
- Curriculum training progressively adds harder hop tasks across stages, using two stages for 3-hop and three for 4-hop tasks.Stages retain the baseline learning-rate scheduler, warm-up, batch size, and gradient accumulation settings.Source: §E.2 · p. 15
F.1 Results for LMs on k-hopsmall
Across k-hopsmall, larger budgets improve accuracy in fewer training steps, while curriculum learning performs best against baseline and mixed learning. Additional analyses find exponential data-budget growth, mostly small run-to-run variation with an insufficient-budget exception, and patching evidence that reasoning primarily occurs at the last token.
F.1 Results for LMs on k-hopsmall
- Larger k-hopsmall training budgets yield higher accuracy in fewer steps, while small budgets improve only 2% over the random baseline; curriculum learning outperforms baseline and mixed learning.These comparisons are reported across Figures 9 and 10.Source: §F.1 · p. 16
F.2 Standard deviation
- Most runs show no large standard deviation, but variance is large for some insufficient-budget runs and decreases when more training data is added.The reported exception includes the curriculum model on 4hoplarge with a ×2 budget.Source: §F.2 · p. 16
F.3 Log scale of data budget
- The minimal data budget required to solve k-hop tasks grows exponentially with k.The log-scale plot confirms the trend using data-budget values from Table 1.Source: §F.3 · p. 16, Figure 11 · p. 17
G.1 Patching preceding prompt tokens
- Patching shows no significant causal effects after the <Entity> token except at the final <space> token, supporting the claim that reasoning primarily occurs at the last token.Relation-token effects at deeper layers are consistent with reading beginning there; MLP-output patching shows relation-token effects only in the first layer.Source: §G.1 · p. 17
G.2 Causal effects across training steps
Checkpoint analyses find that circuits for different hop positions emerge together in a standard model, while curriculum learning builds higher-hop circuits on existing lower-hop circuits. The curriculum analysis attributes this progressive development to the same pattern associated with its data-efficiency gains.
G.2 Causal effects across training steps
- The curriculum checkpoint analysis uses a 4-hop model with a ×5 budget and three training stages, whereas the standard-model analysis tracks a 4-hoplarge model with a ×100 budget.Causal effects are measured at each stage for the curriculum model and at checkpoints saved every 1,000 steps for both analyses.Source: §G.2 · p. 17
- In the standard model, circuits for 1-, 2-, and 3-hop bridge entities emerge together around step 17,000, in distinct layers rather than sequentially.The analysis uses a 4-hoplarge model with a ×100 budget and measures causal effects at the last input token across checkpoints.Source: §G.2 · p. 17, Figure 14 · p. 18
- In the curriculum model, stage 1 establishes 1-hop circuits, stage 2 adds 2-hop circuits, and stage 3 adds 3-hop circuits on top of the earlier circuits.The authors interpret this layer-by-layer construction as supporting progressive circuit development and explaining curriculum learning's effectiveness.Source: §G.2 · p. 18, Figure 15 · p. 19