A Neuro-Symbolic Approach to Length Generalization

Length generalization (LG), which is the ability of a model trained on short inputs to correctly reason over substantially longer inputs, is a fundamental and challenging problem in learning to reason. Although chain-of-thought (CoT) training can improve LG, the challenge remains. Recent approaches have also introduced positional tags to indicate the tokens involved in each CoT step, biasing the model toward more structured reasoning. While effective to some extent, they still struggle to generalize to substantially longer inputs. In this paper, we propose a novel neuro-symbolic approach to LG for a class of reasoning problems, whose CoT input can use tags to indicate the positions of tokens involved in each reasoning step. The neural training attends only to these positions and their immediate neighbors, together with bounded control information. Instead of directly predicting the output sequence as in existing methods, our neural model predicts only a fixed set of actions that are independent of input length. The actions are executed symbolically outside the neural model to produce the next state. This is similar to how humans perform reasoning tasks. Due to the fixed local contexts and action set, the proposed method is length-invariant and can be applied to inputs of arbitrary length for the class of problems. We evaluate the proposed approach on 10 reasoning tasks, including parity, addition, subtraction, multiplication, and division. Despite training on short sequences, our method consistently generalizes to sequences of very long lengths, achieving perfect LG across the evaluated tasks.