马尔可夫式思考机：革新推理LLM的计算效率

通过强化学习，赋予大型语言模型（LLM）推理能力，效果卓著，但计算成本高昂。

这些模型在回答问题前会生成一系列思维链（LongCoT），增加“思考标记”（token）的数量能提升模型性能。与所有强化学习问题一样，它依赖于一个生成轨迹的环境。

对于推理LLM，这个环境相对简单，以至于经常被忽视：状态由提示词（prompt）与已生成的推理token拼接而成，动作则是从策略（即推理LLM）中采样的下一个token。

这种设计看似简洁，但可能导致状态空间无界——随着思考过程延长而不断增长。对于基于注意力机制的策略，这意味着计算量呈二次级增长，令人望而却步。

为降低推理LLM长时间思考的计算量，已提出多种方法，包括使用长度正则化的目标函数、剪枝或早停等。

近日，Mila和微软研究院等机构组成的联合研究团队提出了一个新问题：如果环境从一开始就不会导致计算量二次级增长呢？

他们提出了一种新范式，其中策略基于固定大小的状态进行推理，称之为马尔可夫式思考机（Markovian Thinker）。

论文标题：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

研究团队之一Amirhossein Kazemnejad在𝕏上表示，Delethink的有效性开启了强化学习思维环境的新篇章。此外，马尔可夫思维的程度及其有效性表明，推理LLM可以以不同方式构建，或许采用非二次架构。

马尔可夫式思考机

马尔可夫式思考机的核心在于重构强化学习的构成形式，使得无论思考长度如何，策略读取的有效状态大小都有界。其直接影响深远：更长的思考过程仅需线性计算量和恒定内存，将“模型思考多久”与“它必须处理多少上下文”两个问题分离。

他们通过Delethink这一范式对思想进行了实例化。它是一个强化学习环境，将推理过程组织成一系列固定大小的区块（chunk），以引导马尔可夫行为。

Delethink将思维强化学习环境重新定义为一个分块、马尔可夫的过程：生成过程以固定大小的区块进行，每个区块结束时，环境将上下文重置为一个包含原始查询及前一块内容的提示词。

这迫使策略必须学会维持一个文本状态以跨区块推进思考，从而创建“马尔可夫式思考机”。

相比之下，LongCoT环境会无限制地拼接token，因此其状态（及模型上下文）随轨迹延长而增长。

算法1的伪代码展示了单个查询的训练过程。

更多细节请访问原论文。总之，Delethink中的生成和用于更新策略的反向传播两个阶段均为线性扩展，而LongCoT中为二次级扩展。下图展示了当思考长度从n token增长到nS token时，LongCoT和Delethink的FLOP、内存、反向传播时间、生成时间的变化。

效果显著

实验表明，Delethink效果显著。即使以8K大小的区块进行推理，使用Delethink训练的DeepSeek R1-Distill 1.5B模型仍能在长达24K token的范围内进行思考。在相同的24K思考预算下，其在数学基准测试上的表现达到并超越了LongCoT-RL。

在测试时扩展方面，Delethink在LongCoT-RL性能饱和时仍能持续提升，带来额外增益。