acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Recursive planning, Length generalization, Tower of Hanoi, Transformer

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yKTDOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This article studies the Tower of Hanoi task. The author analyzes the periodicity and parity structure of the optimal solution and proposes a hybrid architecture that combines RoPE with LSTM in a Transformer. Experiments demonstrate significant generalization capabilities to larger-scale tasks.

Critical strengths

The experimental results are very outstanding. The model achieved strong generalization on tasks far beyond the training range.

Critical weaknesses

The tasks and methods are highly specialized, lacking experimentation on other tasks. It is difficult to derive general insights from the article.

The task is simple. The core principles proven in Theorem 1 and Theorem 2 of this paper are classic properties that have already been well studied.

Questions for authors

See Weaknesses.

1 comment

We thank the reviewer for the assessment and for recognizing the strong empirical generalization results. We appreciate the concerns regarding the limited task diversity and the novelty of the structural analysis. We would like to clarify the intended contributions of our work and present additional experimental evidence.

W1. Generalizability Beyond Classical Tower of Hanoi

We agree that experiments on classical three-peg Hanoi alone cannot establish generalization to arbitrary recursive planning problems. In this work, our goal is to investigate how architectural inductive biases affect recursive OOD generalization using a controlled, analytically tractable testbed, where the optimal policy and recursive dependencies can be characterized exactly.

To further examine the generality of our findings, we conducted additional experiments on Cyclic Tower of Hanoi, where disk movements are restricted to the directed cycle 0→1→2→00 \to 1 \to 2 \to 0. Unlike classical Hanoi, this variant involves two mutually recursive transfer procedures, resulting in a different recursive program (see our detailed response to Reviewer ANjp).

The results demonstrate that our hierarchy-aware architecture remains effective under this different recursive structure. At N=100N=100, Hybrid (RoPE) achieves 100% sampled one-step accuracy, while Hybrid (APE) achieves 99.90%. Moreover, a reverse-order LSTM alone achieves 100% accuracy, whereas a forward-order LSTM achieves only 32.31%, despite identical model capacity and training configurations.

These findings support our central design principle: identify the recursive structure of a task and align the architecture's computation with it. We acknowledge that Cyclic Hanoi remains within the same puzzle family, and our results do not establish universal generalization. Rather, they illustrate how structure-aligned computation can improve OOD extrapolation across distinct recursive programs and potentially inform the design of neural solvers for other recursive tasks.

W2. Novelty of the Structural Analysis

We agree that several mathematical properties underlying Theorems 1 and 2 have classical precedents. In particular, the parity-dependent cyclic motion of the smallest disk, the cyclic orientation of individual disks, and the alternating move structure have been studied in the literature on iterative Hanoi algorithms, including:

  1. Peter Buneman and Leon Levy (1980). “The Towers of Hanoi Problem.” Information Processing Letters, 10(4–5), 243–244. https://doi.org/10.1016/0020-0190(80)90150-7

  2. Roland Backhouse and Maarten Fokkinga (2001). “The Associativity of Equivalence and the Towers of Hanoi Problem.” Information Processing Letters, 77(2–4), 71–76. https://doi.org/10.1016/S0020-0190(00)00205-2

  3. Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr (2013). The Tower of Hanoi – Myths and Maths. Birkhäuser Basel, 1st edition, 335 pages. https://doi.org/10.1007/978-3-0348-0237-6

We appreciate the opportunity to clarify that our primary theoretical contribution is not the discovery of previously unknown mathematical properties of Hanoi. Rather, we provide a self-contained structural characterization and use these properties to motivate and evaluate neural architectures for recursive OOD generalization.

Specifically, the structural analysis informs two architectural design principles: (i) relative position-dependent interactions across disk levels, motivating RoPE, and (ii) sequential computation aligned with recursive dependencies, motivating hierarchy-aware recurrence.

We additionally exploit the uniqueness of the legal non-smallest-disk move to construct a compact neural policy-learning interface based on predicting the next position of disk 0. While the underlying combinatorial observation is classical, its use as a three-class neural prediction interface allows us to separate policy learning from legal action reconstruction and systematically compare architectural extrapolation behavior.

Importantly, the central contribution of our work is empirical and methodological: we investigate which architectural and training choices support extrapolation far beyond the training regime and how these choices interact with the underlying recursive structure. Our additional experiments further reinforce this contribution. Hybrid (RoPE) achieves 100% sampled one-step accuracy on arbitrary valid configurations at N=128N=128 and N=256N=256, and retains 99.80% accuracy at N=2048N=2048, despite being trained only on N=3N=3–1010. These results substantially extend the original evaluation and demonstrate the strength of the observed extrapolation within the controlled setting.

We will revise the manuscript to more explicitly acknowledge the classical mathematical foundations, incorporate the relevant references, and distinguish established structural properties from our architectural and empirical contributions.

Thank you again for your constructive feedback.

Reviewer_SoXLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the out-of-distribution generalization of neural networks in recursive reasoning tasks, using the 3-peg Tower of Hanoi as a benchmark and formulating recursive planning as state-based optimal policy prediction. By analyzing parity-controlled cycles and hierarchical recursive patterns, the authors propose a Transformer–LSTM hybrid architecture incorporating rotary positional embeddings and hierarchical LSTMs. Experiments demonstrate single-step policy prediction accuracy on problems with up to 100 disks.

Critical strengths
  1. The paper investigates the out-of-distribution generalization of neural networks in recursive reasoning tasks, addressing the limitations of traditional Transformers in handling increasing recursion depth. This problem is of practical research significance.
  2. Trained on tasks involving only 3–10 disks, the proposed architecture maintains near-perfect accuracy in single-step policy prediction tests with up to 100 disks, outperforming the compared baselines.
Critical weaknesses
  1. The proposed method primarily combines existing Transformer, RoPE, and LSTM components, resulting in relatively limited architectural novelty. Moreover, the paper does not introduce a fundamentally new mechanism for recursive computation.
  2. The authors find that adding a training length with opposite parity improves generalization. However, this length introduces multiple additional training states, making it unclear whether the improvement stems from parity information or simply increased training data.
Questions for authors
  1. Theorems 1 and 2 primarily characterize the structural properties of optimal Tower of Hanoi solutions without providing theoretical guarantees for neural network generalization. Analyze how these structural properties relate to the model's extrapolation error.
  2. The baseline models use different parameter sizes and optimization settings. It is unclear whether the proposed method would maintain its significant performance advantage under unified parameter budgets and optimization configurations.
  3. The paper demonstrates excellent single-step prediction performance on tasks involving up to 100 disks, but the limits of this generalization remain unclear. Further evaluation on larger problem instances is needed to identify the critical scale at which the model's performance begins to degrade.
5 comments

We thank the reviewer for the thoughtful assessment and constructive suggestions. Below, we address the concerns regarding architectural novelty, parity supervision, theoretical implications, experimental fairness, and extrapolation limits.

W1. Architectural Novelty and Scope of the Contribution

We agree that our architecture combines established components rather than introducing a fundamentally new neural network operation. However, our objective is not to propose a universally superior architecture, but to investigate how architectural inductive biases affect recursive OOD generalization.

We deliberately choose Tower of Hanoi as a controlled testbed because its analytically characterized recursive structure allows us to systematically study the relationship between architectural design and length extrapolation.

Our specific architectural contribution is a hierarchy-aware Transformer–LSTM design that aligns neural computation with the recursive dependencies of the task. Specifically, (i) a Transformer with RoPE captures relative interactions across disks, and (ii) an LSTM processes the resulting representations in reverse disk order (largest to smallest), propagating information along the recursive hierarchy. Unlike conventional temporal recurrence, this recurrent computation operates across structural levels within a single state, with computation depth scaling with the number of disks. Our experiments systematically evaluate the contributions of these inductive biases to length generalization.

To further examine the generality of this design principle, we conducted additional experiments on Cyclic Tower of Hanoi, which follows a different recursive program involving two mutually recursive procedures (see our detailed response to Reviewer ANjp). At N=100N=100, Hybrid (RoPE) achieves 100% sampled one-step accuracy, while Hybrid (APE) achieves 99.90%, demonstrating that the proposed hierarchy-aware design remains effective under a different recursive structure. Interestingly, a reverse-order LSTM alone also achieves 100% accuracy, whereas a forward-order LSTM achieves only 32.31%, despite identical model capacity and training configurations.

These findings suggest a broader design principle: identify the recursive structure of a task and align the architecture's computation with it, rather than relying on a universally optimal combination of components. While our conclusions remain limited to controlled Hanoi environments, this principle may inform architectural design for other recursive tasks.

W2. Parity Ablation: Structural Information Versus Additional Training Data

We appreciate the reviewer's observation that introducing an additional training length also increases the amount of training data. We agree that adding training data may benefit the model marginally. However, the substantial improvement observed in our parity ablation cannot be explained solely by an increase in the number of training states: In the original experiment, models trained on a single parity exhibit persistent oscillations in extrapolation accuracy, achieving high accuracy on matching-parity instances but deteriorating substantially on opposite-parity instances. Introducing one training length from the opposite parity largely eliminates this failure.

To further investigate whether this improvement arises simply from additional data or greater training-length coverage, we conducted an additional comparison between the following two training regimes:

  • Regime 1: Odd-only: N∈{3,5,7,9,11}N\in\lbrace 3,5,7,9,11\rbrace.
  • Regime 2: Mixed-parity: N∈{3,5,7,9,10}N\in\lbrace 3,5,7,9,10\rbrace.
RegimeAvg. acc. on odd NAvg. acc. on even N
1100.00%1.52%
2100.00%99.33%

Notably, the odd-only regime includes a larger maximum problem size and a greater number of distinct training states than the mixed-parity regime. Nevertheless, we observe the same qualitative phenomenon: the odd-only model continues to exhibit pronounced generalization failures on even-sized instances, whereas the mixed-parity model achieves substantially more stable extrapolation across both parities.

This comparison provides additional evidence that exposure to both parity regimes, rather than simply increasing training-set size or maximum recursive depth, is important for stable generalization.

These observations are also consistent with Theorem 1, which identifies parity as a global structural variable governing the orientation of the optimal Hanoi trajectory. Training exclusively on one parity does not expose the model to the alternative orientation, allowing it to learn a decision rule that fits the training distribution but extrapolates incorrectly to the unseen regime.

We will incorporate this additional comparison into the revised manuscript to better distinguish the effect of parity coverage from that of training-data volume.

Q1. Relationship Between Structural Theorems and Extrapolation Error

We agree that Theorems 1 and 2 characterize properties of the optimal Hanoi solution rather than providing formal generalization guarantees for the learned neural network. Our theoretical analysis aims to identify structural properties that inform architectural design and explain observed extrapolation behavior, rather than establish a priori bounds on neural-network generalization error.

Specifically, Theorem 1 identifies parity as a global variable governing the orientation of the optimal solution. This provides a structural explanation for the systematic extrapolation errors observed in our parity ablation: models trained on a single parity perform well on matching-parity instances but deteriorate substantially on the opposite parity. Introducing opposite-parity supervision largely eliminates this failure mode.

Theorem 2 characterizes the periodic motion of individual disks and their relative recursive dependencies. These properties motivate two architectural inductive biases: (i) relative positional encoding to capture interactions across disk levels, and (ii) hierarchical recurrence to propagate information through the disk hierarchy with computation depth scaling with NN. Our experiments show that Transformer-only models exhibit rapid extrapolation degradation, whereas hierarchy-aware recurrent models generalize substantially further.

Thus, the structural theorems provide an interpretation of the observed generalization behavior and motivate architectural mechanisms that mitigate specific extrapolation failures. While these connections are supported empirically rather than guaranteed theoretically, they illustrate how aligning neural computation with known recursive structure can improve OOD generalization. We will clarify this distinction in the revised manuscript.

Q2. Parameter Budgets and Optimization Configurations

We appreciate the reviewer's concern regarding differences in parameter counts and training schedules. As explained in Appendix B.3, our objective is to compare the OOD generalization capabilities of different architectures after achieving strong in-distribution performance, rather than enforcing identical optimization configurations.

Different architectures can exhibit substantially different training dynamics and convergence behavior. Consequently, imposing identical parameter budgets, training curricula, or hyperparameters does not necessarily yield a fairer comparison, as these constraints may prevent certain architectures from adequately fitting the training distribution. We therefore adopt an alternative approach: independently tuning each architecture to achieve strong in-distribution performance before evaluating its OOD generalization.

Importantly, we would like to clarify the following details regarding our model configurations:

  • LSTM and Hybrid models: Both architectures contain approximately 133.6K parameters, providing a direct comparison under essentially matched model capacity.
  • Transformer-only models: We initially experimented with parameter-matched Transformer architectures (approximately 130K parameters). However, despite exploring different training schedules and hyperparameter configurations, these smaller Transformers struggled to fit the training data adequately. We therefore increased their capacity to approximately 337.5K parameters and extended training to 1,000 epochs, allowing them to achieve nearly perfect in-distribution training and validation accuracy.

Thus, the Transformer-only baselines are given substantially greater model capacity and longer training schedules to ensure satisfactory in-distribution performance. Nevertheless, they exhibit much weaker OOD length extrapolation than the proposed hybrid architectures.

We think this evaluation protocol is appropriate for our research objective. Since the central question is whether different architectural inductive biases support generalization beyond the training regime, comparing models that have already learned the in-distribution task effectively helps distinguish extrapolation failures from failures of in-distribution optimization.While parameter-matched comparisons and identical optimization budgets provide complementary perspectives, our experiments suggest that the substantial generalization advantage of the hybrid architecture cannot be explained simply by greater model capacity, longer training, or insufficient in-distribution fitting of the baselines.

Q3. Extrapolation Beyond N=100N=100

We thank the reviewer for this valuable suggestion. We agree that evaluating substantially larger problem instances would help characterize the limits of the model's length generalization.

To address this concern, we extended our evaluation to N∈{128,256,512,1024,2048}N\in\{128,256,512,1024,2048\}, corresponding to more than 200 times the maximum training length N=10N=10. For each problem size, we randomly sample 10,000 valid Hanoi configurations, not necessarily lying on the canonical optimal trajectory, and evaluate one-step optimal policy prediction accuracy using the exact shortest-path oracle described in our response to Reviewer ANjp.

The additional results are summarized below.

Table: One-step policy accuracy of Hybrid (RoPE) on randomly sampled valid Hanoi configurations beyond N=100N=100.

Number of disks NNOne-step accuracyCorrect predictions
128100.00%10,000 / 10,000
256100.00%10,000 / 10,000
51299.95%9,995 / 10,000
102499.93%9,993 / 10,000
204899.80%9,980 / 10,000

The results demonstrate remarkably stable length extrapolation far beyond the original evaluation range. Hybrid (RoPE) achieves perfect sampled accuracy at N=128N=128 and N=256N=256. Although a small number of prediction errors begin to appear at N=512N=512, the degradation remains very gradual: even at N=2048N=2048, the model correctly predicts 9,980 out of 10,000 optimal actions, achieving 99.80% accuracy.

These findings further strengthen our empirical conclusion that combining hierarchy-aware recurrence with relative positional encoding can support substantial OOD length extrapolation in the controlled Hanoi setting. Moreover, because the evaluation uses arbitrary valid configurations rather than exclusively sampling from canonical optimal trajectories, the results demonstrate that this behavior is not limited to memorizing or reproducing a particular optimal solution sequence.

We note that further extending the evaluation to even larger problem sizes is computationally increasingly expensive, as the dense self-attention component incurs O(N2)O(N^2) computational complexity with respect to sequence length. More importantly, the purpose of our study is to investigate the architectural factors supporting recursive length generalization, rather than establish the precise maximum sequence length at which a particular trained model fails.

We therefore believe that the extended evaluation up to N=2048N=2048, together with the observed onset of gradual degradation, provides substantial evidence regarding both the strength and the empirical limitations of the proposed model's extrapolation behavior. We will consider incorporating these results into the revised manuscript and explicitly distinguish the observed finite-range performance from any guarantee of unlimited generalization.

Reviewer_ANjpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether neural networks can learn recursive rules from small problems and generalize to much larger ones. The authors use the three-peg Tower of Hanoi as a testbed and analyze the structure of its optimal solution, including the parity-dependent movement of disks and the hierarchical nature of the recursive process.

Based on these observations, the authors propose a hybrid Transformer-LSTM model with RoPE. The Transformer captures relationships between disks, while the LSTM processes disk representations from larger to smaller disks. The task is formulated as next-state prediction, where the model only needs to predict the next position of the smallest disk, and a structural decoding rule determines the actual move.

The experiments show strong length generalization. When trained on puzzles with 3–10 disks, the proposed model achieves nearly perfect one-step accuracy up to 100 disks and can solve complete puzzles with up to 25 disks with very little deviation from the optimal solution.

Critical strengths
  1. The length generalization results are impressive. The strongest part of this paper is the experimental result. The model is trained on puzzles with only 3–10 disks, yet it maintains nearly perfect one-step prediction accuracy up to 100 disks. The full-puzzle results are also strong. In Figure 4, Hybrid (RoPE) remains close to the optimal solution even at 25 disks, while the other models fail much earlier or require substantially more moves. I think this is a meaningful result. Generalizing to larger recursive problems is difficult, and the gap between the proposed method and the baselines is quite large.

  2. The structural analysis provides a useful explanation for the model design. I like that the authors start by analyzing the structure of the problem instead of just trying different architectures. The discussion of parity and disk hierarchy gives a reasonable motivation for using RoPE and hierarchical recurrence. The parity ablation in Figure 5 is also interesting. Training only on odd or even disk counts leads to systematic failures on the opposite parity, while training on both removes this issue. This is a useful observation about how the training distribution affects recursive generalization.

Critical weaknesses
  1. The evaluation is limited to a single problem, and the method relies heavily on its specific structure. This is my main concern. All experiments are conducted on the three-peg Tower of Hanoi. More importantly, the proposed method makes use of several properties specific to this problem, including the ordering of disks, the parity-dependent movement pattern, and the disk-0 decoding rule. In particular, the model does not need to predict the complete next state or directly select an action. It only predicts the next position of the smallest disk, and the rest of the action is recovered using the known rules of the puzzle. I understand why the authors use this formulation, and it is a reasonable way to simplify the learning problem. However, it also makes the task much more structured than general recursive planning. The full next-state prediction ablation in Appendix B.7 further shows that removing this specialized decoding rule leads to a large drop in generalization performance. This raises an important question: how much of the result comes from learning a transferable recursive procedure, and how much comes from designing a prediction problem that is particularly well suited to Tower of Hanoi? I would be more convinced if the authors could demonstrate similar benefits on another recursive or algorithmic task.

  2. The architectural contribution is relatively simple, and the current experiments do not fully establish why this combination is necessary. The proposed architecture combines a Transformer, RoPE, and an LSTM. These are all well-established components. The main idea is to process disk representations in reverse order so that the recurrent computation follows the hierarchy of the puzzle. While the motivation makes sense, the architecture itself is fairly straightforward. The ablations show that Hybrid (RoPE) performs better than Transformer-only and LSTM baselines. However, it is still unclear whether this particular combination is essential, or whether other sequence-processing architectures with an appropriate ordering and positional encoding could achieve similar results. I also noticed in Appendix B.3 that the models have different training schedules and are not exactly parameter-matched. The authors explain their reasoning, but a more controlled comparison would help establish that the improvement mainly comes from the proposed architectural design.

Overall, I find the empirical results interesting, but the technical contribution seems somewhat limited given that the evaluation is restricted to one highly structured task.

Questions for authors
  1. How well does the proposed method generalize to other recursive problems? The current results are limited to Tower of Hanoi, and several parts of the method are specifically designed around its structure. Have the authors considered testing the same architecture on another recursive planning or algorithmic task? Even one additional task would help clarify whether the proposed inductive biases are useful beyond this particular setting.

  2. How much does the disk-0 decoding rule contribute to the reported generalization? The full-state prediction ablation in Appendix B.7 shows a substantial performance drop without this rule. I think this result deserves more discussion. Does it suggest that the strong extrapolation mainly depends on choosing a task-specific output representation? Would an action-prediction formulation that does not rely on disk-0 decoding show similar generalization?

  3. Does the model generalize equally well to states outside the canonical optimal trajectory? As described in the evaluation protocol, large-N states are sampled from the canonical optimal trajectory. This does not necessarily tell us how the model behaves on arbitrary valid configurations or after making an incorrect move. Could the authors evaluate one-step accuracy on states outside the optimal trajectory for larger disk counts? This would help determine whether the model has learned a more general policy or mainly the structure of the canonical solution.

8 comments

Dear Reviewer,

We sincerely thank you for your careful assessment and constructive suggestions. We are glad that you find the length-extrapolation results and structural analysis meaningful. We agree that the scope of generalization, the contribution of the task-specific decoding rule, and the role of architectural inductive bias deserve further clarification.

W1 & Q1. Generalization beyond classical Tower of Hanoi

We thank the reviewer for raising this important concern. We agree that experiments on classical three-peg Hanoi alone cannot establish generalization to arbitrary recursive planning problems. However, we would like to clarify why we deliberately choose Hanoi as a controlled testbed and what conclusions we aim to draw from it. We also provide additional experiments on Cyclic Tower of Hanoi.

Here, our primary objective is not to develop a universally applicable Hanoi solver, but to investigate how architectural inductive biases affect OOD generalization in problems with known recursive structure. The classical Tower of Hanoi is particularly suitable for this purpose: its optimal policy is precisely characterized, its recursive dependencies are analytically tractable, and increasing the number of disks systematically increases recursion depth and execution horizon while preserving the underlying rules. These properties allow us to isolate the effects of architectural choices, such as positional encoding and recurrent computation order, without confounding factors from more complex planning environments.

We acknowledge that our strong empirical results benefit from this controlled formulation, including the task-specific disk-0 decoding rule. We do not claim that the same architecture or prediction interface will achieve comparable performance on arbitrary recursive tasks. Rather, our goal is to identify architectural principles that may inform the design of neural solvers for other problems with recursive structure.

To investigate whether these principles extend beyond the specific recursion of classical Hanoi, we conducted additional experiments on Cyclic Tower of Hanoi, which has a substantially different recursive program.

AuthorsOpenReview ↗

Additional Experiment: Cyclic Tower of Hanoi

Task definition and recursive structure. To further investigate whether our findings extend beyond classical Tower of Hanoi, we consider Cyclic Tower of Hanoi, a variant in which disks can only move along the directed cycle 0→1→2→00\to1\to2\to0, while retaining the original disk-ordering constraints.

Unlike classical Hanoi, whose optimal solution follows a single recursive procedure, Cyclic Hanoi requires two mutually recursive transfer procedures: clockwise transfer (CnC_n, moving a stack one peg forward) and counterclockwise transfer (AnA_n, requiring two forward moves). Their optimal move counts satisfy

Cn=2An−1+1,An=2An−1+Cn−1+2,C_n=2A_{n-1}+1,\qquad A_n=2A_{n-1}+C_{n-1}+2,

with C0=A0=0C_0=A_0=0. In contrast, classical Hanoi follows the simpler recurrence Tn=2Tn−1+1T_n=2T_{n-1}+1. Consequently, Cyclic Hanoi exhibits a different recursive dependency structure and movement schedule, rather than merely changing the direction of the classical optimal trajectory.

Experimental setup. We retain the same state representation, disk-0 prediction and decoding interface, model configurations, parameter counts, hyperparameters, and training curricula as in our classical Hanoi experiments. All models are trained on N=3N=3–1010 and evaluated on unseen lengths up to N=100N=100. We additionally compare forward-order (smallest to largest) and reverse-order (largest to smallest) LSTMs, keeping their configurations identical except for the processing direction.

Results. The following table reports one-step policy accuracy.

ModelN=10N=11N=15N=20N=30N=50N=75N=100
Transformer (APE)1.00000.99340.84940.73060.60140.59120.57350.5806
Transformer (RoPE)1.00001.00001.00000.77750.64180.59550.55580.5666
LSTM (Forward)0.99990.99990.97170.74280.40740.32840.33130.3231
LSTM (Reverse)1.00001.00001.00001.00001.00001.00001.00001.0000
Hybrid (APE)1.00001.00000.99990.99980.99910.99930.99860.9990
Hybrid (RoPE)1.00001.00001.00001.00001.00001.00001.00001.0000

Analysis. The results reveal three important observations. First, Transformer-only models exhibit substantial degradation beyond the training range, whereas both hybrid models maintain strong extrapolation. Second, the processing direction of the LSTM is critical: the reverse-order LSTM achieves 100% sampled accuracy through N=100N=100, while the forward-order LSTM deteriorates to approximately 32% at N=100N=100, despite using the same model capacity and training configuration. Third, unlike classical Hanoi, the reverse-order LSTM alone matches Hybrid (RoPE), indicating that the Transformer component is not universally necessary for strong recursive extrapolation.

Broader implication. These findings reinforce the central design principle investigated in our work: identify the underlying recursive dependency structure of a problem, then align the neural computation with that structure. Classical and Cyclic Hanoi illustrate how matching computation order, hierarchical organization, and effective computation depth to recursive dependencies can substantially improve OOD generalization.

We acknowledge that Cyclic Hanoi remains within the same puzzle family, and our experiments do not establish generalization across arbitrary recursive planning domains. Nevertheless, the consistent benefits of structure-aligned computation across two distinct recursive programs suggest a potentially transferable design principle. The proposed hybrid architecture is not intended as a universal plug-in; for other recursive tasks, the relevant structural dependencies must first be identified, and the architecture adapted accordingly. We will make this distinction more explicit in the revised manuscript.

W2 & Q2. Contribution of disk-0 decoding and architectural design

We thank the reviewer for raising these important questions regarding the role of task-specific representation, architectural novelty, and experimental fairness. We would like to clarify the following points.

1. Role of disk-0 decoding and alternative action representations.

We agree that the disk-0 decoding rule incorporates task-specific structural knowledge and substantially simplifies the prediction problem compared with unconstrained full-state generation. Indeed, we believe that exploiting task-specific structure is an important ingredient for successful generalization in recursive problems. Our disk-0 decoding rule is primarily designed to provide a compact policy-learning interface that ensures legal state transitions without requiring legality masking or joint prediction across all disks.

Crucially, all evaluated architectures use exactly the same disk-0 supervision and decoding rule. Thus, while this representation contributes to the overall generalization performance, it cannot explain the substantial performance differences among the evaluated architectures. Our architectural comparisons are conducted under a shared prediction interface, allowing us to investigate how different inductive biases affect length extrapolation.

We also acknowledge that the full-state prediction ablation in Appendix B.7 changes both the training objective and the decoding procedure. Its performance degradation therefore should not be attributed exclusively to the removal of the decoder. We will clarify this distinction and expand the discussion of task-specific output representations in the revised manuscript.

Regarding direct action prediction, we agree that it provides an interesting alternative. For instance, one could predict one of six ordered peg pairs (i,j)(i,j), representing the action of moving the top disk from peg ii to peg jj. However, this formulation also relies on a task-specific action representation. Moreover, unlike disk-0 prediction, which naturally operates on the disk-wise representations produced by our sequence models, direct action classification requires mapping the entire configuration to a global action label. Such a formulation is certainly feasible, but it introduces a different prediction interface and learning objective. We therefore view the choice of output representation and the architectural inductive bias as two related but distinct factors.

2. Architectural comparisons and training configurations.

We appreciate the reviewer's concern regarding differences in model sizes and training schedules. Our objective is to compare the OOD generalization capabilities of different architectures after achieving strong in-distribution performance, rather than enforcing identical optimization configurations.

In particular, different architectures can exhibit substantially different training dynamics and convergence behavior. Imposing exactly the same training curriculum, number of epochs, or hyperparameters does not necessarily lead to a fairer comparison, since a configuration suitable for one architecture may substantially disadvantage another. We therefore tune the training configurations independently to obtain strong in-distribution validation performance before evaluating length extrapolation, as explained in Appendix B.3.

Importantly, we do not favor the proposed hybrid in terms of model size or training budget. The Transformer-only baselines contain approximately 337.5K parameters and are trained for 1,000 epochs, whereas the hybrid models contain approximately 133.6K parameters and are trained for only 300 epochs. The larger capacity and longer training schedules of the Transformer-only models are necessary to obtain satisfactory in-distribution convergence. Nevertheless, they exhibit substantially weaker OOD generalization. These observations suggest that the hybrid's advantage is not simply attributable to increased model capacity or a larger training budget.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Additional Experiments and Clarifications During the Review Period

We sincerely thank the reviewers for their constructive feedback. In response to the reviews, we conducted several additional experiments and clarified the scope and contributions of our work. We summarize the main updates below.

  1. Generalization to a different recursive program. We conducted additional experiments on Cyclic Tower of Hanoi, which involves two mutually recursive transfer procedures. Hybrid (RoPE) and reverse-order LSTM both achieve 100% sampled one-step accuracy at N=100N=100, whereas forward-order LSTM achieves only 32.31%. These results highlight the importance of aligning architectural computation with recursive dependencies.

  2. Generalization to arbitrary valid states. We extended the evaluation beyond canonical optimal trajectories using an efficient shortest-path oracle. Hybrid (RoPE) maintains 100% sampled accuracy on arbitrary valid configurations for N=3N=3–100100, demonstrating that its extrapolation is not restricted to the canonical solution trajectory.

  3. Extreme length extrapolation. We further evaluated Hybrid (RoPE) at N=128,256,512,1024,2048N=128,256,512,1024,2048, using 10,000 randomly sampled states per length. The model maintains perfect sampled accuracy through N=256N=256 and achieves 99.80% accuracy at N=2048N=2048, more than 200 times the maximum training length.

  4. Parity ablation. We performed an additional comparison between odd-only training on {3,5,7,9,11}\{3,5,7,9,11\} and mixed-parity training on {3,5,7,9,10}\{3,5,7,9,10\}. Despite having more training states and a larger maximum training length, the odd-only model still exhibits systematic opposite-parity failures, supporting the importance of parity coverage rather than data volume alone.

We also clarified our architectural contribution, the rationale for independently tuned baselines, and the relationship between our structural theorems and classical Hanoi literature.

Our central takeaway is that identifying a task's recursive structure and aligning the architecture's computation with it can substantially improve OOD generalization. While our experiments are conducted within controlled Hanoi environments, the consistent findings across distinct recursive programs suggest a potentially transferable design principle: rather than relying on a universal architecture, one can identify the structural dependencies of a recursive task and adapt the model's computation accordingly. We believe this perspective offers a promising direction for developing neural solvers with stronger generalization capabilities across broader classes of recursive reasoning and planning problems.

Detailed experimental results and discussions are provided in our individual reviewer responses. We will incorporate these additional findings, clarifications, and relevant references into the revised manuscript.

We thank the reviewers again for their time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.