Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out
  of Distribution Generalization
Recent progress has pushed AI frontiers from pattern recognition tasks toward
problems that require step by step, System2 style reasoning, especially with
large language models. Yet, unlike learning, where generalization and out of
distribution (OoD) evaluation concepts are well formalized, there is no clear,
consistent definition or metric for reasoning ability. We propose Complexity
Out of Distribution (Complexity OoD) generalization as a framework and problem
setting to define and measure reasoning. A model exhibits Complexity OoD
generalization when it maintains performance on test instances whose minimal
required solution complexity, either representational (richer solution
structure) or computational (more reasoning steps/program length), exceeds that
of all training examples. We formalize complexity via solution description
Kolmogorov complexity and operational proxies (e.g., object/relation counts;
reasoning step counts), clarifying how Complexity OoD differs from length and
compositional OoD. This lens unifies learning and reasoning: many cases
solvable with System1 like processing at low complexity become System2 like
under complexity pressure, while System2 can be viewed as generalization over
solution structures. We translate this perspective into practice with
recommendations for operationalizing Complexity OoD across the stack:
incorporating complexity into benchmark and evaluation metric design,
rethinking supervision to target solution traces, seeking and designing
inductive biases for Complexity OoD generalization, addressing learning to
reason spillovers such as spurious shortcuts, semantic robustness, catastrophic
forgetting, and step wise calibration. Because Complexity OoD cannot be solved
by scaling data alone, progress toward robust reasoning will require
architectures and training regimes that explicitly model and allocate
computation with respect to complexity.
68ecbbbbcd07fb414898cc39
Mohammad Mahdi Samiei Paqaleh
68ecbbbbcd07fb414898cc3a
Arash Marioriyad
68ecbbbbcd07fb414898cc3b
Arman Tahmasebi-Zadeh
claimed_verified
2025-10-13T10:03:51.188Z
66aaa0b3ea309ca5ad17f49b
/avatars/a9e4a92e82a4bf8bf7a5add8735cb7d7.svg
Arman Tahmasebi
user
OstadTahmasb
68ecbbbbcd07fb414898cc3c
Mohamadreza Fereydooni
68ecbbbbcd07fb414898cc3d
Mahdi Ghaznavai
68ecbbbbcd07fb414898cc3e
Mahdieh Soleymani Baghshah
Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out
  of Distribution Generalization
Recent progress has pushed AI frontiers from pattern recognition tasks toward
problems that require step by step, System2 style reasoning, especially with
large language models. Yet, unlike learning, where generalization and out of
distribution (OoD) evaluation concepts are well formalized, there is no clear,
consistent definition or metric for reasoning ability. We propose Complexity
Out of Distribution (Complexity OoD) generalization as a framework and problem
setting to define and measure reasoning. A model exhibits Complexity OoD
generalization when it maintains performance on test instances whose minimal
required solution complexity, either representational (richer solution
structure) or computational (more reasoning steps/program length), exceeds that
of all training examples. We formalize complexity via solution description
Kolmogorov complexity and operational proxies (e.g., object/relation counts;
reasoning step counts), clarifying how Complexity OoD differs from length and
compositional OoD. This lens unifies learning and reasoning: many cases
solvable with System1 like processing at low complexity become System2 like
under complexity pressure, while System2 can be viewed as generalization over
solution structures. We translate this perspective into practice with
recommendations for operationalizing Complexity OoD across the stack:
incorporating complexity into benchmark and evaluation metric design,
rethinking supervision to target solution traces, seeking and designing
inductive biases for Complexity OoD generalization, addressing learning to
reason spillovers such as spurious shortcuts, semantic robustness, catastrophic
forgetting, and step wise calibration. Because Complexity OoD cannot be solved
by scaling data alone, progress toward robust reasoning will require
architectures and training regimes that explicitly model and allocate
computation with respect to complexity.
A framework called Complexity Out of Distribution (Complexity OoD) is proposed to define and measure reasoning ability in AI models by evaluating their performance on test instances requiring higher solution complexity than training examples.
Complexity OoD generalization out of distribution Kolmogorov complexity operational proxies System1 System2 solution traces inductive biases spurious shortcuts semantic robustness catastrophic forgetting step-wise calibration