模仿游戏：图灵机模仿器是长度可泛化的推理器

长度泛化，即解决比训练中观察到的序列更长的问题的能力，是基于 Transformer 的大型语言模型（LLM）面临的核心挑战。尽管现有研究主要集中于针对算术运算和符号操作任务的数据驱动方法，但这些方法往往是任务特定的，且整体性能有限。为了寻求更通用的解决方案，本文关注一类更广泛的可计算推理问题，即可由算法解决，因此也可由图灵机解决的问题。基于此视角，本文提出了图灵机模仿学习（TAIL）来提高大型语言模型的长度泛化能力。TAIL 通过计算机程序合成模仿图灵机执行过程的思维链（CoT）数据，将推理步骤线性扩展为原子状态，以缓解捷径学习，并采用显式内存提取机制来降低基本操作中动态和远程数据访问的难度。为了验证 TAIL 的可靠性和普适性，我们构建了一个包含 8 类算法和 18 个任务的具有挑战性的合成数据集。在没有额外复杂功能的情况下，TAIL 仅使用合成数据就显著提升了 Qwen2.5-7B 在各种任务上的长度泛化能力和性能，超越了以往的方法和 DeepSeek-R1。实验结果表明，图灵机中的关键概念而非思维方式，对于 TAIL 实现长度泛化是不可或缺的，通过这些概念，模型在其注意力层中表现出与图灵机特性一致的读写行为。这项工作为未来从合成数据中学习大型语言模型推理能力的研究提供了一个有前景的方向。