A Theory for Length Generalization in Learning to Reason
This addresses a fundamental bottleneck in reasoning systems for AI, though it is incremental as it builds on existing theoretical and empirical work.
The paper tackles the challenge of length generalization in learning to reason, where models trained on smaller problems fail on larger ones, by proposing a theoretical framework for problems modeled as DAGs and achieving perfect length generalization on tasks like parity, addition, and multiplication using a Transformer.
Length generalization (LG) is a challenging problem in learning to reason. It refers to the phenomenon that when trained on reasoning problems of smaller lengths or sizes, the resulting model struggles with problems of larger sizes or lengths. Although LG has been studied by many researchers, the challenge remains. This paper proposes a theoretical study of LG for problems whose reasoning processes can be modeled as DAGs (directed acyclic graphs). The paper first identifies and proves the conditions under which LG can be achieved in learning to reason. It then designs problem representations based on the theory to learn to solve challenging reasoning problems like parity, addition, and multiplication, using a Transformer to achieve perfect LG.