Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Authors: Nayoung Lee
Ziyang Cai
Avi Schwarzschild
Kangwook Lee
Dimitris Papailiopoulos
Venue: ICML 2025 poster (2025)
Keywords: self-improvement
length generalization
self-training
Primary area: general_machine_learning

Abstract: Large language models often struggle with length generalization and solving complex problem instances beyond their training distribution. We present a self-improvement approach where models iteratively generate and learn from their own solutions, progressively tackling harder problems while maintaining a standard transformer architecture. Across diverse tasks including arithmetic, string manipulation, and maze solving, our method enables models to solve problems far beyond their initial training distribution—for instance, generalizing from 10-digit to 100-digit addition without apparent saturation. We observe that filtering for correct self-generated examples leads to exponential improvements in out-of-distribution performance across training rounds. Additionally, starting from pretrained models significantly accelerates this self-improvement process for several tasks. Our results demonstrate how controlled weak-to-strong curricula can systematically expand model capabilities while preserving architectural simplicity.

Self- lero-inno Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Nayoung Lee"! 1 Ziyang Cai"!
Avi Schwarzschild
Kangwook Lee"
Dimitris Papailiopoulos 13
Abstract
tions, including changes to positional embeddings (Ruoss et al., 2023; McLeish et al., 2024; Kazemnejad et al., 2024; Li et al., 2023; Sabbaghi et al., 2024; Cho et al., 2024; Zhou et al., 2024), architectural modifications (Fan et al., 2024; Duan et al., 2023), and data format changes such as index hinting (Zhou et al., 2023: 2024). While effective in con- trolled setups, these approaches often incompatible with large language models (LLMs) in practice, they introduce task-specific modifications that are difficult to scale across diverse applications.
Large language models often struggle with length generalization and solving complex problem in- stances beyond their training distribution. We present self-imprrvement approach where mod- els iteratively generate and learn from their own solutions, progressively tackling harder problems while maintaining standard transformer archi- tecture. Across diverse tasks including arith- metic, string manipulation, and maze solving, our method enables models to solve problems far beyond their initial training distribution for in- stance, generalizing from 10-digit to 100-digit addition without apparent saturation. We ob- serve that filtering for correct self- generated exam- ples leads exponential improvements in out-of- distribution performance across training rounds. Additionally, starting from pretrained models sig- nificantly accelerates this self- improvement pro- cess for several tasks. Our results demonstrate how controlled stak-to--ttoon curricula can sys- tematically expand model capabilities while pre- serving architectural simplicity.
Instead of architectural modifications, we exploit transform- ers' tendency to exhibit some "transcendence" (Zhang et al., 2024) beyond their training distribution models trained on simple task instances sometimes solve slightly harder ones. Specifically, models trained simple instances of task can sometimes generate correct outputs for slightly harder instances. We leverage this property by applying a self-improvement framework, where the model iteratively generates its own training data and progressively learns from harder examples.
Self- celf-improvement has been widely studied in various con- texts (Singh et al., 2023; Gulcehre et al., 2023; Liang et al., 2024), typically in settings where external verifiers, weak supervision, or filtering mechanisms are used to ensure data quality. We demonstrate that extreme length gener- alization possible under this framework, even without architectural modifications. For tasks like reverse addition and string copying, self-improvement succeeds with ex- plicit data filtering. However, for harder problems such as multiplication and shortest path finding in mazes, naive self- improvement fails due to error accumulation. We show that simple data filtering techniques- such as length filtering and majority voting-suffice to maintain data quality and enable self eell-vmmrovementt to extend far beyond the initial training distribution.
1. Introduction
Despite the remarkable success of transformer-based lan- guage models (Vaswani et al., 2017) across a wide range of tasks, these models exhibit significant limitations in length generalization-thee ability to extrapolate to longer sequences than those seen during training. Even in simple algorithmic tasks such as arithmetic, standard transformer models trained with autoregressive objectives struggle to generalize to longer problem instances (Anil et al., 2022).
To address this, prior work has explored various modifica-
Our findings suggest that self-improvement is not limited to lenghh generalization but also enables easy-to-han hhad general- ization, where a model trained on simpler tasks successfully learns harder tasks without additional supervision. Notably, our approach does not introduce a new self-improvement framework but instead demonstrates its effectiveness across diverse algorithmic tasks.
'Equal contribution 'University of Disconsin-Maddion "Carnegie Mellon University 'Microsoft. Correspondence to: Nayoung Lee <nayoung, edsc Ziyang Cai zzcai55@wisc.ceo
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Self- Belf-Improving Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Forward Addition
Maze-Solving
Multiplication
Sourdi
Round
C.00
Aecuracy
Ga-
120r6-1 12uns-30 '2und-17
Number of Dights
646
10-0g1
14-8gh
278885536
20m
L101
1402
504
String Copying
00g
Number
540 Tound))
PITTP"SSC 250H) 10 S00
Hops /ound
Hope jound 10)
d:cd Joured
30
Digis
65
122
Haps
KTO 197329
10
SOGESTT 56607177717710000000
Figure 1. Overview self self-improvement results. Models trained with self eeproveereeentt can tackle increasingly complex tasks that extend far beyond their initial training distributions, achieving significant generalization without any additional supervision.
Furthermore, we investigate the dynamics of self- improvement and show that: (1) controlling the weak-to- strong curriculum is crucial, as models require a struc- tured difficulty schedule to avoid catastrophic failure, (2) relf-improvement accelerates over time, as models increas- ingly benefit from harder examples, leading to exponen- tial extrapolation, and (3) pretrained models are better at self- cof--improvement, generalizing further and faster than models trained from scratch. These results position self- improvement as a scalable solution for length generalization and beyond. Our contributions can be summarized as:
2023; McLeish et al., 2024; Kazemnejad et al., 2024; Sab- baghi et al., 2024: Cho al., 2024; Zhou et al., 2024), loop- ing (Fan et al., 2024), novel attention mechanisms (Duan et al., 2023), and input format augmentation (Zhou et al., 2023; 2024). In contrast, our approach adheres to the stan- dard transformer architecture without introducing signifi- cant modifications to architecture, positional encoding, or input structure. While prior approaches typically rely on one fixed-length training dataset, we alternate between training and generating training datasets.
More generally, easy-to- generalization is the paradigm where human annotation is provided for easier tasks but aiming to enable generalization to harder tasks with no addi- tional supervision (Schwarzschild et al., 2021; Bansal et al., 2022; Burns et al., 2023; Hase et al., 2024; Sun et al., 2024). For instance, Zhang et al. (2024) study this transcendence phenomenon in chess, showing that chess transformers can sometimes outperform all players in the training dataset. Similarly, Sun et al. (2024) finds that reward model trained easier math problems can be effectively transferred to harder problems, through reinforcement learning.
1. We apply an iterative teafnitai framework to train transformers on the arithmetic, maze and string ma- nipulation tasks, and successfully tackle easy-to-hard generalization extreme out-of-distribution test data. 2. We motivate the importance of carefully crafted self- improvement schedule and label filtering based length and majority voting, which are central to consis- tent self-improvemmen.
3. We show that the rate of self-improvement can be expo- nential and pretrained models can achieve faster accel- eration in easy-to-had tard generalization.
4. We deep-dive into reverse addition and investigate error avalanche caused by label noise, a key failure case of the self self-improvement process.
Self Improvement. When high-quality training labels are unavailable or costly to obtain, training on self-generated labels provides an efficient way to enhance model capabil- ities. Typically, this involves generating candidate labels, filtering or verifying them to prune errors, and retraining on the refined self-generated data (Zelikman et al., 2022;
2. Related Works
Length and Easy-to-Hard Generalization. Length gen- eralization is concerned with extrapolating to longer se- quence lengths than those seen during training (Anil et al., 2022). Previous approaches to improve length generaliza- tion includes architectural modifications, including special- ized positional embeddings (Li et al., 2023; Ruoss et al.,
Wang et al., 2022b; Huang et al., 2022; Singh al., 2023;
Chen et al., 2023; Gulcehre et al., 2023; Madaan et al., 2024;
Yuan et al., 2024; Liang et al., 2024). This approach has been successfully applied across various domains, including reasoning (Zelikman et al., 2022; Huang et al., 2022; Singh et al., 2023), mathematics (Zhang & Parkes, 2023; Charton
2

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
al., 2024; Liang et al., 2024), coding (Chen al., 2023), and general instruction tuning (Wang et al., 2022b; Yuan et al., 2024).
Tranoonirtial difiicuity
Repeattorr 1u R-
improsement
Extensive discussion of related works is in Appendix A.
Coflect orefictioncnn 0o0 Suka
3. Preliminaries and Experimental Setup
+
In this section, we describe the experimental setup, includ- ing the model architecture, tasks, training methodology, evaluation criteria, and the self-improvement framework.
Filter ourpur bosed on majerity vate langes
T
Seffmm-ouemer
Models We adopt the LLaMA architecture with six layers, six attention heads, and an embedding dimension of 384 and 14m parameters. We modified the architecture to use No Positional Encoding (NoPE) proposed in (Kazemnejad et al., 2024). We use character-level tokenization across all tasks except for the maze-solving task, where numbers ranging from 0 to 99 are tokenized as individual tokens.
Cont ruc training on expanded ditaset
Figure 2. Illustration of our self-improvement procedure. At cach round, the training data is updated with the model's predictions on progressively harder problems.
Details on data generation and sampling are provided in Appendix C.2.
Tasks We evaluate our approach on a diverse set of tasks, categorized into arithmetic operations, string manipulation, and maze solving. All tasks we consider admit a straightfor- ward notion of difficulty. We denote the difficulty level of a problem instance x as an integer Difficulty Table pro- vides examples, difficulty definitions, and relevant sections of each task.
Self-Improvenne Improvement Framework The self-improvement framework begins by training a model using the labeled training dataset Do, which gives us our base model Mo-
For each subsequent round r (r 1.2.3....) ), we increase the problem difficulty, such the number of digits or string length for arithmetic and string manipulation tasks, or the number of hops for maze-solving tasks, to d,. Using the previous model M,-1, we generate N, new self-improve data samples D, defined as:
Arithmetic operations:
1. Addition: We consider both reverse and forward ad- dition of two numbers of equal length. In reverse addition, both operands and the answers are reversed, so they are written with the least significant digit first. Forward addition, in contrast, follows the standard format, with the most sigmificant digit first.
D, = ((1, (x)) d,11 5 Difficully()))) S d,
Instead of the true labels yi, we obtain the predicted labels M1-1(1;) from the output of the model.
2. Multiplication: Multiplication tasks are presented in chain-of-thought (CoT)) data format (Deng et al., 2024), which includes intermediate steps to guide the computation.
At each self-improvement round r, the model is trained on the combined dataset Do U Dj U ... U D,-1, which includes the initial labeled dataset and all subsequent self- improvement datasets. To ensure sufficient training on the most recently generated data D,-1, we up-sample it with sampling probability of 50%. The remaining datasets Do. D,-2 are sampled uniformly at random. This iter- ative process allows the model to gradually tackle harder problems, leveraging its own predictions to expand the train- ing data and improve generalization.
String manipulation:
1. Copy:
Copying the input sequence.
2. Reverse: Reversing the input sequence.
Maze solving: The task to solve mazes represented as tree graphs. Given a tree graph and a specified start node and end node, the goal is to find the shortest path.
Data Filtering We employ two unsupervised data- filtering methods to refine our self-improvement dataset: 1) length filtering and 2) majority voting. For a given self-improved dataset D,- {(x,, (z.1( N. at round r, data is filtered based specific criteria on the model- generated outputs M,-1(#;), producing smaller, refined dataset D, = ((x,, M We provide more de- tails on the motivation and implementation in Section 5.
Data Generation and Sampling We generate an initial supervised training dataset Dy of up to a fixed difficulty level do by uniformly sampling the difficulty level < do- followed by independent sampling of the data conditioned on the difficulty. Denoting the input as x;, labels as y/.
Do- = ((. No where Difficulty(x:) S do.
3

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Table I. Examples of Tasks Considered
Task Type
Input (Q: Prompt, A: label)
Task Difficulty
Sections
Reverse Addition
Q: 31538+91786=
A: 232451
4.1
Max digit length of the two operands
Forward Addition
Q: 85513+687199
A: 154232
6.1
Multiplication
Q: 34895*148=
A: 11339904779222555522-44744444449
6.2
Copy
Q: 12345=
A:12345
Length of string
4.2
Reverse
Q: 12345=
A: 54321
Finding shortest path from node 2 to 19
Maze (Nodann, Hapan
example image illustration)
(1) Number hops between start & end
2> 02221999733300777777270000-02723 755777..001922297-:07755----
Maze Solving
(2) Number of nodes
6.3
A: 2>97>>70=33-75511
Training and Evaluation Except for the experiments on pretrained Llama 3.2 models, all models are trained from scratch using the conventional next-token prediction objec- tive. The loss is computed solely the completion, mean- ing that the input prompt is masked, and only the model's predictions are included in the loss computation. Detailed settings, including hyperparameters and training schedules, are provided the Appendix C.3.
Setsmaron Unmmrro hours
Mamber of Dagie
Figure 3. Reverse addition task. The self celf-improvement framework enables model initially trained 1-16 digit examples general- ize perfectly to over 100-digit addition. Each shade of color a different self imp-roemmmentttt round.
During inference, we use greedy decoding and exact-match accuracy as the primary metric for evaluation. A prediction deemed correct if all tokens in the output sequence match the ground truth; any discrepancy in the generated tokens is classified an incorrect prediction.
Tuusc
mand
4. Length Generalization on Reverse Addition and String Copying/ Reversing
Hund
In this section, we apply our self-improvement framework to reverse addition and string copying/reversing.
Cumrnn Accusety
Namber
Figure 4. Error avalanche is common failure case for self- improvement. As inaccuracies in self- geffggeerrtedd data accumulate, they degrade future rounds of training, leading eventual failure.
4.1. Reverse Addition
Reversed addition, where the operands and output are writ- ten with the least significant digit first. has been shown to enhance sample efficiency and performance (Lee et al., 2023). Reversed addition has become a popular setting for studying length generalization arithmetic tasks (Lee al., 2023; Shen et al., 2023; Zhou al., 2023; 2024; Cho al.,
4.2. String Copy & String Reverse
Copying and reversing input string is another task that considered hard for vanilla transformers (Zhou et al., 2023).
Results. Similar to reverse addition task, Figure 31 demon- strates that starting with strings of length 10, the self- improvement framework enables the model perfectly gen- eralize string lengths of over 120 after approximately 100 ceff-improvement rounds.
2024; McLeish et al., 2024).
Results Figure 3 demonstrates that, starting with model trained on to 16-digit reverse addition, the self- improvement framework enables near- near-perfect length gener- alization up to 100 digits without any additional supervision or modifications to positional encodings, input formats, or the Transformer architecture.
5. Unsupervised Data Filtering
Our framework leverages models' ability to generalize slightly beyond their training difficulty to sample increas- ingly hard examples. A critical component for success

---

Self- Sefr-Impoo Transformers Overcome Easy-to- and Length Generalization Challenges
worward Adation vania
Forward Acunarr lenghn Hferr
Pacoddy
Tex Feccncllggh mibtt Filer cennlliole
0.-
Figure 5. Overview of the two data-filtering methods employed. Length filtering removes data points with outputs shorter than a predefined threshold, relative the maximum output length in the batch. Majority voting filters data based on consensus among predictions from multiple models trained on different seeds.
Number 34pe5
Figure 6. Models trained on forward addition over 10 self- improvement rounds. (Left) Without data filtering, (Right) With length-based filtering using a threshold of 2. Data filtering signifi- cantly enhances length generalization performance.
the quality of the self-generated data. Low-quality data can negatively impact the model's generalization perfor- mance, leading to even lower-quality data in subsequent rounds and ultimately causing a cascading degradation of the self-improvement process as illustrated in Figure 4.
ter the data such that only pairs {(T2, MM, (a)))} where M (Ix)) matches at least [T x k] outputs among the A models are retained. This ensures that only high-consensus data are preserved for training in subsequent rounds, thereby significantly improving overall data quality and model per- formance. This approach is conceptually similar an itera- tive version of the bagging algorithm (Breiman, 1996).
While cascading error effects are analyzed in greater detail in Section 8 and Appendix 5, this section focuses on two key data-filtering methods used in this work: length filtering and majority voting (Figure 5). And in Section 6 we apply the filtering methods to enable difficulty generalization in forward addition, multiplication and mazes.
6. Length and Difficulty Generalization on Forward Addition, Multiplication, Maze
Relative Length Filtering. common error in model- generated data is that the generated labels are often shorter than the correct answers (Figure 17). These observa- tions motivate a filtering method based on the relative lengths of model-generater predictions. Specifically, pre- dictions shorter than a predefined threshold-calculant relative to the maximum prediction length within their batch-are filtered out. For a batch of model-predicted outputs, we identify the maximum length of the output == max |M,- (z:) and filter out predictions M, (x.)) with lengths shorter than predefined threshold т. This method is unsupervised, as it relies solely on comparing lengths within model-generated outputs rather than referenc- ing ground wround-truthha labels. While particularly suited to length generalization tasks, where harder problems are expected to yield longer answers, length-based based filtering shows broader potential for addressing similar challenges in other tasks.
We extend evaluation to class of harder tasks, in- cluding forward addition, multiplication, and maze-solving. Our results demonstrate that the framework is not limited to length generalization but extends to difficulty gener- alization, where the model incrementally learns to solve increasingly difficult problems. By employing controlled sampling of problem difficulty and data filtering techniques for each round, the model successfully adapts harder tasks, highlighting the versatility and robustness of the self- improvement approach.
6.1. Forward Addition
Forward addition is straightforward task, yet very chal- lenging for transformer models to length generalize In reverse addition, each step only requires processing a fixed- size subset of the input. However, in the forward addition, the size of the relevant input required to generate correct tokens increases, making the problem more complex (Zhou et al., 2023).
Majority Voting Generating multiple candidate answers to ensure self-consistency is a widely used approach for enhancing data quality (Huang et al., 2022; Wang et al., 2022a; Qu et al., 2024; Peng et al., 2024). However, unlike the common practice of sampling multiple reasoning paths by generating outputs with a non-zero temperature, our task of interest requires single correct answer for each instance. To address this, we train k models (M M,( using different random seeds and self-improvement data, then apply a vojority-voting mechanism with threshold r.
Results. Figure shows the results of forward addition experiments, where the model is initially trained on labeled data of up to 10 digits and then undergoes 10 rounds of self- improvement. Without any data filtering (Left), the model's s performance begins to deteriorate after few rounds of training, leading to collapse in generalization. However, applying the length- filtering approach with threshold length of 2 results in significant improvements in length generalization performance (Right). By refining the self- improvement dataset at each round, the self-improvement
Concretely, for each self-improved dataset D; ((r,, M (z:))) where 8 is the seed index, we fil-
5

---

Self- Self-Improving Transformers Overcome Dasy-to-Harde and Length Generalization Challenges
Forward Andten with date reknnng
ods round 7, where models are trained on self- sefffggeeratedd data for up 6-by-6 multiplication. All three filtering meth- ods enhance self-improvement, with majority voting outper- forming length filtering. The combined approach- applying both majority voting and length perfect generalization to 6-by-6 multiplication.
achieves near-
Rurder Dott
Figure 7. Performance on the forward addition task with length filtering. The model is initially trained on laheled forward addition data of lengths to 10. With over 60 self- infrrrrppoeeettt rounds, the model achieves strong generalization to lengths up to 75.
Training for additional rounds further extends this general- ization. The combined filtering strategy continues to yield near- near-perfect accuracy up to 9-by-9 multiplication at round 31 (Figure 36), with the potential for even further generaliza- tion in subsequent rounds. We further demonstrate that we can accelerate the process, achieving perfect performance on 10-by-10 multiplication in just 19 rounds (Figure 23).
6.3. Maze
Figure 8. Comparison of filtering methods at round 7. From left to right: no filterin,, length filtering, majority voting, and a com- bination of majority voting and length filtering. Data filtering significantly improves self-improvement performance, with the combined approach achieving the best results.
We extend our evaluation from arithmetic to a more com- plex problem: finding the shortest path in a maze. Pathfind- ing presents significant challenges for autoregressive mod- els (Bachmann & Nagarajan, 2024). Our mazes can be represented by a tree graph in a 2-dimensional space and they do not have loops. Figure 30 provides visualization of this task and the corresponding input and output data format. Details on maze generation are provided in Appendix C.2.3.
framework remains robust across multiple rounds.
With continued training over 60 self- improvement rounds, the model maintains performance exceeding 98% accuracy for sequences up to length 70 (Figure 7). This demonstrates the effectiveness of length-basel filtering in sustaining the self- self-improvement process and enabling models to generalize to much longer sequences.
We evaluate two generalization settings: 1) increasing the number of hops while keeping the number of nodes fixed, and 2) increasing the number of nodes while keeping the number of hops fixed. In the first setting, the input graph description remains constant in size, but the output length grows as the difficulty increases. In the second setting, the input graph expands with more nodes, while the output remains of fixed length.
6.2. Multiplication
We also extend our approach on multiplication, which is a challenging task even in-distribution (Dziri et al., 2024). Fine-tuning large language models on datasets with chain- of (ooT steps has shown limited success. We adopt a data format similar to Deng et al. (2024), where multi- plication is given a problem of multiplying two numbers, the label expands the multiplication into steps that include partial products of multiplying the first operand with each digit of the second operand and the intermediate results.
1.3.1. 1. INCREASING THE NUMBER HOPS
The difficulty of the maze-solving task increases with the number of hops required from the start node to the end node. We begin by training the model on a labeled dataset contain- ing paths of up to h = 9 hops. In each eelf-imrrvemment round, we increase h by one, progressively introducing longer paths, while fixing the number of nodes N = 30.
The model is initially trained on n-by-n multiplication ex- amples with 5. Directly introducing + 1-by-n + examples results in poor performance, hence, we adopt a more fine-graid ine-grrined difficulty schedule where we sample n + 1-by-m and m-by-n +1 1 examples with m growing from to n + 1. This gradual progression allows the model to adapt incrementally to larger operand sizes, making the transition harder examples more manageable.
Results. As shown in Figure 9, without data refinement, self-generated training data degrades over successive rounds, leading to an eventual collapse in the self- iefrommprovetttt process. In contrast, majority voting stabilizes data quality, allowing near-perfect data quality and the model continues to successfully generalize to paths up to 30 hops.
To improve the quality of self-generated training data, we apply three data filtering methods: length filtering, majority voting, and a combination of both (Appendix C.3).
Results.
6.3.2. INCREASING THE NUMBER OF NODES
Another approach to increasing task difficulty is to expand the number of nodes in the graph while keeping the number of hops fixed at h = 9. We begin by training the model on
Figure& compares the effectiveness of these filtering meth-
6

---

Self- Self-Improvng Transformers Overcome Masy-to-Hardy and Length Generalization Challenges
or www.e
Round
Figure 9. saze-solving with increasing hops (N nodes). Models are trained on graphs with to hops and generalized by incrementally increasing hops by in each self-improvement round. Results show mean accuracy across 3 seeds. (Left) No filterin. (Middle) Majority voting. (Right) Self-improve data accuracy per round. Filtering significantly enhances data accuracy and improves generalization.
Figure 11. Number of extra OOD digit lengths achieving over 99% accuracy when improviig with one additional digit per round. (Left) copy and (Right) reverse addition tasks. The growing OOD capability suggests the potential to sample more digits per round self-improvement progresses.
7. Ablations
7.1. Increasing OOD generalization with more self-improvement
Sampling instances that are too difficult for the current model is detrimental to the quality of self-improvement data, which causes downstream performance to break down. However, in tasks like reverse addition and copy, we observe that the out-o--distribution (OOD) extrapolation capabili- ties improve progressively as the model undergoes more rounds of self cofroimproveeett, which means we can sample more and more difficulty levels every round. Figure 11 illus- trates how the number of additional OOD lengths achieving over 99% accuracy grow with each round when the model is self-improved using only one additional digit per round. The model's 's OOD extrapolation capabilities expand as it is trained on longer sequences.
Figure 10. Maze-solving with increasing nodes (h hops). Models are trained on graphs with up to 30 nodes and generalized by incrementally increasing the number of nodes by 3 per round. Majority voting improves generalization to larger graphs.
a labeled dataset containing paths of fixed number of hops h 9, and nodes N 10 to 30. In each self- improvepptee round, the number of nodes is increased by 3.
Results. As shown in Figure 10, training without filtering leads to gradual performance degradation, whereas major- ity voting preserves high-quality data, maintaining a self- improvement accuracy above 99.7% and enabling general- ization to larger graphs with 9 hops.
7.2. Accelerating self-improvement
Since the amount of extra OOD generalization increases roughly linearly with each additional round of self- improvement (Figure 11), sampling as many difficulty levels as possible per round could lead to exponential improve- ments in performance. Therefore, we propose an acceler- ated self-improvement schedule: At each round, the self- improvement dataset is uniformly sampled from all difficulty levels achieving over 99% evaluation accuracy, instead of incrementally sampling by only one additional length. As shown in Figure 12, this approach allows the model to achieve 100 digit extrapolation with less than half of the rounds. All other hyperparameters remain unchanged. We also provide results in the multiplication setting in Figure 23.
While these experiments focus on fixing one dimension (number of hops or number of nodes) and increasing the other, alternating between increasing the difficulty in both dimensions is expected to generalize the maze- solving task to handle larger graphs and longer paths simultaneously.
6.3.3. VERIFIERS
Solving the shortest path problem can be computationally expensive, but verifying the correctness of given solution is significantll simpler. A valid path can be verified by traversing the sequence and ensuring three conditions: 1) each move is valid, meaning the path follows adjacency constraints; 2) the final destination matches the intended goal; and 3) no nodes are repeated, confirming that the solution is indeed the shortest path.
7.3. Pretrained Models
We extend our self- infroimproveentt framework to pretrained models, specifically I.lama and Llama-3B (Al @ Meta, 2024), to explore scaling effects and the impact of finetuning on larger models. For consistency in tokenization, we use character-leve tokenization instead of the default tokenizer of the Llama models, and use LoRA (Hu al., 2021).
We show in Appendix B.3 that while filtering self self-generated data using oracle verifiers based on move and end validity is effective, majority voting based filtering-wee withoout any external verification perffores comparably, highlighting its effectiveness.
7

---

Sell-Impoovng Transformers Overcome Easy-to-Hare and Length Generalization Challenges
Accelerated Addition
Accelerated Copy
round 5
round 20
175
Scratch
unfiem pertarb drop-dights drop proturo
Scratch, Optinstk:
CLaR securney
156
30
porturo drop-digts dropprettr
00
0.4
0.6
64
24
5.5
Setl-mprove Rounch
SetHimprove Roands
Figure 13. Simulating error avalanche. Errors are injected at the end of rounds 5 and 20, and the seff-improvement process contin- ues for five additional rounds. The model tolerates emors up to a threshold before performance collapses. This tolerance increases with more rounds of reff-improvement.
Figure 12. Maximum input length achicving over 99% accuracy at different selff- improvement rounds for (Left) Reverse addition and (Right) Copy task. The dashed linear line represents the standard schedule of sampling one additional length per round. Faster self- improvement schedules allow the model to generalize to longer inputs with fewer rounds. Furthermore, finetuning from pretrained models enhances the accelcration.
We inject these errors at rounds 5 and 20 of the reverse addition task and track their effects after five subsequent self-improvement rounds. As shown in Figure 13, inject- ing enough of these errors into the training data causes performance on the next difficulty crash. In particular, we find that 1) structured noise (perturb, drop-digits) are more harmful than uniform noise and 2) more rounds of self iellovmmroeeeentt lead to robustness against label noise.
Results. Larger models achieve better extrapolation per- formance, which leads to faster acceleration with larger models. Figure 12 compares self-improvement acceleration between Llama-3B, Llama- IB, and smaller 14M parame- ter model trained from scratch. The results demonstrate that larger pretrained models can generalize to longer sequences with fewer rounds of self eeffimmproveent.
These findings emphasize the critical need for maintaining high-quality self-generated data to sustain effective and per- sistent self-improvement. We present more results on label noise and robustness in Section B.7
8. Error Avalanches in Self- Self-Improvement
The success of self-improvement hinges on the accuracy of self-generated data. Figure highlights a key challenge for out-of-distribution (OOD) generalization, specifically in + 1-digit performance. Inaccuracies in self-generated n-digit data negatively affect generalization, leading to even poorer performance in the subsequent round.
9. Limitations
In our framework, we identify three core limitations: First, our approach only generates solutions (labels) rather than new input instances during eeff-improvement. It is a sep- arate challenge to model input distributions based on task difficulty. Second, defining and quantifying task difficulty remains an open challenge in real-world domains, though we find models show some robustness to imperfect dif- ficulty scheduling, particularly with pretraining. Finally, while our framework assumes models can handle slightly harder tasks than their training data, this may not hold for all problems as demonstrated by raw multiplication tasks. However, breaking problems into intermediate steps can enable the necessary out-of-distribution generalization for self- infroveproveett.
This cascading effeet, or error avalanche, compounds over successive seff-improvement rounds, ultimately degrading the model's 's overall performance and risking a collapse of the self-improvement process.
A natural question is: how much error is required trigger an avalanche? We investigate this question by first char- acterizing the model mistakes, and then injecting synthetic wrong examples into the celf-improvement data.
Simulating Avalanche We identify that model mistakes are mainly of two types: (1) incorrect digits by 1 and (2) dropped digits (see section B.6). We simulate these errors by constructing four kinds of noises:
10. Conclusion
In this work, we have shown self-improvement training enables transformers gradually generalize from easy to hard problems without access to hard labels. One extension is to incorporate more sophisticated verifiers as well as problem classes that is easy to verify but hard to solve. We expect self-improve to synergize with strong verification to enable transformers to solve harder problems beyond arithmetic or mazes.
uniform: replacing the label with another random number of the same length.
perturb: perturbing last three digits of the label by 1 drop-digits: dropping 1-3 digits from the last 3 digits. drop- perturb:: first applying "perturb" and then "drop- digits", effectively combining the effect of both noises.
8

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Impact Statement
2024. URL https: //api. wwwanticscoolaa......
org/ 2ttp/ooopuTDD:2761105555
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Bertrand, Q., Bose, A. J., Duplessis, A., Jiralerspong, M., and Gidel, G. On the stability of iterative retraining of gen- erative models on their own data. ArXiv, abs/2310.00429, 2023. URL https: /app..app.////// www.nti org/ //Croorruuaaa 263334017.
Acknowledgment
Breiman, L. Bagging predictors. Machine learning, 24:
D.P. is supported by NSF Medium award No. 2403074, ONR Grant No. N00014-21-11 1-2206 and No. N00014-23- 1-2848. K.L. supported by NSF Award DMS-2023239, NSF CAREER Award CCF-2339978, Amazon Research Award, and grant from FuriosaAI.
123-140, 1996.
Briesch, M.. Sobania, D., and Rothlauf, F. Large language models suffer from their own output: An analysis of the self-consuming training loop. ArXiv, abs/2311.11622.
2023. URL https: / api semanticscholar. org/ :Trruu
References
AI@ Meta. Llama 3 model card. 2024. URL bttts::/gitthne com/ aetammmtaaaeeee aalaaaaaa/aa aaammmmmmm/////////////aa blob/main http://mannMMMELLLL_B /MOD/M .nd.
Burns, C., Izmailov, P., Kirchner, H., Baker, B., Gao, L., Aschenbrenner, L.., Chen, Y., Ecoffet, A., Joglekar, M., Leike. J., et al. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. arXiv preprint arXiv:2312.00 2209990, 2023.
Alemohammad, S., Rodriguz,, J., Luzi, L., Humayun, A. I., Babaei, H. R., Leleune, D., Siahkoohi, A., and Baraniuk, R. Self-consuming mad. ArXiv, abs/2307.0185h) 2023. URL https:/ http:::://ap....aaaaaa.mmmm.m org Co CtrrCrrrpssti IDp 259341807
Charton, F., Ellenberg, J., Wagner, A. Z., and Williamson, G. Patternboost: Constructions in mathematics with a little help from ai. arXiv preprint arXiv:2411.00566, 2024.
generative models
Chen, X., Lin, M., Schärli, N., and Zhou, D. Teaching large language models to self-debug. arXiv preprint arXiv:2304.051226 2023.
Alfarano, A., Charton, F., and Hayat, A. Global іyapunov functions: a long-standing open problem in mathematics, with symbolic transformers. In The Thirty-eigtth Annual Conference on Neural Information Processing Systems, 2024.
Cho, H., Cha, J., Awasthi. P., Bhojanapalli, S., Gupta, A., and Yun, C. Position coupling: Improving length general- ization of arithmetic transformers using task structure. 2024. URL https: /api..... semant www.mmtticcchlar........ cscholar. org/ :ttp:/oopuIID:23355000
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. Exploring length generalization in large language models. Advances in Neural Information Pro- cessing Systems, 15:38546-38555 2022.
de Arcaute, G. M. R., Watson, I.., Reviriego, P., Hernández, J. A., Juárez, M., and Sarkar, R. Combining generative artificial intelligence (ai) and the internet: Heading to- wards evolution or degradation? ArXiv, abs/2033.02555. 2023. URL https: /api. semanticscholar. org /
Bachmann, G. and Nagarajan, V. The pitfalls of next-token prediction. arXiv preprint Stt.::24030066666 2024.
Bansal, A., Schwarzschild, A., Borgnia, E., Emam, Z., Huang, F, Goldblum, M., and Goldstein, End-to- end algorithm synthesis with recurrent networks: Ex- trapolation without overthinking. Advances in Neural Information Processing Systems, 35:20232-20242, 2022.
Deng, Y., Choi, Y., and Shieber, From explicit cot implicit cot: Learning to internalize cot step by step. arXiv preprint arXiv:2405.14833 2024.
Dohmatob, E., Feng, Y., Yang, P., Charton, F., and Kempe, J. A tale of tails: Model collapse as a change of scaling laws. ArXiv, abs/2402.07043, 2024. URL https::/appi.smmmatteee http:///app.emettsssscoooooo semanticscholar. org / /otp///oi::::/677 628004.
Bansal, H., Hosseini, A., Agarwal, R., Tran, V. Q., and Kazemi, M. Smaller, weaker, yet better: Training I1m reasoners via compute-optimal sampling, arXiv preprint arXiv:2408. 16737, 2024.
Bayat, R., Pezeshki, M., Dohmatob, E., Lopez- Paz, D., and Vincent, P. The pitfalls mem- orization: When memorization hurts generalization.
Duan, S., Shi, Y., and Xu, W. From interpolation to extrap- olation: Complete length generalization for arithmetic transformers. arXiv preprint arXiv:2310. /1884 2023.

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Dubois, Y., Dagan, G., Hupkes, D., and Bruni, E. Location attention for extrapolation to longer sequences. arXiv 2019.
Self-improvement in language models: The sharpen- ing mechanism, 2024.
preprint
Abs/2412.01
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Le Bras, R., et al. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems, 36, 2024.
Huang. J., Gu, S. S., Hou, L., Wu, Y., Wang, X., Yu, H., and Han, J. Large language models can self-improve. arXiv preprint arXiv:22 10. 11610, 2022.
Hupkes, D., Dankers, V., Mul, M., and Bruni, E. Compo- sitionality decomposed: How do neural networks gen- eralise? Journal of Artificial Intelligence Research, 67: 757-795, 2020.
Fan, Y., Du, Y., Ramchandran, K., and Lee, K. Looped transformers for length generalization. arXiv preprint arXiv:2409.15647 2024.
Jelassi, S., d' Ascolli S., Dooiiooo--miinnn Ennich, C., Wu, Y., Li, Y., and Charton, Length generalization in arithmetic transformers. arXiv preprint arXiv:2306. 15400, 2023.
Feng. Y., Dohmatob, E., Yang, P., Charton, F., and Kempe, Beyond model collapse: Scaling up with synthesized data requires reinforcement. arXiv preprint arXiv:2406.07515 2024.
Kazemnejad, A., Padhi, I., Natesan Ramamurthy, K., Das, P., and Reddy, S. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36, 2024.
Gerstgrasser, M., Schaeffer, R., Dey, A., Rafailov, R., Sleight, H., Hughes, J., Korbak, T., Agrawal, R., Pai, D., Gromov, A., et al. Is model collapse inevitable? breaking the curse of recursion by accumulating real and synthetic data, arXiv preprint prXiv:2404.0141: 2024.
Kim. D., Lee, J., Park, J., and Seo, M. How language models extrapolate outside the training data: A case study in textualized gridworld. arXiv preprint arXiv:2406.1522 15275, 2024.
Gillman, N., Freeman, M., Aggarwal, D., Hsu, C.-H., Luo, C., Tian, Y., and Sun, C. Self-correcting self-consuming loops for generative model training. arXiv preprint arXhv:2402.07087 2024.
Lee, N., Sreenivasan, K., Lee, J. D., Lee, K., and Papail- iopoulos, D. Teaching arithmetic to small transformers. arXiv preprint (xXiv:337700388) 2023.
Li, S., You, C., Guruganesh, G., Ainslie, J., Ontamon, S., Zaheer, M., Sanghai, S., Yang, Y., Kumar, S., and Bho- janapalli, Functional interpolation for relative posi- tions improves long context transformers. arXiv preprint arXiv:2310.0444 2023.
Gulcehre, C., Paine, T. L., Srinivasan, S., Konyushkova, K., Weerts, I.,, Sharma, A., Siddhant, A., Ahern, A., Wang, M., Gu, C., et al. Reinforced self-training (rest) for language modeling. arXiv preprint urXiv:2308.08900 2023.
Liang, Y., Zhang, G., Qu, X., Zheng, T., Guo, J., Du, X., Yang, Z., Liu, J., Lin, C., Ma. L., al. I- sheep: Self-alignment of Ilm from scratch through an iterative self-enhancement paradigm. arXiv preprint arXiv:2408.0807 2024.
Hase. P., Bansal, M.. Clark, P., and Wiegreffe, S. The unreasonable effectiveness of easy training data for hard tasks. arXiv preprint arXiv:2401.06751, 2024.
Hataya, R., Bao, H., and Arai, H. Will large-scale generative models corrupt future datasets? In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), pp. 20555-20566
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, Let's verify step by step. arXiv preprint arXiv:2305.20050, 2023.
October 2023.
Hosseini, A., Yuan, X., Malkin, N., Courville, A., Sordoni, A., and Agarwal, R. V-star: Training verifiers for self- taught reasoners. arXiv preprint 07Xiv:2402.06457, 2024.
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S.. Yang, Y., al. Self-refine: Iterative refinement with self- feedback. Advances in Neural Information Processing Systems, 36, 2024.
Hu, J. E., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., and Chen, W. Lora: Low-rank adapta- tion of large language models. ArXiv, 0os/2106.09685, 2021. URL htttts::/app..mmmatii.... semanticscholla.. http://oopii:::4:555:
McLeish, eish, S., Bansal, A., Stein, A., Jain, N., Kirchenbauer, J., Bartoldson, B. R., Kailkhura, B., Bhatele, A., Geip- ing, J., Schwarzschild, A., et al. Transformers can do arithmetic with the right embeddings. arXiv preprint arXiv:2405. 17399, 2024.
Huang, A., Block, A., Foster, D. J., Rohatgi, D., Zhang, C., Simehowitz, M., Ash, T., and Krishnamurthy, A.
10

---

Self-Improving Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Newman, B., Hewitt, Liang, P., and Manning, C. D. The decision and length extrapolation. arXiv preprint arXiv:2010.07174. 2020.
Shumailov, I., Shumaylov, Z., Zhao, Y., Papernot, N., Ander- son, R., and Gal, Y. Ai models collapse when trained on recursively generated data. Nature, 63 (8122)))7555775 2024.
Pang. R. Y. Yuan, W., Cho, K., He, H., Sukhbaatar, S., and Weston, J. Iterative reasoning preference optimiza- tion, 2024. URL https: p hopps///arae /ttp//axiiv...////////e////.aavl orggabs/2400/ 19733.
Singh, A., Co-Reyes, D., Agarwal, R., Anand, A., Patil, P., Garcia, X., Liu, P. J., Harrison, J., Lee, J., Xu, K., et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXiv:2312.06558 2023.
Peng, X., Xia, C., Yang, X., Xiong, C., Wu, C.-S., and Xing, C. Regenesis: Llms grow into reasoning generalists via ieproventreeeent.. arXiv preprint arXiv:2410.02108, 2024.
Song. Y., Zhang, H., Eisenach, C., Kakade, S., Foster, D., and Ghai, U. Mind the gap: Examining the self- improvement capabilities of large language models. arXiv preprint arXiv:2412.02672 2024.
Pise, N. N. and Kulkarni, P. A survey of semi-supervised learning methods. In 2008 International conference on computational intelligence and security, volume 2, pp. 30 34. IEEE, 2008
Sun, Z., Yu, L., Shen, Y., Liu, W., Yang, Y.. Welleck, S., and Gan, C. Easy-to-hard generalization: Scalable alignment beyond human supervision. arXiv preprint arXi::2403.044/ 2024.
Qu, Y., Zhang, T., Garg, N., and Kumar, A. Recursive introspection: Teaching language model agents how self-improve. arXiv preprint arXiv:2407.18219 2024.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Quirke, P. and Barez, F. Understanding addition in trans- formers. arXiv preprini arXiv:2310.3312/ 2023.
Wang. X., Wei, J., Schuurmans,
D., Le. Q., Chi, E., and Zhou, D. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.1 /171, 2022a.
Rolnick, D. Deep learning is robust to massive label noise. arXiv preprint orXiv:/705, 1et..70559.44 /0694, 2017.
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csor- dás, R., Bennani, M., Legg, S., and Veness, J. Random- ized positional encodings boost length generalization of transformers. arXiv preprint arXiv:2305. /6843, 2023.
Wang. Y., Kordi, Y.. Mishra, S., Liu, A., Smith, N. A., Khashabi, D., and Hajishirzi, H. Self-instruct: Aligning language models with self-generan -eferaedddted instructions. arXiv preprint arXiv:2212. 10560, 2022b.
Sabbaghi, M., Pappas, G., Hassani, H., and Goel, S. Ex- plicitly encoding structural symmetry is key to length generalization arithmetic tasks. arXiv preprint arXiv:2406.01189 895, 2024.
Wen, K., Li, Z., Wang, J., Hall, D., Liang, P., and Ma, Understanding warmup-stable-decn learning rates: A river valley loss landscape perspective. arXiv preprint arXiv:2410.055 192. 2024.
Schwarzschild, A., Borgnia, E., Gupta, A., Huang, F.,
Vishkin, U., Goldblum, M., and Goldstein, T. Can you learn algorithm? generalizing from easy to hard prob- lems with recurrent networks. Advances in Neural Infor- mation Processing Systems, 34:6695-6706, 2021.
Yang, X., Song, Z., King, I., and Xu, Z. A survey on deep semi-super learning. IEEE Transactions on Knowl- edge and Data Engineering, (5(9))8934-8955 2022.
Ychudai, G., Fetaya, E., Meirom, E., Chechik, G., and Maron, From local structures size generalization in graph neural networks. In International Conference on Machine Learning, pp. 11975-11999 11966. PMLR, 2021.
Shen, R., Bubeck, S.. Eldan, R., Lee, Y. T., Li, Y., and Zhang, Y. Positional description matters for transformers arithmetic, arXiv preprint arXiv:2311.14737 2023.
Shin, C., Cooper, J., and Sala, Weak-to-strong gener- alization through the data-centric lens. arXiv preprint arXiv:24/2.0388// 2024.
Yuan, W., Pang, R. Y., Cho, K., Sukhbaatar, S., Xu, J., and Weston, J. Self-rewarding language models. arXiv preprint arXiv:2401.
2024.
Shumailov, I., Shumaylov, Z., Zhao, Y., Gal, Y., Papernot, N., and Anderson, R. The curse of recursion: Training on generated data makes models forget. arXiv preprint arXiv:2305. /7 2023.
Zelikman, E., Wu, Y., and Goodman. N. D. Star: Bootstrapping reasoning with reasoning. 2022. URL https://api.at http:///app.eeeantccccool..a.a CorpusID::247722779

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Zhang, E., Zhu, V., Saphra, N., Kleiman, A., Edelman, B. L., Tambe, M., Kakade, S. M., and Malach, E. Transcen- dence: Generative models can outperform the experts that train them. arXiv preprint arXiv:2406. 11744, 2024.
Zhang, H. and Parkes, D. C. Chain-of-thought reason- ing is policy improvement operator. arXiv preprint arXiv:2309.08558 2023.
Zhang. L.,, Song, J., Gao, A., Chen, J., Bao, C.,, and Ma, K. Be your own teacher: Improve the performance of convolutional neural networks via self distillation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 3713-3722, 2019.
Zhou, H., Bradley, A., Littwin, E.,, Razin, N., Saremi, O., Susskind, J., Bengio, S., and Nakkiran, What algo- rithms can transformers learn? study in length general- ization. arXiv preprint arXiv:23 10. /6028, 2023.
Zhou, Y., Alon, U., Chen, X., Wang, X., Agarwal, R., and Zhou, D. Transformers can achieve length generalization but not robustly. arXiv preprint vrXiv:2402.0937, 2024.
Zhu, X. Semi-supervised learning literature survey. Tech- nical Report 1530, Computer Sciences, University of Wisconsin-Madison 2005.
12

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
A. Detailed Discussion of Related Work
Length Generalization. While Transformers (Vaswani et al., 2017) have achieved remarkable success, they often struggle with length ceneralization-weeeee a model trained on problems of fixed length fails to extrapolate to longer sequences (Dubois et al., 2019; Hupkes et al., 2020; Newman et al., 2020; Anil et al., 2022). Addressing this limitation is erucial, as poor length generalization indicates that language models may not fully understand the underlying task. Zhou et al. (2023) hypothesize that Transformers are more likely to length generalize on tasks with small RASP-L complexity. They demonstrate that tasks such as reverse addition and copying have low RASP-L complexity, making them casier to length generalize, whereas forward addition poses greater challenge.
Several approaches have been proposed to improve length generalization, particularly in arithmetic tasks. These include modifications to positional embeddings, such as Abacus embeddings (McLeish et al., 2024), NoPE (Kazemnejad et al., 2024), FIRE (Li al., 2023), and pairwise positional encodings (Sabbaghi et al., 2024; Cho et al., 2024), well as randomized positional encodings (Ruoss et al., 2023; Zhou et al., 2024). Other approaches focus architectural changes, such introducing looping mechanisms (Fan et al., 2024) or incorporating hand-crafted bias corrections in attention score matrices (Duan et al., 2023). Additionally, input modifications, such as index hinting, have been explored to enhance generalization (Zhou et al., 2023; 2024).
Beyond arithmetic, length generalization has also been studied in broader contexts. For instance, size generalization in graph- based tasks has been investigated (Yehudai et al., 2021), while Kim et al. (2024) leverage cognitive map framework for path planning tackle the maze-solving problem.
In contrast, our approach adheres to the standard transformer architecture without introducing modifications to architecture, positional encodings, or input structure. A key distinction lies in the training methodology. While prior approaches typically rely on fixed-length training datasets without further updates to model weights, we iteratively update model weights on self- reff-generated datasets, enabling the model to progressively improve and extend its generalization capabilities.
Our self- celf-improvement framework and results on forward addition (Section 6. are closely related to those of Zhang & Parkes (2023), where self-training enables forward addition generalization from 6-digit examples 24-digit addition. Like their approach, we iteratively apply self- self-training on progressively harder problems. However, a key distinction is that their method follows a two-step process in each round: first generating solutions using chain-of-thought (CoT) reasoning, then fine-tuning the model to produce direct answers without COT.
Our multiplication results in Section 6.2 have relevance with findings by Jelassi et al. (2023), who showed that dataset priming (adding a small number of labeled long-sequence examples) can enable length generalization for multiplication (although this is not strictly out-of-distribution).. Our approach of incorporating accurate, self- celf-generated -uitt--distribution data via filtering can be seen thought (CoT) data for multiplication, we believe it is possible to length generalize non-COT multiplication as well, by incorporating methods like Deng et al. (2024) to help the model iteratively internalize the CoT steps.
automated form of dataset priming. Furthermore, while our approach uses chain-of-
Easy-to-hard Generalization. Our self- infroimproeeentt framework operates in a setting where human annotation is provided for casier tasks, enabling generalization to harder tasks with no additional supervision. This paradigm, often referred to as easy-to-hard generalization (Schwarzschild et al., 2021; ; Bansal et al., 2022; Burns et al., 2023; Hase et al., 2024; Sun et al., 2024), leverages the transfer of learned policies or reward models from simpler problems to more challenging ones. For instance, Zhang et al. (2024) study this phenomenon in chess, showing that chess transformers can sometimes outperform all players in the training dataset. Similarly, Sun et al. (2024) finds that a reward model trained on easier mathematical problems can be effectively transferred to harder problems, facilitating generalization through reinforcement learning. Shin containing both easy and hard patterns
et al. (2024) identifies overlap data points-instanne weak-to-strong generalization, allowing weak models to pseudolabel easier patterns while stronger models use these labels to learn harder patterns. Our work shows that a similar mechanism emerges naturally within self-impun inff-mmprovemett, where progressively increasing difficulty enables models to generate useful supervision signals for harder tasks without explicit human intervention.
key mechanism for
Self Improvement. Self-training is a common approach in semi-supervised lcarning that leverages unlabeled data to enhance model performance (Zhu, 2005; Pise & Kulkarni, 2008; Yang et al., 2022). When high quality training labels are not available, training on self-generated labels is an efficient way to extract more capabilities from the model. Usually, this involves generating candidate labels, pruning wrong labels through verification or filtering, and retraining with self- self-generated
13

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
data. ReST (Gulcehre al., 2023) and I-SHEEP (Liang et al., 2024) propose self-improvement general purpose alternative reinforcement learning from human feedback (RLHF), while Yuan et al. (2024) propose "self-rewarding" model that generates its own instruction tuning set.
The improvvette framework has been applied to a wide range of tasks. For example, Zhang et al. (2019) replaces an expensive teacher distillation with self-distillation for image recognition tasks. In LLM reasoning domains, Huang et al. (2022); Singh et al. (2023); Pang et al. (2024), and STaR (Zelikman et al., 2022) bootstrap complex reasoning capabilities by asking models to generate rationales for unlabeled questions and training on self- self-generated rationals that yielded correct answers. Similarly, Zhang & Parkes (2023) shows self-improving using thain-of-thoughe (COT) data sampled from the model allows generalization of the integer addition task to more digits. For coding tasks, Chen al. (2023) teaches LLMs to self-debug with feedback using self-generated code explanation and unit test execution results. In mathematics, PatternBoost (Charton et al., 2024) shows that transformers can discover unsolved mathematical constructions of various problems using an algorithm that alternates between sampling constructions from the model (local search) and training on self- generated data (global learning). Similarly, Alfarano et al. (2024) generate synthetic training samples to train transformers to discover new Lyapunov functions. Recent works also investigate theoretical and empirical aspects of self-improvement. Bansal et al. (2024) highlight the effectiveness of smaller models in self-improvement, while Song et al. (2024) identify the generation--erificaation gap as key factor governing the self improvement process. Huang et al. (2024) introduce the "sharpening mechanism," where training on best-of-N responses from the model amortizes maximum likelihood inference and improves output quality.
Our work is greatly inspired by ReST (Gulcehre et al., 2023) and STaR (Zelikman et al., 2022), in which models iteratively generate predictions, filter high-quality responses, and fine-tune on the self-generated dataset.
Model Collapse Recent research has extensively investigated the phenomenon of model collapse, where repeated training on a model's own outputs leads to performance degeneration and a loss of the true underlying data distribution (Shumailov al., 2024; Hataya al., 2023; de Arcaute et al., 2023; Shumailov et al., 2023; Alemohammad al., 2023; Briesch et al., 2023).
Shumailov et al. (2024) provide evidence that iterative training on model-generated data, without filtering, results in rapid degeneration and forgetting of the true data distribution. They emphasize the importance of preserving original data sources over time. Similarly, Shumailov et al. (2023) show that the tails of the original content distribution diminish after repeated self-training, while Zhang& & Parkes (2023) highlight the error avalanching effect, where errors compound as models are trained on their own generated data.
Despite its apparent inevitability, several strategies have been proposed to mitigate model collapse. Research shows that the risk of collapse diminishes when the initial model closely approximates the true data distribution (Bertrand et al., 2023), or when real data is retained throughout training rather than being fully replaced (Gerstgrasser et al., 2024; Dohmatob et al., 2024; Briesch et al., 2023). Additionally, Gillman et al. (2024); Feng et al. (2024) suggest using reliable verifiers during self- self-training to ensure high-quality self-generated data, further reducing the likelihood of collapse.
Our approach addresses these challenges by maintaining a core labeled dataset throughout training, consisting of examples of limited length or difficulty. Synthetic data, generated incrementally by the model, is added in controlled manner. By incorporating unsupervised filtering techniques such as length filtering and majority voting, we ensure the quality of self- self-generated data. Our framework builds upon prior findings by preserving clean data and selectively incorporating synthetic data.
Additionally, our results in Section 8 align with findings from Rolnick (2017), which demonstrate that deep neural networks are robust to significant label noise in image classification tasks. Additionally, Bayat et al. (2024) recently emphasized that memorization alone does not harm generalization; rather, the combination of memorization with spurious correlations is what undermines learning. Our results suggest that despite memorizing past mistakes, the self-improvement framework remains effective, provided that incorrect samples do not dominate the training distribution.
14

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
B. Additional Results
B.1. Does the Model Truly Learn Addition?
When the two operands are sampled randomly, the probability of encountering an instance with a carry chain length of N decays exponentially with N. Under this sampling strategy, the model may rarely, if ever, see "hard!" instances of addition, as illustrated in Figure 14. To address this, we manually construct test dataset to include least 500 examples for each maximum cascading carry length. This ensures that the evaluation captures the model's ability to handle harder instances of addition.
The results in Figure 15 show that the model is capable of performing additions with up to 20 cascading carries, even though has never encountered such cases during training. This demonstrates that the model can generalize to harder instances of addition despite being trained predominantly on easier examples.
8000
Number of data points
14000
Number of data points
7000
12000
Number of data points
Number of data points
6000
100000
5000
8000
4000
6000
3000
2000
1000
2000
0.0
2,5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
0.0
2.5
5.0
75
10.0
12.5
15.0
17.5
20.0
Total Carry
Max Cascading Carries
Figure 14. Number of carries in the self-improve dataset of 20-digits. The models does not see examples of high numbers of carry during training.
Accuracy by Max Cascading Carries, 20-digits
14000
Number of data points
1.00
12000
Number of data points
10000
Accuracy
8000
6000
Seed 41
Seed 42
Seed 43
Average
0.90
0.0
2.5
5.0
75
10.0
12.5
15.0
17.5
20.0
0.0
2.5
5.0
7.5
50.0
12.5
15.0
17.5
20.0
Max Cascading Carries
Max Cascading Carries
Figure 15. Performance of the model at round 10 (trained with self celfe-eneeated data up to 20 digits). (Left) Accuracy as a function of the maximum cascading carries. (Right) Number of examples with each maximum cascading carry length the self-improve training dataset. Models can successfully perform hard - with high number of cascading carries addition tasks even without encountering such examples the training dataset.
B.2. Motivation for Data Filtering
B.2.1. IMPORTANCE OF DATA FILTERING
Figure 16 demonstrates this effect in the reverse addition task. The x-axis represents the accuracy of the self-improve dataset Dr. generated by model M,-1 at round r, while the y-axis shows the resulting n + 1-digit performance of model Mp. The prevalence of data points below the y = x line indicates that low-quality data diminishes performance, underscoring the need for maintaining high-quality data throughout the self-improvement process.
we define hard instance of addition to be cases with multiple numbers cascading carries (Quirke & Barez, 2023)
15

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
n-digit n+1-digit accuracy
1.0
11-digit
12-digit
13-digit
Model Accuracy
14-digit
15-digit
0.6
16-digit
17-digit
18-digit
0.4
X
0.2
x
0.0
0.2
0.4
0.6
0.8
1.0
Self-Improve Data Accuracy
Figure 16. Effect of self-generated data accuracy on length generalization performance in the reverse addition task. Each data point represents the accuracy self- self-improve data D, (on digit addition) generated by model M,-1. and the resulting 1-digit performance of the trained model M, at round The prevalence of points below the z line highlights the critical importance of high-quality data successful self-improvement.
B.2.2. OOD RESULTS ARE OFTEN SHORT
Shorter Answer Ratio among Wrong
Number of Incorrect and Short Answer
Average & Length
Number of Incorret/Short Answer
Incorrect
25-
Short Answer
Shorter Answers (%6
2,000
Short Answer
Short CoT
Morraa 6 Length
20
359
50-
1,500
160
15
30
500
57 36
3.00
Digits
Digit
Digit
Figure 17. (Left) Reverse addition the proportion shorter answers among incorrect predictions increases with each round. (Mid & Right) CoT-multipicatioon task with majority voting: (Mid) The majority of incorrect answers are short. (Right) The average length discrepancy short answers compared to correct answer or CoT reasoning part.
Figure illustrates this phenomenon for both the reverse addition and CoT-multiplication tasks. reverse addition (Left), as the number of digits in the training data increases (or as self-improvement rounds progress), the proportion of incorrect self-generated data where the answer is shorter than the correct label length also increases. Similarly, for CoT-multiplication (Mid and Right), most incorrect answers shorter than the correct ones. Furthermore, in cases where the answers shorter, the outputs often miss one or more reasoning steps in the chain-of-thought (CoT) reasoning process.
B.2.3. MAJORITY VOTING LEVERAGES LABEL DIVERSITY
Self-imprrvement relies on the model's ability to generalize to slightly harder problems. However, this generalization not always robust and can vary significantly across different training instances (Zhou et al., 2024). Majority voting mitigates this variability by aggregating predictions across multiple independently trained models, thereby improving the reliability of self-generated labels.
To illustrate this variability, Figure 18 shows test accuracy across five models trained with different random seeds on the initial training dataset containing up to 5-by-5 multiplication. Even when trained on identical training data, models exhibit substantial performance differences in extrapolation. Similarly, Figure 19 demonstrates that this variability persists even when models are trained from the same seed data.
Figure 20 demonstrates the effectiveness of majority voting the multiplication task across five models trained with
16

---

Self-Improvig Transformers Overcome Maay-to-Harde and Length Generalization Challenges
Seed 41
Seed 42
Seed
43
1,20
Lo03
1600
6.00
2.302
0.832
0.006
2,302
1.205
.00
2.926
00223
1.00
1000
1.300
6.600
6822
6.302
1.00
2.990
1260
681
2.000
1333
1.600
1.002
0.345
0.000
4-0000
2.002
1.302
1800
1.00
1.79
0033
1.00
..00
1.020
1.00
6304
0000
5,000
4,03
1.00
1.000
1.302
0.34
0.266
5- 5-1000
2,000
1.302
1246
1.00
1,90
6033
5- 1000
1,00
1,000
1.010
1.00
5355
6.00
8.929
0.330
6.322
0.206
0826
0.333
2,00
0030
3.666
0.842
0.22
1.00
0.002
Seed 44
Seed 45
1.000
1,030
1.000
600
0000
0.984
0.203
1000
1,000
1,093
1,302
0.000
0.6
6.935
2- 1,00
3,200
1.028
1.00
3.000
0.300
0.002
2-
5.00
2,000
1.033
1,33
1.000
0.25
0.200
1,00
3.000
1.500
2.000
0,702
0.002
2,000
1350
0372
0.200
3.975
0.524
0.910
3853
6:301
0.797
2938
5.059
5.035
0.314
0560
5,000
0.377
7,094
0:020
0.070
2000
1 000
0.307
0.707
2000
2.004
0,033
0,712
0 X22
3,000
0.77
digit
digit 2
Figure 18. Test accuracy on 5 different seeds during the initial training phase. Models exhibit high variance in performance.
Seed 41
Seed 42
Seed 43
5,000
L003
1000
6000
3.302
0.502
0.065
1- 5.000
3.203
3,202
1.000
1.000
3.914
0.033
1,00
1,000
1,000
3.038
0.594
05443
6:000
1,000
L000
1.000
0.702
0.006
3.000
3.200
3.943
0.00
L000
1,000
1,000
0.00
6.000
2.000
1.32
1.000
1.000
1.002
0:22
0.500
5-0000
2.007
1.202
1800
1000
2.044
0033
3.56
1,000
1.257
0.734
0.27
8.000
0.007
5.955
0.247
0.200
0.50
6.002
0.224
0:200
0514
0.357
0.342
2.48
2.755
1,2L
0003
3,612
2.645
2.150
0.055
0.526
8000
0.000
5,023
(6323
0.000
0.00
312
6:332
0.006
600
0:301
6:200
1.66
2,02)
0023
3.64
3/000
2.000
0.000
0.000
digit
digit
digit
1.000
1002
1000
0.713
0.243
2,00
3.000
0.228
1,000
1.72
1.000
000
5.755
0.707
2,000
2.097
1
1.000
3.590
0.077
3- 1,000
1,300
1.000
1000
1.000
0.40
0.707
3-
5.000
2,000
3.032
1.37
1.000
2.50
0.77
digt
1,000
1.000
1.52
0,201
0.207
2,000
1327
1.000
3350
0.001
3,000
0.022
0:000
stre
1000
8.301
0.103
5,002
5.012
0.305
3,000
0.932
1
2
5
6
7
2
2
5
6
7
digit
digit
Figure 19. Test accuracy on models trained with the same seed data but different training seeds. Despite identical training data, models exhibit large variability.
different seeds during the initial training phase on data Do, which consists of up to 5-by-5 multiplication problems. The mean accuracy (Left) is relatively low, with a high standard deviation (Mid), indicating substantial variability among the models. By applying majority voting with a consensus on at least out of model outputs, the generated dataset quality improves significantly (Right). For example, while the 5-by-6 multiplication task achieves an average accuracy of 31
17

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
across models, the majority- strategy generates dataset with 93.3% accuracy.
In practice, datasets for larger multiplications, such 5-by-6 digits, are created after multiple rounds of self self-improvemmnn training, gradually incorporating m-by-6 and 6-by-m data with incrementally increasing m at each round.
Majority Vited data accuracy
Accuracy
Accuracy Standard Deviation
8.5
524
digi
1.00
A39
0.023
0.826
140
6660
2844
6.20
0.599
5.998
506
0.997
6:313
digh:
digit
Figure 20. (Left & Mid): Mcan and standard deviation of accuracy among five models trained with different seeds on the initial training round. (Right): Accuracy of majority data points. Majority voting significantly boosts data quality, with 5-by-6 multiplication data accuracy increasing from an average of 31% to 93.3%
B.2.4. ABLATIONS FOR MAJORITY VOTING
Our majority voting method requires training multiple models in parallel. In our primary setting, train k models with different random seeds, allowing each to generate and train on its own independent self-improved dataset at every round.
To evaluate the necessity of training multiple independent models and generating separate self-improvement datasets, we compare our approach against the following baselines:
1. No majority voting, but larger celf-improve data: Instead of using multiple models, we train single model while sampling is times more self-impros data per round, ensuring that the total amount of generated data matches our main setting.
2. Shared self- eef--imprve data: We train i models with different initial seeds but subsequently train all models on the same self-improved dataset.
3. Shared initial training seed: All models are initialized from the same seed but then trained separate self- seff-improved datasets.
4. Our main setting: Each model is initialized with different seed and trained on its own independently generated self-improve dataset.
Figure 21 presents the performance of these variations, highlighting the importance of training on independently generated self-improve datasets rather than simply increasing dataset size sharing training trajectories across models.
Table 2. Comparison of Data Cost Across Majority Voting Variants
Method
Initial Training Data Cost
Self-Improve Data Cost (Per Round)
No Majority Voting, Larger Data
k
Shared Self-Improve Data
k
1
Shared Initial Training Seed Full Majority Voting (Ours)
1
k
k
We set = and report the average performance across five models. Figure 21 shows that simply increasing the amount of self-impres cef--improvement data without filtering leads to poor performance. Surprisingly, using 5x more self self-improvement data per round performs even worse than using less data (Figure 32), consistent with our findings in Section B.7.1.
18

---

Self- Self-Impoovng Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Mean Accuracy for Round
Mean Accuracy for Round 7
Mean Accuracy for Round
Mean Accuracy for Round 7
1:302
L000
1,02
1.811
1
1.000
2.302
1002
1.000
L,30
0.414
2,302
L000
1.030
0.535
1
1.000
1.250
3.002
1,02
2.939
2-
2.307
1072
1,500
2339
0.335
3.007
1,00
0.714
2-
2.0000
3.307
1O30
3,500
2.50
1.000
1,200
1.60
2.641
0.66
(00
1.460
2,441
1,302
1160
0.967
1.00
1.400
2.66
0.500
2,202
2.500
0.358
2.50
0.020
2.302
1000
1032
1.00
2.09
0.324
1.000
2,002
L000
1.000
1.000
1.00
0.220
5-1.00
2.002
1200
1000
1.00
2.00
0.464
0,880
6644
(.:4)
SAM
0.000
6
0.660
1.392
1.600
1992
1.400
2,99
0.690
1,302
1,600
1.00
1.400
1,00
0.797
6
1.000
1.392
1.400
(.00
0,144
0,02
0155
0.27
0::02
2.350
0.355
0.064
2,000
0.824
7-
7.0600
6.297
2,40
6891
0.067
2.675
0.826
7-05
7-0.788
6.303
3,041
3,809
0.237
3.007
0.050
7-0.66
6.297
0.864
3,022
0.067
2.605
0.526
2
5
6
1
2
7
3
5
6
digit
digit
digit
dig
Figure 21. Ablations on majority voting. (Left) No majority voting, but larger self-improve data. (Left-Center) Majority voting with shared self-improve data. (Right- (eight-Center) Majority voting with shared initial training seed. (Right) Our primary setting with fully independent training and self-improve datasets.
Additionally, majority voting with shared self-improve data (second panel from the left) underperforms in OOD compared to models trained on separate self-improve datasets. This suggests that model eeeesity-eeabled by training on different self-improve data-may be important for majority voting to be effective.
On the other hand, comparing the right two panels in Figure 21, where the difference lies in whether the base models were trained on different labeled data Do, we find minimal differences in OOD performance. This may be due to the large size of the initial training set (5M examples), which provides sufficient diversity. Furthermore, as Figure 19 shows, models trained on the same initial dataset but with different training seeds still exhibit substantial variability, suggesting that model diversity can emerge from different training trajectories alone.
B.3. Verification Filters on Mazes
Solving the shortest path problem can be computationally expensive, but verifying the correctness of given solution is significantly simpler. A valid path can be verified by traversing the sequence and ensuring three conditions: 1) each move is valid, meaning the path follows adjacency constraints; 2) the final destination matches the intended goal; and 3) no nodes are repeated, confirming that the solution is indeed the shortest path.
Self- self-improvement frameworks commonly incorporate verifiers to filter self geleraenerteed data, often leveraging trained models or reward models (Zelikman et al., 2022; Singh et al., 2023; Hosseini et al., 2024; Lightman al., 2023). While our primary focus is not on training designing an additional verification mechanism, we investigate the effectiveness of using an external verifier as data-filten filtering method.
To this end, we evaluate an oracle verifier that enforces two essential constraints: 1) move validity, ensuring that every transition in the generated solution adheres to the adjacency constraints of the maze, and 2) end validity, confirming that the final node in the solution corresponds to the correct destination. We compare the effectiveness of this oracle-based filtering against self- eeff-imprveement without data filtering and majority-voting-banl filtering to assess its impact on performance and stability.
Results. Figure 22 shows results for mazes with increasing hops, increasing nodes, and three different verification strategies: checking moves, checking end validity, and checking both. As expected, verification improves data quality and serves effective filtering technique in self-improvement. Notably, verifying move validity proves be significantly more effective than verifying only the correctness of the end node. Interestingly, however, majority voting strategy that does not rely on an external verifier-perfone comparably to verification- based filtering. This suggests that self-consistency mechanisms alone can be sufficient for maintaining high-quality training data.
Additional results, including finer grained analysis of move validity and end validity beyond exact match accuracy, are provided in Appendix D.0.3.
19

---

Self- Self-Improvigg Transformers Overcome Easy-to-Hare and Length Generalization Challenges
Maze (Hops) Verilier (Moves & Ends)
Maze (Hops) Verifier (Moves)
Maze (Hops) Veriffer (Ends)
1.-
1.0
1.0
0.8
0.8
0.8
Accuracy
0.6
Accuracy
0.6
Accuracy
0.6
round
1ound-10
mund-15
roundk15
munnd-15
mund-19
0.4
FoundkE
0.4
round-14
0.2
0.2
0.0
Number
Number
Number Hops
Maze (Nodes)- Verifier (Move Endss
Maze (Nodes)
Verifier (Moves)
(Nodes) Verifier (Ends)
0.6
mands1
Accuracy
mund-1
Accuracy
mandel
mundes
mundes
moandes
mund-10
mund-10
mundd-10
0.2
0.0
10
20
40
3.0
80 70
80
90
100
0.0
10
20
30
40
50
60
70
90
100
30
20
30
40
50
70
80
90
100
Number of Nodes
Number of Nodes
Number of Nodes
Figure 22. (Top) Increasing hops. (Bottom) Increasing nodes. (Left) Verifier on both moves and ends. (Middle) Verifier on moves only. (Right) Verifier ends only. Verifier-based filtering improves self-improvement performance, with validation proving effective than end validation alone. Interestingly, majority voting performs on par with oracle verification, suggesting that self-consistency mechanisms
effective alternatives explicit verification.
B.4. Accelerated Seff-mmprovement for Multiplication
We validate the accelerated self- cef-imprrvemeet (Section 7.2) setting to the task of multiplication. For the multiplication task, we observe similar enhancement using an accelerated schedule, as depicted Figure 23. Under the standard schedule, reaching 10-by-10 multiplication from 5-by-5 requires 41 self-improvement rounds, incrementally increasing operand by at time. With the accelerated schedule, we progressively sample more operand pairs self-improvement proceeds, reducing the required rounds to 19 while achieving perfect test performance (see Figure 37 for full results). The settings for multiplication follow the setting in Section
2
10
3
(5x 5) (ID)
7
17
0.000
3.000
0.000.0000
1.000
1.000
1.000
1.000
1.000
2.000
1.000
2.000
1.000
2.000
0.000
1.000
1.000
1.000
1.000
digit
3.000
1.000
1.000
1.000
2.000
1.000
1.000
1.000
1.000
12
7
7.0000
1.000
3.000..000
1.0000
1.000
1.000
1.000
1.000
1.000
1.000
8
1.000
1.000
1.000
1.000
1.000
1.000
1.000
12
18
9
0.0000
1.0000
1.000
10
1.000
10
18
19
1
2
6
7
8
9
10
digit
Figure Accelerated self-improvement in multiplication. (Left) Accelerated schedule for multiplication. The rows columns represent the number of digits in the two operands of the multiplication task. The number within each cell indicates the improvnnpeeemennt round which the corresponding digit pair included for training. (Right) Results at round 19, Controlled scheduling progressively incorporates more digit pairs in each round, accelerating the self-improvement process.
20

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
B.5. Results on Pretrained Models
Figure 24 shows the self-improvement results for LoRA finetuning Llama-1 and Llama-3B on the reverse addition task. Pretrained models show more extrapolation than from-scratch models.
1.0
1.0
Accuracy
0.6
0.4
0.4
4.
15
20
30
35
0.0
20
25
30
35
Number of Digits
Number of Digits
Figure Reverse addition results pretrained models. (Left) Llama-1B model. (Right) Llama-3B model. Larger models exhibit better extrapolation performance across rounds of self-improvement.
B.6. Additional Error Analysis on Reverse Addition
B.6.1. PATTERNS IN MODEL MISTAKES
We can categorize all mistakes into two bins. At each digit position, either the model drop the digit, or that it outputs a wrong digit. Since these two kinds mistakes are entangled practice, we use string matching algorithm to compare model output and predictions and obtain the best guess. figure 25, we find that digit drops by the model are concentrated near the send of the sequence, and wrong digits are most often off by 1.
Error distribution
Error distribution
Position of dropped characters
18
120-
600
14-
100-
Frequency
Position
12-
Frequeno
80-
10
100
40-
200
4-
2-
20-
7
98.76554221122345
0
8
10 12
14
16
18
20
Error
Error
Position
Figure 25, Patterns in model errors. (Left) Most incorrect digits are off by (Middle) Errors cluster near the end the sequenee. (Right) Digit drop errors strongly location-dependent.
Additionally, Figure 26 shows that when models generate incorrect answers, the first mismatch with the ground truth typically occurs near the final digits of the sequence (i.e., near the most significant digit in reverse addition). These observations inform systematic error simulations, which are used analyze the error avalanche phenomenon in Section 8.
B.7. Additional Experiments on Label Noise and Robustness
Models can Generalize Despite Memorizing Past Mistakes Since self- seff-improvement involves recycling model predictions into training data, important question is whether the model continues making mistakes previously incorrect examples. To investigate this, we isolate incorrect self-generated samples and evaluate the model's performance on them. As shown in Figure 27, the model struggles to rectify these errors. Accuracy on incorrect training examples decreases over successive rounds, suggesting that repeated exposure to errors reinforces them rather than correcting them.
However, memorizing past mistakes does not necessarily cause an emrr avalanche. The model under self- self-improvement often generalize higher difficulties while treating the incorrect samples as outliers. For example, Figure 13 shows that after 20
21

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
First Incorrect Position
Avg. First Incorrect Position
20
16
14
10
12
14
16
18
20
Digit Length
Figure first incorrect digit in model outputs tends to occur near the most significant digit reverse addition.
rounds of self improvement, the model can tolerate a surprisingly large amount label noise, from both uniform noise and structured noise. This suggests that while individual mistakes persist, they do not necessarily hinder overall generalization.
0.200
seed 41 (0.998)
0.175
seed 42 (0,984)
seed 43 (0.999)
0.150
seed 44 (0.617)
seed 45 (0.928)
Accuracy
0.125
0.100
0.075
0.050
0.025
10
11
12
13
14
Rounds
Figure Models memorize their mistakes. Accuracy on incorrect training examples (of Do) decreases with additional self-improvement rounds, indicating that repeated exposure reinforces memorization of errors instead of correcting them.
To further examine the model's resilience to errors in data, we introduce randomiza- tion into the labels during training- Correct labels are replaced with random numbers of the same length with probabilities 1, 0.8, 0.5, 0.2, 0.1, and A probability of corresponds entirely incorrect labels, while 0 indicates fully correct data.
Robustness against Random Labels
The model is initially trained on 1-10 digit reverse addition and further trained across 8 self- seff-improvement rounds, using self-generated data of lengths 1 1-18 digits. We then construct dataset of 19-digit data with randomized labels, denoted as D The model is fine-tuned on combined dataset consisting of the original dataset Do. self-improved datasets DI,... Ds. and Drand
Results in Figure show that the models can tolerate substantial random label noise, maintaining robust performance even when up to 80% the training data is corrupted. This demonstrates the model's resilience random errors in the training data and its ability self-correct such mistakes during learning.
Model Bias Random Labels. Interestingly, biases in self self-generated data more detrimental than uniformly random label noise. As shown in Figure 28, models trained with self-improved data perform worse than random-labeled data of comparable accuracy, given the same dataset size and fine-tuning steps. This suggests that the inherent biases in self-generated data hinder generalization more than randomly introduced noise.
These observations align with findings from Bayat et al. (2024), which highlight that memorization alone does not harm generalization; instead, the combination of spurious correlations undermines learning. Despite memorizing mistakes in
22

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
With Random Labels, 19-digit
With Random Labels, 20-digit
1.0
0.8
0.6
Accuracy
0.6
0.4
0.5
0.5
D:1
0.2
0.2
X
self improve
X
self ielf-ve
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
D.4
0.6 Label Probability
0.8 1.0
Correct Label Probability
Figure 28, Effect of training on randomized labels. The model trained on 1-10 digit data, further fine-tuned on 11-18 digit self self-generated data over 8 self-improvement rounds, and additionally fine-tuned on 19-digit data with varying probabilities of random label replacement. (Left) Accuracy on 19-digit data. (Right) Accuracy on 20-digit data. The results demonstrate that while the model can self-correct random errors, biases from self self-improved data can result in worse performance compared to models trained madom-llbbled data of similar accuracy.
self- gelf-generated data, the model's 's overall performance at the same difficulty level often exceeds the quality of the training data.
B.7.1. EFFECT OF SELE-GENERATED DATA QUANTITY ON PERFORMANCE
We investigate how the quantity of self seff-generated training data impacts model performance. We first train 10 base models M13) (s = 1,.... 10) on a supervised 1-10 digit reverse addition dataset Dÿ, each using a different random seed. These models are categorized based on their accuracy on 1 1-digit addition: low-performing models (less than 98% accuracy) are represented with red colors, while high-performing models (more than 98% accuracy) are depicted with blue colors.
To study the effect of dataset size, we generate self impromeeevetttt datasets Dj = {x,,, M,6 (x of varying sizes (N1 = 10, 000, 50, 000, 100, 000, 500, 000, 1, 000, 000). Each model is then trained on the combined dataset Dj U Dj.. The number incorrect examples in each self-generated dataset is approximately N₁ x (1 11-digit accuracy of My).
Results in Figure 29 show that for low-performing models, increasing the quantity of self-generated data (which is of lower quality) degrades performance on both in-distribution (1 (Il-dig and out-of-distribution (12-digit) addition. In contrast, for nigh-performing models, the relationship between the number of self self-generated examples and performance is less clear. The total number of 1-digit examples seen during training remains constant across experiments, with smaller datasets being repeated more often. This suggests that exposure to a greater diversity of incorrect examples can bias the model more negatively.
23

---

Self-Improving Transformers Overcome Masy-to-Harde and Length Generalization Challenges
11-Digit
12-Digit
10
0.8
seed 41 (0.903)
Accuracy
seed 42 (0.995)
Accuracy
seed 43 (1.000)
seed 44 (0.999)
0.94
seed 45 (0.997)
0.4
seed 46 (0.997)
seed 47 (0.988)
0.92
seed 48 (0.906)
seed 49 (0.992)
0.90
16'
10
0.0
10a
Number of Wrong Samples
Number of Wrong Samples
Figure 29, Effect of self-ge reffreenerate training data quantity and quality model performance. Each model is trained on Da (1-10 digit addition) and self- seff-geeettee DD (11-digit addition), then evaluated on 11 11-igi (in (in-distribution) and 12-digit (out-of-distribun test performance. For low- perforrrfnmig models, increasing the quantity of self-generated data leads degraded performance. For high- performing models, the impact of dataset size is less clear.
C. Experimental Setup
C.1. Model
For all experiments, we use a Decoder-only Transformer architecture. Specifically, for all experiments except for pretrained models settings, we use the Llama architecture (AI@ Meta, 2024), except we remove the rotary positional encoding. For the inputs format, we have one example per line, and stack all example on the batch dimension. Since the examples can have variable length, we pad each line on the right to the maximum length in the batch. We exclusively use a character level tokenizer. For pretrained models, we replace the default tokenizer with our character tokenizer, while keeping the embedding component of the pretrained model unchanged.
Table Model Parameters
Model
Self-Attn Layers
Num Heads
Emhedding Dim
From-Scratch
384
Llama 3 1B
24 32
16
1024
Llama 3 3B
32
2048
C.2. Data Formats and Data Sampling
C.2.1. DATA GENERATION AND SAMPLING
We generate an initial supervised training dataset Da of up to fixed difficulty level dg by uniformly sampling the difficulty level d S do, followed by independent sampling of the data conditioned on the difficulty. Denoting the input as 22, labels as V:
Do = (1;, 9:) N: where Difficulty(:)) S do-
For arithmetic tasks such as addition multiplication, each problem instance is represented as a tuple x; (a,, b.), with Do containing problems of up do-digit numbers. The digit lengths (da,, de,) ) uniformly sampled from {1. ... ) and the numbers and b; are uniformly sampled from the ranges [10d.. 10da, 1| and [10 10th 1]. respectively.
For string manipulation tasks (c.g., copying or reversing), we uniformly sample string lengths to do and generate random sequences. Similarly, for maze-solving tasks, we uniformly sample the number of hops or total nodes in the maze and generate random graphs that satisfy these constraints. This strategy ensures balanced coverage across all difficulty levels up do-
24

---

Self-Impoovng Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Example Maze (N-30, Hops 4)
Example Maze (N=30, Hops 13)
Example 1 ID (N-30, Hops=4)
Start
Start
Input:
2--2255:78-49:11
10-1:22 1:2,414 22,99,22 (,95-3383 89--54665,11--8666
28
25
21:1-4:90.34:6100.
01995:199:80055-99--666
188,,44522-2299988888
(199988-65:00 (6:
Label:
2-600-80-9-52
Example 2- OOD (N=30, Hops=13)
Input:
11-299E2-91148:4445544444
89
9-59:39-22:89.85--22 099-9992229993--77996------282
89:22, 98 011.666.--13344::066600 6:83 85:48222--222-
Figure 30. Maze-solving task with N 30 nodes. (Left & Middle) Visualization of the maze task with 4 hops (ID) and 13 hops (OOD), (Right) Example of the data format: the input specifies the start and end nodes along with the graph structure, and output lists the shortest path hops. The labeled training dataset includes paths of to hops, with difficulty increased by adding one hop in each subsequent round.
C.2.2. MULTIPLICATION
We adopt data format similar to Deng et al. (2024), where the input prompt is 9172+9431~, and the label expands the multiplication into steps, such as: 17442+06788 (132331) +10331+00055000 +0075180 (1398490) +00091720=139 6630. Each step includes the intermediate results (in parentheses) representing partial products formed by multiplying the first operand with each digit of the second operand.
The data format is inherently asymmetrical. For example, an m-by-n multiplication requires intermediate steps, where each step corresponds to multiplying the m-digit number by one digit of the n-digit number. Conversely, an n-by-m multiplication involves m intermediate steps of multiplying the n-digit number by each digit of the m-digit number.
C.2.3. MAZE
25

---

Self-Improving Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Listing Code for the maze format generation used
sreate_trees hops. (total_nodea, hops) import networkx as nx
Step Create the path hops graph nx..pth eraphhhh_rap (raph hops
Step extra suzrent__aodes 1ist sedep..ndedds/ee new_nodes = (range hnum total_rodes)
zandom waik
while new_nodess
12
nek_aode ney_nodes.
randon waik
graph
walk [new_rode]
15
while walk[-1] not in current_nodes:
random node from
nodes
randon_node randor.cholf ce (eurrent_nodee new_nodes]
18
walk, [ceeoonnoe if randem_node new_nodes: new_rodea, remove (randon_nodde))
add oóges
for in rançe (len (walk)
1):
graph. add_ (walk]i], Malk[1 11) current_nese coctt__oddessee append (new_node)
Step start_rode = and_nade rum_hops
return grapt, start_node, end_node
Cormat_graph, Igraph, start_rode, end_node): Assign random labels to nodes
34
node_-abels = assign_labele (graph, (), label_range- (1, 991:
Get the shortest path terms edge count) from start_node to and nade shortest_path
37
shorleet__p.hhqqappl souroesatact_.ode, nodde
the path string lath_-abele - (node_labell [node] for node in shortest_pathh path_string *5", *>".join
40
pata_labels))
# Format atart and end nodes stert_lebel node_labels [oder__nde]] end_labe node_labele (end_ start_end_st f* (start_labee )> (end_laabel]]] label)
Butid graph_atr graph_etr start_rodd ttart_rode_str end_noda_st *.
end_ connections
Temporazy storage for the start_node part
Temporary storage the end_node part
randomize the order of nodes randon_nodas 11st Igraph.rodaa randon, shuffle (rrandom_nndes) for node in random_nodes nodes: nade_label
side__abbllaneede (ndde)
# randomize the order neighbors
59
handem_zeighban
list (graph. adj [node])
sardom. (tarffeoottrrdmmniiiiioooo neighber_labei. graph_atr += f" [node_label] (m""toortmmpsssst
[neightat)
neighbor sandoa_neighhbere
".".join (mar, (oighhor__abbls)) +
Combine everything, plasing end
groph_str = start_nade_str graph_str
end_node_atr
start_end_stz graph_eos(i-1 "e", striin, cabe_l
26

---

Self-Improvng Transformers Overcome Easy-to-Hard and Length Generalization Challenges
C.3. Experimental Settings
C.3.1. HYPERPARAMETER CONFIGURATIONS
In this section, we provide detailed overview of the hyperparameter configuration used in our experiments in Table 4 and 5, To enhance memory efficiency and training speed, employ flash attention and tf32, bfloat16. Our experiments using PyTorch2 2.4 and CUDA 12.1. Detailed dependencies are provided in our github repository². We use Warmup stable decay (Wen et al., 2024) as the learning rate schedule. In table 4 and 5, the number of constant LR steps is equal to the total training steps minus the sum of warmup and decay steps.
Table 4 shows the training hyperparameters for the initial training phase on labeled data Dy- Table 5 shows the hyperparam- eters for each the self-improve training rounds on D.....R.
Table 4. Hyperparameters for initial training on labeled data
Task
Batch Size
Optimizer
LR
Betas
Epsilon
Iterations
Warmup Iter
Decay Iter
Wt decay
Reverse Addition
1024
AdamW
5e-4
(0.9, 0.99)
le-12
10000
1000
2000
0.1
Reverse Addition (Llama 3B)
128
AdamW
Ic-4
(0.9, 0.99)
lc-12
1200
120
600
0.1
Reverse Addition (Llama IB)
128
AdamW
le-4
(0.9.0.99 0.99)
le-12
1200
120
600
0.1
Copy/Reverse
1024
AdamW
5e-4
0.99)
le-12
5000
500
1000
0.1
Forward Addition
1024
AdamW
5c-4
(0.9, 0.99)
1c-12
10000
1000
1000
0.1
Multiplication
1024
AdamW
5e-5
(0.9, 0.99
lc-12
10000
1000
2000
0.1
Maze (hops)
1024
Adam
5e-4
(0.9, 0.99)
le-12
25000
2500
3500
Maze (nodes)
512
AdamW
Se-4
(0.9, 0.99)
le-12
12000
1200
2800
Table 5. Hyperparameters for self-improvement rounds
Input Format
Batch Size
Optimizer
LR
Betas
Epsilon
Iterations
Warmup Iter
Decay Iter
Wt decay
Reverse Addition
1024
AdamW
Se-4
(0.9, 0.99)
le-12
1500
1500
0.1
Reverse Addition (Llama 3B)
128
AdamW
le-4
(0.9, 0.99
le-12
600
600
0.1
Reverse Addition (IJama 1B)
128
AdamW
lc-4
(0.9. 0.99)
lc-12
600
0
600
0.1
Copy/Reverse
1024
AdamW
5e-4
0.99.
le-12
500
0
500
0.1
Forward Addition
1024
AdamW
5c-4
0.99)
lc-12
3000
0
1000
0.1
Multiplication
1024
AdamW
5e-5
(0.9, 0.99)
le-12
3000
1000
0.1
Maze (hops)
1024
AdamW
2e-4
(0.9, 0.99
le-12
5000
500
1000
0.1
Maze (nodes)
1024
AdamW
2c-4
(0.9, 0.99)
1c-12
4000
400
1000
0.1
C.3.2. SELF-IMPROVEMEN SETTING FOR EACH TASK
Reverse Addition. The initial supervised dataset Do contains 2 million examples reverse addition, with operand lengths ranging from 16 digits. This dataset is used to train the model for 10,000 steps. In subsequent seff-improvement rounds, we sample 50,000 additional training examples at each round, extending the operand length by one digit. Specifically, at self- self-improvement round the self -eferated data D, consists of length-16 16 + examples produced by the model M,. The model is fine-tuned on the combined dataset Do U D2 U ... U.D for 1,500 steps, resulting in an improved model M,+1-
String Copy & String Reverse. The initial training set D, consists of 2 million examples of strings of length I to 10. The vocabulary of the string is the digits 0 to 9. For each subsequent round r, we sample D, consisting of 50, 000 examples of length 10 + r from the model M,. Then we continue training M, on the combined dataset D₁ U .... D,, for 500 steps to obtain Mr+1-
Forward Addition The models are initially trained on dataset Do containing 2 million labeled examples of forward addition, with operand lengths ranging from 1 to 10 digits. This initial training phase spans 10,000 steps. In each subsequent self-improvement round, we generate 50,000 additional training examples, incrementally extending the operand length by one digit. Specifically, at self-improvemmnt round r, the self-generated dataset D, contains length-10 + examples produced by the model M,. The model then fine-tuned for 3,000 steps on the combined dataset Do UD, U...U D,, resulting in an updated model M++1-
Phtpps: // thub. com Saom/JaakCaaaa wwwetiitciteeeee sel fmiprove
27

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
The model is initially trained on 5 million n-by-n multiplication examples with 5. Directly introducing 1-by-n examples results in poor performance, hence, adopt more fine- ene-grained difficulty schedule. In each self-improvement round, we incrementally increase operand by one digit, sampling + 1-by-m and m-by-n + 1 examples, where m grows from 1 to n + 1. This gradual progression allows the model to adapt incrementally to larger operand sizes, making the transition to harder examples more manageable.
Multiplication
For data filtering, we use the following setting: for length filtering, we remove self-generated samples where the output length is shorter than the longest output in the batch by more than 10 tokens. This helps eliminate incorrect solutions that omit intermediate steps. For majority voting, we train five models in parallel using different random seeds and retain only those data points where least out of the 5 models produce the same output. This strategy ensures that only high-consensus, reliable data points are used for training.
Maze Solving Increasing Hops. The model is first trained on dataset Do containing 5 million labeled maze-solving examples, where the number of nodes is fixed at N = 30 and paths range from h = 1 to h = 9 hops. This initial training phase spans 25,000 steps. In subsequent self-improvement rounds, we generate 50,000 additional training examples, increasing by and fine-tune the model for 5,000 steps per round. We experiment with both unfiltered training data and majority voting, where only outputs agreed upon by all 3 models are retained.
Maze Solving- Increasing Nodes. The model is first trained on a dataset Du containing million labeled maze- solving examples, with fixed hop count h 9 and node counts ranging from N 10 to N 30. This initial training lasts 12,000 steps. In relf-imppoveeent rounds, the number of nodes N is increased by per round, generating 50,000 additional training examples at each step and fine-tuning for 4,000 steps. We compare training without filtering against majority voting, where only outputs agreed upon by all 3 models are kept.
Ablation Task Pretrained Models To maintain consistency in tokenization, we use character-level tokenization instead of the default tokenizer of the Llama models. We use LoRA (Hu et al., 2021) with r = 64 and a = 128 for Llama- Mi and r = 32 and a = 128 for Llama-3B. In the initial round, we train for 1200 steps with a learning rate schedule that includes 10% warm-up steps to constant learning rate of 1e-4, followed by 20% cosine decay steps to a final learning rate of 1e-6. For subsequent rounds, we train for 600 steps per round using cosine decay learning rate schedule without warm-up. starting at le-4 and decaying to 1e-6.
28

---

Self-Improvnng Transformers Overcome Hary-to-Hard and Length Generalization Challenges
D. Full Results
D. RESULTS ON STRING COPY & STRING REVERSE
Copy
101
0.8
Accuracy
0.4
0.2
0.0
20
40
60
80
100
Number of Digits Reverse
0.8
Accuracy
0.2
0.0
20
200
Number of Digits
Figure 31. Results string manipulation tasks. (Top) Copying task. (Bottom) Reversing task. The model, initially trained on strings of length to 10, generalizes to strings over 120 digits through self-improvement.
D.0.2. RESULTS ON MULTIPLICATION
Each figure represents the average over different models.
D.0.3. RESULTS MAZES
We provide additional evaluation on mazes, based on the validity of moves and correctness end nodes.
29

---

Self- Self-Improving Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Mean Accuracy for Round
Mean Accuracy for Round 2
Mean Accuracy For Round
Mean Accuracy for Round 4
LAVE
5.50
LOV
5-8L
LAVE
L2Ve
LOW
5000
60%0
0002
6:01
5:400
8.00
8:90
1214
8:50
800
0.00
5:000
0831
8:80
0.0
5:00
0200
S.M
5:300
0.08
5:000
800
5.05
d:tt22
d
diR:2
digh
Neaa Acturacy Round
Nean
Round
Heean Acturasy for Round
04400
1000
1200
0.00
1.00
L,00
2.00
-000
2
1.00
1250
1.57
0.54
2-
1.00
2
1350
1.00
1.000
1.20
1000
1250
174
1200
1.00
L,00
5.00
510
1300
5.00
100
1000
0.04 8:00
0.21
(89 0.04
dgh
Figure 32. Results for multiplication without filtering. Each cell represents the accuracy on r--igit by m-digit multiplication. Red boxes indicate labeled n--istribution examples, while magenta boxes indicate evaluations after training on self self-improved data. The model initially trained on up to 5-by-5 multiplication. Generalizing to larger multiplications is challenging without data filtering.
Accuracy
Accuracy
Accuracy
Accuracy
204
1.00
1.50
1:00
1.00
1:500
250
1.00
1.05
5314
2000
1.50
1.50
1.050
800
1.00
0.114
3.55
LUV
12VE
LE00
1000
0832
1:50
LEV
L20
LU07
L00
LVR
LOVE
0.5
D0W
LOVE
100
LOS
1.00
1.00
1200
1200
1000
2:00
1200
2200
1,00
100
1200
1.07
0.51
3.00
1.00
5.000
digh2
4ghh3
diit22
Accuraty
Accuracy Round
Mcan Acturacy
Accuracy for Round
224
200
1200
1.05
3
1.000
1.AE
1.500
1.05
2740
1.A0
5.50
1.000
0350
1.000
200
LO0
K/0G
2014
1.00
Mean Accuracy for Round
Mean Accural acy Round
Mean Accuracy for Round 12
Mean Accuracy for Round
1.24
1.00
0311
2.222
1220
1505
1.50
1200
1230
1000
1.50
1.000
1.20
1999
0600
1122
5
1.80
0597
1000
0.69
1110
13.0
1000
1.06
317
5-
1300
1330
(197
0370
0354
0.02
2302
2231
E321
0
EBC
2322
C327
2234
0.411
1,42
2321
C322
2353
5.50
500
5
0200
1222
$322
Figure 33. Results for multiplication with length filtering with length threshold 10.
30

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Accuracy
Accuracy Round
Acouracy
LOSE
L:00
1,00
0.00
LO0E
250
0.03
LCC0
1.00
C.00
1-00
LOVE
5-000
LOW
1000
8.05
1.00
0.000
LPN
5,07
1111
Accuracy araayyyC
acy
Round
Mean Accuracy
Round
Mean Accuracy
1200
205
120
1.00
1250
1277
1.00
221
2.00
1.00
120
1.0
CML
1200
1.05
1350
1.00
1000
12X
135
1.00
1o00
1000
180
100
1000
1500 LM0
1.00
DER
1.0000
1.00
135
1.300
1.00
L.07
1:0
000
5 1.00
2353
1.00
1.00
0250
1.00
2387
1230
0.00
E.5
04/8
3.09
12.1
1.00
080
3.14
5.72
5.07
0.57
2107
5.5
080
Meon Accuracy for Round 9
Mean Accuracy for Round 10
Mean Acciurayy for Round 12
Mean Accuracy for Round 14
1.00
1.005
1
1
2-3.0
1.003
0.59
6-11
5.08
1.50
3.80
2217
1.97
5.79
2397
2.00
0.00
dgi
Figure 34. Multiplication with majority voting where filtering is based on agreement of at least 4 out of models. Applying majority voting enables effective generalization from n-by-n (n + 1)-by-(n + 1) multiplication tasks.
31

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
aocuracy
Accuracy
Accuracy
Accuracy
205
1.NE
0.00
000
100
CARE
5.00
5.14
2605
CC000
1.00
500
LOW
180
1000
LOW
040
LO00
120
LON
-00
0357
1000
L000
1800
LOW
D0W
0.00
1.00
2000
1.800
1.00
5.00
5.31
096
3007
C007
150
000
dith2
Maan cacaarayyy for Round
Mean Accurady For Round
Mean Accuracy o for Round
Mean Accuracy For Round
0.50
1000
1.00
1300
1800
1.00
1.00
1397
L000
190
1.08
190
1300
1105
120
7
0.308
1300
5.00
7
0350
026
5:18
5231
2009
244
6307
3.0
2.03
5.00
2.02
5.00
0.11
3
Maan Accuracy for Round
Mean Accuracy for Round 10
Mean Accuracy Round 11
Moan Accuracy for Round
.50
1,00
800
1.000
1,00
L.0E
6000
L400
1.50
L200
1.00
2
1.00
100
1.00
1.00
1.00
2.000
1.00
1.00
2 11.00
LOB
L.00
120
LO0E
120
C900
2000
150
LU0
21212
696.2
4242
dgt.2
Figure 35. Multiplication task with majority voting with shared self-improve data (Sce Section B.2.4).
32

---

Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges
Mean Accuracy for Round
Accuracy Round
Mean Accuracy for Round
Mean Accuracy Round
LOCO LO 00000990000000
8.00
digit
GLO0eL 0000 8.00
8.00
J00 EX 0000
9000
9 0,00
C/CC SOCE 1990 1990
10
8004
10
10 CICE
10
digit Mean Accuracy for Round
2igit
digit
diait
Mean Accuracy for Round 11
Mean Accuracy for Round
Mean Accuracy for Round 15
BA00OCOO LOCE
dit 1
000.0000000000 B00.000
J,000 10010000000000 200000 3000
wx 03908990.00 A304
www. 206 8396.0 A004
9
10
3004
10
SUCE
10
LOCE 3
A004
10
10
10
10
10
digit
digit
digit
digit
Mean Accuracy for Round 17
Mean Accuracy for Round 19
Mean Accuracy for Round 21
Mean Accuracy for Round 23
1000
dig:1
8204
1,00 5w0. 667.0. 3004
Londo www.s......oooooo
LO110 usp 1w to
10
10
10
10
10
2
2
digit2
digit2
Mean Accuracy for Round
Mean Accuracy
Mean Accuracy for Round
Accuracy
582 0.000
9
837003500.000000
10
2
3
7
20
8
2
dgt
2
Figure 36. Combining majority voting with length filtering. This approach achieves near-perfect length generalization up to 9 x 9, and potentially achieving further generalization.
33

---

Self- Copr-vipo Transformers Overcome Basy-to-Hard and Length Generalization Challenges
Mean Accuracy for Round
Mean Accuracy for Round 2
Mean Accuracy for Round 3
Mean Accuracy for Round 4
2010 nXe
2000 2000
627 8200
2010
det
830 00000000000000 500.00000000000000000000 106
KUT1 N. EACCOCPL.C 3.004
10
10 JUCC NLC
10
10 LUCE
10
10
aigit
digit
digit
digit
Mean Accuracy for Round
Mean Accuracy for Round
Mean Accuracy for Round
Mean Accuracy for Round
00000000 X00
500K 8004
0-0000 100000000000000000000000 87 0000000 XX0
18900.00 8004
5
5.0000 KG 000.000..00... 000.000000 Canc BO0
5 5-0000000 B900 80000000000000 E33 CODD
8.00
8-
S:0 8211 20100000000000000
8-
00000000..000 100
GUDE ICC 000000000000000 8000
10
10
Mean Accuracy for Round
Mean Accuracy cy for Round 10
Mean Accuracy
Accuracy for Round 12
dit
9- 20000000 200 1000 ww0. D2E MCS 634 00000.000 500
30000 M4 CCACAR5E 2EE C3908000000 8000
9
2.0CE 33333335880 5337 LO0 154 0.00 8004
0.045 3OCE 5900 354 0 RODE B L0020.00
10 0/03
10
10 0333
10
Mean Accuracy For Round
Mean Accuracy cy for Round 14
Mean Accuracy for Round
Mean Accuracy for Round 16
dggt1
10
G. 200
10
10
0.00 204 20w.33000000000 2015 8706
10
2
3
5
10
7
10
2
3
6
8
9
10
7
8
10
digit
2 2
digit 2
digit 2
Mean Accuracy for Round 17
Mean Accuracy for Round 18
Mean Accuracy for Round 19
3
4-
4
L300
7
7 7
LE
8
8
30
30
LCCL 1,00
20 3.00
2
5
10
3
6
7
9
10
2
5
9 10
digh
digh
2gg
Figure 37. Accelerated multiplication. We can significantly reduce the self- ceff-improvement rounds by carefully sampling a wider range of difficulties at every round. Perfect length generalization is achieved up to 10-by-10 10 multiplictiion with 19 self-improvement rounds.
34

---

Self-Improving Transformers Overcome Casy-to-Harde and Length Generalization Challenges
Hobetty
(Pogo)
Mevee
(Nogal
Maze (hogo) Nerther
231
Coper
Vaoe ([ops) Varia
182e (liope) Hujetty Vite
Maze (lose) Vettter (ovve Ende:
Maaze (1lope) Vertier (Moyes)
Maze dioge: Serteer SCh.0)
"urter opt
Munberc 1100
Nurte Hoa
Rampor cmnorratiin
DUNN CH
Figure 38. Maze solving task with increasing hops (Top to bottom) Exact match accuracy, move validation accuracy, and end validation accuracy. (Left right) No data filtering, majority voting based filtering, verifier on both moves and ends, verifier on moves only, verifier on ends only.
Medes) Muariy
Bodeal
Mac: Madees Volfect (Mores)
NaNe: (M632e)) Va
Mare [Wstes] Muntty Vite
Maze Puedest Verleer theee & Eniss)
Nace (lodte] Velfier (Moveo
Hore (hodeg) Verder Fndd
Humber lodes
Humbe Weco
Hamber Vode
Number 2oide
GINE DEI serrt
Figure 39. Maze solving task with increasing nodes. (Top to bottom) Exact match accuracy, move validation accuracy, and end validation accuracy. (Left right) No data filtering, majority voting based filtering, verifier on both moves and ends, verifier on moves only, verifier on ends only.
35


Reviews:
[{"review_id": "io1PHilnjE", "reviewer": "Reviewer_vrfN", "summary": "The paper introduces a self-improvement framework for transformer models that enables them to progressively tackle problems beyond the training distribution. Rather than modifying the underlying transformer architecture, the authors leverage an iterative self-training procedure in which a model generates its own training data and incrementally learns from increasingly difficult examples. The work is demonstrated across a range of algorithmic tasks—including arithmetic (both reverse and forward addition, as well as multiplication), string manipulation (copying and reversing), and maze solving. Two key unsupervised data filtering techniques are proposed: length filtering, which removes outputs shorter than an expected threshold, and majority voting, which retains only those examples that a set of independently trained models agree on. The experiments show that models trained with this framework can, for instance, generalize from 10-digit to 100-digit arithmetic problems and similarly extend their capabilities in other tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback and for acknowledging that the iterative framework is a compelling strategy to push the boundaries of the generalization capabilities of Transformer models, and recognizing our extensive ablations and analyses. Please find our responses to each of the concerns you have raised below.\n\n**W1,W2, Q1 Real world applications**\n> W1 The experiments focus solely on synthetic tasks. More real-world applications would be valuable to assess practical utility. I would expect the authors try their method to adapt a model trained on shorter text sequences to process longer inputs\n\n> W2 The method's performance on tasks with more complex or less structured data remains to be explored.\n\n> Q1 How do you envision scaling this self-improvement framework to tasks beyond synthetic benchmarks? Could you provide examples of potential real-world applications or domains where you expect similar performance gains?\n\nPlease refer to our General Response below in our response to Reviewer MReD (General response to overlapping concerns) regarding the limitations on synthetic tasks.\n \n**W3-1 Necessity of self-improvement vs. positional encodings**\n> Why do we need self-improvement while we can use positional encoding and not requires training to generalize to longer sequence?\n\nWhile approaches like RoPE indeed improve length generalization, they are complementary rather than replacements. Our self-improvement method is architecture-agnostic, requires no positional encoding modification, and naturally scales across diverse applications without architecture changes. This generality positions our method advantageously, especially when considering broad applicability to existing large pretrained models, avoiding retraining costs or architectural modifications. For example, for our pretrained model experiments, we employed pretrained LLaMA models utilizing RoPE. Hence, the choice of positional encoding is orthogonal to our core contribution. We will clarify and elaborate this point.\n\n**W3-2. On RoPE scaling for long-context**\n> The authors did mention that 'While effective in controlled setups, these approaches are often incompatible with large language models (LLMs) in practice, as they introduce task-specific modifications that are difficult to scale across diverse applications.' but RoPE, for example is applied on Deepseek and it is not 'task-specific'.\"\n\nRoPE itself is only a positional encoding choice, but we agree that RoPE scaling, used in DeepSeek, is proposed as a way to generalize to longer contexts without retraining the model. However, existing works on long context model evaluation [https://openreview.net/pdf?id=293V3bJbmE] shows that RoPE still struggles to achieve reliable performance on OOD input lengths. Furthermore, applying RoPE scaling on our synthetic tasks did not help with length generalization in our experiments. We will add our result on using RoPE scaling in the Appendix. \n\n\n**Q2. Sensitivity of Filtering Thresholds**\n> Have you conducted experiments to assess how sensitive the method is to the choice of filtering thresholds in both length filtering and majority voting? What guidelines can you offer for tuning these parameters in practice?\n\nWe agree this is important and will add further clarification in the paper. Based on our current observations, the impact of length filtering is task-dependent. In tasks like multiplication where errors tend to drop intermediate steps, the threshold is less sensitive. In contrast, tasks like forward addition(where incorrect outputs are typically just 1–2 digits short), stricter filtering is needed to avoid error propagation. Regarding majority voting, we plan to expand our ablations to show how the number of models affects filtering effectiveness. As indicated in prior work (e.g., https://arxiv.org/pdf/2306.15400), even a small number of highly accurate training examples can suffice for strong length generalization. Therefore, filtering for high-precision data by strong consensus among multiple models - even at the cost of sample quantity - can be beneficial. We thank the reviewer for suggesting this analysis and will include it in our revision.", "claims_and_evidence": "The paper’s core claims are:\n\n- Self-improvement enables transformers to overcome length and difficulty generalization challenges. They back this up with extensive experimental results on arithmetic (up to 100-digit addition, up to 10-by-10 multiplication), string tasks (copying, reversing up to 120 tokens), and maze pathfinding (from up to 9 hops to 30 hops, or from 30 nodes to 100 nodes). The evidence is convincing: they show consistent gains and near-perfect accuracies over multiple self-improvement rounds.\n- Data filtering is critical for stable self-improvement. The authors highlight “error avalanches,” illustrating how low-quality self-labeled data can accumulate and degrade performance. They demonstrate that straightforward filters—length-based filtering and majority voting across multiple models—significantly reduce noise. They also document label noise injection experiments that lead to self-improvement collapse, underscoring the importance of high-fidelity synthetic labels. This is well-supported by thorough ablations.\n- Pretrained models accelerate and improve self-improvement. The authors show that starting from larger LLaMA-based checkpoints (1B and 3B parameters) makes it easier to expand to out-of-distribution difficulties. These results, while not deeply analyzed in terms of underlying reasons, are plausible and are backed by side-by-side comparisons of smaller vs. larger models.\n- Long-horizon iterative training can lead to exponential improvements. They present an “accelerated self-improvement” schedule where the new round’s difficulty is not just “one step harder” but rather includes all newly mastered tasks. This quickly expands the range of tasks the model can solve. The experimental plots do show faster improvement under these scheduling choices.", "methods_and_evaluation_criteria": "- Self-Improvement Procedure: The iterative framework alternates between data generation (using the current model) and training with an expanded dataset, where new examples are filtered by length and consensus.\n- Data Filtering Techniques: Two unsupervised filters (length filtering and majority voting) are presented to prune noisy outputs.\n- Evaluation: Performance is measured by exact-match accuracy using greedy decoding. For arithmetic tasks, generalization is quantified by the maximum digit length (or operand size) that achieves near-perfect accuracy.", "theoretical_claims": "The paper is primarily experimental, focusing on empirical performance improvements rather than deep theoretical guarantees.", "experimental_designs_or_analyses": "The experimental setup is sound:\n\n- Controlled Difficulty Increase: For each task, a clear definition of difficulty (e.g., number of digits or hops) is provided. The incremental increase per round is systematic.\nAblation Studies: The paper examines the impact of filtering techniques, accelerated curricula, and the role of pretraining.\n- Error Avalanche Analysis: By injecting synthetic errors and tracking their impact, the authors provide a useful analysis of how self-improvement can collapse if noise is not managed.\n\nOne potential weakness is that all experiments are conducted on synthetic or algorithmic tasks. While these tasks are standard in the literature on length generalization, additional evaluations on more diverse real-world tasks might help demonstrate broader applicability.", "relation_to_broader_scientific_literature": "The paper is well-situated within the current literature:\n\n- It builds on prior work in length generalization (e.g., Anil et al., 2022; Zhou et al., 2023) and transformer modifications.\nThe self-improvement framework is related to recent studies on self-training and self-refinement in large language models (e.g., Huang et al., 2022; Singh et al., 2023).\n- The idea of easy-to-hard curriculum learning connects with literature on curriculum learning and weak-to-strong generalization.\n- The work distinguishes itself by showing that without modifying the transformer architecture, one can achieve significant extrapolation capabilities using a controlled self-improvement loop.", "essential_references_not_discussed": "The paper is well-cited", "other_strengths_and_weaknesses": "Strengths:\n\n- The iterative framework is a compelling strategy to push the boundaries of what transformers can generalize.\n- By relying on standard transformer architectures without task-specific modifications, the method is both simple and potentially widely applicable.\n- The paper presents extensive ablations and analyses, particularly on error propagation and the impact of filtering.\n\nWeaknesses:\n\n- The experiments focus solely on synthetic tasks. More real-world applications would be valuable to assess practical utility. I would expect the authors try their method to adapt a model trained on shorter text sequences to process longer inputs.\n- The method’s performance on tasks with more complex or less structured data remains to be explored. \n- Why do we need self-improvement while we can use positional encoding and not requires training to generalize to longer sequence? The authors did mention that \"While effective in controlled setups, these approaches are often incompatible with large language models (LLMs) in practice, as they introduce task-specific modifications that are difficult to scale across diverse applications.\" but RoPE, for example is applied on Deepseek and it is not \"task-specific\".\n\nOverall, this paper presents a solid contribution to understanding how self-generated data and controlled curricula can extend transformer capabilities beyond their initial training distribution. While certain aspects—such as scalability to non-synthetic tasks and formal theoretical analysis—remain open, the empirical results and methodological innovations make this work a significant and promising step forward.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "- How do you envision scaling this self-improvement framework to tasks beyond synthetic benchmarks? Could you provide examples of potential real-world applications or domains where you expect similar performance gains?\n- Have you conducted experiments to assess how sensitive the method is to the choice of filtering thresholds in both length filtering and majority voting? What guidelines can you offer for tuning these parameters in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mFhtsrxPK4", "reviewer": "Reviewer_J7z1", "summary": "This paper proposes and validates a simple and intuitive idea to train a model to solve hard problems that require long reasoning processes. The authors train the models on a task with progressively increasing complexity, leveraging the models' capability to generalize to slightly harder ones for self-improvement. The authors validate the success of this method with a number of synthetic tasks, including a maze puzzle. Analyses highlight the importance of filtering correct self-synthetic data through length filtering and majority voting in this method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition of our extensive experimental validation and clear presentation. We respond to your questions inline below.\n\n**W1 Limitations to Synthetic Setting**\n> It would be better if the authors can discuss more on how their findings can potentially help facilitate real-world tasks.\n\nPlease refer to our general response below in our response to Reviewer MReD (General response to overlapping concerns). \n\n**W2 Filtering**\n> The method in this paper is limited to synthetic settings with several implicit assumptions: ... (2) the existence of (unsupervised) filtering rules that enable near-perfect filtering, without which the accuracy drops obviously after few iterations.\n\n> It is not surprising to see reliable filtering is critical for the success of [.] (note: this comment appears to be cut off)\n\nWe agree that filtering is central to the framework. One interesting result is that simple majority voting over models trained with different seeds is surprisingly effective. This unsupervised, task-agnostic approach allows for easy application to a variety of tasks, including more complex ones.\n\n**Difficulty schedule**\n> The method in this paper is limited to synthetic settings with several implicit assumptions: (1) single task with fine-grained controllable difficulties ...\n\n> I am particularly interested in how much difficulty increased in each round of iteration for each task.  As mentioned in the Introduction, controlling the weak-to-strong curriculum is crucial, as models require a structured difficulty schedule to avoid catastrophic failure. But the authors only discuss this by directly putting the final setups without explaining the rationales in the Appendix.\n\nThank you for pointing out the need to clarify how we selected difficulty increments. Our primary consideration was to ensure data quality sufficient for reliable training in subsequent rounds, thus preventing error avalanches (Section 8). We recognize that our rationale behind difficulty increments could be clearer, and we will explicitly connect the choice of difficulty scaling with the avoidance of error accumulation. Additionally, we will include an experiment demonstrating the consequences of overly aggressive difficulty scaling, further clarifying the importance of difficulty schedule. \nOur existing \"accelerated self-improvement\" experiments (Section 7.2, Section B.4, Figures 12 & 23) also offer insights into the flexibility of our difficulty schedules, demonstrating the allowable range of difficulty increases with self-improvement rounds.\n\n**Connection to Length Scaling of Reasoning Models**\n> Results in this paper seem to relate to the inference length scaling of reasoning models[1].It would be interesting to discuss the connection between length scaling during RL and the findings in this paper. ([1] DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning)\n\nThank you for pointing out the potential connection between our results and the inference length scaling observed in reasoning models like DeepSeek-R1. Indeed, both lines of work emphasize iterative and incremental learning paradigms. We add a short discussion of this  connection and its implications in our revised manuscript.", "claims_and_evidence": "The main claim of this paper is that language models can generalize easy-to-hard and we can leverage this capability to self-improve models to solve progressively complex problems of a task. This claim is supported by convincing evidence of several synthetic tasks including difficult maze-solving.\n\nThe author emphasizes that reliable filtering is central to consistent self-improvement and that error avalanche caused by label noise as a key failure case of the self-improvement process. The results Fig. 6 and Fig. 9 justify this.\n\nThe rate of self-improvement can be exponential and pretrained models can achieve faster acceleration in easy-to-hard generalization. The evidence in Fig. 12 supports this.", "methods_and_evaluation_criteria": "This paper presents the effectiveness of the methods under synthetic tasks. These tasks make the task difficulties easy to control which might cause concerns about adopting the method to real-world tasks. Besides, it is unclear in what situations the proposed unsupervised filtering method works or fails.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The experiment designs are presented clearly. I am particularly interested in how much difficulty increased in each round of iteration for each task. As mentioned in the Introduction, controlling the weak-to-strong curriculum is crucial, as models require a structured difficulty schedule to avoid catastrophic failure. But the authors only discuss this by directly putting the final setups without explaining the rationales in the Appendix.", "relation_to_broader_scientific_literature": "Results in this paper seem to relate to the inference length scaling of reasoning models[1]. \n\nIt would be interesting to discuss the connection between length scaling during RL and the findings in this paper.\n\n[1] DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning", "essential_references_not_discussed": "Not found.", "other_strengths_and_weaknesses": "Strengths:\n1. This paper is clearly organized and the experiments are extensive.\n2. The claim in this paper is well justified through well-controlled experiments.\n3. It is interesting to see unsupervised filtering technique is enough to drive fil\n\nWeaknesses:\n1. The method in this paper is limited to synthetic settings with several implicit assumptions: (1) single task with fine-grained controllable difficulties; (2) the existence of (unsupervised) filtering rules that enable near-perfect filtering, without which the accuracy drops obviously after few iterations. \n\nIt would be better if the authors can discuss more on how their findings can potentially help facilitate real-world tasks.\n\n2. It is not surprising to see reliable filtering is critical for the success of .", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SLHOAUTB3Y", "reviewer": "Reviewer_MReD", "summary": "This paper presents a self-improvement approach where standard decoder transformer models iteratively generate and learn from their own predictions. The authors show that this self-improvement approach allows models to achieve extreme length generalization, where the length of a test instance can be up to 5x-6x longer than the length of a training instance, for addition, string copy, multiplication, and shortest path problems. For these problems, length generalization corresponds naturally to easy-to-hard generalization, where longer input instances are also harder to solve. The core of the proposed self-improvement approach is a data filtering procedure. Data filtering ensures that the self-generated labels are accurate enough so that they will not degrade the model's performance when it is fine tuned on its own predictions.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and for recognizing the thoroughness of our experimental design.\n\n**W1 Limitations to simple tasks**\n> This paper is very much limited by the simplicity of the task[...] length of the input corresponds nicely to the difficulty of the problem. However, in many (and more realistic) cases, such a correspondence is not that straightforward.\n\nWe agree that for most of the tasks we considered, longer length implies higher difficulty. But for tasks like maze solving, a larger number of nodes do not correspond strictly to harder instances; it is possible to have a smaller maze that is harder due to a higher branching factor. It would indeed be interesting to consider tasks whose difficulty scales constantly or inversely with length. Moreover, we absolutely agree that estimating the difficulty of real-world tasks is an important future direction, and we discuss this point more in the Limitations section of our paper.\n\nFor more on real-world applicability, please refer to our general response below.\n\n**W2 Data filtering**\n> Without the data filtering procedure, the self-improvement framework will lead to much worse result. It is unclear how to design good data filtering procedure on more complex tasks.\n\nIndeed data filtering is crucial to the success of our self-improvement framework. One key finding from our experiments is the effectiveness of simple majority vote filtering. This strategy is notable because it does not rely on task-specific heuristics, making it potentially applicable to more complex scenarios.\nMoreover, filtering based on majority voting to ensure self-consistency is a widely-used approach, as we mention in our paper (L265).\n\n**W3 Implications for Complex Settings**\n> Therefore, the implications of the findings presented in this paper to more complex settings is not clear. Besides stating this as a limitation, the authors should at least discuss how the results on simple tasks would be useful for more complex tasks.\n\nWe acknowledge your valid concern regarding the implications of our findings for more complex, real-world settings. As we discuss explicitly in our Limitations Section, defining and quantifying task difficulty remains an open and significant challenge in practical applications. However, our results provide valuable insights into systematically scaling task difficulty, an essential step for enabling transformers to tackle more complex real-world problems effectively.\n\nMoreover, our experiments show that models exhibit robustness to imperfect difficulty scheduling, especially when starting from pretrained models. This robustness improves further with increased training rounds. Additionally, we find that decomposing complex problems into intermediate steps enhances the model's ability to generalize. Notably, pretrained models are particularly effective at leveraging these decompositions, highlighting a promising avenue for applying our method to complex tasks.\n\n---\n## General response to overlapping concerns:\n> Real-world Applicability and Generalization Beyond Synthetic Tasks.\n\nWe acknowledge this valid concern. We selected synthetic tasks for their well-defined difficulty and clear evaluation metrics, which allow for controlled and rigorous analysis.\n\nAdditionally, the scope of our chosen tasks aligns with common practice in the length generalization literature. Many influential works (Li et al., 2023;Ruoss et al., 2023;Zhou et al., 2023;McLeish et al., 2024;Kazemnejad et al., 2024;Sabbaghi et al., 2024;Cho et al., 2024;Zhou et al., 2024;Fan et al., 2024) have focused on the problem of generalizing beyond lengths seen during training using synthetic tasks, gaining recognition for providing critical insights into model limitations and capabilities. In fact, this line of research dates back to early works such as Neural GPUs(Kaiser and Sutskever, 2016) and Universal Transformers (Dehghani et al., 2019). We cite these studies to legitimize our methodology, demonstrating that insights derived from synthetic tasks are widely considered meaningful and impactful.\n\nCompared to many prior works, our work considers a broader range of synthetic tasks with varying difficulty, encompassing arithmetic operations, string manipulations, and maze-solving problems. These tasks allow us to stress-test self-improvement in diverse settings and build insights applicable to more complex domains. Although out of the scope of this paper, we plan to extend self-improvement to long-context natural language reasoning benchmarks.\n\nOverall, we believe our paper presents an important step forward. We demonstrate improvements to the existing length generalization literature by providing a method that can continue the trend of generalization indefinitely, on a wider range of tasks. We supplement the work with robust empirical analyses. Our work establishes foundational insights on how self-generated data and iterative self-improvement can extend the capabilities of transformer models.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "There is no theoretical claim.", "experimental_designs_or_analyses": "I checked all experimental designs and analyses in the main paper, as well as the motivation for data filtering discussed in the appendix. The experiments are well designed and thorough.", "relation_to_broader_scientific_literature": "Achieving good length generalization is an important and difficult problem. The results in this paper can motivate future work on achieving length generalization on more complex tasks, by adopting appropriate data filtering within a self-improvement framework.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "While I appreciate the comprehensive empirical evaluation and analysis presented in this paper, I think the scope of this paper is very much limited by the simplicity of the tasks considered by the authors. On these tasks, it is natural that the length of the input corresponds nicely to the difficulty of the problem. However, in many (and more realistic) cases, such a correspondence is not that straightforward. More importantly, as the authors show in the paper, the success of self-improvement hinges on the quality of the model's prediction at every round, which in turn is almost entirely dependent on the data filtering procedure. Without the data filtering procedure, the self-improvement framework will lead to much worse results. It is unclear how to design good data filtering procedure on more complex tasks. Therefore, the implications of the findings presented in this paper to more complex settings is not clear. Besides stating this as a limitation, the authors should at least discuss how the results on simple tasks would be useful for more complex tasks.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pb2VdBPKl9", "reviewer": "Reviewer_FEuQ", "summary": "The paper demonstrates the capability of language models for self-improvement: achieving improved performance on problem instances beyond the training data, using model generations alone (without additional labeled data). The work focuses on two settings: length generalization, where the model is trained on shorter sequences and extrapolates to longer ones; and easy-to-hard generalization, where model is trained on easy/simple problem instances and is trained to generalize to harder instances. The authors study different arithmetic problems (addition and multiplication), copying and maze-solving, and show impressive results in all settings. To achieve self-improvement, the authors initially train a model on short/simple instances with fully supervised labels, and then iteratively increase the length/complexity of the problems, training the model on its own generations instead of using labeled data. The authors utilize data filtering techniques -  majority voting and filtering based on length, and demonstrate their effectiveness in achieving out-of-distribution generalization in harder settings. Finally, the authors analyze how errors accumulate during the execution of the self-improvement procedure, and how data filtering can mitigate this.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and appreciating the novelty, clarity, and thoroughness of our approach and experiments. We address your specific comments and suggestions below:\n\n**Computational Cost**\n> Length generalization is interesting for two reasons: First, because we don't have training data with long sequences; and second, because training on long sequences is very costly. ...  While I believe that addressing only the first issue is important, the authors should discuss this limitation explicitly. Additionally, I think that discussing the overall computational cost of the method (and ideally compare it to other methods for length generalization) would be helpful.\"\n\nWe appreciate your highlighting this point. While our manuscript briefly mentions the inherent differences of our method from other length generalization approaches (lines 82, 623-626), we agree that explicitly mentioning computational costs is crucial. Indeed, our iterative training method does require higher computational resources compared to single-round training strategies, as it involves multiple iterations of model training. We will clearly discuss this computational trade-off and compare it with other methods explicitly in the revised manuscript.\n\n**Comparison with Positional Encoding Method**\n>  I think the authors should directly compare their results, at least in some of the experiments, to other length generalization methods on the same tasks.\n\nWe acknowledge your suggestion to explicitly compare our approach with other positional encoding (PE) methods. We want to emphasize that our framework is fundamentally architecture-agnostic and can be combined seamlessly with various positional encodings, including both NoPE and RoPE. \nSpecifically, we used NoPE in experiments involving small models trained from scratch due to its better length generalization properties compared to absolute position encoding (APE) or RoPE. Conversely, for our pretrained model experiments, we employed pretrained LLaMA models utilizing RoPE. Hence, the choice of positional encoding is orthogonal to our core contribution. We will clarify and elaborate this point.\n\n**Clarification on Majority Voting Filtering**\n> In the majortiy voting based filtering, the authors use an ensemble of models, all trained from scratch with different seeds and datasets. This seems much more expensive than sampling with temperature. Does temperature sampling simply not work, requiring this more complex method? I think that discussing the computational cost of this ensemble method would be useful, and also maybe comment on how it could be improved (e.g., how large should k be for the method to work)?\n\nWe did not consider temperature scaling because our tasks are structured to have a specific input-output format. Thus, temperature sampling did not yield sufficient output diversity. Specifically, we observed very high confidence (over 0.999) in top-1 outputs using beam search (for reverse addition task), indicating minimal diversity even with temperature sampling. However, we anticipate temperature scaling could be more effective for pretrained models that can generate more varied outputs.\n\nRegarding computational cost, we conducted ablation studies for majority voting in Appendix Section B.2.4, exploring data cost and performance trade-offs. Given computational costs scale linearly with the number of ensemble models, we will add explicit commentary on this trade-off, as well as provide new results on how accuracy and performance vary with ensemble size (k) and consensus thresholds in our revision.\n\n**Q1. Generalization beyond 100 digits**\n> In the addition experiments, the authors claim that they achieve generalization to over 100 digits, but from the plots it seems that performance could keep improving. How far does the generalization actually reach? Did the authors run experiments beyond this range?\n\nOur experiments show that self-improvement can continue indefinitely as long as data accuracy remains high. We halted our experiments around 100-digit sequences due to memory constraints, but since performance remained stable, we anticipate continued successful generalization beyond this length.\n\n**Q2. Relative Filtering**\n> The description of relative length filtering is unclear. How is used? Are the lengths filtered based on a fixed constant, or relative to the maximal length L?\n\nWe apologize for the unclear description. Currently, relative length filtering uses fixed thresholds (e.g., threshold value of 2 for forward addition and 10 for multiplication). We will clarify this clearly in our revised manuscript. Following the suggestion from Reviewer vrfN, we will also add sensitivity analyses for filtering thresholds. Employing thresholds relative to maximal sequence length L would be a valid (and insightful) approach as well, although it is not used in our experiments.", "claims_and_evidence": "The method and the results shown in the paper are novel, with very impressive performance on hard tasks like multiplication and maze solving. The paper is very well-written, the ideas are clearly introduced and the authors did a very good job in presentation of the results. The study of error accumulation is also interesting in its own right, and overall the experiments demonstrate the success and limitation of different methods very thoroughly.\nSome concerns regarding the results:\n- I think that the comparison to other length generalization works is a little misleading. Length generalization is interesting for two reasons: First, because we don't have training data with long sequences; and second, because training on long sequences is very costly. The method presented in the paper addresses the first problem, i.e. - gives a solution that could be applied in cases where we don't have training data with long sequences (although, the method does require input \"questions\" for longer sequences, also discussed in the limitations section). However, it does not improve the computational cost of training on long sequences, and if anything makes the training cost much higher. While I believe that addressing only the first issue is important, the authors should discuss this limitation explicitly. Additionally, I think that discussing the overall computational cost of the method (and ideally compare it to other methods for length generalization) would be helpful.\n- Related to the above, I think the authors should directly compare their results, at least in some of the experiments, to other length generalization methods on the same tasks. The authors claim that other length generalization methods change the positional encoding, architecture and data to address length generalization, in contrast to this paper. However, the paper also uses a somewhat non-standard positional encoding (NoPE). So, how do the results in the paper compare to length generalization methods that make \"reasonable\" changes (i.e., changing the positional encoding but not the data)?\n- In the majortiy voting based filtering, the authors use an ensemble of models, all trained from scratch with different seeds and datasets. This seems much more expensive than sampling with temperature. Does temperature sampling simply not work, requiring this more complex method? I think that discussing the computational cost of this ensemble method would be useful, and also maybe comment on how it could be improved (e.g., how large should k be for the method to work)?\n\nMore minor comments:\n- In the addition experiments, the authors claim that they achieve generalization to over 100 digits, but from the plots it seems that performance could keep improving. How far does the generalization actually reach? Did the authors run experiments beyond this range?\n- The description of relative length filtering is unclear. How is $\\tau$ used? Are the lengths filtered based on a fixed constant, or relative to the maximal length L?\n\nTo summarize, I think this is a very good paper, demonstrating the effectiveness of self-improvement method for achieving out-of-distribution generalization in different settings. The experiments are very convincing, but I believe that proper discussion of computational cost compared to other methods could improve the paper.", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "See above.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary of the Paper:**
This paper introduces a self-improvement framework for transformer models, enabling them to progressively tackle problems beyond their training distribution. The approach leverages iterative self-training, where models generate their own training data and learn from increasingly difficult examples. Demonstrated across tasks like arithmetic, string manipulation, and maze solving, the method shows significant improvements in out-of-distribution performance, such as generalizing from 10-digit to 100-digit addition.

**Strengths and Weaknesses Highlighted by Reviewers:**
- **Strengths:** Reviewers praised the innovative self-improvement framework and its solid empirical results across diverse tasks. The method's simplicity and potential broad applicability were highlighted, along with thorough ablations and analyses on error propagation and filtering techniques.
- **Weaknesses:** Concerns were raised about the focus on synthetic tasks and the practical relevance of the findings. Some reviewers questioned the scalability of the method to real-world applications and the computational cost involved.

**Rebuttal and Discussion with Reviewers:**
The authors provided detailed responses, emphasizing the foundational insights gained from synthetic tasks and the potential for future extensions to real-world scenarios. They clarified the effectiveness of their filtering techniques and addressed concerns about computational costs and the choice of positional encoding. Reviewers acknowledged the thorough rebuttal, with most maintaining their positive evaluations, while one reviewer (MReD) remained skeptical about practical implications.

**Recommendation for Acceptance:**
Given mostly positive (although not unanimous) assessments, we recommend accepting this paper as it presents a step forward in understanding and improving transformer models' generalization capabilities. While reviewer MReD raised valid concerns about practical relevance, narrow results in synthetic settings do have a place in science, as they are often crucial initial steps towards broader understanding and future applications. Thus, we believe the paper's innovative approach, extensive empirical validation, and detailed analyses make it a valuable contribution to the field.
Decision: Accept (poster)