Skip to content
conftrace_
2026 EMNLP EMNLP 2026

When Structure Is Hidden: Measuring and Diagnosing the Compositional Gap in LLMs

AbstractLarge language models often recover the local pieces of a problem yet still fail to assemble them into a correct global solution. We study this compositionality gap in settings where the underlying structure is implicit and must be inferred from the input, using a two-pass framework that first verifies piece-level understanding and then measures composition on the same example via P(composed wrong | all pieces correct). We evaluate task formulations in five domains (contracts, math, SQL, code, and logic) and four model families; across the gold-anchored domains, larger conditional gaps are associated with settings where relevant structure is less directly exposed. A controlled intervention with correct and incorrect structural hints indicates heterogeneous bottlenecks: hints substantially reduce the gap in contracts and SQL, have no aggregate effect in math, and have no reliable effect in logic. Structure-aware prompting does not repair the gap and often harms smaller models. We conclude that composition failure is not a single phenomenon, and that diagnosing the dominant bottleneck in each task is the practical output of our framework

More from EMNLP 2026

All EMNLP 2026 papers →