- Arxiv日期：2024.10.4
- 機構：Harvard University
關鍵詞
-
圖靈機
-
CoT
-
長度泛化
核心結論
-
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表示中間變量）標記狀態，確保模型明確跟蹤計算進展。
仍然具有以下問題：
-
當前方法依賴冗長的 CoT 數據，可能限制實際應用效率。
-
部分任務的泛化魯棒性不足（如超長序列的誤差累積問題）。
-
需進一步探索更高效、通用的訓練框架，以支持復雜現實任務的長度泛化。
注：本系列不包括基礎的知識點講解，為筆記/大綱性質而非教程，用于論文知識點和思想和快速記憶和回顧，更多細節建議閱讀論文原文
