  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.
