PaperlayerView exact revision on arXiv

Source-linked AI summary

Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out of Distribution Generalization

Mohammad Mahdi Samiei Paqaleh, Arash Marioriyad, Arman Tahmasebi-Zadeh, Mohamadreza Fereydooni, Mahdi Ghaznavai, Mahdieh Soleymani Baghshah

arXiv:2510.06274v1cs.AIcs.LG

TL;DR

Reasoning lacks a clear, consistent framework for defining and measuring generalization, unlike learning. The paper proposes Complexity OoD generalization as a framework for assessing reasoning across solution complexity, and argues that this lens links learning and reasoning while motivating changes to evaluation, model building, and training.

  • Problem

    Unlike learning, reasoning lacks a clear, consistent framework for defining and measuring generalization.

    Source: §1 · p. 3

  • Method

    The paper defines reasoning ability as generalization to test instances requiring greater representational or computational solution complexity than training instances.

    Source: §6 · p. 19

  • Results

    Complexity OoD links System-1 tasks that face greater complexity with System-2 challenges, while viewing successful System-2 performance as learning to generalize over solution-path structure.

    Source: §6 · p. 19

  • Takeaways & Limitations

    Progress toward System-2-level AI requires shifts in evaluation, model building, and training, including inductive biases for generalizing across complexity.

    Source: §6 · p. 19

    LLMs do not have guaranteed length generalization for complex or lengthy multiplication when computing internally.

    Source: §2.1 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper identifies a lack of a consistent framework for measuring reasoning and introduces Complexity OoD generalization as a way to define and evaluate it. It connects reasoning to generalization over more complex solution structures and motivates changes to evaluation and research priorities.

1 Introduction

  • Roman-numeral conversion and visual question answering illustrate tests requiring deeper solution steps than training, with VQA also adding scene clutter.The figure describes the shift as one in solution complexity, not domain or content.Source: Figure 1 · p. 2
  • Reasoning benchmarks often score final answers without examining traces, domain scope, or performance across problem difficulty, leaving reasoning ability difficult to assess consistently.The paper notes that strong results on simple cases may reflect data exposure or contamination rather than robust reasoning.Source: §1 · p. 3
  • Complexity OoD defines reasoning ability as generalizing to test problems whose solution complexity exceeds training, in representational richness or required solution steps.The framework proposes using this criterion to measure reasoning rather than relying only on final-answer correctness.Source: §1 · p. 3
  • The framework links System-1 learning and System-2 reasoning: tasks usually handled by System-1 can demand System-2 when test-sample complexity significantly surpasses the training-data distribution.System-2 thinking is slow, deliberate, and effortful, involving analytical thought and multi-step solutions.Source: §1 · pp. 2–3
  • The paper distinguishes Complexity OoD from related settings such as compositional OoD and proposes formalizing complexity using Kolmogorov complexity.It also surveys how aspects of Complexity OoD appear across domains without a unified perspective.Source: §1 · p. 3
  • The framework motivates shifts in research methodology and evaluation priorities when assessing reasoning through Complexity OoD.The paper’s outlined contributions include revisiting benchmarks and evaluation as well as how reasoning is studied.Source: §1 · pp. 3–4

2 Complexity Out of Distribution

Complexity OoD frames reasoning as generalization to test solutions whose required complexity exceeds every training example, distinguishing this demand from input or output length alone. It formalizes representational and computational complexity and proposes practical proxies for evaluating them.

2.1 Motivation

  • Complexity OoD arises when a test solution exceeds training complexity, unlike length OoD, which concerns sequence size, or systematicity, which recombines bounded familiar primitives.The framework says data scaling alone cannot resolve the challenge because a test solution can always exceed training complexity; suitable inductive biases are needed.Source: §2.1 · pp. 4, 6

2.2 Formal Definition of Complexity OoD

  • Kolmogorov complexity gives a theoretical lens for treating System-2 solutions as programs built from primitives, while its uncomputability motivates empirical proxies.The paper frames solving as searching for a shortest valid program over representation or computational primitives.Source: §2.2 · pp. 6–7

2.2.1 Representational Complexity OoD

  • Representational complexity measures an input’s description length; a test instance is OoD when its description exceeds that of every training instance.Higher description complexity corresponds to richer or more intricate structure requiring more expressive representations.Source: §2.2.1 · p. 7

2.2.2 Computational Complexity OoD

  • Computational complexity captures the procedure needed to map input to solution; a test pair is OoD when its solution program exceeds the maximum training complexity.The paper uses conditional Kolmogorov complexity K(y | x) to express the length or intricacy of the computation needed for y given x.Source: §2.2.2 · p. 7

2.3 Proxies of Complexity OoD

  • Practical proxies use scene object, attribute, and relation counts for representational complexity and reasoning-chain length for computational complexity.Figure 2 illustrates mathematical operation counts as a proxy; these measures distinguish semantic richness and reasoning depth from input length.Source: §2.3 · p. 8, Figure 2 · p. 8

3 The Duality of Learning and Reasoning under Complexity OoD

The paper treats learning and reasoning as related forms of generalization under complexity pressure: System-1 tasks can demand System-2 processing at higher complexity, while System-2 success reflects learning to generalize over solution structures.

3 The Duality of Learning and Reasoning under Complexity OoD

  • Complexity pressure links learning and reasoning: System-1 tasks can become System-2 challenges, and successful System-2 reasoning can be viewed as learning to generalize over solution structures.The framework contrasts pattern recognition with deliberate multi-step problem solving but treats them as connected under complexity shifts.Source: §3 · p. 8

3.1 From Learning to Reasoning: When System-1 Fails, System-2 Emerges

  • A recognition model trained on a few separated objects may need segmentation, relation parsing, and feature composition when tested on scenes with many interacting objects.The increased representational complexity can make a formerly straightforward recognition task require System-2-like processing.Source: §3.1 · p. 9

3.2 From Reasoning to Learning: System-2 as Generalization over Solutions

  • System-2 generalization reflects learning a procedure for constructing valid solutions, visible in improved first-attempt accuracy or fewer attempts when a verifier is available.The paper describes solutions as learned heuristics that guide search toward promising paths and prune the search space.Source: §3.2 · p. 9
  • That procedure depends on learning sufficient, minimally redundant primitive units and a heuristic policy for combining them from successful and unsuccessful traces.The paper characterizes System-2 reasoning as guided step-by-step search powered by learned System-1-like intuition, generalizing over solution structures rather than surface problem-answer statistics.Source: §3.2 · pp. 9–10

4 Related Works

The related-work review gathers research on variable-length representations and computation, LLM reasoning methods, and complexity-conditioned evaluation under a Complexity OoD perspective. It highlights evaluation of task complexity and long-horizon execution rather than relying only on aggregate performance.

4 Related Works

  • The review organizes prior work around representational and computational complexity, LLM methods that combine reasoning with learning, and complexity-conditioned evaluation.It advocates complexity-aware reporting rather than single aggregate scores.Source: §4 · p. 10

4.1 Variable-length representation.

  • Object-centric methods such as Slot Attention use dynamic slots to represent scene elements, but causal and compositional representations remain challenging to acquire with minimal supervision.Conventional fixed-length representations can entangle entities in complex scenes; emergent-language research instead studies flexible, structured communication.Source: §4.1 · pp. 10–11

4.2 Variable-length computation

  • Adaptive Computation Time lets an RNN halt or continue processing dynamically, while program-synthesis approaches search over expressions or programs of varying lengths and complexity.The review also describes Universal Transformers as extending halting mechanisms to transformer architectures.Source: §4.2 · p. 11

4.3 Some Shines of Integrating System-1 and System-2 via LLMs

  • Chain-of-thought prompting supports longer stepwise solutions but cannot backtrack; search methods such as Tree of Thought allow branching, evaluation, and revision of reasoning paths.Repeated sampling and self-correction generate or revise candidate solutions, with verification strategies used to select among them.Source: §4.3 · pp. 11–12
  • Process reward models assess intermediate steps and can guide search, but their step-level annotations are costly; outcome reward models give coarser final-answer feedback.Reinforcement-learning approaches use verifier or reward feedback, and the review describes verifier-free variants using correctness and structural rewards.Source: §4.3 · pp. 12–13

4.4 Considering Task Complexity in the Evaluation of LLMs

  • Reported reliability drops as context length and reasoning complexity increase, and models can fail over long execution horizons even when given the correct plan.The reviewed work motivates complexity-conditioned benchmarks and metrics that couple horizon length with step-level correctness.Source: §4.4 · p. 13

5 Constructing the Foundations of Complexity OoD Generalization

The section proposes practical shifts for building and evaluating robust reasoning agents: measure performance across complexity levels, supervise solution paths, and develop biases that support more complex representations and computation. It also identifies learning challenges that reappear in reasoning, including shortcuts, semantic brittleness, forgetting, and poor calibration.

5.1 Rethinking Evaluation: Tasks and Benchmarks

  • GSM8K accuracy falls as arithmetic-step complexity rises, with a sharper decline for non-reasoning models; complexity-aware evaluation reveals weaknesses hidden by average accuracy.The dataset is strongly imbalanced toward simpler problems, which can make average accuracy overly optimistic.Source: Figure 3 · p. 14, §5.1 · p. 14
  • On AIME and Omni-MATH, accuracy declines as human-solution token length rises, while reasoning-oriented models show higher accuracy and a more gradual decline.Token length is used as a proxy for reasoning complexity where fine-grained step annotations are unavailable.Source: Figure 4 · p. 15, §5.1 · p. 15

5.2 Rethinking Training: Supervision Paradigms

  • Training options range from costly, explicit solution-trace supervision to scalable final-answer supervision with sparse rewards, alongside meta-learning and self-supervised objectives for reusable reasoning structure.With final-answer supervision, intermediate reasoning is latent, creating a credit-assignment challenge; self-supervision could use unlabeled solutions or traces.Source: §5.2 · p. 16

5.3 Rethinking Methods: Inductive Biases for Complexity Out-of-Distribution

  • Complexity OoD calls for modular solution representations, such as syntax trees or computational graphs, that support reusing and composing subroutines.These structures contrast with treating a solution as a flat token sequence.Source: §5.3 · p. 17
  • Adaptive computation and recursive or iterative procedures could let models extend reasoning depth at inference for problems harder than their examples.The section identifies halting and recurrent mechanisms as early examples of adaptive computation.Source: §5.3 · p. 17
  • Persistent external memory and tools such as verifiers could help models track intermediate state and faithfully execute longer procedures.The proposed memory lets models offload intermediate results instead of keeping the entire computation history in transient activations.Source: §5.3 · p. 17

5.4 Rethinking Problems: Revisiting Learning Challenges in the System-2 Domain

  • Reasoning models can learn shortcuts from superficial wording and remain vulnerable to small meaning-preserving changes, motivating tests of solution semantics and robustness.The examples include mapping “more” to addition and sensitivity to changes in word order.Source: §5.4 · p. 18
  • Reasoning also faces skill forgetting, uncertainty about intermediate steps, and unstated assumptions that can corrupt a solution chain.The section calls for continual learning that preserves prior skills and methods that surface and challenge implicit assumptions.Source: §5.4 · p. 18

6 Conclusion

The conclusion frames reasoning as generalization to problems whose required solution complexity exceeds that seen in training, addressing the lack of a robust framework for measuring it. Complexity OoD unifies learning and reasoning and motivates changes to evaluation, supervision, and model design.

6 Conclusion

  • Reasoning evaluation remains difficult because existing paradigms can rely on contamination-susceptible average-case metrics that miss capability breakpoints on novel, complex problems.The paper argues these paradigms are insufficient for System-2 reasoning.Source: §6 · p. 19
  • Reasoning ability is framed as generalization to problems whose minimal representational or computational solution complexity lies outside the training distribution.This shifts evaluation from final-answer correctness toward the problem-solving process.Source: §6 · p. 19
  • Complexity OoD links System-1 and System-2: complexity pressure can make System-1 tasks System-2 challenges, while System-2 performance generalizes over solution-path structure.The framework also proposes measuring how performance scales with problem complexity.Source: §6 · p. 19
  • Benchmarks should explicitly test Complexity OoD and measure performance across stratified difficulty levels.The conclusion calls for complexity-aware evaluation rather than relying on static benchmark performance.Source: §6 · p. 19
  • System-2 supervision should move beyond outcome-based rewards toward process-based supervision, including settings with minimal or no step-by-step guidance.The paper also calls for inductive biases such as adaptive computation, external memory, and abstraction, arguing that Complexity OoD is not a matter of scale alone.Source: §6 · p. 19
  • Reliable solution synthesis must address spurious correlation, catastrophic forgetting, and adversarial robustness as they reappear in reasoning.The conclusion calls for a shift in how models are evaluated, built, and trained, with inductive biases for generalizing across complexity.Source: §6 · p. 19
Loading 2510.06274v1…