算力成本大降！馬爾可夫思考機(jī)讓LLM推理成本直接降為線性
馬爾可夫思考者：突破大模型推理長度的計(jì)算瓶頸
最近，強(qiáng)化學(xué)習(xí)(RL)已成為訓(xùn)練推理LLMs的有效方法，使其能夠產(chǎn)生長鏈思考(LongCoT)。然而，這種方法面臨著一個嚴(yán)峻的挑戰(zhàn)：計(jì)算成本隨思考長度呈二次方增長。今天，我們介紹一篇來自Mila、微軟研究院、麥吉爾大學(xué)等機(jī)構(gòu)的研究團(tuán)隊(duì)發(fā)表的重要論文——《The Markovian Thinker》，他們提出了一種革命性的方法，成功解決了這一難題。
- 論文標(biāo)題：The Markovian Thinker
- 論文地址：https://arxiv.org/abs/2510.06557v1
- 模型地址：https://huggingface.co/collections/McGill-NLP/the-markovian-thinker-68debd2919c4ae47f50706cd
- 代碼倉庫：https://github.com/McGill-NLP/the-markovian-thinker
研究背景：推理長度的計(jì)算困境
當(dāng)前，強(qiáng)化學(xué)習(xí)訓(xùn)練推理LLMs的標(biāo)準(zhǔn)"思考環(huán)境"中，狀態(tài)是提示加上所有先前的推理token，這導(dǎo)致狀態(tài)無界增長。對于基于注意力的策略來說，這意味著隨著思考變長，計(jì)算成本呈二次方增長。這種計(jì)算負(fù)擔(dān)極大地限制了模型進(jìn)行長鏈思考的能力。
論文作者指出："在標(biāo)準(zhǔn)LongCoT RLVR中使用的逐個token生成MDP指定了以下狀態(tài)S、動作A和轉(zhuǎn)換動力學(xué)。在時間t，狀態(tài)st∈S是提示和到目前為止生成的token的串聯(lián)：st = x ⊕ y<t = [x1, . . . , xN, y1, . . . , yt?1]，其中⊕表示串聯(lián)。"
圖1，展示LongCoT和Delethink環(huán)境的對比
為了解決這一問題，研究者們提出了馬爾可夫思考(Markovian Thinking)范式，其核心思想是讓策略在推進(jìn)推理時基于恒定大小的狀態(tài)，從而將思考長度與上下文大小解耦。這一思想的直接后果是：更長的思考只需要線性計(jì)算和恒定內(nèi)存，與思考長度無關(guān)。
Delethink：馬爾可夫思考的實(shí)現(xiàn)
研究者們通過Delethink這一RL環(huán)境實(shí)現(xiàn)了馬爾可夫思考。Delethink將推理組織成一系列固定大小的塊。在每個塊內(nèi)，模型像往常一樣進(jìn)行推理；在塊邊界，環(huán)境重置上下文，并使用來自前一個塊的簡短"攜帶"(carryover)重新初始化提示。
通過強(qiáng)化學(xué)習(xí)，策略學(xué)會在每個塊的末尾編寫一個文本狀態(tài)，這個狀態(tài)足夠在重置后無縫繼續(xù)推理。這種設(shè)計(jì)使得模型可以在恒定的上下文大小下進(jìn)行任意長度的推理。
Delethink的工作原理
Delethink的軌跡生成過程如下：
- 在第一個塊中，模型以查詢q作為提示，生成最多C個token的響應(yīng)：y1 ～ π(·|x1 = q)
- 如果響應(yīng)y1以[EOS]結(jié)束，軌跡完成
- 否則，Delethink通過從原始查詢和前一個塊輸出的最后m個token組成的馬爾可夫狀態(tài)構(gòu)建下一個提示： xl = q ⊕ y(l?1)[?m :], l ≥ 2
- 給定xl，模型為塊l生成最多C?m個新的思考token：yl ～ π(·|xl)
- 此過程重復(fù)，直到生成[EOS]或達(dá)到迭代上限I
計(jì)算復(fù)雜度分析
Delethink的最大優(yōu)勢在于其線性計(jì)算復(fù)雜度。論文中詳細(xì)分析了Delethink與LongCoT的計(jì)算成本對比：
方法 | 思考Token數(shù) | FLOP | 內(nèi)存 | 反向時間 | 生成時間 |
基礎(chǔ)模型 | n | O(n2) | O(n) | TB | TG |
LongCoT | nS | O(n2S2) | O(nS) | O(TBS2) | O(TGS2) |
馬爾可夫思考(Delethink) | nS | O(n2S) | O(n) | O(TBS) | O(TGS) |
論文中進(jìn)一步解釋："在LongCoT中，KV緩存隨著思考長度線性增長，限制了GPU上的并行請求。例如，R1-Distill 1.5B模型上100萬token軌跡的KV緩存本身就填滿了整個H100。超越這一點(diǎn)需要跨GPU分片序列，增加了大量通信開銷。相比之下，Delethink只保留當(dāng)前塊的KV緩存，因此使用量保持恒定。"
圖3，展示LongCoT和Delethink的計(jì)算成本對比
實(shí)驗(yàn)結(jié)果：Delethink的卓越表現(xiàn)
研究團(tuán)隊(duì)在多個基準(zhǔn)測試上驗(yàn)證了Delethink的有效性，結(jié)果令人印象深刻。
主要發(fā)現(xiàn)
- 性能相當(dāng)，計(jì)算成本大幅降低：盡管在8K塊中推理，但通過Delethink訓(xùn)練的R1-Distill 1.5B模型可以思考多達(dá)24K token，匹配或超過使用24K預(yù)算訓(xùn)練的LongCoT-RL。
- 測試時間擴(kuò)展能力：在測試時間擴(kuò)展方面，當(dāng)LongCoT達(dá)到平臺期時，Delethink繼續(xù)改進(jìn)。例如，在AIME'25上，一些問題只有在推理多達(dá)140K思考token后才能解決，盡管模型只訓(xùn)練了24K。
- 計(jì)算效率：線性計(jì)算的效果是實(shí)質(zhì)性的：研究團(tuán)隊(duì)估計(jì)，在96K平均思考長度下，LongCoT-RL需要27個H100月，而Delethink只需要7個。
圖2，Delethink與LongCoT在訓(xùn)練曲線、測試時間擴(kuò)展和訓(xùn)練成本方面的對比
詳細(xì)實(shí)驗(yàn)結(jié)果
研究團(tuán)隊(duì)在多個數(shù)學(xué)基準(zhǔn)測試上評估了Delethink，包括AIME'24、AIME'25和HMMT'25，以及作為分布外(OOD)測試的GPQA Diamond和LiveCodeBench。
在數(shù)學(xué)任務(wù)上，Delethink 24K在AIME'24、AIME'25和HMMT'25上都取得了比LongCoT-RL 24K更高的分?jǐn)?shù)。LongCoT-RL 8K則持續(xù)表現(xiàn)不佳，強(qiáng)調(diào)了擴(kuò)展推理的必要性。
在OOD任務(wù)上，雖然絕對收益較為溫和，但Delethink仍然匹配或略微超過LongCoT-RL 24K。
圖4，Delethink與LongCoT在不同任務(wù)上的性能對比
上下文大小消融實(shí)驗(yàn)
研究團(tuán)隊(duì)還對Delethink的上下文大小C進(jìn)行了消融實(shí)驗(yàn)，將其從8K減少到4K和2K，同時調(diào)整迭代次數(shù)以保持最大思考長度為24K token。結(jié)果顯示：
- 4K變體略遜于8K
- 2K變體從低得多的初始化點(diǎn)開始
- 盡管在整個過程中準(zhǔn)確性低于8K和4K，但2K變體仍然超越了基礎(chǔ)模型性能，表明Delethink即使在最小的上下文大小下也能工作
圖6: 不同上下文大小的Delethink性能對比
擴(kuò)展到96K思考長度
研究團(tuán)隊(duì)還將思考預(yù)算從24K擴(kuò)展到96K token，這得益于Delethink RL訓(xùn)練的線性計(jì)算成本。具體來說，他們保持思考上下文為C=8K，并將迭代上限從I=5增加到I=23，產(chǎn)生96K的總預(yù)算。
盡管訓(xùn)練時間表很短，但Delethink 96K不僅超越了Delethink 24K檢查點(diǎn)的基礎(chǔ)性能，還匹配或超過了使用128K token預(yù)算評估的測試時間擴(kuò)展的Delethink 24K。此外，模型的平均思考長度達(dá)到36K(AIME'24)和42K(AIME'25)token，表明有效利用了更大的預(yù)算。
圖8，Delethink 96K的性能和平均軌跡長度
為什么Delethink有效？
為了探究Delethink為何有效，研究團(tuán)隊(duì)分析了RL初始化時的模型。他們觀察到，R1-Distill系列(1.5B-14B)在沒有任何額外訓(xùn)練或提示的情況下，已經(jīng)能夠零樣本生成馬爾可夫軌跡，甚至恢復(fù)了大部分標(biāo)準(zhǔn)LongCoT性能。
這種強(qiáng)初始化（許多所需行為的正面、同分布樣本）為RL提供了一個有利的起點(diǎn)。研究團(tuán)隊(duì)進(jìn)一步研究了Delethink環(huán)境中高達(dá)120B參數(shù)的推理模型。例如，GPT-OSS 120B在博士級問題、編碼任務(wù)、數(shù)學(xué)競賽和填字游戲等任務(wù)中表現(xiàn)出穩(wěn)健的馬爾可夫思考能力。
圖9，R1-Distill在初始化時的Delethink軌跡性能
現(xiàn)有SOTA模型的馬爾可夫思考能力
研究團(tuán)隊(duì)還評估了兩個最先進(jìn)的開源推理LLMs——GPT-OSS 120B和Qwen3 30B-A3B Thinking在Delethink下的表現(xiàn)。他們發(fā)現(xiàn)：
- 16K上下文是一個可靠的默認(rèn)值，可以恢復(fù)大部分原始性能
- 8K實(shí)現(xiàn)了合理的分?jǐn)?shù)，適合計(jì)算緊張的情況
- 兩種模型在LongCoT和Delethink Tracing下都通過更多推理獲得了更高的分?jǐn)?shù)
- Delethink Tracing在C=16K時在Qwen3上匹配或超過LongCoT，在GPT-OSS上幾乎匹配
圖10，GPT-OSS 120B和Qwen3 30B-A3B在Delethink下的表現(xiàn)
壓力測試Delethink Tracing
為了找到Delethink不是從強(qiáng)初始化開始的任務(wù)，研究團(tuán)隊(duì)評估了CrossWordBench，這是一個包含不同難度級別填字游戲的任務(wù)。在這個任務(wù)中，推理需要維護(hù)一個實(shí)時網(wǎng)格和填充條目——這種狀態(tài)可能超過m的容量。
結(jié)果顯示，Delethink Tracing在7×7謎題上實(shí)現(xiàn)了與LongCoT大致相當(dāng)?shù)男阅堋Ｔ诟咛魬?zhàn)性的14×14謎題上，性能相對于LongCoT有所下降，盡管兩種模型繼續(xù)產(chǎn)生大量有效的馬爾可夫軌跡。這表明即使在設(shè)計(jì)用來壓力測試Delethink的設(shè)置中，它也保留了有意義的概率覆蓋，并 readily 發(fā)現(xiàn)馬爾可夫解決方案。
圖11，Delethink與LongCoT在問題解決重疊和CrossWordBench上的對比
結(jié)論與意義
馬爾可夫思考的成功表明，將思考長度與上下文大小解耦原則上可以讓下一代推理模型思考數(shù)百萬個token。它突顯了RL環(huán)境（通常被視為固定）作為進(jìn)步的強(qiáng)大杠桿。它還表明，非二次序列架構(gòu)（如線性注意力）可能特別有利于推理模型，因?yàn)樗伎伎梢杂行У刈兊民R爾可夫。
研究團(tuán)隊(duì)總結(jié)道："我們引入了馬爾可夫思考范式，它限制了策略的輸入狀態(tài)，并產(chǎn)生與思考長度成線性計(jì)算和恒定內(nèi)存的關(guān)系。我們提出了一個簡單的實(shí)例化Delethink，它訓(xùn)練現(xiàn)成的推理LLMs成為原生馬爾可夫思考者，經(jīng)驗(yàn)上匹配并超越了LongCoT-RL訓(xùn)練。"
這項(xiàng)研究的意義不僅在于提高了計(jì)算效率，更在于它重新定義了推理環(huán)境的設(shè)計(jì)思路。通過重新思考RL環(huán)境本身，而非僅僅優(yōu)化現(xiàn)有框架，研究團(tuán)隊(duì)為未來更高效、可擴(kuò)展的推理LLMs開辟了新路徑。
隨著大模型應(yīng)用的不斷深入，長鏈推理能力將成為衡量模型智能水平的重要指標(biāo)。而Delethink的出現(xiàn)，無疑為我們提供了一個在有限計(jì)算資源下實(shí)現(xiàn)這一目標(biāo)的有力工具。我們期待看到這一方法在更多領(lǐng)域和更大規(guī)模模型上的應(yīng)用與突破。
本文轉(zhuǎn)載自??AIGC深一度??，作者：一度
