The Compositionality Gap in Neural Reasoning

25 concepts17 papers1 proposal

Large language models often appear to reason with human-like fluidity, yet they frequently stumble on tasks that require combining simple, known rules into complex chains. This phenomenon, often called the compositionality gap or a failure of systematicity, suggests that neural models are "syntactic creatures" rather than logical ones. As Yanaka et al. observe, even state-of-the-art models like BERT can achieve high accuracy on language tasks while failing to generalize when logical structures change slightly, indicating they lack a fundamental understanding of how meaning is systematically constructed.

The Transitivity Wall

A core manifestation of this failure is the inability to perform transitive reasoning. In its simplest form, if a model knows that $A$ leads to $B$ and $B$ leads to $C$, it should be able to deduce that $A$ leads to $C$. However, Yanaka and Mineshima demonstrate that models frequently fail to compose these independent logical steps unless they have been explicitly trained on the combined sequence.

This limitation is described by Wang et al. as a "transitivity wall." In path-finding tasks, autoregressive Transformers can learn individual segments of a graph but struggle to stitch them together into novel global solutions. The authors argue that the standard next-token prediction objective may be insufficient for models to acquire this capability, as it encourages learning observed sequences rather than the underlying recursive process of logical deduction.

Monolithic Processing vs. Discrete Operations

Why do models struggle to chain these steps? One reason is that they often treat complex queries as monolithic sequences rather than structured compositions of discrete operations. Gupta and Lewis argue that this lack of compositional understanding prevents models from reasoning through multi-step logic effectively.

When a task requires a specific sequence of filters, comparisons, and aggregations—such as verifying a claim against a table—monolithic networks often fail to decompose the statement into executable parts. To address this, Zhong et al. proposed hybrid frameworks like LogicalFactChecker, which use neural module networks to explicitly map linguistic nuances to structured logical operations. Without such mechanisms, models struggle to maintain accuracy as the number of logical "hops" increases.

The Systematicity Paradox

A surprising finding in this research area is that a model’s ability to solve a complex problem does not guarantee it understands the problem's constituent parts. Besançon et al. found that models trained on multi-hop reasoning tasks often fail to solve simpler, single-hop versions of the same problems. This suggests that high performance on complex benchmarks may be driven by statistical shortcuts or "pattern matching" rather than a foundational mastery of logical building blocks.

This gap persists even in domains like arithmetic. Kudo et al. show that while models can handle long problems (productivity) and different variable names (substitutivity), they fail to reliably access and reuse intermediate results. They can follow a long path, but they cannot systematically apply known logic in new structural contexts.

Bridging the Gap

Research into overcoming the compositionality gap generally falls into three categories:

  1. Prompting Strategies: Zhou et al. introduced least-to-most prompting, which teaches models to explicitly decompose a difficult problem into a sequence of simpler subproblems. By solving these sub-tasks incrementally, models can tackle problems more complex than those seen in their prompts.
  2. Architectural Tweaks: To break the transitivity bottleneck, Wang et al. suggest that multi-token prediction and specialized transfer layers can help models better internalize the underlying graph structure of a problem, allowing them to find paths they have never seen before.
  3. Extended Training: Wang et al. found that models can eventually "grok" implicit reasoning, but only by training far beyond the point of zero training loss. This suggests that while the capacity for compositionality exists within Transformers, it is often latent and requires significant optimization to emerge.

Ultimately, as Fu demonstrates with the SETI benchmark, the challenge is not just learning rules, but learning how to combine them. While models can master new reasoning primitives with very few examples, their ability to synthesize those primitives into novel logical chains remains the primary hurdle for achieving human-like systematicity.

Key Foundational Work

LogicalFactChecker: Leveraging Logical Operations for Fact Checking with Graph Module Network (2020) — contributed 1 concept elements to this direction.
Do Neural Models Learn Systematicity of Monotonicity Inference in Natural Language? (2020) — contributed 1 concept elements to this direction.
Neural Compositional Denotational Semantics for Question Answering (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compositional_reasoning_failure_composit_ad96fbab,
  title = {compositional reasoning failure (compositionality gap)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-reasoning-failure-compositionality-gap/rdr_ad96fbabc66444fd8b86d2dc5a61819b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_compositional_reasoning_failure_composit_ad96fbab_v1,
  title = {compositional reasoning failure (compositionality gap)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-reasoning-failure-compositionality-gap/rdr_ad96fbabc66444fd8b86d2dc5a61819b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake