The Dilemma of Recursive Reasoning: Fundamental Limitations of Neural Network Reasoning Ability

Current large language models (LLMs) demonstrate impressive reasoning abilities with the support of chain-of-thought prompting technology. However, this article reveals their fundamental limitations in recursive reasoning tasks: although they can solve complex problems via chain-of-thought, they cannot effectively generalize to deeper recursive calls. The study points out that true recursive reasoning requires an explicit call stack mechanism, which is a core missing component in current neural network architectures.

Large language models (LLMs) exhibit reasoning-like abilities in tasks such as mathematical problem-solving and logical puzzles using chain-of-thought technology, but whether this ability is equivalent to human true reasoning remains questionable. As a core mechanism of human thinking (e.g., mathematical induction, divide-and-conquer algorithms), recursion has become a touchstone for testing the essence of LLM reasoning. The core question explored in this article is: Can neural network reasoners effectively use recursive decomposition to solve complex problems?

The experimental design focuses on tasks with inherent recursion, controllable depth, and clear answers, including: tree traversal tasks (pre-order/in-order/post-order traversal of binary trees), divide-and-conquer algorithms (reasoning about merge sort/quick sort), recursive mathematical problems (Tower of Hanoi, Fibonacci sequence derivation), and nested structure parsing (JSON/XML parsing, bracket matching), to systematically evaluate the model's recursive ability.

Experimental results show that models perform well on recursive tasks with similar training depths, but their performance collapses sharply when exceeding the training depth (e.g., models trained on depths ≤5 almost completely fail on tasks with depth 10). Typical error patterns include: stack overflow simulation (confing states at different levels), premature termination (stopping before reaching the base case), and a tendency toward infinite loops (repeating calls to the same state), suggesting that models lack a true call stack mechanism.

From the perspective of computational theory, architectures like Transformer are essentially finite state machines. The attention mechanism's access is simultaneous and flat rather than hierarchical and stateful; positional encoding only provides absolute/relative positions and cannot capture dynamic hierarchical structures; LLM reasoning is more like statistical pattern matching than symbolic program execution, leading to the failure of depth generalization.

To address recursive limitations, the study explores architecture improvement schemes: explicit call stack mechanism (pushing/popping states to improve depth generalization), hierarchical positional encoding (encoding both sequence position and recursive depth), and recursion-aware training objectives (supervising stack state changes). These improvements significantly expand the range of recursive depths that models can handle.

The implications of the study for AI development include: the need to re-examine ability evaluation (emphasizing out-of-distribution and compositional generalization), the necessity of architectural innovation (mere scale expansion is insufficient), and the prospects of neuro-symbolic fusion. Future directions include: verifying findings on a wider range of tasks, exploring recursion-specific architectures, bionic human recursive processing mechanisms, and developing better evaluation benchmarks.