The Imitation Game: Turing Machine Imitator is Length Generalizable
  Reasoner
Authors: name: Zhouqi Hua, name: Wenwei Zhang, name: Chengqi Lyu, name: Yuzhe Gu, name: Songyang Gao, name: Kuikun Liu, name: Kai Chen
Organization: Intern Large Models

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.