The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner
Authors: Zhouqi Hua
Wenwei Zhang
Chengqi Lyu
Yuzhe Gu
Songyang Gao
Kuikun Liu
Dahua Lin
Kai Chen
Venue: ICLR 2026 Poster (2026)
Keywords: Length Generalization
Large Language Models
Turing Machine
Chain-of-Thought
Computable Reasoning
Synthetic Dataset
Primary area: foundation or frontier models, including LLMs
TL;DR: Train LLMs to imitate Turing machines for universal and effective length generalization on a challenging synthetic dataset of 18 tasks across 8 algorithmic classes.

Abstract: Length generalization, the ability to solve problems of longer sequences than those observed during training, poses a core challenge of Transformer-based large language models (LLMs).
Although existing studies have predominantly focused on data-driven approaches for particular arithmetic operations or symbolic manipulation tasks, these approaches tend to be task-specific with limited performance on individual tasks.
To pursue a more general solution, this paper focuses on a broader case of reasoning problems that are *computable*, *i.e.*, problems that algorithms can solve, thus can be solved by the Turing machine, which operates over inputs of unbounded length.
From this perspective, this paper proposes **T**uring m**A**chine **I**mitation **L**earning (**TAIL**) to improve the length generalization ability of LLMs.
TAIL uses computer programs to directly synthesize chain-of-thought (CoT) data that imitate the execution process of a Turing machine, which *linearly* expands the reasoning steps into *atomic* states to alleviate shortcut pattern learning and explicit *memory* fetch mechanism to reduce the difficulties of dynamic and long-range data access.
To validate the universality and reliability of TAIL, we construct a challenging synthetic dataset covering 8 classes of algorithms and 18 tasks.
Without bells and whistles, TAIL significantly improves the length generalization ability as well as the performance of Qwen2.5-7B in individual tasks using only synthetic data, surpassing previous methods and DeepSeek-R1.
The experimental results reveal that the key concepts in the Turing machine, instead of the human-like thinking styles, are indispensable for TAIL for length generalization, through which the model exhibits read-and-write behaviors consistent with the properties of the Turing machine in their attention layers. This work provides a promising direction for future research in the learning of LLM reasoning from synthetic data.

Published as a conference paper at ICLR 2026
THE IMITATION GAME: TURING MACHINE IMITATOR IS LENGTH GENERALIZABLE REASONER
Zhouqi Hua"
Wenwei Zhang2+t
Yuzhe Gu Kuikun Liu² Dahua Lin 2.4 Kai Chen
Chengyi Lyu²
Songyang G
FFudan University Shanghai AI Laboratory Shanghai Jiao Tong University
"MMLab, The Chinese University of Hong Kong
(huazhougi, zhangwenwei, chenkai jep detpr//ewweeeeeeaaeeeeg.......re org.cn
ABSTRACT
Length generalization, the ability to solve problems of longer sequences than those observed during training, poses a core challenge of Transforrer-baaedd large lan- guage models (LLMs). Although prior work explores data-driven methods for specific arithmetic or symbolic tasks, such approaches remain task-specific with limited performance. To pursue universality, this paper studies computable rea- soning problems, i.e., those solvable by algorithms and hence by Turing machines with unbounded input length. From this perspective, this paper proposes Turing mAchine Imitation Learning (TAIL), which uses computer programs to directly synthesize chain-of-thought (CoT) data that imitate the execution process of a Turing machine, which linearly expands the reasoning steps into atomic states alleviate shortcut pattern learning and explicit memory fetch mechanism to reduce the difficulties of dynamic and long-range data access. To validate the univer- sality and reliability of TAIL, we build a challenging synthetic dataset spanning 8 algorithm classes and 18 tasks. Using marginally shorter CoT than reasoning models such as DeepSeek-R1 (671B), TAIL achieves improved length generaliza- tion and superior task performance on Qwen2.5 (7B) with only synthetic training data. Experiments show that Turing-mach machine principles, rather than human-like thinking styles, are critical for length generalization, inducing readwrite behaviors in attention layers consistent with Turing machines.
INTRODUCTION
Length generalization (Press al. 2021), i.e., the ability to handle a problem with input sequences of various lengths in the open world, especially those longer than previously seen, is fundamental aspect of human intelligence and serves as a crucial evaluation criterion for Al systems (Anil et al.) 2022 Sinha et al.) 2024; Ahuja & Mansouri 2024; Shi et al. 2022). Although the ability and
generalizability of large language models (LLMs) to solve complex problems have been significantly improved by Mhain-of-thouse
(CoT) (Wei et al. (222). recent studies (Saparov & He 2022; Anil jet al. 2022; Zhou et al.) 2024) indicate that LLMS still struggle with length generalization, which sometimes explores and falls into shorteuts that eventually cause errors (Saparov et al. 2024).
To address the challenge, existing works (Zhou et al. 2024; 2023 Lee et al. 2023 Shen et al. 2023 McLeish et al. (2024) primarily focus on data-driven approaches, which refine the training data by modifying the structure of CoT to be more effective and generalizable. However, these methods remain inherently task- specific, e.g., Index Hint (Zhou et al. 2024, 2023) for symbolic reasoning tasks and Reversed Format (Lee et al., 2023) Shen et al., 2023; Zhou et al. 2023) McLeiih et al.) 2024) for arithmetic problems, and yield only moderate performance gains. Thus, a question arises: Is there universal and effective CoT structure for length generalization?
This paper aims to answer this question by first taking deeper look at the commonalities among the problems. Notably, we observe that many of these tasks admit well-defined stepwise procedures that can be solved by program algorithms that generalize to inputs of arbitrary length. We refer to
Equal contribution, i Corresponding author

---

Published as a conference paper at ICLR 2026
Tape
Step Consiter dp(10)111).
Step
11(
Virtte
Wee have get dp(9][5]=+> 16.
Head
-ee have get dp( 15.
Step Consider dp[
Step
maximum the backpack dp(t0][[1-
Rend
N2
Step & Consider dp(s)(11
Step
(16.15)
Retum dp(10
Writle
Read (16,15)
Write 16
State Transition
Reasoning CoT
LaNoe UNIV
dMis
S₃
16
15
(a) Turing Machine
(b) Turing Machine Imitation
Figure 1: Turing machine and its imitation in LLMs. (a) Illustration of a Turing machine performing
algorithmic execution over symbolic tape via sequential state transitions. (b) TAIL simulates Turing machine execution by linearly structuring CoT into atomic read-write steps. Attention maps reveal operand retrieval and memory update patterns analogous to symbolic computation.
such tasks as Computable Problems, which serve as the focus of investigation in this paper. Thus, the core of achieving length generalization lies in letting LLMs faithfully simulate the execution process of the corresponding programs within their CoT for each problem. In essence, the LLM acts like a Turing machine (Figure [a), performing a sequence of fundamental operations on a memory tape, guided by finite states and logical transitions.
From this perspective, we propose Turing mAchine Imitation Learning (TAIL), which contains the three key structures in the synthesized CoT data that emulate three core properties of Turing machine execution: Linear Transition, Atomic State, and Memory Fetcher. First, similar to the Turing machine execution process, Linear Transition enforces complete and línear arrangement of reasoning steps to eliminate potential shortcut learning. Second, TAIL decomposes the reasoning content into minimal units, termed Atomic States reduce difficulty and further reduce shortcut learning, which essentially correspond to the states of a Turing Machine, including read, write, and logical control operations. Third, because LLMs can only append instead of modify in-place the tokens in their context due to their auto-regressive nature, the context of LLMs, which essentially serves as memory, will keep growing as the reasoning continues. This poses difficulties for LLMS because of their attention mechanisms when they need to conduct elementary operations operands that have long and dynamic distances among them. Therefore, TAIL further adopts a mechanism, termed Memory Fetcher, read the necessary operand data and explicitly output them in the current step before conducting elementary operations.
To assess the universality and effectiveness of TAIL, construct challenging dataset spanning 18 tasks across algorithms, substantially harder than those in prior length generalization stud- ies. Fine-tuning Qwen2.5-7B (Yang et al. 2024) on this dataset yields high label accuracy across length ranges, with consistent gains on longer sequences, demonstrating strong length generaliza- tion over difficult samples. The model outperforms prior methods (Zhou al. 2024 Lee et al.) 2023 Shen et al., 2023) Zhou et al.] [2023] Martinez et al.] 20233] McLeish et al., 2024)) and sur- passes DeepSeek-Re RI (Guo et al.] (002).. Ablation studies show that removing any core module of TAIL severlly degrades seggeeeeennce performance. Notably, even minimalist CoT data containing only core modules without any thinking styles" maintains full effectiveness, confirming TAIL as the key data-driven enabler of length generalization. We also visualize the attention maps of the TAIL- fine-tuned model and observe that the attention during write operations focuses on fetched operands within the same state, resembling Turing machine behavior (Figure (p))
Thinking styles refers to the human-lik linguistic expressions in CoT reasoning which are very common in existing large reasoning models, iee., the surface-level natural language narrative rather than the underlying reasoning mechanism.
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
2.1 LENGTH GENERALIZATION AND COMPUTABLE PROBLEMS
For large language models (LLMs), length generalization means that model can process long input sequences, although it is only trained on short sequences. For example, a model trained on 10- 30 digit addition can maintain strong performance on 30-50 digit addition tasks. Fundamentally, successful length generalization implies that the model has extracted a structural pattern from the training data. This pattern should be general and can scale adaptively with input length.
After deeper look at the problem, incorporating insights from prior indirect conclusions (Delétang al. 2022). we observe that many tasks can essentially be solved through discrete symbolic trans- formations governed by bounded algorithmic computational rules (Turing et al. 1936 Sipser 1996. Arora & Barak 2009. Boolos et al,, 2002). For example, Parity can be solved through a simple enumeration procedure, while arithmetic addition can be handled by simulating the full digit-wise addition process, including carry propagation. We refer to such tasks as Computable Problems, whose commonality lies in being solvable by well-defined, deterministic algorithmic procedure. Such algorithms inherently handle inputs of arbitrary length, which aligns with the goal of length generalization. Training LLMs to learn their step-by-step execution thus enables generalization across input lengths when solving computable problems.
2.2 TURING MACHINE
While all computable problems are solvable by algorithms, their structural diversity makes chain- of-thought (CoT) design impractical. Therefore, a more abstract and general framework is essential to unify the CoT paradigm for computable problems. Based on the Church-Turinn Turing thesis (Copeland) 1997]. a Turing machine can solve any algorithmically computable problem, thereby providing universal and higher-level framework for problem solving. In other words, the computational trace data of any computable problem can be constructed by simulating the execution of a Turing machine.
The formal definition of the Turing machine (Turing al. 1936 Hopcroft et al., 2001) consists of an lnfinite-length tape, read/write head, and a table containing a finite set of state transitions. It can be represented as 7-tuple
M = = L,,,,T,& qu. B,F),
(1)
where Q is finite set of states, 8 is the transition function, go E Q refers the initial state (see Appendix [ for full definitions). In any non-accepting state E Q. the head reads a symbol from the tape, overwrites with a new symbol b, and moves the head new position, thereby transitioning to the next state Io+1, which can be formally defined as:
8(g,, a) = (g++1, b. D):
(2)
where the head moves one position in direction D. Thus, 8 represents a complete state transition conflating two logically independent states, and a linear unfolding of states qu 91 represents the complete process of Turing machine implementing the program. In order to align the reasoning process of L.MMs with Turing Machine, the reasoning procedure can be unfolded into multi-step reasoning with the help of COT. Each single reasoning step can be formalized as x; in COT, deriving the current reasoning result based on the preceding reasoning steps Zeg. note that the granularity of I; is determined by the size of the reasoning step in the specific task. Typically, it corresponds to the prediction of multiple tokens, forming an intermediate reasoning outcome at each stage. Zn represents the query and thus the complete reasoning path (CoT) can be expressed as Zo - 21 - ... - In. In line with the Turing machine, each reasoning step corresponds to a Turing Machine state y in (q.(2), which includes reading an input symbol a. The entire CoT formed by a linear composition of such steps, analogous to the full unrolling of the Turing Machines state transitions 8 from @1 Gn.
4n.
important to
Previous work (Li et al. 2024) has theoretically shown that Transformers can achieve Turing Com- pleteness given sufficiently long CoT, but has not provided concrete guidelines for constructing such CoT sequences in a wide range of tasks. Based on our analysis, multi-step reasoning CoT can be structurally aligned with the computation process of Turing machine. This leads us to hypothe- size that, by endowing the reasoning process of LLMs with key properties of a Turing machine, the model can effectively simulate algorithmic execution and achieve length generalization.
3

---

Published as a conference paper at ICLR 2026
(a) Core Modules TAIL
(b) CoT Example of TAIL
(c) Traditional CoT
Bach
Atomic State 1
value Dt, 7u46 9.5, 03 Find the maximum harvest.
and ylelds harveet
Larger Subtask 1
Shotout
Legic Control
which
imapsack problem
Larger Subtask 2
Memory Fetcher
Blementory
Step Consider Sdp[soj[Lijs
The value of the 10th-item is and the weight of the 10th-rhem in
Logl: Control
@ (TAAKE the 10tt-item,
Larger Subtask
2 NOT
maximum the above ino.
Linear Transition
Imeegllrr expansion
Return back dp[o)(4).
Atomic State n
we have got dp/9]]11]15..
We have dod9))3)ddnd.
Larger Subtask M (Mi+<N)
qet The maximum volue baccpaok
Figure 2: An overview of TAIL. (a) Core Modules TAIL imitate a Turing Machine, containing
Linear Transition of Atomic State with Memory Fetcher of previous reasoning results. (b) CoT gen- erated by TAIL: the solution to 0/1 knapsack problem using a dynamic programming algorithm. (c) Traditional CoT consists of oversized subtasks, shortcut learning, and irregular expansion.
TURING MACHINE IMITATION LEARNING
Based on the preceding analysis, this paper proposes Turing mAchine Imitation Learning (TAIL) to align the Chain-of-thought (CoT) of large language models (LLMs) to simulate the execution of a Turing machine for achieving universal and effective length generalization. TAIL imitates key properties of Turing Machine (Figure 2), comprising three modules spanning macro to micro levels: Linear Transition (Section 3.1 Atomic State (Section 3.2) and Memory Fetcher (Section 3.3
3.1 LINEAR TRANSITION
According the RASP-Generalizatte Conjecture (Zhou et al., 2023). Transformer-bast LLMs struggle with problems that involve intricate control structures, such as loops. This suggests the need to transform these structures into simpler forms that align better with the capabilities of the model. In particular, complex reasoning structures (like trees and graphs) can be linearly unrolled and traversed to enable complete and non-redundant execution all reasoning steps, thereby pre- venting shortcuts in the reasoning process. Similarly, in Turing machine, the execution of com- plete program corresponds to a linear unfolding of states 91 - 92 - ... > 9n as shown in Eq.(), where even control structures such as loops can be flattened into sequential process. To align with this characteristic, we introduce Linear Transition, which describes from a macro-level perspective how individual reasoning steps composed into linear and orderly structure within the overall reasoning process, and collectively form the CoT.
3.2 ATOMIC STATE
Although Linear Transition defines the overall structure of CoT reasoning as a linear sequence of reasoning steps, does not impose constraints on the size of each step. Overly large reasoning steps not only increase the difficulty of learning for the model but also risk introducing shortcuts within a single step. Therefore, we attempt to constrain the size reasoning step by enforcing a standardized internal structure. Inspired by the Turing machine, each state encompasses sequence of simple operations: reading data from the tape, writing new data, and transitioning to the next state. Following this principle, define Atomic State consisting of operand retrieval (realized via Memory Fetcher, detailed in Section 3.3), the elementary solution produced within the reasoning step, and set of logical control statements, shown in Figure a). Meanwhile, following the
4

---

Published as a conference paper at ICLR 2026
Traditional CoT
546E10R1115
Long contint value the backpack S4p(PP))
Lorg content
value of the backpask ls $05091113
Long content
The maximum value of tackppdd
Sop(1211111
16
Long distance
attention Reasoning
Decouple
TAIL-CoT-styled
The masimum
The mucimum 541081))11 = 15
Retum back 545t10g1158
We masimum
Long contiont
Long content
Long content
Sig(Pig5) 16
$da(10g111 16
Retrievol
2 Reasoning
Figure 3: Comparison of traditional CoT and TAIL's Memory Fetcher, which decouples long- distance attention and the reasoning process.
RASP-L hypothesis argue that each Atomic State should adhere to the principles of realizability and simplicity. Specifically, since we use Python programs to synthesize COT, we define an Atomic State as single algorithmic step in the program without internal loops.
3.3 MEMORY FETCHER
In Turing machine, every state reads data from the tape and replaces it with processed result. How- ever, auto-regressive models (e.g., Transformer) can only extend the token sequence by appending new tokens instead of in-place token modification. So the action of data reading is typically achieved by constructing attention mechanisms over previous tokens. As reasoning progresses, the sequence grows longer, requiring the model to retrieval over increasingly distant and dynamically shifting tokens. Furthermore, simultaneously performing data retrieval and generating the elementary solu- tion at the same time increases the learning difficulty for the model. To address this, we propose Memory Fetcher to decouple these two operations by: (1) first explicitly outputting all relevant operands at the beginning of every Atomic State, (2) then performing reasoning and outputting local results. As shown an example in Figure 3 Memory Fetcher changes the attention structure by localizing operands and improves reasoning accuracy, which has been theoretically proved by recent work (Wang et al.) 2025). Figure HT compares the attention structures with and without Memory Fetcher. It is obvious that Memory Fetcher enables precise localization of relevant operands during reasoning through prominent local attention. See more details in Appendix
4 EXPERIMENT
4.1 DATASET SYNTHESIS
Task Selection. This work focuses on length generalization in hard samples rather than unlimited extension simple tasks. So we synthesize a set of challenging tasks based on classic algorithmic paradigms in computable problems to verify the effectiveness of TAIL. As shown in Table CI the dataset comprises 18 tasks, including previously studied problems such as addition, but with randomized digit lengths and decimal places to increase difficulty. Each task has a high degree of diversity in query narratives, some of which incorporate real-world problems (e.g., Diophantine Equation, 0-1 Knapsack, etc).
Synthesis Approach. We employed supervised fine-tuning (SFT) with synthetic data to internalize the model's 's ability to generate Chain-of-Thouug (CoT) with TAIL's 's core modules, Figure D] illustrates the data synthesis process of TAIL. We claim that TAIL is task universa 8 because for each task belonging to specific algorithm, it's feasible construct Python program and add
We do strictly follow RASP-I. constrain each reasoning step, hut it indicate problems directly solvable by Transformers. This relaxed view shows strong length generalization in our experiments. >previous methods like Index Hint Reversed Format, due to their structural specificity, cannot be effec- tively constructed for tasks beyond simple bit-matching operations.
5

---

Published as a conference paper at ICLR 2026
Compare Numbers WwL.ATI
Bubble Sort CONULATION
Word Flip CIPALATION
Large Number Addition FINLEATION
Large Number Division sowa 601M
Any Subsiring recuusioN
2.00
Derangement RXC-RSSON
Papulation Growth CIBAAERON
Dijkstro onsion
Multi-Machine Schadule
Count Letters INGMIISATION
Diaphantine Equation IYAHAWArOy
ORBEDT
Prime Search
LCS
0-1 Knopsock oo
Levenshtein Distance
Binary Search cocco's convucee
Pallindrme Combination BACKTRACCINNG
OHUMCSATION
OP
Swend.--7 Bate
Swen25-77 Enenuct
DeepSeeb-R11 (A75))
TAIL-8 (Ours)
In-domain
Figure 4:
Length generalization performance of Qwen2.5-7B finetuned with TAIL-CoT-style across all 18 tasks, in comparison with Qwen2.5-7B (base model), Qwen2.5-7B Instruct and DeepSeek-RI.
string append statements to assemble COT. When the program runs, the resulting CoT reflects the complete program execution flow. We implement the injection of three core modules in CoT through following methods: (1) Treating each algorithmic step as an Atomic State, especially each time entering loop. (2) Unfolding the algorithmic process sequentially
Linear Transition, achieved by using programs to synthesize CoT itself. (3) Explicitly outputting all relevant operands of current algorithm step Memory Fetcher in COT. During the generation process, performed strict de- duplication and ensured that none the data in the evaluation set was included in the training set. For training data, first validated the sufficiency of the TAIL architecture by synthesizing TAIL- CoT that only includes three core modules a format similar to that shown in Figure [3] Then we enrich TAIL-CoT into generalization ability on all 18 tasks, as shown in Figure 4 See Appendix D for more details.
using natural language (see Figure D4) and verify length
Dataset Size. To better facilitate training and evaluation of length generalization, defined three length ranges for each task: Short (S), Medium (M) and Long (L). For comprehensive training, we synthesized 100,000 training samples and 500 evaluation samples for each length range, resulting in 1,500 evaluation samples per task. The validation of length generalization refers to whether model trained on the S-range training set can avoid sharp performance degradation on the M- and L-range evaluation sets. The length ranges of each task are detailed in Table
4.2 EXPERIMENTAL SETTINGS
Metrics. Previous work (Saaarov& He 2022 has demonstrated experimentally that label accuracy well suited to measure reasoning capability of LLMss. We pass@1 label accuracy under the zero-shot setting and use greedy decoding to evaluate.
Training. We fine-tuned Qwen2.5-7B with training 2 epochs for most tasks and more epochs for a few more challenging ones with global batch size of 1024. The initial learning rate was le-5, decaying to 7e-7, with weight decay of 0.1.
Evaluation. To facilitate a more efficient evaluation procedure, we follow a dual-model framework. First, a small 1.5B specialized model extracts the answers. Then, Qwen2.5-72B-IInst. performs evaluations, outputting \boxed (YSS) } or (NO) to represent the evaluation result.
4.3 PERFORMANCE
Overall Performance. Due to its greater readability, we synthesized TAIL-CoT-styled (as shown in Figure D4 all 18 tasks across 8 classes of algorithms, and fine-tuned Qwen2.5-7B. As shown in Figure We observe length generalization on most difficult tasks, where there was no sharp performance degradation out-of-domain length sequences. Several tasks like Compare Numbers,

---

Published as a conference paper at ICLR 2026
Simulation
Enumeration Dicshantine Equatiion
Iteration
Divide & Conquer
Compare Numbers
Popuration Growth
Binary Search
Label Accuracy (1)
Recursion
DP LC6
Greedy
Backtracking
Any Substring
Hutt-Mochine Schedure
Permuration Combinatton
Label Accuracy (1)
M
M
6
Qwen2.5:78
TAIL-7B
TAIL-stylad
In-domain
Figure 5: Comparison fine-tuned Qwen2.5-7B with TAIL core module and the base model. For each algorithm, we select representative task. After fine-tuning, model demonstrates length gener- alization on sequences that are to 10 times longer than those in training.
Simulation
Enumeration
Iteration
Divide & Conquer
Model
M
L.
M
M
I.
M
Qwen2,5-7P Base
A
38.6
26.8
36.8
12.4
17.0
21.6
13.6
w/o Atomic State
82.6
73.6
68.2
69.0
77.2
61.2
86.2
71.0
w/o Lincar Transition
80.0
75.4
63.6
58.8
76,2
54.0
85.0
75.6
Memory Fetcher
90.2
88.0
64.2
73.8
67.6
92.4
88.2
TAIL
94,2
90.0
96.0
92.6
90.0
84.4
98.6
89.2
Recursion
DP
Greedy
Backtracking
Model
L.
I.
Qwen2.5-7B Base
19.4
3.0
11.2
13.0
5.4
3.4
7.2
4.0
Atomic State
52.2
32.0
77.4
61.0
39.0
16.0
75.8
61.4
w/o Lineur Transition
43.0
30.8
77.4
74.2
20.6
11.2
79.0
62.8
w/o Memory Fetcher
87.2
84.8
80.8
74.8
45.6
30.8
80.0
69.2
TAIL
99.6
87.0
90.2
71.8
91.8
62
83.6
76
Table I: Ablation study in core modules of TAIL. For each algorithm, we select representative task and evaluate pass@1 I accuracy (%) only on sequences that exceed the training length. Results show that the absence of any core module leads to sharp degradation in length generalization performance.
Bubble Sort and Any Substring reach near saturation in out-of-domain sequences. Moreover, TAIL also outperformed Qwen2.5-7B (base model), Qwen2.5-7B Instruct dine-tuning on a large amount of traditional non-TAlL-Coo data), and DeepSeek-RI 671B (representative open-source reasoning model) both label accuracy and length generalization abilities. Compared with reasoning models (i.e., DeepSeek-RI), we conclude that the huge leap in performance lies in their different under- lying mechanisms. Reasoning models often try many approaches but only scratch the surface and exploit shorteuts to bypass the structured reasoning process, instead of delving into a step-by-step approach (see more details in section 4.5). Regarding concerns about CoT length, experiments show that TAIL-CoT achieves significant performance leap with slightly less token usage compared to inference models, shown in Appendix
Comparison with Previous Works. Since pre- vious methods (Index Hint (Zhou et al. 2024 Lee et al. 2023 Shen et al.
Method
2023 Zhou et al.
Index Hint
$7.0
34.5
24.0
2023 Martinez al. 2023 McLeish et al. 2024 and Reversed Format (Zhou et al.) 2023 2024)) have proven effective limited problems such as large number operations, we choose Large Num- ber Addition of Simulation algorithm com-
Reversed Format
39.5
35.5
TATL (Ours)
97.0
92.5
86.5
Table Pass @ (%) on large-number addition, compared to previous data-driven approaches.
7

---

Published as a conference paper at ICLR 2026
Compare Numbers Simucction
Bubble Sort Simdotion
Word Flip Simuoorion
Large Number Addition Large Number Division Simulation
Any Subetring Recuriion
Simulation
Lãs sin sis eás
1át sia
são såz
Derangement
Populattion Growth
Dijkstro
Multi-Machine Schedule
Diophantine Equation
3os 150 Elt
7A1 R3G 455
Dose 150 011 721 S15 455
Sore
203
02)
7211
552 455
Sow :80 CL 721 252 435
Dose 230 EL 721 532 425
Done 150 R1c 721 252 455
Prime Search Enumerotoe
LCS
0-1 Knopsack
Levenshtein Distance
Binary Search Oiride & Corpan
Palindrome Combination
bookhoceng
159
781 882
721 852
Small (8)
Mediam (M)
Large (1)
Figure 6: Experiments on the proportion of training data of different lengths. We find that adding small amount of long data to most unsaturated tasks achieves fast performance gains.
mon task for comparison. Unlike prior work using fixed-length integers, our setup samples two operands with random lengths and optional decimal points, greatly expanding the state space. We followed the method in previous works to construct the same amount of training data (see details in Appendix[G] G and fine-tuned Qwen2.5-7B separately. As shown in Table 2 dex Hint and Reversed Format under-perfone TAIL by a large margin, highlighting the inadequacy of prior methods in addressing the challenges of length generalization in difficult tasks.
models trained with In-
Length Generalization Activation. In previous experiments, we only trained on S-range data to evaluate the generalization performance on longer sequences (M, I.). For tasks that haven't achieved saturation, we gradually introduce longer examples into the training set and analyze the optimal proportion for effective length generalization at minimal token cost. We explored five training con- figurations of <S, M, L> data while keeping the total number of samples constant: <1:0:0 0> (the previous method using only short sequences), <8: 1 1>, <7: 2: 3:2>, and :4:3:33 As shown in Figure [ for almost all tasks, even small addition of longer sequence data (i.e., at <8:1:1>) led to a rapid saturation in long-sequence reasoning, a phenomenon we refer to as length generalization activation. This observation is quite different from the "balanced length" conclusion of training data in previous works (Lee et al. 2023), indicating that TAIL has the potential to expand to much longer sequences at lower cost in the future. See more details in Appendix
4.4 ABLATION STUDY
Key module ablation. To assess the necessity of each core module, we ablate them individually and examine the performance drop. As shown in Table removing any module leads a notable de- cline in length generalization. Importantly, the impact varies by task: for example, Memory Fetcher critical for Population Growth baeratton-based,, but less so for Compare Numbers (simulation- based). We attribute this variation to differences in task structure. Tasks like Compare Numbers involve only local transitions and weak long-range dependencies, making Memory Fetcher less es- sential. In contrast, recursion- hhavy tasks benefit significantly from Linear Transition. Most tasks are also sensitive to scale, highlighting the general need for Atomic State decomposition. Overall, TAIL integrates all three modules synergistically to support diverse reasoning structures.
Thinking style ablation. To investigate the influence of different CoT styles on performance, we conducted fine-tuning experiments using both standard TAIL-CoT and TAIL-CoT-styled data. As illustrated in Figure [3] the results indicate that the choice of CoT style has minimal impact on the final performance. This suggests that for the length generalization task, the specific style of CoT
8

---

Published as a conference paper at ICLR 2026
is not critical factor. Instead, key modules of TAIL appears play more significant role in determining the overall performance.
Attention visualization of Memory Fetcher. As shown in Figure HI when Memory Fetcher is present, we observe strong and focused attention on the corresponding tokens (highlighted in se- lected Transformer layers). In contrast, the attention patterns become sparse and disorganized with- out Memory Fetcher, showing insufficient focus on the operands. See more details in Appendix H
4.5 COMPARISON WITH REASONING MODELS
It seems that both (Tsy-le)())))ledd and reasoning models (i.e., DeepSeek-R1 can improve perfor- mance by extending the CoT length, but underlying principles are quite different. Reasoning models aim expand the search space by prolonging the reasoning trajectory, encouraging broad method exploration instead of delving into the problem step by step (as shown in Section L.T). In contrast, TAIL focuses on controllable and structured reasoning chains that support stable generalization to longer sequences (as shown in Section L.2). See Appendix for more details.
Despite appearances suggesting that the linear expansion of small reasoning steps with explicit operands output make TAly-Co)((sttyled) longer than traditional CoTT, experimental results show that TAIL-COT can achieve significantly higher accuracy at comparable CoT length to DeepSeek- RI (as shown in Table J1 It demonstrates that TAIL's core modules are essential for promoting length generalization. See Appendix ! for more details.
To rigorously evaluate the difference, we also fine-tuned Qwen2.5-7B using an equal amount of correct data distilled by DeepSeek-RR. As shown in Table [I, RI-Distilled- Beailled--wwe2.5-78B exhibits lower accuracy and generalization ability. See Appendix K for more details.
RELATED WORK
Length Generalization. Large language models (LLMs) often struggle to process inputs longer than those seen during training, a limitation referred to as length generalization (Dubois et al.) 2019; Newman al. on model architecture enhancements and data-driven approaches to improve length generalization. However, architectural enhancements modify the components (e.g., forward mechanism (Fan al.
2020: Saparov & He 2022 Anil al. 2022). Previous works primarily focus
2024), attention mechanisms (Duan et al. (023), position encodings (Ruoss et al. 2023 Li et al.,
Kazemnejad et al.) 2023) and external queries (Giannouu et al.) 2023)) of Transformers for specific tasks and further adaptation to be applicable to prevailing LLMs. Data-driven approaches
2023
construct specific chain-of thouhhttht (CoT) structures for training, such as digit-order reversal (Zhou
2024: Lee et al.] [023] Shen et al.) 2023 Zhou et al.] [2023] Martínez et al. 2023 McLeish ctt al.
et al.
2024), sequence padding (Jelassi et al.) 2023), and index hints (Zhou et al.) 2023 2024),
which are task-specific and lack universality. Our TAIL focuses universal data-driven approaches, exploring a more general and effective CoT structure, and directly adopting mainstream LLMs (Bai
et al. 2023 Yang al. 2024 Touvron al. 2023 Liu al., 2024 Team 2023 Cai et al., 2024] Bai et al. 2025) for fine-tuning, without modifying any components of the pretrained model. Similar to ours, recent work (Hou et al. 2024) adopts a Turing-like step-by-step tape update, but it limited to specific positional encodings and data settings, and lacks verification across diverse tasks.
-fhouughtt Construction. Structured thinking demonstrably enhances the rea- soning capabilities of LLMs (Wei et al. 2022). Prior research explored various recognition heuris- ties within CoT paradigm, aiming imbue LLMs with more human- thoughts (Suzgun Kalai 2024 Zou et al. 2023 Zheng et al.] 2023). Concurrently. investigations into diverse structured data formats, including linear chains Wei et al.] 2022), hierarchical trees (Yao et al.) 2023a). in- terconnected graphs (Besta et al.) 2024), and dynamically adapting structures (Pandey et al. 2025), which enable LLMs to search easily and improve the complex problem-solving performance. In this paper, we introduce novel approach to synthesizing structured CoT data by drawing inspira- tion from a Turing machine, which can handle inputs of arbitrary length. This emulation offers a theoretically powerful advantage: varying complexity, and broad applicability to the entire domain of computable problems. Notably,
Structured
geggghhgeeerrllzablitty enabling the model to tackle problems of
the search capability and different graph structures (Besta al. 2024 Pandey et. 2025 Yao al.

---

Published as a conference paper at ICLR 2026
2023a) and their targeted tasks can all be taken as instances of a Turing machine solving computable problems.
Eliciting Chain-of- Thought. Efforts guide LLMs in generating CoT rationales with specifie, de- sired structures primarily involve prompting, supervised fine-tuning (SFT), and reinforcement learn- ing (RL). Prompting- g-asedd methods, encompassing static example-based approaches (Shao et al. (2023); (hou et al. (2022); Wang et al. (202)) and adaptive generation strategies Shum et al. (2023); Yao al. (2023b); Wang & Zhou (2024), guide the model through carefully crafied prompts. How- ever, these methods do not fundamentally enhance LLMs' inherent reasoning capabilities Wang al. (204g;; Rueda et al. (2025). SFT methods Yu et al. (2025); Trung et al. (2024); Kim et al.
(2023); ; Zhang et al. (2024) emphasize guiding single or multiple LLMs to synthesize training data with specific CoT structures, allowing the model learn and imitate the target reasoning behavior. RL-based methods Xiang et al. (2025); [Tang et al. (2025;; ) [Shen et al. (2025) allow the model to generate own CoT reasoning
rearoanni traces and optimize via reward function, where the resulting struc-
tures emerge during training and remain partly uncontrollable Xu 2025); Liu et al. (2025). Despite the progress SFT and RL, a persistent challenge remains to mitigate shortcuts and logical omis- sions during CoT reasoning, especially when relying model- senee--eeerated rollouts Lightman et al. (2023); Zhang et al. (2024); Wu et al. (2024); Yu et al.] (2025). To address this, we explore using Python programs synthesize SFT CoT data guarantee that the structure of CoT strietly mimics the execution process of a Turing Machine and reduce the possibility of learning shortcuts.
6 LIMITATIONS
Challenges in compositional generalization. Although TAIL improves the length generalization performance on each single task, the training of one task does not significantly improve the perfor- mance of other tasks under the same algorithm (as shown in Appendix Db. In future work, we will take individual tasks as the entry point, to explore more diverse data composition strategies, with the goal of achieving compositional generalization.
Gap with close-source models. In the experiment, we found that open-source models such as Qwen2.5 and DeepSeek-RI series did not perform well on our tasks, but several closed-source models (e.g., O4-mini) were able to solve these problems well. While we acknowledge the strong performance of closed-source models, our focus is on bridging this gap solely through supervised fine-tuning of open-source models with TAIL data.
Challenges in modeling non-deterministic algorithmic tasks. The scope of this work is limited to computable problems, and the core idea of simulating a Turing Machine is based on this assumption. However, for non-deterministic problems algorithm to solve it, which is a problem that TAIL cannot currently solve. We will actively explore ways to break through the boundaries of computable and fuzzy problems with structured CoT in future work.
open-ended reasoning,
cannot directly model an
7 CONCLUSION
We introduced Turing mAchine Imitation Learning (TAIL), a data-driven framework that instanti- ates three modules (i.e., Linear Transition, Atomic State, and Memory Fetcher) to align CoT structure with program execution and thereby promote universal and effective length generaliza- tion. Across algorithm classes and 18 tasks, fine-tuning TAIL-synthesized data yields strong length generalization on cattof--iitributiinn sequence lengths, with consistent gains on difficult cases and performance that surpasses DeepSeek-RL Unlike reasoning models that expand trajectories to explore many heuristics, TAIL. enforces a controllable and step-by-step execution, which supports stable extrapolation to inputs of arbitrary length.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank the anonymous reviewers and area chair for their helpful comments. This project is sup- ported by the Shanghai Artificial Intelligence Laboratory. The authors would like to thank Xun Zhao for her valuable suggestions and comments.
STATEMENT LLMs USAGE
In this paper, we used LLMs to aid and polish writing. We did not use LLMs for retrieval, discovery research ideation.
REFERENCES
Kartik Ahuja and Amin Mansouri. On provable length and compositional generalization. arXiv preprint arXhv:2402.04877 2024.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-38556, 2022.
Sanjeev Arora and Boaz Barak. Computational complexity: modern approach. Cambridge Uni- versity Press, 2009.
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng. Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint arXiv:2309.16609 2023.
Lei Bai, Zhongrui Cai, Maosong Cao, Weihan Cao, Chiyu Chen, Haojiong Chen, Kai Chen, Pengcheng Chen, Ying Chen, Yongkang Chen, et al. Intern-sl: scientific multimodal foun- dation model. arXiv preprint arXiv:2508. 15763, 2025.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gian- inazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17682-17690. 2024.
George S Boolos, John P Burgess, and Richard C Jeffrey. Computability and logic. Cambridge university press, 2002.
Zheng Cai, Maosong Cao, Haojiong Chen, Kai Chen, Keyu Chen, Xin Chen, Xun Chen, Zehui Chen, Zhi Chen, Pei Chu, et al. Internlm2 technical report. arXiv preprint 2XXv:2403.17299 2024.
Jack Copeland. The church-turing thesis. 1997.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg. Joel Veness, et al. Neural networks and the chomsky hierarchy. arXiv preprint urXiv:2207.02099 2022.
Shaoxiong Duan, Yining Shi, and Wei Xu. From interpolation to extrapolation: Complete length generalization for arithmetic transformers. arXiv preprint arXiv:2310.11984, 2023.
Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. Location attention for extrapolation to longer sequences. arXiv preprint arXiv: 1911:/3911037 2019.
Ying Fan, Yilun Du, Kannan Ramchandran, and Kangwook Lee. Looped transformers for length generalization. arXiv preprint vrXiv:2409.156417 2024.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. International Conference Machine Learning, pp. 11398-1 1442. PMLR, 2023.

---

Published as a conference paper at ICLR 2026
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501. 2025.
John Hoperoft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, lan- guages, and computation. Acm Sigact News, 32(1):600 66666556666666 2001.
Kaiying Hou, David Brandfonbrener, Sham Kakade, Samy Jelassi, and Eran Malach. Universal length generalization with turing programs. arXiv preprint ar arXiv:2407.053: 007.0330,, 2024.
Samy Jelassi, Stéphane d' A'scoll,, Carles Domingo-Eninn Enrich, Yuhuai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306. 15400, 2023.
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36:24892-249999 24928, 2023.
Seungone Kim, Se June Joo, Doyoung Kim, Joel Jang, Seonghyeon Ye, Jamin Shin, and Minjoon Sco. The cot collection: Improving zero-shot and few-shot learning of language models via chain-of-thought fine-tuning, arXiv preprint arXiv:2305.14044 2023.
Nayoung Lee, Kartik Sreenivasan, Jason D Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.0338/ 2023.
Shanda Li. Chong You, Guru Guruganesh. Joshua Ainslie, Santiago Ontanon, Manzil Zaheer, Sumit Sanghai, Yiming Yang. Sanjiv Kumar, and Srinadh Bhojanapalli. Functional interpolation for relative positions improves long context transformers. arXiv preprint arXiv:2310.04418, 2023.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402. /2875, 1, 2024.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference Learning Representations, 2023.
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437, 2024.
Huanyu Liu, Jia Li, Chang Yu, Taozhi Chen, Yihong Dong, Lecheng Wang, Hu XiaoLong, and Ge Li. Evocot: Overcoming the exploration bottleneck reinforcement learning. arXiv preprint wrXiv:2508.07800 2025.
Gonzalo Martínez, Lauren Watson, Pedro Reviriego, José Alberto Hernández, Mare Juarez, and Rik Sarkar. Combining generative artificial intelligence (ai) and the internet: Heading towards evolution or degradation? arXiv preprint arX2v:2303.01255, 2023.
Sean McLeish, Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer, Brian Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping, Avi Schwarzschild, et al. Transformers can do arithmetic with the right embeddings. Advances in Neural Information Processing Systems, 37: 108012-108041, 2024.
Benjamin Newman, John Hewitt, Percy Liang, and Christopher D Manning. The cos decision and length extrapolation. arXiv preprint arXiv:2010.07174, 2020.
Tushar Pandey, Ara Ghukasyan, Oktay Goktas, and Santosh Kumar Radha. Adaptive graph of thoughts: Test-time adaptive reasoming unifying chain, tree, and graph structures. arXiv preprint 0500:2550000007... 2025.
Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108, 12409, 2021.
12

---

Published as a conference paper at ICLR 2026
Alice Rueda, Mohammed S Hassan, Argyrios Perivolaris, Bazen G Teferra, Reza Samavi, Sirisha Rambhatla, Yuqi Wu, Yanbo Zhang. Bo Cao, Divya Sharma, et al. Understanding Ilm sci- entific reasoning through promptings and model'ss explanation the answers. arXiv preprint arXiv:2505.00 0142, 2025.
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Ben- nani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. arXiv preprint arXfv:2305.16843, 2023.
Abulhair Saparov and He He. Language models are greedy reasoners: systematic formal analysis of chain-of- chain-of-thought. arXiv preprint arXiv:2210.01244 2022.
Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang. Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, and He He. Transformers strug- gle learn search. arXiv preprint arXiv:2412.04703, 2024.
Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang, Nan Duan, and Weizhu Chen. Synthetic prompting: Generating chain-of-thought demonstrations for large language models. In Interna- tional Conference on Machine Learning, pp. 30706-30773 PMLR, 2023.
Maohao Shen, Guangtao Zeng, Zhenting Qi, Zhang-Wei Hong, Zhenfang Chen, Wei Lu, Gre- gory Wornell, Subhro Das, David Cox, and Chuang Gan. Satori: Reinforcement learning with chain-of-acttoo-thouul enhances Ilm reasoning via autoregressive search. arXiv preprint arXiv:2502.02508, 2025.
Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li, and Yi Zhang. Positional description matters for transformers arithmetic. arXiv preprint arXiv:2311.147: 2023.
Kensen Shi, Joey Hong, Manzil Zaheer, Pengcheng Yin, and Charles Sutton. Compositional gen- eralization and decomposition in neural program synthesis. arXiv preprint arXiv:2204.0375.. 2022.
KaShun Shum, Shizhe Diao, and Tong Zhang. Automatic prompt augmentation and selection with thutugt from labeled data. arXiv preprint arXiv:2302. 2023.
Sania Sinha, Tanawan Premsri, and Parisa Kordjamshidi. A survey compositional learning of ai models: Theoretical and experimetnal practices. arXiv preprint wwXiv:2406.08787, 2024.
Michael Sipser. Introduction to the theory of computation. ACM Sigact News, 27(1)227-29 1996.
Mirac Suzgun and Adam Tauman Kalai. Meta-prompting: Enhancing language models with task- agnostic scaffolding. arXiv preprint arXiv:2401. 2024.
Yunhao Tang, Sid Wang, and Rémi Munos. Learning to chain-of-thought with jensen's evidence lower bound. arXiv preprint arXiv:2503. 19618, 2025.
InternLM Team. Internlm: multilingual language model with progressively enhanced capabilities, 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov. Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.0922 000.0888, 2023.
Luong Trung, Xinbo Zhang, Zhanming Jie, Peng Sun, Xiaoran Jin, and Hang Li. Reft: Reasoning with reinforced fine-tuning. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 7601-7614, 2024.
Alan Mathison Turing et al. On computable numbers, with an application the entscheidungsproo- lem. J. of Math. 58(345-363):5. 1936.
Guoqing Wang, Zeyu Sun, Zhihao Gong, Sixiang Ye, Yizhou Chen, Yifan Zhao, Qingyuan Liang, and Dan Hao. Do advanced language models eliminate the need for prompt engineering in soft- ware engineering? arXiv preprint arXiv:241 1.22411.2220 1.02093, 2024.
13

---

Published as a conference paper at ICLR 2026
Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. slan-and-solve prompting: Improving zero-shot thtougt reasoning by large language models. arXiv preprint arXiv:2305.0409, 2023.
Ru Wang, Wei Huang, Selena Song. Haoyu Zhang, Yusuke Iwasawa, Yutaka Matsuo, and Jiax- ian Guo. Beyond in-distribution success: Scaling curves of cot granularity for language model generalization. arXiv preprint arX1v:2502.18273,200 2025.
Xuezhi Wang and Denny Zhou. Chain-of Chain-of-thouuht reasoning without prompting. arXiv preprint arXiv:2402. 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
Yexin Wu, Zhuosheng Zhang, and Hai Zhao. Mitigating misleading chain-of of-toughtt reasoning with selective filtering. arXiv preprint arXiv:2403. 2024.
Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, et al. Towards system reasoning in Ilms: Learning how to think with meta chain-of-thouge arXiv preprint arXiv:2501.04683 2025.
Xingcheng Xu. The policy cliff: A theoretical analysis of reward-poliss maps in large language models. arXiv preprint arXiv:2507.201500 2025.
An Yang. Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang. Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115 2024.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 16:11809-11820 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023b.
Bin Yu, Hang Yuan, Yuliang Wei, Bailing Wang. Weizhen Qi, and Kai Chen. Long-short chain- of-thought mixture supervised fine-tuning eliciting efficient reasoning in large language models. arXiv preprint arXiv:2505.03444 2025.
Xuan Zhang, Chao Du, Tianyu Pang. Qian Liu, Wei Gao, and Min Lin. Chain preference opti- mization: Improving chain-of-thought reasoning in llms. Advances in Neural Information Pro- cessing Systems, 37:333-356, 2024.
Huaixiu Steven Zheng, Swaroop Mishra, Xinyun Chen, Heng-Tze Cheng, Ed H Chi. Quoc V Lc, and Denny Zhou. Take a step back: Evoking reasoning via abstraction large language models. arXiv preprint arXiv:2310.00 17, 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625 2022.
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? a study length generalization. arXiv preprint arXiv:2310.1600 2023.
Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang. Rishabh Agarwal, and Denny Zhou. Trans- formers can achieve length generalization but not robustly. arXiv preprint arXiv:2402.09:: 2024.
Anni Zou, Zhuosheng Zhang, Hai Zhao, and Xiangru Tang. Generalizable chain chain-of-thoughh prompt- ing in mixed-tame task scenarios with large language models. arXiv preprint arXiv:2310.0660 2023.
14

---

Published as a conference paper at ICLR 2026
A FORMAL DEFINITION OF TURING MACHINE
Turing machine (Turigg et al. 1936 Hoperoft et al. 2001) can be formally defined as a seven- tuple:
M = (Q.E,T, 90, B,F),
(A1)
where is finite set of states, Σ is a non-empty finite input alphabet, I' denotes the of tape symbols, 8 is the transition function, symbol, and F denotes the final states.
Q refers to the initial state, B r E is the blank
B THE UNDERLYING MOTIVATION OF TAIL
TL;DR. To improve length generalization, TAIL resolves two fundamental limitations of tra- ditional CoT: shortcut reasoning and sparse long-distance attention. The Atomic State and Linear Transition address shortcut behavior at the micro and macro levels respectively, while the Memory Fetcher mitigates the sparse-attention issue.
B. SHORTCUT REASONING
Previous works Anil et al. (202); Saparov et al. (2024) show that when SFT'd on non-sequential COT, LLMs prefer take shortcuts during inference, and subsequently fail generalize to longer sequences. From micro perspective, shortcuts appear as overly large single-step reasoning, which means the model jumps substantial sub-results instead of reasoning step by step al. (2022); Saparov et al. (2024); From macro perspective, we also observe shortcut behavior as step-skipping and frequent switching between reasoning strategies (see Appendix L.T for CoT example of DeepSeek-RI).
Atomic State focuses on the micro level of each reasoning step. Guided by the RASP-L theory Zhou et al.]((210))) (2023), it produces wongth-generalizable steps of appropriate granularity (i.e., steps without internal loops).
Linear Transition focuses on the macro structure of connecting reasoning steps. It linearly unfolds the entire reasoning process step by step, and the tight logical linkage between Atomic States prevents step-skipping.
B.2 SPARSE LONG-DISTANCE ATTENTION
Previous work Wang et al. 2025)) shows that long-sequence reasoning leads to severe attention sparsity in later steps. As illustrated in FigureHH][lower part). traditional CoT attends to distant past states while performing the current reasoning action, resulting in sparse long-distance attention. Memory Fetcher decouples long-range attention construction from action execution: (1) First build long-range attention via simple copy operation, copying the relevant operands to the end of the sequence; (2) then performs the reasoning action.
As shown in Fig H1 (upper part), introducing Memory Fetcher significantly improves attention dis- tribution during reasoning actions. More attention focused on nearby relevant operands, improving single-step correctness, and thereby stabilizing long-sequee sequence reasoning.
15

---

Published as a conference paper at ICLR 2026
C TASK INTRODUCTION
The dataset consists of purely synthetic data, covering major algorithms and 18 tasks, as shown in Table CI Most tasks have approximately 100,000 training samples and 500 test samples (a small subset of tasks, which are more difficult to construct, retain 20,000 training samples and 200 test samples). All test queries have been verified and are included the training set.
Algorithm
Task Name
Task Content
Large Number Addition
#i + 22 (len((r) = n, len( = m)
Large Number Division
ii + #-22" (lem(ar) n, len( m)
Simulation
Bubble Sort
Bubble sort list of non-repeal numbers
Word Flip
Flip a sentence containing letters
Compare Numbers
Compare 1 and ag (len(z1) n, len(22) m)
Any Substring
Find all substrings of given string with length Derangement count for elements
Recursion
Derangement
Calculate total pairs after units, starting reproduction at æ-th unit (rr with initial y pairs, pairs produced per unit (g/ E N+)
Iteration
Population Growth
Dijkstra Multi-Machine Schedule
Shortest path values in graph with vertices Maximum benefit of n tasks on x queues (ir < n)
Greedy
Count Letters
Count letters in sentence of length
Enumeration
Diophantine Equation
integer solutions to æ1 x22 n (a, 2 0) All prime numbers in the interval [n, m] (n m)
Prime Search
0-1 Knapsack
Maximum benefit of n-element 0-1 knapsack
LCS
LCS of string X₁ and X₂ (len(X) = n1 (en( m)
Levenshtein Distance
Minimum operations converting string X, X;
Divide & Conquer
Binary Search
Binary search index in of increasing numbers
Backtracking
Permutation Combination
Number of combinations n-element list (step by step)
Dataset synthesised under instruction of TAIL, containing algorithms and 18 tasks, and represent length in a given range G E (S, (, LJ. indicates that a decimal point can be inserted any bit of the operand in specific task.
Table C1:
16

---

Published as a conference paper at ICLR 2026
D DATA SYNTHESIS AND COT EXAMPLES
Figure Di illustrates our data synthesis process. Specifically, for each task, we manually write Python program that can accept any input under that task. Because each task is assigned to algo- rithm, writing this program is very convenient and well-reasoned. We then add string concatenation statements the program link the reasoning process and form a complete Chain-of of-Thhthh (CoT), Since CoTs are generated as the program executes, they completely follow the program's ' execution process, which the core idea behind TAIL. As the synthetic CoTs strictly follows the running process of Python programs, they will exhaustively explore all possible solutions.
During this process, we can output two types of CoT: (1) TAIL-CoT contains only the TAIL core module, without any other verbiage and is more symbolic. (2) TATL-CoT-styled adds more style statements and more human-readable and interpretable, which adds more cohesive and planning statements.
In experiments, we trained TAIL--CoT-syyled on 18 tasks across all algorithm classes and verified its strong length generalization performance, shown in Figure We then verified that removing all explicit style statements (TAIL-CoT) did not lead to a performance degradation, as shown in Fig- ure demonstrating that length generalization is the core module of TAIL., not the style statement.
Take Binary Search task in Divide & Conquer algorithm as an example. Figure D2 is the query as direct input LLMs. For each task, constructed more than 20 query templates simulate the diversity. Figure D3 is an example of TAIL-CoT and Figure D4 is an example of TAIL-CoT-syyled.
Algorithim
CoT.py
Evaluation Set
Taak
8:500
Mt 500
500
resuttoo
Training Set
Manual Coding
Deduplication
TAIL_CoT withttttttyypt Style
Algorithm
Training
Algorithm
ZAIL Out with styde
100,000
Figure DI: Overall pipeline of data synthesis. We manually code task-specific python programs and use them massively generate chain-of-thought (CoT) data, either in plain form (TAIL-CoTT) After deduplication. we construct large-scale train-
or with stylistic variations (TAIL-CoT-stylee ing sets and balanced evaluation sets for subsequent experiments. (S Short sequence data, M Medium sequence data, L Long sequence data)
17

---

Published as a conference paper at ICLR 2026
Query: (Example 1)
Determine the index of S-5259$ the sorted list $[-5957, -5259, -4195, -2263, 1289, 3514, 3632, 4284, 5991, 6578, 7333JS with binary search (start from $OS). Other search methods are not allowed.
Query: (Example 2)
Find the index of $-52595 in the sorted list S-5957, -5259, -4195, -2263, 1289, 3514, 3632, 4284, 5991, 6578, 7333S, starting from $O$. For teaching purposes, you must use binary search and show the process step by step.
Query: (Example 3)
Provide the O-based binary search index for S-5259$ in $[-5957, -5259, -4195, 2263, 1289, 3514, 3632, 4284, 5991, 6578, 7333JS.
Figure D2: Example queries belonging to the Binary Search task (Divide & Conquer algorithm).
Minimalist reasoning chain of TAIL:
<Atomic State> {0,10)
<Memory Fetcher> [(sg = 5957), (s1 = -5259), (82 = -4195), (s3 -2263),
(s4 1289), (35 = 3514), (s6 3632), (37 4284), (s8 5991), (sg. 6578),
($10 = 7333)]
<Memory Fetcher> Find 5259
Mid = 8, = 3514 > Find
<Linear Transitions (0.10) (0.4)
<Atomic State> {0.4)
<Memory Fetcher> [(so = 5957), (s1 = -5259), (82 = -4195), ($3 = -2263),
(s4 = 1289)]
<Memory Fetcher> Find - 5259.
Mid 2, 82 4195 Find
<Linear Transition (0.4) + {0.1}
<Atomic State> {0.1}
<Memory Fetcher> [(8g = 5957), (81 -255))
<Memory Fetcher> Find - 5259
Mid = 0, 8p = -595 < Find
<Linear Transition: [1.1} {1.1}.
<Atomic State> {1,1]
<Memory Fetcher> [(s] = 5259)]
<Memory Fetcher> Find -5259
Mid = 1,81 5259 Find
<Linear Transition> (1.1)
Final Answer: Index
I
Figure D3: Example of TAIL-CoT, with only core modules aligned with Turing machines. <TAG>
for demonstration purposes only and does not exist in the actual CoT content.
18

---

Published as a conference paper at ICLR 2026
User-friendly CoT of TAIL:
Let's perform the binary search step by step.
1. The currently processed interval is [-5957, -5259, -4195, -2263, 1289, 3514, 3632, 4284, 5991, 6578, 7333].
First we map each number to its index:
OOiginal index 0: -5957
Original index I: 5259
Original index 2: -495
Original index 3: -2263
Original index 4: 1289
Original index 5: 3514
Original index 6: 3632
Original index 7: 4284
Original index 8: 5991
Original index 9: 6578
Original index 10: 7333
The left boundary index 0 and the right boundary index is 10.
Median index [00 + 10]/2] = 5, the median number is 3514.
The target number 5259 is less than the median number 3514, continue these operations on the left subinterval [-5957, -2259, -4195, -2263, 1289].
2. The currently processed interval is [-5957, -5259, - 4195, 2263, 1289].
First we map each number to its index:
Original index 0: -5957
Original index
-2259
Original index 2: -4195
OOiginal index 3: -2263
Original index 4: 1289
The left boundary index 0 and the right boundary index is 4.
Median index |0 + 4] 2, the median number is -4195.
The target number -5259 is less than the median number - 4195, continue these opera- tions the left subinterval 5957, 5259).
3. The currently processed interval [-5577,- 5255)..
First we map each number to its index:
Original index 0: -5957
Original index 1: -5259
The left boundary index 0 and the right boundary index is 1.
Median index [0 + 1J 0, the median number is -595..
The target number 55259 greater than the median number 5957, continue these operations the right subinterval 52599..
4. The currently processed interval is (-5259). First we map each number to its index:
Original index 1: -5259
The left boundary index is 1 and the right boundary index is 1.
Median index |1 + 1] 1, the median number -5259.
The target number -5259 is equal to the median number 5225,, the search ends.
The target number 5225 is located at index
Figure D4: Example of TAIL--ooT-syyled, improving human readability on top of core modules
19

---

Published as a conference paper at ICLR 2026
E DATA PROPORTION STUDY
For each task, we divided the data into three length ranges (S, M. and L), and synthesized 100,000 training samples for each range. In studying length generalization, we trained solely on the S-range data without including any M- or L-range samples (i.e., the data proportion is < 0>), and then evaluated on all three ranges to assess the ability to generalize to longer sequences. In this section, for tasks that haven't t reached saturation, S-range training data and investigate the data proportion that achieves saturation performance with the minimal number of training tokens. Specifically, keep the total number of training samples fixed, while varying the proportions of the three length ranges as <1 : O: 0>, <8:1: 1>, <7 2212;1>, <5: 3: 2>, and <6 3:3>.
progressively incorporate longer sequences into the
As shown in Figure 66 we found that using TAIL-CoT, performance saturation can be quickly achieved by simply adding a small amount of long data large amount of short data. Guided by this observation, TAIL-CoT can leverage imbalanced sequence length proportions to reduce training costs. We call this length generalization activation.
F
TASK LENGTH RANGE
Algorithm
Task Name
Small (S)
Medium (M)
Long (I.
Large Number Addition
[10, 30]
[31, 40
[41, 50]
Large Number Division
[2,5]
[6,
[11, 20]
Simulation
Bubble Sort
[2.4]
[5, 6]
[7. 8]
Word Flip
[10, 20]
[21, 50
[51, 100)
Compare Numbers
[5 10
11, 20
[21,
Any Substring
[3,
[6.9] 9]
[10, 14]
Recursion
Derangement
[3,30
[31, 60
[61, 100
Iteration
Population Growth
[1, 10
[11,
[26, 50]
Dijkstra
[.5
(G. 10]
[11, 20
Greedy
Macti-Machine Schedule
55. 10
11, 20
[21, 50)
Count Letters
6]
7. 10
[11, 20]
Enumeration
Diophantine Equation
[10, 50]
[51, 100)
1101, 200)
Prime Search
55. 100)
101, 200]
200,
0-1 Knapsuck
[2,
[4.
[6, 8
DP
LCS Levenshtein Distance
[2. 6]
[7.9]
[10, 12]
[2,
[5. 7]
[8.
Divide & Conquer
Binary Search
[6, 20'
[21, 40
[41, 70]
Backrmcking
Palindrome Combination
[2,
[5.
[7.8]
Table Fl: The setting of length ranges across all tasks. See Table C1 for the definitions of length.
G BASELINE DATA CONSTRUCTION
This section describes the data construction methods for the baseline methods (i.e., Index Hint and Reversed Format). The experimental task was Large Number Addition (Simulation algorithm), and unlike the experiments in previous works, in this paper contain random number of decimals. We followed data construction methods accordingly based on the principles of these baselines.
G.1
INDEX HINT
The Index Zhou al. 2023: 2024) method refers to adding hint of indexes to the correspond-
ing numeric or logical bits of two operands for positioning in arithmetic or parity operations. This method has been extensively proven to be effective in both tasks. To compare the performance of
20

---

Published as a conference paper at ICLR 2026
Index Hint and TAIL, refer to the method (Zhou al. 2024) that displays the indexes locate as follows:
3a6b1c+5a776c-99333
However, the above approach is for the case where two operands have the number of digits without decimals, so we make following improvements for non-fixed-length cases with decimals:
(b) (-c) (b) =1 -1(-)))
(-a). (a) (b)
(b)
G.2 REVERSED FORMAT
Reversed Format Zhou et al. 2024 Lee et al. 2023 Shen et al.) 2023 Zhou et al. 2023 Martínez
ctt al. 2023; McLeish et al. 2024) refers to reversing each of the two operands in arithmetic opera- tions such addition. The rationale for this method is that the addition is usually performed from the first digit, Le., from right to left. However, the order of next token prediction (NTP) large language models (LLMs) is from left right, which leads overly complex search paths during model learning and affects the length generalization performance. This method also a widely proven effective length generalization facilitation method, constructed follows:
(Origin) 123. 45+67 19-191.1..
(Reversed Format) 54. 321+ 98 76.4199399
H DETAILS ABOUT MEMORY FETCHER
This section presents the details of the Memory Fetcher in TAIL. As shown in Figure 3 the Memory Fetcher designed decouple long-range attention from the reasoning action. It first retrieves all relevant operands from the long sequence to the end, and then performs more precise reasoning through local attention.
We visualize this local attention and compare it with the traditional CoT. As shown in Figure H1 at- tention across layers tends to focus on the end of the sequence. With the introduction of the Memory Fetcher, operands attend to reasoning actions (via local attention) and the retrieval of distant operands (via long-range attention), which results in significant sparsification of long-range attention.
captured more accurately. In contrast, traditional CoT must simultancously
16
15
Rotum book 10115
Writee
16
Retum back to Stettgge
So on get maddmmm calue of backppeck in S1g10o111
Sax0g3 wids
1115
Figure H1: Ablation study attention visualization of Memory Fetcher.
21

---

Published as a conference paper at ICLR 2026
I COMBINATORIAL GENERALIZATION RESULTS
For tasks that belong to the same algorithmic idea, test whether they have combinatorial general- ization (i.e. generalization between tasks). As shown in Figure I1] the combinatorial generalization property is not significant, which is the target of our future works.
DP (0-1 Kaapsack)
DP
DP Distance)
100
100
100
Performance (%)
90
80
80
40
40
20
20
20
Creedy
Greedy
(Multi- Mhulit--Mcchieee Schedule)
Performance mance (%)
80
80
60
60
40
20
20
Pretmin
SFT (Rest)
SET (Task)
SFT (AII)
In-domain
Figure II: Generalization performance between tasks within a single algorithm (e.g., DP and Greedy). Pretrain represents Qwen 2.5-7B as the basis for subsequent SFT. For each task, SFT(Rest) indicates training using data from other tasks within the algorithm, SFT(Task) indi- cates training using data from this task, and SFT(AII) indicates training using data from all tasks within this algorithm. indicates that this piece of data has a label accuracy of less than 5%.
J COT LENGTH COMPARISON
Since TAIL simulates the implementation of Turing machine, where all algorithm steps panded and explicit recall of operands added, it may lead to a significant increase CoT. There- fore, taking Compare Number task of Simulation algorithm as example, we compared the average lengths of TAIL-CoT and DeepSeek-R CoT.
As shown in Table J1] despite the increased length, the average number of tokens of TAIL remains on par with that of DeepSeek-RI. With such acceptable length, it significantly outperforms the 671B reasoning model with only 7B parameters, which demonstrates the efficiency of TAIL.
Metric
TAIL-CoT (7B, Finetuned Qwen2.5
DeepSeek-RI (671B)
avg. Tokens
1455
1461
Label Accuracy
90.0
51.2
Table J1: Comparison between TAIL-CoT (7B, Finetuned Qwen2.5 7B) and DeepSeek-RI (671B)
on average token usage and label accuracy. The average number of tokens retains the integer part.
K DEEPSEEK-R1- -DISTILL TRAINING RESULTS
For fairer comparison, we fine-tuned Qwen2.5-7B using the same amount of PrepSeek-RI-Diisee data and TAIL-CoT. As shown in Table KI although DeepSeek-R1 i's CoT can significantly improve in-domain performance, the improvement is not as significant as TAIL-CoT, and the performance shows sharp decline in longer sequences. Since DeepSeek-Ri R1 has low accuracy rate some tasks, distilling the same amount of training data requires a large number of tokens, so this experi- ment not conducted on large scale.
22

---

Published as a conference paper at ICLR 2026
Setting
TAIL (7B)
RI-Distill R1-Distil-- Qween2.-7nnn
S (In Domain)
98.0
72.2
94.2
67.2
L
90.0
61.8
Table K1: Performance comparison between TAIL. (7B) and S11-Distlll-ween2.55 across different sequence lengths. (S Short sequence data, M Medium sequence data, L Long sequence data)
L COT STRUTURE COMPARISON OF DEEPSEEK-RI AND TAIL
Take a Word Flip task of Simulation algorithm as an example.
Zero-shot Query: Provide the flipped string based on "As he measured, he said, Every Ollivander wand has a core powerful magical substance". Reverse the entire string character by character (including spaces).
L.1 RESPONSE OF DEEPSEEK-RY
<think>
We are to flip the string based the given sentence: "As he measured, he said, Every 0llivander wand has core powerful magical substance"
The instruction is to "flip" the string, let me reverse the entire string
Original: "As measured, he said, Every Ollivander wand has of powerful magical substance" We can reverse it character by character
Steps:
1. Take the string,
2. Reverse the order of the characters. Example: "hello" becomes "olleh"
Let's do it:
Original: 'A' 's' 'h 'e',
nt ee' la 'ss 'n' ee' d' r ' 'v' 'e' 'r' 'y' '0'0
'e"
a v' a' n'
b
a'
'c' of
oo
p
"rr 'f' 'u', '1' " ml 'g' li d al (1' "t''' 'n',,
Reverse:
Start from the last character and go to the first.
But note: we can use a simple methed in programming to reverse the string
do it manually, I'll write the reversed string. Let me break the original string into parts then reverse the whole: Original: "As he measured, he said, Every Ollivander wand has a core of powerful magical substance"
However, since
We can write the reversed string as:
Last character: 'e' Then: 'c', 'n', a 't', (s' "b 'u', 's aa' 'e', 'i', 'g', 'a', 'm'
lu' " 'r' re'
of 'p', s'', ta', "
'a',
"1, 'o',
'd', 'n', la', (w 'o' d
'a',
'r', e 'd 'n'
(a' ly' 'i', "1' "1 '0',
ly' 'r' re' "y' "B
d', 'i', la', (9'
'g', 1
'r' tu'
aa' 's', 'e', mm'
'e', 'b' 's', /
But wait, let's do it step by step:
lot splitting achieve the number of digits omitted.)
Wait, I think I made a mistake. Let me write the entire string without spaces and then add the spaces and punctuation:
Actually, it's easier just reverse the string whole.
23

---

Published as a conference paper at ICLR 2026
We write the string s "As he measured, he said, Every ollivander wand has core a powerful magical substance" Reversed string s[::-1] in Pythen.
But manually:
Start from the end: 'e' (from substance) 'e' 'n' far 't' 's' bb fut 's'
' (space before substance?
but actually the last word is "substance", and before that is "magical", so there's a space between them)
(A lot repeated veritication attempts emitted.)
Actually, the string is: a powerful magical substance So the order in the original is: 'a', space, ''''''''" ''','r', 'f', 'r','", ,'', ',' ''','', space, 's', 's','u',' '''',''', 't''''
space, 'm' '''c'''e' Therefore, when zeversed, we start from the last character the last word and go backwards: Start: 'e' Then: 'n', 't',, s','b' 'b', "u','s" -> then space -> then the word "magical" reversed: '1 ''','' ''m, -> then space -> then the word "powerful" '''', "o'''''''' -> then space -> then 'a'
''''''c' ''', ''',,' '''''''
reversed: '1','u' "f' then space then the word "of" becones 'f','o"?
(A lot of attempts at different reversal methods critted.)
Astually, the comma already handled? Wait, 1et reconstruct: The original string: "As he measured, he said, Every Ollivander wand has a core of a powerful nagical substance" Breaking down: "As" -> ['A',' s'1 space -> [' (] "he" -> ['h','et space -> [' '1
We
the entire list. The last character is 'e' (from substance , then the one before 'c', then 'n', then 'a', then 't', then
Therefore, the flipped string is: "ecnatsbus lacigam lufrewop & fo croc sA" But note: the
dnaw rednavillo yrevž dias eh derusaem original had a space at the end? No, the last word "substance" without any trailing space. similarly, the first word "As" has no leading space. So the reversed string should not have leading space ? it ends with "sA", which ia correct. Final anawer: "scnatsbus sah dnaw rednavi 110 yrevE. dias
lacigam lufrewop fo derusaem. SA"
</think>
The original string is: "As he measured, said, Every Ollivander wand core of a powerful magical substance"
Reversing the entire string character by character (including spaces, punctuation, and maintaining case) results in: ** **""enatsbus lacigam lufrewop fo eroc a sah dnaw rednavill0 yrevE dias en derusaem e h s****
### ixplanation:
last character the original string ("e" from "substance") becomes the first character of the flipped string, and so on.
reversal done on per-character basis,
Spaces, commas, and capitalization are preserved they appear in the original.
This not word reversal (where words are reversed but characters within words stay in order); it is full charactor-level reversal.
The final output is "ecnatsbus lacigam lufrewop a fo sah dnaw rednavillO yrevE ,dias eh derusaem e sA". The model tried many methods, but did not actually perform the flipping opera- tion step by step, and directly output incorrect result the end of the inference.
24

---

Published as a conference paper at ICLR 2026
L.2 TAIL-CoT-styled
<think>
Decompose the string bit by bit (starting from $19)
Index $19: 'A'
Index $28: 's'
Index $38:
Index $48: 'h'
Index $58: 'e'
Index $69:
Index $79: 'm'
Index $88: 'e'
Index $9$: 'a'
Index $10$:
(Omitted and will be expanded in actual reasoning.)
Index $809:
Index $81$: 's'
Index $82$: 'u'
Index $83$: 'b'
Index $849: "g'
Index $855: 't'
Index $868: 'a'
Index $875: 'n'
Index $889: 'c'
Index $899: 'e'
We find that 'As he measured, he said, Every Ollivander wand has a core of a powerful magical substance' has $898 words, indexed from $1s to $895.
The original string is the concatenation the letters with indices from $1$ to $89$. If you reverse it, the result is the reverse concatenation of the indices, that is, from $89$ to $1$.
Let's perform the reverse stitching step by step: Index $89$: 'e', intermediate result is 'e'
Index $885: 'c', intermediate result is 'ec'
Index $875: 'n', intermediate result is 'een'
Index $869: 'a', intermediate result is 'ecna'
Index $855: 't', intermediate result is 'ecnat'
Index $849: 's', intermediate result is 'ecnats'
Index $835: "b', intermediate result is 'ecnatsb'
Index $829: 'u', intermediate result is 'ecnatsbu'
Index $815: 's', intermodiate result 'ecnatsbus'
Index $808:
intermediate result is recnatsbus
(Omitted and will be expanded in actual reasoning.)
Index $10$: 's', intermediate result 'ecnatsbus Lacigan lufrewop
to eroc a sah dnaw rednavillo yrevE dias eh derus'
Index $98: 'a', intermediate result is 'ecnatsbus lacigam lufrewop
fo eroc sah dnaw rednavil10 yrevE dias eh derusa' Index $89: te', intermediate result fo eroc a sah dnaw rednavil10 yrevE dias eh derusae' seseeda fo eroc a sah dnaw rednavil10 yrevE dias eh derusaem' intermediate result
'ecnatsbus lacigam lufrewop
Index $78: 'm', intermediate result is 'ecnatsbus lacigam lufrewop
Index $68:
'ecnatsbus lacigam lufrewop
Io eroc a sah dnaw rednavillo yrevE dias eh ,erussam serpiiitteerreutteeeeeeeeeeeeeee Index $5$: 'e', intermediate result is 'ecnatsbus lacigan lufrewop
fo eroc a sah dnaw rednavill0 yrevE dias et ,erussam e' Index $48: "h', intermediate result is 'ecnatsbus 1acigam 1ufrewop fo eroc sah dnaw rednavi110 yrevE. dias eh derusaam sh'
25

---

Published as a conference paper at ICLR 2026
Index $33: r intermediate result is 'ecnatsbus lacigan lufrewop fo eroc a sah dnaw redhavillo yrevE dias eh derusaem Index $25: 's', intermediate result is 'ecnatsbus lacigam lufrewop Io eroc a sah dnaw rednavill0 yrevE dias eh derusacm eh s'
-Index $19: 'A', intermediate result is "ecnatsbus lacigam lufrewop fo eroc sah dnaw rednavil10 yrevž dias eh derusaem sA
</think>
The final result is 'ecnatsbus lacigan Lufrewop to eroc dnax rednavil10 yrevE dias derussam eh SA'.
26


Reviews:
[{"review_id": "TZwoM5xiDz", "reviewer": "Reviewer_P9RF", "summary": "This paper proposes Turing Machine Imitation Learning (TAIL), which synthesizes CoT data that imitates the execution process of a Turing Machine to enhance the length generalization of Transformer-based LLMs. The authors claim that fine-tuning a model on synthetic data generated via TAIL improves its length generalization capability. They validate this claim on Qwen2.5-7B across various tasks and show that the fine-tuned model consistently outperforms the original one.", "questions": "See Weaknesses.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of imitating Turing Machine execution is interesting and conceptually appealing.\n\n2. TAIL is orthogonal to other approaches such as Index Hint, making it easily combinable with them.", "weaknesses": "1. The paper lacks sufficient elaboration and analysis on why TAIL improves length generalization.\n\n2. The experimental design does not convincingly demonstrate TAIL’s effectiveness. Specifically, the comparison between the original Qwen2.5-7B and the model fine-tuned on task-specific data is not fair. Moreover, the paper does not include comparisons with other prompt-engineering methods, such as Program-of-Thought, to justify the claimed advantages of TAIL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Rqy8s4oiZl", "reviewer": "Reviewer_RUTK", "summary": "This paper focuses on a key limitation of current large language models: length generalization, meaning their ability to maintain correct reasoning on inputs far longer than those encountered during training. To address this, the authors propose TAIL (Turing mAchine Imitation Learning), a training approach let the mode mimic the step-by-step execution of a Turing machine. Experiments show that using only this synthetic data, TAIL can improve model’s length generalization ability and task performance.", "questions": "1. How does the proposed method extend to more realistic reasoning domains, such as GSM8K, MATH, or BIG-bench reasoning tasks? It would be crucial for verifying the real effectiveness of proposed method.\n2. The work argues that TAIL improves computational reasoning, but many of the evaluated tasks could be directly solved LLM's tool use. Why just let LLM to write the code and execute the program for these type of tasks with deep computation depths? What advantages does TAIL provide over the agentic method?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-motivated, studying  length generalization – an important problem of LLM\n2. The proposed method only require synthetic data, which makes it easier to extend to more tasks. \n3. The paper performed comprehensive experiments and achieved improvements across diverse benchmarks, demonstrating strong generality and robustness.", "weaknesses": "1. Limited practical significance: The benchmarks are largely rely on deterministic symbolic computation. The so-called Chain-of-Thought effectively becomes a **Chain of Computations**, simply executing predefined procedural steps rather than engaging in genuine high-level reasoning. As a result, the improvements may reflect better simulation of algorithmic traces, rather than any substantive enhancement in “reasoning ability.”\n2. Limited Transferability to real-world reasoning scenarios. The work does not evaluate performance on realistic tasks that require conceptual decision-making or deeper inference, such as multi-hop mathematical reasoning or logic problems. So it is unclear how TAIL can contribute to practical reasoning challenges.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "BssUNjDR9r", "reviewer": "Reviewer_8yiH", "summary": "This paper proposes TAIL, a data-driven framework for improving length generalization in LLMs. By synthesizing cot data that mimics the execution of a Turing machine, TAIL improves the performance of LLM's ability of length generalization. In general, TAIL enforces three structural properties, linear transition, atomic state and memory fetcher.\n\nThe method is evaluated on a challenging synthetic dataset spanning 8 algorithmic classes and 18 tasks. Results show that TAIL significantly enhances length generalization in Qwen2.5-7B, outperforming prior task-specific methods and even larger models like DeepSeek-R1.", "questions": "1. Can the authors provide more baselines such as SFT with simple CoT or SFT without CoT?\n2. It seems that simulating Turing execution with atomic states and memory fetching substantially increases reasoning length. Is it true? If so, will it be limited by the finite context, causing TAIL to actually fail in solving very long problems?\n3. What are the additional contributions and innovations of TAIL compared to the two works mentioned above?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "1. The Turing machine alignment provides a principled approach to structured reasoning, systematically addressing length generalization through linearized execution and explicit memory management.\n2. Evaluation across 8 algorithm classes and 18 tasks demonstrates impressive universality beyond simple tasks commonly studied.", "weaknesses": "1. Incomplete baselines. The paper doesn't compare against standard CoT fine-tuning, making it unclear whether gains come from Turing imitation or simply SFT. Comparisons are limited to un-trained base models.\n\n2. The approach requires manually writing Python code for each task to generate TAIL-formatted CoT data, creating significant engineering overhead. This limits real-world adoption where users need automated solutions for new tasks.\n\n3. The paper overlooks important connections to relevant literature. Two papers \"Show Your Work: Scratchpads for Intermediate Computation with Language Models\", \"Beyond Single-Task: Robust Multi-Task Length Generalization for LLMs\" deserves explicit discussion. The latter explores similar concepts of program-based CoT generation for length generalization but extends to multi-task transfer learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "QGk60dkJG1", "reviewer": "Reviewer_txZ2", "summary": "This paper presents TAIL, which is a specific chain-of-thought format inspired by Turing machines that facilitates length generalization. It synthesizes large datasets for a set of traditional algorithms and then finetunes Qwen models on that data and illustrates length generalization exceeding standard reasoning models (R1).", "questions": "none", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Compared to prior work on length generalization it considers a more varied set of tasks and shows strong results.\n2. Most prior work on length generalization focuses on small models trained from scratch on simple tasks, this instead finetunes large models in a way that is perhaps more interesting or has more practical implications.\n3. The specific method for generating varied synthetic data in the Turing machine style is clever.\n4. The ablations of the chain-of-thought format are rigorous and useful", "weaknesses": "1. The paper over-claims the novelty of the idea of using a Turing-machine formulated CoT for length generalization. This is the central point of Hou et al. which is barely cited in the related work section. This paper does do much larger scale experiments and does study some intricacies of how to exactly define the CoT when finetuning larger models, but the core idea is exactly the same as Hou et al. and this should be made more clear in the paper.\n2. Some of the claims of universality should also be more careful. While it is true that hypothetically any algorithmic task can be formulated as a TAIL-style cot, this still requires someone to hand-design the linearization, state, and memory fetcher components of the CoT used for the SFT data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)