The Coverage Principle: A Framework for Understanding Compositional
  Generalization
Large language models excel at pattern matching, yet often fall short in
systematic compositional generalization. We propose the coverage principle: a
data-centric framework showing that models relying primarily on pattern
matching for compositional tasks cannot reliably generalize beyond substituting
fragments that yield identical results when used in the same contexts. We
demonstrate that this framework has a strong predictive power for the
generalization capabilities of Transformers. First, we derive and empirically
confirm that the training data required for two-hop generalization grows at
least quadratically with the token set size, and the training data efficiency
does not improve with 20x parameter scaling. Second, for compositional tasks
with path ambiguity where one variable affects the output through multiple
computational paths, we show that Transformers learn context-dependent state
representations that undermine both performance and interoperability. Third,
Chain-of-Thought supervision improves training data efficiency for multi-hop
tasks but still struggles with path ambiguity. Finally, we outline a
mechanism-based taxonomy that distinguishes three ways neural networks
can generalize: structure-based (bounded by coverage), property-based
(leveraging algebraic invariances), and shared-operator (through function
reuse). This conceptual lens contextualizes our results and highlights where
new architectural ideas are needed to achieve systematic compositionally.
Overall, the coverage principle provides a unified lens for understanding
compositional reasoning, and underscores the need for fundamental architectural
or training innovations to achieve truly systematic compositionality.
68353261bc28496925a185c9
Hoyeon Chang
admin_assigned
2025-05-27T12:58:28.992Z
64d0d6684dfd5df70744b237
/avatars/4ea57bfd407e8cb727c624f64af75478.svg
Chang
user
Hoyeon
68353261bc28496925a185ca
Jinho Park
68353261bc28496925a185cb
Hanseul Cho
admin_assigned
2025-05-27T12:59:21.074Z
6486e2e3c4799f43eaf3602c
/avatars/cfd3055e1f2604d07475b31f33d43d52.svg
Hanseul Cho
user
HanseulJo
68353261bc28496925a185cc
Sohee Yang
admin_assigned
2025-05-27T12:59:14.789Z
606ae0adb579bb0e88515311
https://cdn-avatars.huggingface.co/v1/production/uploads/1617617060380-noauth.jpeg
Sohee Yang
user
soheeyang
68353261bc28496925a185cd
Miyoung Ko
admin_assigned
2025-05-27T12:59:07.932Z
6485d617097c4b9f75d350e9
/avatars/8dfc0fa03a7d5846fd38014beafb0381.svg
Miyoung Ko
user
miyoungko
68353261bc28496925a185ce
Hyeonbin Hwang
admin_assigned
2025-05-27T12:59:02.515Z
647eaaf61a1fcad2fdc5d1ef
/avatars/596d7a61d6e6227d38b661210a32fed0.svg
Hyeonbin Hwang 
user
hbin0701
68353261bc28496925a185cf
Seungpil Won
68353261bc28496925a185d0
Dohaeng Lee
68353261bc28496925a185d1
Youbin Ahn
admin_assigned
2025-05-27T12:58:47.652Z
65386bbe6d1c2659e102bbbb
/avatars/6ed42e65f64cd72c7b3615c24beedb01.svg
Youbin Ahn
user
youbina
68353261bc28496925a185d2
Minjoon Seo
admin_assigned
2025-05-27T12:58:41.960Z
621f05ba970615ad5861ceb1
/avatars/7e1902aa71369a524afda9b0a9e88e22.svg
Minjoon Seo
user
minjoon
The Coverage Principle: A Framework for Understanding Compositional
  Generalization
Large language models excel at pattern matching, yet often fall short in
systematic compositional generalization. We propose the coverage principle: a
data-centric framework showing that models relying primarily on pattern
matching for compositional tasks cannot reliably generalize beyond substituting
fragments that yield identical results when used in the same contexts. We
demonstrate that this framework has a strong predictive power for the
generalization capabilities of Transformers. First, we derive and empirically
confirm that the training data required for two-hop generalization grows at
least quadratically with the token set size, and the training data efficiency
does not improve with 20x parameter scaling. Second, for compositional tasks
with path ambiguity where one variable affects the output through multiple
computational paths, we show that Transformers learn context-dependent state
representations that undermine both performance and interoperability. Third,
Chain-of-Thought supervision improves training data efficiency for multi-hop
tasks but still struggles with path ambiguity. Finally, we outline a
mechanism-based taxonomy that distinguishes three ways neural networks
can generalize: structure-based (bounded by coverage), property-based
(leveraging algebraic invariances), and shared-operator (through function
reuse). This conceptual lens contextualizes our results and highlights where
new architectural ideas are needed to achieve systematic compositionally.
Overall, the coverage principle provides a unified lens for understanding
compositional reasoning, and underscores the need for fundamental architectural
or training innovations to achieve truly systematic compositionality.
The coverage principle highlights limitations in Transformers' compositional generalization, emphasizing the need for new architectures or training methods to achieve systematic compositionality by distinguishing different mechanisms of generalization.
coverage principle data-centric framework sequential application pattern matching compositional generalization Transformers two-hop generalization token set size training data efficiency context-dependent state representations performance interoperability Chain-of-Thought supervision multi-hop tasks path ambiguity structure-based property-based shared-operator architectural innovations