The Imitation Game: Turing Machine Imitator is Length Generalizable
  Reasoner
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 (LLM). Although existing studies have predominantly
focused on data-driven approaches for arithmetic operations and symbolic
manipulation tasks, these approaches tend to be task-specific with limited
overall performance. 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. From this
perspective, this paper proposes Turing MAchine Imitation Learning (TAIL) to
improve the length generalization ability of LLMs. TAIL synthesizes
chain-of-thoughts (CoT) data that imitate the execution process of a Turing
Machine by computer programs, which linearly expands the reasoning steps into
atomic states to alleviate shortcut learning and explicit memory fetch
mechanism to reduce the difficulties of dynamic and long-range data access in
elementary operations. To validate the reliability and universality 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 on various
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 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.
6879b01621b37e676c8e40a8
Zhouqi Hua
claimed_verified
2025-07-18T07:49:38.507Z
66214b4e4991d64ad0e28675
/avatars/2574928aab7e45bc581c567d556a4cfd.svg
Zhouqi Hua
user
ZhouqiHUA
6879b01621b37e676c8e40a9
Wenwei Zhang
claimed_verified
2025-08-22T07:25:17.608Z
64e8505321540e1da3226b54
/avatars/18958b8406d1ce492b54c1c839f18c54.svg
Wenwei Zhang
user
ZwwWayne
6879b01621b37e676c8e40aa
Chengqi Lyu
6879b01621b37e676c8e40ab
Yuzhe Gu
claimed_verified
2025-07-18T07:49:36.203Z
6601196cc91ba4c08ad6e270
https://cdn-avatars.huggingface.co/v1/production/uploads/6601196cc91ba4c08ad6e270/X2YPNzUOQXBz5Gv-xR9LW.jpeg
yuzhe gu
user
vanilla1116
6879b01621b37e676c8e40ac
Songyang Gao
6879b01621b37e676c8e40ad
Kuikun Liu
claimed_verified
2025-07-23T08:37:21.187Z
63fd691794cc8f815d50c112
/avatars/87305d1cbfcc717e910ccdfaf0568f80.svg
liu
user
Harold-lkk
6879b01621b37e676c8e40ae
Kai Chen
The Imitation Game: Turing Machine Imitator is Length Generalizable
  Reasoner
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 (LLM). Although existing studies have predominantly
focused on data-driven approaches for arithmetic operations and symbolic
manipulation tasks, these approaches tend to be task-specific with limited
overall performance. 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. From this
perspective, this paper proposes Turing MAchine Imitation Learning (TAIL) to
improve the length generalization ability of LLMs. TAIL synthesizes
chain-of-thoughts (CoT) data that imitate the execution process of a Turing
Machine by computer programs, which linearly expands the reasoning steps into
atomic states to alleviate shortcut learning and explicit memory fetch
mechanism to reduce the difficulties of dynamic and long-range data access in
elementary operations. To validate the reliability and universality 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 on various
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 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.
TAIL, a method that imitates Turing Machine execution processes, enhances the length generalization and performance of LLMs by synthesizing chain-of-thought data and reducing shortcut learning.
Transformer-based large language models length generalization Turing MAchine Imitation Learning (TAIL) chain-of-thoughts (CoT) Turing Machine synthetic dataset Qwen2.5-7B read-and-write behaviors attention layers