作者介紹：本文第一作者是豐田工業(yè)大學(xué)芝加哥 PhD 學(xué)生楊晨曉，研究興趣是機器學(xué)習(xí)理論和大模型推理，在 ICML，NeurIPS，ICLR 等頂級會議上發(fā)表過論文。

本文提出一個交替「推理 - 擦除」的深度思考新范式 PENCIL，比傳統(tǒng) CoT 更高效地解決更復(fù)雜的推理任務(wù)。理論上，我們證明 PENCIL 可用最優(yōu)空間與最優(yōu)時間下解決所有可計算問題，而這對于傳統(tǒng)的 CoT 是不可能的！該工作已被機器學(xué)習(xí)頂會 ICML 2025 收錄。

• 題目： PENCIL: Long Thoughts with Short Memory
• 鏈接： https://arxiv.org/pdf/2503.14337
• 代碼： https://github.com/chr26195/PENCIL 

最近的大模型（如 OpenAI 的 o1/o3、DeepSeek 的 R1）發(fā)現(xiàn)能通過在測試階段深度思考（Test-Time Scaling）來大幅提高模型的推理能力。目前實現(xiàn)深度思考的關(guān)鍵在于使用長鏈思維鏈（Long Chain-of-Thought，CoT），即讓模型生成更長中間結(jié)果得到最終答案。然而，傳統(tǒng)「只寫不擦」的方法在處理高難度、大規(guī)模任務(wù)時面臨以下瓶頸： 

1. 超出上下文窗口：一旦鏈條過長，就會觸及模型的最大上下文長度限制；
2. 信息檢索困難：隨著上下文不斷累積，模型難以從冗長歷史中 Retrieve 關(guān)鍵線索； 
3. 生成效率下降：上下文越長，每步生成新 token 的計算量越大。

不過實際上，并非所有中間思路都后續(xù)推理有用：例如定理證明里，引理一旦驗證通過，其具體推導(dǎo)可被丟棄；解數(shù)學(xué)題時，已知某條思路走不通就無需保留那段「嘗試」的細(xì)節(jié)。縱觀計算機科學(xué)的發(fā)展歷史，這一「隨時清理」的理念早已滲透到幾乎所有計算模型之中：從最早的圖靈機模型中，已讀寫的磁帶符號可以被覆蓋或重寫，直到現(xiàn)在高級編程語言中，垃圾回收機制會自動清理不再可達(dá)的內(nèi)存單元。

基于這樣的動機，我們提出一個新的深度思考范式 PENCIL，迭代地執(zhí)行生成（Generation）和擦除（Reduction），即在生成的過程中動態(tài)地擦除不再需要的中間結(jié)果，直到得到最后的答案。

一、交替「生成 - 擦除」的深度思考范式

下圖以一個簡單的算術(shù)題為例展示了 PENCIL 的工作機制： 

• CoT 將每步推理串聯(lián)到上下文中直到給出答案并返回整個序列。
• PENCIL 交替執(zhí)行生成（圖中加粗部分）和 擦除（圖中綠色高亮部分）：模型先寫出新的思考過程，再刪掉對之后的推理無用片段，只保留對后續(xù)的推理過程有用的部分，內(nèi)部形成一系列隱式思維，最后僅返回最終答案。

PENCIL 擦除機制的設(shè)計借鑒了邏輯學(xué)與經(jīng)典自動定理證明中的重寫規(guī)則（Rewriting Rule 和函數(shù)式編程語言中的棧幀內(nèi)存管理（Stack Frame）。 具體地，我們引入三個特殊字符（Special Token），叫做 [CALL], [SEP], [RETURN]，并用以下的規(guī)則（Reduction Rule）來實現(xiàn)擦除： 

其中 C（Context）表示上下文，T（Thoughts）表示中間思考，A（Answer）表示回答。每當(dāng)生成的序列與左側(cè)模式完全匹配時，PENCIL 即觸發(fā)一次擦除，丟棄 T。重要的是，C、T、A 本身均可包含其他特殊標(biāo)記，從而支持類似多層函數(shù)調(diào)用的遞歸結(jié)構(gòu)。

PENCIL 的擦除機制能夠靈活支撐多種推理模式，例如：

• 任務(wù)分解（Decomposition）：通過 [CALL] 啟動子任務(wù)，完成后用 [RETURN] 合并輸出并擦除子任務(wù)推理細(xì)節(jié)；
• 搜索與回溯（Search and Backtrack）：在搜索樹中，用特殊字符管理探索分支，沖突或失敗時擦除無效路徑； 
• 摘要與總結(jié)（Summarization）：將冗長的思考片段歸納為簡潔摘要，類似編程中的尾遞歸（Tail Recursion）：

其中 T 表示原始的復(fù)雜思考過程（或更難的問題），T' 歸納或簡化后的摘要（或等價的、更易處理的問題）。

示例： 布爾可滿足性（SAT）是經(jīng)典的 NP-Complete 問題：給定一個 n 個變量布爾公式，判斷是否存在一組變量賦值使其為真。這個問題（廣泛認(rèn)為）需要指數(shù)時間但僅需多項式空間來解決，其中最簡單的做法是構(gòu)造一個深度為 n 的二叉搜索樹遍歷所有可能。傳統(tǒng) CoT 將每步計算附加到上下文，長度與搜索樹節(jié)點數(shù)成正比 (O (exp (n)))，導(dǎo)致指數(shù)爆炸；PENCIL 在遞歸分支嘗試時，遇到?jīng)_突立即回溯并擦除該分支所有思考，僅保留關(guān)鍵結(jié)果，使上下文長度僅與搜索深度成正比 (O (n))。

如圖所示，對比 CoT 無擦除（藍(lán)）與 PENCIL 擦除（紅）兩種思考模式下的最大上下文長度，隨著問題規(guī)模增大，PENCIL 能將所需序列長度控制在千級或百級，而傳統(tǒng) CoT 則迅速攀升至數(shù)萬甚至數(shù)十萬。即使在復(fù)雜的 Einstein's Puzzle 中，PENCIL 也能將需要幾十萬 token 的上下文壓縮到幾千 token。

二、訓(xùn)練和實驗結(jié)果

訓(xùn)練和測試：在訓(xùn)練時，CoT 每個新 token 的損失計算都基于完整的歷史上下文；PENCIL 在每輪「寫 — 擦」循環(huán)結(jié)束后只在被擦除后的短序列上計算損失。即使兩者生成 token 數(shù)量相同，PENCIL 每一個 token 對應(yīng)的上下文長度卻大幅縮短；另一方面，在每次 Reduction 后，C 部分的 KV cache 可以直接復(fù)用，只需為更短的 A 部分重新計算緩存。這樣， PENCIL 在訓(xùn)練和測試時能顯著減少自注意力計算開銷。 

實驗設(shè)置：我們針對三種具有代表性的高難度推理任務(wù)構(gòu)建數(shù)據(jù)集：3-SAT（NP-Complete）、QBF（PSPACE-Complete）和 Einstein’s Puzzle（自然語言推理）。所有實驗均在相同配置下從隨機初始化開始進(jìn)行預(yù)訓(xùn)練和評估，采用小型 Transformer（10.6M 參數(shù)和 25.2M 參數(shù)），訓(xùn)練超參數(shù)保持一致。 

1. 準(zhǔn)確率

相比 CoT，PENCIL 能解決更大規(guī)模的推理問題。如下圖所示，在 SAT（左圖）和 QBF（右圖）任務(wù)中，當(dāng)問題規(guī)模較小時，CoT 與 PENCIL 均能完美解決問題；但隨著規(guī)模增大，傳統(tǒng) CoT 的準(zhǔn)確率顯著下降（例如 SAT 在 n=10 時僅約 50%），而 PENCIL 始終保持 ≥ 99% 的高準(zhǔn)確率。 

2. 計算效率

PENCIL 還能顯著節(jié)省計算資源。如圖所示，我們在相同 FLOPs 預(yù)算下對比了 CoT（藍(lán)色）與 PENCIL（紅色）的訓(xùn)練收斂表現(xiàn)。PENCIL 訓(xùn)練早期迅速達(dá)到 100% 準(zhǔn)確率，訓(xùn)練損失更快穩(wěn)定；CoT 因上下文膨脹需投入更多資源才能接近最優(yōu)。隨著問題規(guī)模增加，兩者之間的差距愈發(fā)明顯。 

3. 自然語言推理任務(wù)：Einstein’s Puzzle

我們測試了 PENCIL 在極具挑戰(zhàn)性的 Einstein's Puzzle 上的表現(xiàn)。該問題要求從一系列線索（如「綠房子在養(yǎng)鳥者右側(cè)」、「養(yǎng)狗者住在紅房子」等）推斷出五個房屋中人們的全部屬性（顏色、國籍、飲品、香煙和寵物）。即使是 GPT-4 也難以解決此類邏輯推理問題 [1]。下圖展示了 n=3 時的問題簡化：

如圖所示，對于該大模型也難以解決的問題，而 PENCIL 僅用一個 25.2M 參數(shù)的小模型將準(zhǔn)確率提升至 97%；相比較之下，傳統(tǒng) CoT 準(zhǔn)確率僅 25%，接近隨機猜測的準(zhǔn)確率。

三、理論：PENCIL 用最優(yōu)的空間 / 時間實現(xiàn)圖靈完備

我們進(jìn)一步從理論表達(dá)能力的角度展示 PENCIL 相較于傳統(tǒng) CoT 的根本性優(yōu)勢。具體地，我們證明：使用一個固定的、有限大小的 Transformer，PENCIL 可以用最優(yōu)的時間和空間復(fù)雜度模擬任意圖靈機的運算過程（即實現(xiàn)圖靈完備），從而高效地解決所有可計算問題： 

具體而言，若任意圖靈機在某輸入上需 T 步計算和 S 空間，PENCIL 僅需生成 O (T) 個 token 并保持上下文長度至多為 O (S) 即可輸出相同結(jié)果。值得注意的是，大多數(shù)算法的空間復(fù)雜度都遠(yuǎn)小于其時間復(fù)雜度，即 S << T。

相比之下，傳統(tǒng) CoT 雖能實現(xiàn)圖靈完備 [2] —— 思維鏈的每一步表示圖靈機的一步中間計算過程，因此思維鏈足夠長就可以解決所以可計算問題。但這意味著其生成序列的上下文長度必須與運行步數(shù) T 成正比，代價十分昂貴：對于中等難度任務(wù)也許尚可承受，一旦面對真正復(fù)雜需要深度思考的問題，這種指數(shù)級的上下文爆炸就變得不切實際。

例如，一系列（公認(rèn)）無法在多項式時間內(nèi)解決卻可在多項式空間內(nèi)解決的 NP-Complete（如旅行商等等），對于使用有限精度 Transformer 的 CoT 而言至少需要超越多項式（例如 exp (n)）規(guī)模的上下文長度，在真實應(yīng)用中由于內(nèi)存的限制完全不可行；而 PENCIL 只需 poly (n) 規(guī)模的上下文就能高效求解，讓「深度思考」變得切實可行。 

證明思路：證明關(guān)鍵在用一系列「思考 — 總結(jié)」循環(huán)來替代持續(xù)累積的思維鏈。

具體地，如上圖左圖所示，我們先將圖靈機狀態(tài)轉(zhuǎn)移編碼為三元組 token（新狀態(tài)、寫入符號、移動方向）。模型通過自注意力計算讀寫頭位置，并從上下文回溯讀取符號。未經(jīng)優(yōu)化時，需保留 T 步完整歷史，上下文長度為 O (T)。

PENCIL 能夠?qū)崿F(xiàn)空間 / 時間最優(yōu)的核心是利用交替「思考 - 總結(jié)」的生成方式：

1. 思考 （Simulation）：生成連續(xù)狀態(tài)轉(zhuǎn)移 token，模擬圖靈機計算； 
2. 總結(jié) （Summarization）：當(dāng)新 token 數(shù)超過實際所需空間兩倍時，用不超過 S 個的 token 總結(jié)當(dāng)前狀態(tài)，觸發(fā)擦除規(guī)則丟棄中間過程。

通過這種策略，PENCIL 生成總 token 數(shù)仍為 O (T)，卻把最大上下文長度嚴(yán)格限制在 O (S)，達(dá)到了空間與時間的雙重最優(yōu)。

最后，我們需要證明這種「思考 - 總結(jié)」的生成方式可以被現(xiàn)實中的 Transformer 實現(xiàn)。為此，我們設(shè)計了 Full-Access Sequence Processing (FASP) 編程語言，并證明所有用 FASP 寫的程序都可被 Transformer 表達(dá)。通過構(gòu)造能執(zhí)行「思考 - 總結(jié)」操作的 FASP 程序，我們證明了等價存在固定大小 Transformer 完成相同功能，從而理論上證明 PENCIL 可用最優(yōu)復(fù)雜度模擬任意計算過程。