Learning to Generalize Recursively: Structural Insights from the Tower of Hanoi

Transformer-based reasoning models achieve strong performance on multi-step reasoning benchmarks, yet their ability to generalize out-of-distribution (OOD) on structured reasoning and planning tasks, especially those involving recursive strategies, remains brittle. We study this limitation through the 3-peg Tower of Hanoi, a canonical recursive planning problem that requires preserving structural invariants over exponentially long execution horizons. We formulate the task as deterministic policy learning with a minimal state-based decoding rule, which separates one-step policy prediction from long-horizon deployment. We then analyze the structure of the optimal Hanoi trajectory and show that it has a parity-controlled cyclic pattern, which reveals two inductive biases important for recursive generalization: relative, shift-invariant interactions across disks and hierarchical computation aligned with recursive structure. Guided by these insights, we propose a hierarchy-aware Transformer-LSTM hybrid architecture that combines recurrence over disk order with rotary positional encoding (RoPE). Through systematic length-extrapolation experiments, we show that hierarchical recurrence substantially improves stability, and that combining it with RoPE enables near-perfect generalization far beyond the training regime. These results identify architectural inductive biases required to preserve structural consistency under deep recursive composition.