当前位置：首页 > ai >正文

LLM论文笔记 28: Universal length generalization with Turing Programs

ai 2025/5/14 12:16:17

Arxiv日期：2024.10.4
机构：Harvard University

Turing Programs 的提出
- 提出 Turing Programs，一种基于图灵机计算步骤的通用 CoT 策略。通过将算法任务分解为逐步的“磁带更新”（类似图灵机的读写操作），允许模型通过简单的文本复制与局部修改完成复杂计算
- 通用性：适用于任何算法任务（加法、乘法、SGD），不依赖任务特定的数据格式优化
长度泛化的实验突破
- 加法：50位数训练可泛化至 100 位数加法（准确率 98%），优于传统 scratchpad 方法
- 乘法：首次展示对 n×1 和 n×3位数乘法的长度泛化（50→100 位，准确率 97%）
- SGD 算法：在 50 个训练样本上训练的模型可泛化至 80 个样本（准确率 95%）
- 随机图灵机模拟：模型在未见过的更长输入（50→100+ token）上能预测图灵机的下一步状态，表明其对任意算法任务的泛化潜力
位置编码的关键作用
- Hard-ALiBi 位置编码（结合局部硬注意力与全局无位置头）显著提升长度泛化能力，优于 ALiBi、RoPE 等传统编码
- 实验表明，位置编码与数据格式的协同设计是成功的关键
指出传统 scratchpad 方法在长度泛化上的局限性，强调迭代式局部修改的重要性（而非单纯分步输出）

主要方法：Turing Programs 提出，将CoT过程拟合为图灵机的操作

磁带（Tape）：模拟图灵机的存储结构，每一步的中间状态以文本形式表示。例如，在加法任务中，磁带可能包含当前处理的数字位、进位值等信息。
局部修改：每一步仅对磁带的局部内容进行修改（如更新某一位的数字或进位），而非完全重写。例如，图2中的加法步骤通过逐步移除操作数的最后一位并更新中间结果。
显式状态标记：使用特殊符号（如 ^ 表示当前处理位置，a, b, c 表示中间变量）标记状态，确保模型明确跟踪计算进展。