Conditions for Length Generalization in Learning Reasoning Skills
This addresses a fundamental limitation in AI reasoning capabilities, though the theoretical focus makes it incremental for practical applications.
The paper investigates why large language models struggle with length generalization in reasoning tasks, identifying and proving theoretical conditions that determine whether this problem can be solved for tasks formulated as Markov decision processes or directed acyclic graphs.
Reasoning is a fundamental capability of AI agents. Recently, large language models (LLMs) have shown remarkable abilities to perform reasoning tasks. However, numerous evaluations of the reasoning capabilities of LLMs have also showed some limitations. An outstanding limitation is length generalization, meaning that when trained on reasoning problems of smaller lengths or sizes, the resulting models struggle with problems of larger sizes or lengths. This potentially indicates some theoretical limitations of generalization in learning reasoning skills. These evaluations and their observations motivated us to perform a theoretical study of the length generalization problem. This work focuses on reasoning tasks that can be formulated as Markov dynamic processes (MDPs) and/or directed acyclic graphs (DAGs). It identifies and proves conditions that decide whether the length generalization problem can be solved or not for a reasoning task in a particular representation. Experiments are also conducted to verify the theoretical results.