马尔可夫思维：优化LLM长序列推理的计算效率

1. 马尔可夫思维突破长序列推理的算力瓶颈在大型语言模型LLM的推理任务中传统的链式思维Chain-of-Thought, CoT方法存在一个根本性缺陷随着推理步骤的增加模型需要处理的上下文长度线性增长导致注意力机制的计算复杂度呈二次方上升。这个问题在需要长序列推理的任务如复杂数学证明、程序代码生成等中尤为突出往往成为制约模型性能的瓶颈。1.1 传统链式思维的效率困境标准链式思维的工作流程可以概括为模型接收初始提示prompt逐步生成推理token即思考过程最终输出答案在这个过程中每个新生成的token都会被追加到上下文窗口导致两个关键问题计算复杂度Transformer架构的自注意力机制需要为每个token计算与所有先前token的关系使得FLOPs浮点运算次数与序列长度成二次方关系O(n²)内存压力KV缓存Key-Value缓存随序列长度线性增长在长序列场景下会耗尽GPU内存例如当模型进行24K token的推理时标准CoT需要处理24K长度的完整上下文每个注意力层的计算量约为576M次操作假设d_model1024实际应用中这会导致训练成本激增和推理延迟显著提高1.2 马尔可夫思维的核心创新马尔可夫思维提出了一种范式转换将推理过程分解为固定大小的块chunk在每个块边界重置上下文仅保留关键的状态信息。这种方法的核心特征包括分块推理将长序列拆分为多个固定长度的推理块如8K token状态压缩在块边界处只保留最后m个token作为马尔可夫状态如m4K上下文重置每个新块开始时用原始提示前一块的状态重新初始化上下文这种设计带来了三个关键优势计算效率最大上下文长度被限制为块大小如8K使计算复杂度从O(n²)降至O(n)内存恒定KV缓存大小不再随总推理长度增长始终保持稳定训练稳定性模型学习在有限上下文中维持推理连贯性反而提升了长程依赖处理能力实践表明这种方法的有效性源于一个有趣的现象即使在零样本zero-shot情况下现有LLM生成的推理轨迹往往已经表现出较强的马尔可夫性。这意味着模型天然具备在有限上下文中维持思维连贯性的能力为马尔可夫思维的训练提供了良好基础。2. Delethink基于强化学习的马尔可夫思维实现2.1 环境设计原理Delethink是一个专门为训练马尔可夫思维设计的强化学习环境其核心机制包括分块生成过程初始块模型接收完整提示q生成最多C个tokeny₁后续块环境构造新提示xₗ q ⊕ yₗ₋₁[-m:]模型生成C-m个新token终止条件遇到[EOS]或达到最大迭代次数关键参数选择典型配置C8Km4K即保留最后4K token作为状态状态大小m需要平衡过小可能丢失关键推理信息过大降低计算效率优势2.2 强化学习训练框架Delethink采用改进的RL训练流程其策略梯度估计器针对分块推理进行了特殊设计轨迹生成对每个查询q采样G条分块轨迹{τ_g}优势估计使用GRPO风格的归一化优势 Â (R(τ) - μ)/σ策略更新优化包含KL散度约束的目标函数J(θ) [∑(min(πθ/πold·Â, clip(πθ/πold,1±ϵ)·Â)) - βKL(πθ∥πref)]与标准RL训练相比Delethink有两个关键区别奖励分配最终奖励基于整个轨迹的最终结果但梯度更新作用于各个分块长度归一化损失函数按总token数归一化避免长轨迹主导训练2.3 计算效率分析下表对比了不同方法在扩展到nS token时的计算特性指标标准CoTLongCoT-RLDelethinkFLOPsO(n²)O(n²S²)O(n²S)峰值内存O(n)O(nS)O(n)反向传播时间T_BO(T_B·S²)O(T_B·S)生成时间T_GO(T_G·S²)O(T_G·S)实际测试中当思考长度从8K扩展到96K时LongCoT-RL需要约27个H100月GPU-hoursDelethink仅需7个H100月节省74%计算资源这种效率提升主要来自KV缓存优化Delethink只需维护当前块的缓存而LongCoT需要保留完整序列并行度提升固定上下文大小允许更高的请求吞吐量见图4右边界成本虽然Delethink需要在块边界重新编码m个token但该操作在现代推理引擎中效率很高3. 实现细节与性能优化3.1 模型架构适配虽然马尔可夫思维理论上架构无关但在实际实现中需要考虑以下工程因素注意力模式选择标准Transformer完全兼容但受限于二次方复杂度稀疏注意力可进一步降低计算量但需要调整稀疏模式Mamba等SSM架构天然适合因其具有线性复杂度KV缓存管理class DelethinkCache: def __init__(self, chunk_size8192, state_size4096): self.chunk_size chunk_size self.state_size state_size self.current_chunk [] def update(self, new_tokens): self.current_chunk.extend(new_tokens) if len(self.current_chunk) self.chunk_size: # 保留最后state_size个token作为马尔可夫状态 carryover self.current_chunk[-self.state_size:] self.current_chunk [] return carryover return None3.2 训练配置建议基于R1-Distill 1.5B的实验我们总结出以下最佳实践超参数设置学习率1e-6 ~ 5e-6使用余弦退火批次大小1024个轨迹128提示×8轨迹PPO clip范围0.1 ~ 0.3温度系数0.6 ~ 0.8稳定训练技巧使用动态微批次dynamic microbatching处理不同长度的块在块边界添加特殊token如[CHUNK]作为分割标记对长轨迹实施梯度裁剪max_grad_norm1.0基础设施优化使用SGLang等高效推理框架采用FSDP完全分片数据并行进行参数分布避免序列并行以减少通信开销3.3 推理优化策略在生产环境中部署马尔可夫思维模型时这些策略能显著提升性能预填充优化对原始提示q进行预计算和缓存使用FlashAttention加速块边界的状态重新编码动态块大小调整根据问题复杂度动态调整C值简单问题使用较小块如4K复杂问题使用较大块如16K早期终止机制在块内设置多个检查点评估推理质量当置信度足够高时提前输出结果4. 实证结果与性能对比4.1 数学推理任务表现我们在多个数学竞赛数据集上评估了Delethink的性能方法AIME24AIME25HMMT25平均长度LongCoT-RL (8K)0.290.230.157.2KLongCoT-RL (24K)0.350.280.1819.3KDelethink (24K)0.370.300.2122.7KDelethink (96K)0.460.400.2836.4K关键发现在相同24K预算下Delethink平均比LongCoT-RL高5-8%准确率Delethink能有效利用更大的思考预算96K而LongCoT因计算限制难以扩展模型生成的解决方案长度与性能正相关证实了长序列推理的价值4.2 泛化能力测试为评估方法的通用性我们在两个OODOut-Of-Distribution任务上进行测试GPQA Diamond博士级问答Delethink 24K0.36LongCoT-RL 24K0.35基线无RL0.28LiveCodeBench代码生成Delethink 24K0.23LongCoT-RL 24K0.21基线0.17结果表明即使训练数据仅为数学问题马尔可夫思维也能有效迁移到其他领域在需要分步解决的复杂任务上优势更明显4.3 扩展性分析通过测试时扩展test-time scaling实验我们观察到性能曲线LongCoT在达到训练长度如24K后很快进入平台期Delethink能持续受益于更长的思考长度直至128K token计算效率在24K长度时Delethink的吞吐量是LongCoT的2.3倍随着长度增加这个差距会进一步扩大内存占用LongCoT的峰值内存随长度线性增长Delethink保持恒定内存使用支持更长序列推理5. 应用场景与最佳实践5.1 适合马尔可夫思维的任务类型以下任务类型特别适合采用这种技术多步数学证明需要维持大量中间结论示例IMO问题、组合数学证明长程序生成需要保持API一致性示例完整项目生成、复杂算法实现结构化写作需要维持叙述连贯性示例技术文档撰写、长篇故事创作5.2 参数选择指南根据实际应用场景调整这些关键参数块大小C平衡点足够容纳有意义的推理步骤建议值对于1.5B模型4K-16K更大模型可适当增加状态大小m经验法则m ≈ C/2可尝试范围C/4到C/2迭代次数I取决于任务复杂度典型设置3-10次5.3 常见问题排查在实际部署中可能遇到的问题及解决方案问题1块间推理不连贯检查状态token是否包含足够信息尝试增加m或在块尾添加总结性语句问题2短问题性能下降实现动态块大小调整对简单问题使用更小的C值问题3训练不稳定检查优势估计的归一化调整PPO clip范围增加批次大小6. 未来方向与扩展应用马尔可夫思维为LLM的长序列推理开辟了多条创新路径混合注意力机制在块内使用标准注意力跨块使用线性注意力或SSM分层状态压缩开发更高效的状态表示方法尝试token压缩或抽象表示领域自适应针对特定任务优化状态保留策略例如数学推理侧重公式编程侧重API签名在实际应用中我们发现这种技术特别适合需要长时间保持上下文一致性的场景。一个有趣的案例是使用Delethink进行复杂数学竞赛问题的求解——模型能够在数十步推理后仍然准确引用最早得出的引理这种能力在传统CoT中很难实现。