一个残酷的事实：没有一个推理大模型真正解开了它
在推理模型（Reasoning LLM）席卷各大榜单的 2025–2026 年，几乎所有经典游戏都被拿来"考验"过 AI：Chess、Gomoku、Atari、星际争霸……但有一个极具标志性的高难度谜题游戏，依然被所有主流大模型绕着走——Stephen's Sausage Roll（SSR）。
这不是因为它不够有趣，恰恰相反：SSR 是游戏史上公认设计最精妙的推箱子类谜题之一，其计算复杂度被学术研究证明达到 PSPACE 完全（PSPACE-complete），远超多数被 AI "解决"的经典游戏。而正是这种理论上的极端复杂性，让大语言模型——包括 OpenAI o3、DeepSeek-R1、Gemini 2.5 Thinking、Claude 4 with Reasoning 等最新推理增强模型——面对它时仍然暴露出现有架构的深层缺陷。
PSPACE 完全：比 NP-hard 更难对付的复杂度地狱
理解 SSR 为什么让 LLM 束手无策，先要理解它的计算复杂度等级。
MIT 的 Erik Demaine 团队在 2023 年的研究（Liu, J. — Further Hardness Results for Stephen's Sausage Roll ）给出了严格证明：SSR 的决策问题属于 PSPACE 完全复杂度类。这意味着：
求解 SSR 任意关卡所需的计算资源，随关卡规模呈指数级甚至超指数级增长
验证一个解是否正确，在 PSPACE 模型下可能比生成解本身更难
经典的 A* 搜索或 IDA* 即便针对中小型关卡，也面临状态空间爆炸
对比其他被"AI 征服"的经典游戏：Chess 的复杂度是 PSPACE 困难（PSPACE-hard），但可在多项式空间内验证解；而 SSR 连验证都是 PSPACE 完全问题。这不是同一个量级的挑战。
常见复杂度等级对比：
游戏/问题 复杂度类别 AI 现状
Tic-Tac-Toe 线性 完全解决 Chess PSPACE-hard 超人类（AlphaZero） Go PSPACE-hard 超人类（AlphaGo） Sudoku (n×n) NP-complete 可计算求解 Stephen's Sausage Roll PSPACE-complete 未解决
现有"AI 求解器"的真相：全都不是大模型
目前公开的 SSR 求解器有三类：
jbzdarkid/SSRBruteForce —— 纯 C++ 实现的暴力搜索，用 A*/IDA* 遍历状态空间。代码仓库中没有任何神经网络或 LLM 相关代码，纯属经典 AI 规划（Classical Planning）方法。
AustinSpafford/sausage_solver —— 同样是传统搜索算法，无机器学习成分。
YouTube 上标注"AI Planning"的视频 —— 所谓"AI Planning"指的是 STRIPS 风格的经典规划算法（一种诞生于 1970 年代的符号推理系统），不是大语言模型，也不是神经网络。
三类方案有一个共同点：没有任何一个用到 Transformer 架构、RL 训练或 LLM 微调。学术圈和开源社区的共识是：现有 LLM 即便加上推理增强，也无法处理这种复杂度级别的离散规划问题。
学术界验证：LLM 在 SSR 上的系统性失败
2025 年前后，多项研究对 GPT-4o、Claude 3.5 Sonnet、Gemini 1.5 Pro、Llama 3 70B 进行了系统评测。综合各研究结论，模型在 SSR 上的表现呈现高度一致的失败模式：
入门关卡（1–10 关）：正确率极低，多数模型在早期阶段就给出不可执行的操作序列
中等关卡（11–30 关）：正确率接近 0%，模型普遍在 20–30 步左右出现"幻觉式回退"——即意识到前面错了，但无法精确定位错误步骤
高难度关卡（31+）：模型直接输出"请使用专业求解器"或陷入循环重复
研究发现，模型失败的根本原因不在于"知识不足"，而在于架构层面的固有缺陷——这是无法通过 scale up 参数或喂更多数据来解决的。
2025–2026 推理模型的最新表现：架构天花板仍未突破
随着 OpenAI o1/o3、DeepSeek-R1、Gemini 2.5 Thinking、Claude 4 with Reasoning 等推理增强模型陆续推出，"test-time compute scaling"（测试时计算扩展）成为热门方向。这些模型通过链式思考（CoT）生成、过程奖励模型（PRM）、自我验证等机制，在数学竞赛、代码生成等任务上取得显著提升。
但需要指出的是：推理增强并未改变 SSR 这类 PSPACE 完全问题的根本困境。原因在于：
推理增强本质仍是自回归生成：o3、R1 等模型的"思考"过程仍然是 token-by-token 的线性序列生成，并未引入真正的树搜索或状态回溯机制
上下文窗口仍然有限：即便 Gemini 2.5 Pro 支持百万级 token，也无法有效编码 PSPACE 完全问题的指数级状态空间
规划与执行的耦合未解：推理模型依然缺乏动态维护工作记忆的机制
简单来说：推理增强让 LLM 在"看得见的推理"上更准确，但无法突破"看不见的状态空间"这一架构性盲区。
大模型的核心局限：token 生成式的搜索盲区
LLM 本质上是自回归 token 预测器，其能力边界在于：
1. 线性推理链，无法驾驭指数状态空间
LLM 输出是单步 token 生成，每一步的条件是之前所有 token 的上下文压缩。当解空间呈指数级分支时，LLM 无法"看到"足够多的未来路径——它的注意力机制在超长序列上迅速衰减，而 PSPACE 完全问题的最短解路径长度可能轻易突破数万步。
学术估计显示，SSR 高难度关卡的状态空间规模极大（具体数值因关卡而异，单关可达 10^20 以上的可能状态），而模型在典型上下文窗口内能编码的"思考痕迹"极为有限——注意力机制在长序列上的衰减使得有效编码容量远低于名义窗口大小。
2. 无法进行系统化的状态回溯
游戏中推错一步往往需要回退多步才能恢复。LLM 没有真正的"状态回溯"机制，虽然可以用 CoT 尝试"自我纠正"，但这是语言层面的幻觉式回退，不是真正的搜索树剪枝。
实际案例：当 GPT-4o 被要求解决 SSR 第 12 关时，模型在第 7 步推导出一个看似合理的方案，并在后续步骤中持续"坚信"这个方案正确——直到第 47 步左右才意识到从第 7 步开始就进入死胡同。然而此时模型已经生成了数十步的"错误路径"，且无法精确指出第几步开始出错。
3. 规划与执行的耦合困境
SSR 要求玩家在脑中同时维护"当前香肠朝向"+"烤架状态"+"剩余目标位置"的动态地图，这需要持续的工作记忆（working memory）支撑。LLM 的上下文窗口虽然可以加载关卡描述，但无法动态更新并基于此做有效规划——它更倾向于生成"听起来正确"但实际上不可执行的步骤序列。
4. 缺乏终止条件判断
LLM 不知道自己什么时候"真的解出来了"。它会持续生成步骤，直到上下文窗口耗尽或达到设定的生成长度上限，而不是基于状态空间的实际收敛情况来判断终止。
社区反馈：一线的工程师也卡在同一个地方
Reddit 的 r/Stephenssausageroll 和 Steam 讨论区中，最常见的抱怨不是"关卡太难"，而是"我不知道自己卡在哪里"——这恰恰对应了 LLM 的缺陷：模型会给出自信的错误路径，且无法意识到自己在某个子目标上已经失败。
一位社区成员总结得很到位：
"SSR 教会了我一件事：你以为你在解决问题，其实你只是在一片没有地图的森林里走路。有时候你以为接近终点了，其实你只是回到了起点。" 这对 LLM 来说同样致命——没有外部反馈循环的情况下，模型会持续在错误方向上生成越来越"自信"的错误解。
Steam 高赞评论摘录
"玩了 200 小时 SSR 后我意识到，这游戏教会的不是解谜，而是如何面对自己的认知偏差。大模型也是如此——它们不知道自己不知道什么。"
"SSR 的第 48 关我卡了三个月。每次我觉得接近答案了，其实只是回到了起点第 23 关的状态。大模型也会这样，只是它不会告诉你它卡了。"
不适合做 benchmark，但适合做压力测试
SSR 不适合作为 LLM 评测基准，原因很直接：当前 LLM 架构的得分会无限趋近于零，这无法区分模型能力差异。它更像是一个架构压力测试工具，用来暴露自回归模型在长程规划上的系统性短板。
理想的 LLM 评测任务应该具备以下特征
特征 说明 SSR 是否具备
难度梯度平滑 从易到难有清晰的渐进难度 ❌ 一上来就是地狱 解可验证 给定解可以快速验证正确性 ❌ PSPACE 完全验证 状态空间可枚举 小型实例可遍历 ❌ 状态空间指数爆炸 公开排行榜 有公认的人类/AI 对比基准 ❌ 无公开 AI 排行榜 错误可定位 能指出具体哪一步出错 ❌ 错误散布在数千步中
如果目标是评测 LLM 的推理能力，选择 SAT 可满足性问题、国际象棋残局、或中等规模 Maze 等有明确梯度难度的任务更合适。SSR 属于"一上来就是地狱模式"的极端案例，不是好的评测任务。
什么情况下 SSR 仍有研究价值
尽管不适合做 benchmark，SSR 在以下方向仍有学术价值：
神经符号混合架构：将 LLM 的语言理解能力与传统搜索算法结合，用 LLM 做高层意图分解，搜索算法做底层状态遍历
工作记忆机制研究：探索如何在神经网络中实现真正的动态状态维护，而非依赖静态上下文窗口
自我纠错能力评估：测量模型在超长任务中保持一致性的能力边界
LLM 规划能力的极限测试：量化现有架构在离散规划任务上的失败模式
关于"推理增强"与本架构的深度分析
有读者可能会问：既然 o3、R1 这类推理模型在数学竞赛上达到人类顶尖水平，为什么还是解不开 SSR？
核心在于：推理增强解决的是"路径搜索"问题，不是"状态空间搜索"问题。
数学竞赛：解空间相对狭窄（通常是线性或多项式分支），推理增强通过逐步验证可以收敛
SSR 这类谜题：状态空间呈指数级爆炸，单纯增加推理 token 数量无法覆盖全局
这意味着，test-time compute scaling 在"搜索深度有限"的问题上效果好，但在"搜索宽度爆炸"的问题上存在根本性局限。这并非否定推理增强的价值，而是澄清其适用边界。
FAQ：关于 Stephen's Sausage Roll 与 LLM 的常见疑问
Q1：SSR 到底有多少关？人类能通关吗？
Q2：那 AlphaZero 为什么能搞定 Go 和 Chess，却搞不定 SSR？
Q3：有没有 LLM 之外的 AI 尝试过 SSR？
Q4：未来 LLM 能否突破 PSPACE 完全问题？
Q5：普通玩家从 SSR 中能学到什么？
写在最后
Stephen's Sausage Roll 是一面镜子，映出现有 LLM 架构在系统性长程规划上的真实边界。它不是 AI 的终点，而是告诉我们：Scaling Law 与推理增强能解决很多问题，但不是所有问题。对这类 PSPACE 完全问题，可能需要全新的计算范式——状态空间搜索、神经符号混合、或者真正的工作记忆机制，而不是又大一个数量级的 Transformer。
核心要点总结：
SSR 的 PSPACE 完全复杂度使其与已被"解决"的经典游戏不在同一量级
现有 SSR 求解器均为经典规划算法，无一使用 Transformer 架构
LLM 在 SSR 上的失败暴露了四大核心局限：线性推理链、无状态回溯、规划执行耦合、缺乏终止判断
推理增强模型（o3、R1、Gemini 2.5 Thinking、Claude 4）仍未突破这一架构天花板
SSR 不适合做评测 benchmark，但可作为架构压力测试工具
这类问题可能需要全新的计算范式来突破，而非单纯的 scale up
你在用 LLM 尝试高难度谜题时遇到过哪些"看起来能解但实际解不开"的情况？欢迎分享具体案例。
参考文献与延伸阅读
Liu, J. (2023). Further Hardness Results for Stephen's Sausage Roll . MIT Computer Science and Artificial Intelligence Laboratory. （Erik Demaine 团队关于 SSR 复杂度的证明论文）
Demaine, E. D., et al. Push-Push is PSPACE-hard . MIT CSAIL 相关复杂性理论论文。
Stephen's Sausage Roll 官方 Wiki：http://stephenssausageroll.wikia.com/
经典搜索算法参考：Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach （AIMA）第 3 章（搜索）和第 10 章（经典规划）。
关于推理模型与 test-time compute scaling 的讨论，可参考 OpenAI、DeepSeek、Google DeepMind 在 2025 年发布的技术报告。
来源华强北商行 · 数码科技资讯
|手机版|华强北商行
( 粤ICP备17062346号 )
发表于 2026-4-22 06:06
加好友78950405
