💬 NLP

Multi-Hop Knowledge Composition is Bound by Pretraining Exposure

This paper demonstrates that Large Language Models' failure in implicit multi-hop reasoning stems not from a lack of memorized facts but from a pretraining deficiency, as compositional reasoning capabilities only transfer to individuals explicitly exposed to multi-hop contexts during pretraining.

Original authors: Yannis Karmim, Luis Marti, Djamé Seddah, Valentin Barrière

Published 2026-06-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yannis Karmim, Luis Marti, Djamé Seddah, Valentin Barrière

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 super-smart librarian (the AI) who has memorized a massive library of biographies.

If you ask, "When was Thierry born?", the librarian answers instantly.
If you ask, "Who is Zinedine's closest friend?", the librarian also answers instantly.

But if you ask, "When was Zinedine's closest friend born?", the librarian freezes. Even though they know both facts perfectly, they can't connect the dots to give you the answer in one go. They know the pieces, but they can't assemble the puzzle.

This paper investigates why this happens and whether we can teach the librarian to do it just by changing the books they read during their training.

The Core Problem: The "Missing Link"

The researchers call this the Compositionality Gap. It's like having a toolbox full of perfect hammers and nails, but not knowing how to build a chair when asked. The AI can find the facts, but it can't "chain" them together implicitly.

The Experiment: Two Groups of People

To study this, the researchers created a fake world with 100,000 people. They split these people into two groups:

The "Exposed" Group: These people appear in the training books in complex stories. For example, the books might say: "Marcus's friend is Delia, and Delia was born in Paris." This teaches the AI to link "Marcus" to "Delia" to "Paris."
The "Held-Out" Group: These people appear in the books, but only in simple, single-fact stories. The books say: "Marcus was born in London." They never appear in a story that links them to someone else. They are the "strangers" who never get introduced to the complex web of relationships.

The researchers then trained the AI on these books and tested it on questions about both groups.

The Big Discovery: You Can't Teach What You Haven't Seen

The researchers tried nine different ways to "augment" the training data (changing how the stories were written, using natural language, or using structured data like RDF).

Here is what they found:

For the "Exposed" Group: When the AI saw the complex stories during training, it got much better at answering multi-step questions. If it learned that "A is friends with B" and "B was born in X," it could answer "When was A's friend born?" correctly.
For the "Held-Out" Group: No matter how much they tweaked the training data, the AI failed completely on this group. Even if the AI knew the facts perfectly, it couldn't connect them if the specific person had never appeared in a "complex" story during training.

The Analogy:
Imagine teaching a child to solve math problems.

Exposed Group: You show the child a problem: "If John has 2 apples and gives 1 to Mary, how many does Mary have?" You do this many times. The child learns the logic of sharing.
Held-Out Group: You show the child a different child, "Bob," but only ever ask, "How many apples does Bob have?" You never ask about Bob sharing apples.
The Test: When you ask, "If Bob gives an apple to Alice, how many does Alice have?" the child (the AI) fails. They know Bob has apples, but because they never saw Bob in the context of sharing, they can't apply the logic to him.

Key Takeaways

It's a Training Issue, Not a Memory Issue: The AI isn't failing because it's "dumb" or doesn't have enough memory. It fails because it was never exposed to the specific type of reasoning for those specific people during its "schooling" (pretraining).
Exposure is Mandatory: To learn how to connect the dots, the AI must see the dots connected before it is tested. You cannot teach the AI to reason about a person it has never seen in a complex context.
Explicit vs. Implicit: The researchers tried writing the stories in two ways:
- Explicit: "Marcus's friend Delia was born in Paris." (Naming the friend).
- Implicit: "Marcus's friend was born in Paris." (Hiding the friend's name).
  They found that Implicit (hiding the name) was actually better for teaching the AI to reason, because it forced the AI to figure out the link itself, rather than just reading the answer. However, even the best training methods failed for the "Held-Out" group.

The Conclusion

The paper concludes that implicit multi-hop reasoning is bound by pretraining exposure.

If the AI hasn't seen a specific person (or entity) in a "multi-step" context while it was learning, it will likely fail to reason about that person later, no matter how smart the model is or how much data you feed it. The ability to connect the dots isn't a general superpower the AI develops on its own; it's a specific skill it only learns for the specific characters it has practiced with.

Technical Summary: Multi-Hop Knowledge Composition is Bound by Pretraining Exposure

Problem Statement
Large Language Models (LLMs) demonstrate high fidelity in storing and retrieving individual factual knowledge but consistently fail at implicit multi-hop reasoning within a single forward pass. A model may correctly answer "When was X born?" and "Who is Y's closest friend?" yet fail to answer "When was Y's closest friend born?" even when both constituent facts are perfectly memorized. This phenomenon, known as the compositionality gap, persists across model scales and architectures. While existing solutions externalize reasoning via chain-of-thought or decomposition during inference, it remains unclear whether compositional reasoning can emerge solely from pretraining. Furthermore, on proprietary models, the root cause is undiagnosable due to undisclosed pretraining data.

Methodology
The authors investigate this gap using a controlled natural language setting that strictly separates individuals exposed to compositional contexts during pretraining from those that are not.

Dataset Construction: Building on the synthetic biography framework of Allen-Zhu and Li (2024), the authors created a dataset of $N=100,000$ individuals, each described by six attributes (e.g., birthday, birth city) and directional "friend" and "enemy" relations.
Population Partitioning: The population is split into two disjoint sets:
- $P_{comp}$ (Compositional): Individuals whose relations point exclusively to other members of $P_{comp}$ . These individuals are exposed to compositional contexts during pretraining.
- $P_{held}$ (Held-out): Individuals whose relations point exclusively within $P_{held}$ . Crucially, these individuals never appear as intermediate (bridge) entities in any compositional chain seen during pretraining.
Pretraining and Augmentation: The authors pretrain GPT-2 models (Small, Medium, Large) from scratch. They introduce nine distinct data-centric augmentation strategies for $P_{comp}$ $P_{co m p}$ , varying along two axes:
- Format: Natural Language (NL) vs. RDF (structured triples).
- Verbalization: Explicit (naming the bridge entity) vs. Implicit (omitting the bridge entity).
- All conditions include atomic 1-hop biographies with multi5p-permute augmentation.
Evaluation Protocol: Models are fine-tuned on 75% of $P_{comp}$ ( $P^{train}_{comp}$ ) and evaluated on the remaining 25% ( $P^{test}_{comp}$ ) and the entirely unseen $P_{held}$ . Evaluation measures first-token accuracy for 1-hop, 2-hop, and 3-hop queries without access to intermediate entities in the context.

Key Results
The experiments yield three primary findings:

The Compositionality Gap is a Pretraining Failure: Even with near-perfect 1-hop accuracy (97%), models score near 0% on 2-hop queries for $P_{held}$ and only marginally better for $P_{comp}$ under baseline training. This confirms the gap is not a capacity limit or a lack of knowledge, but a failure to compose facts during pretraining.
Pretraining Exposure is a Necessary Condition: Compositional pretraining significantly improves multi-hop QA on unseen questions for exposed individuals ( $P^{test}_{comp}$ ), with 2-hop accuracy reaching up to 0.83 under specific augmentation strategies (e.g., implicit + explicit NL-RDF). However, zero transfer occurs to $P_{held}$ . No data-centric augmentation compensates for the absence of exposure to an individual in a compositional context.
Implicit vs. Explicit Augmentation:
- Implicit augmentation (where the bridge entity is omitted) consistently outperforms explicit augmentation (where the bridge is named) in isolation. Explicit formats improve the localization of the bridge token (verified via Logit Lens analysis) but do not translate to compositional success.
- Hybrid approaches (mixing implicit and explicit signals) yield the best performance on $P^{test}_{comp}$ , suggesting that mixing signals improves representation alignment.
- RDF formats (specifically implicit RDF) prove highly effective, achieving high compositional accuracy at a fraction of the data cost compared to NL.

Significance and Claims
The paper establishes that exposure to compositional contexts during pretraining is a necessary condition for implicit multi-hop reasoning. The authors argue that augmentation induces entity-specific associations rather than a reusable, generalizable composition logic. Consequently, models fail to compose facts for individuals they have never encountered in a multi-hop context, regardless of model scale or fine-tuning strategies.

The study challenges the notion that compositional reasoning can be induced purely through data augmentation for unseen entities. It suggests that to achieve implicit multi-hop reasoning, the training distribution must explicitly include the specific entities within the required relational chains. The authors release their code and a reproduction of the biography framework to support future investigations into training objectives or architectural modifications that might overcome this fundamental limit.

Limitations
The authors acknowledge that their setting is fully synthetic and that generalization to naturally occurring corpora remains untested. They note that while their experiments use GPT-2 scales, the compositionality gap is known to persist up to 175B parameters. Additionally, the study focuses on data-centric interventions under standard pretraining and does not evaluate alternative objectives like reinforcement learning or knowledge distillation.