A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings¶

会议: NeurIPS 2025 arXiv: 2505.24550 代码: GitHub 领域: LLM推理 / 模型压缩 关键词: reasoning efficiency, CoT compression, A* search, bidirectional importance, long-to-short

一句话总结¶

提出 A-Thought——基于 A 搜索算法的 CoT 压缩框架，通过双向重要性评分（BIS）衡量每个推理步骤对问题和答案的相关性，结合路径级 A* 搜索在指数级搜索空间中高效找到最紧凑的推理路径，在 512 token 预算下将 QwQ-32B 准确率提升 2.39 倍，在 4096 token 预算下减少约 50% 输出 token 且几乎不损失准确率。

研究背景与动机¶

领域现状：大型推理模型（LRM）如 o1、R1、QwQ 通过长链推理（CoT）获得强大推理能力，但冗长的思考轨迹导致巨大推理开销，严重限制资源受限场景的部署。
现有痛点：(a) 现有 long-to-short 方法多假设"过度思考"并尝试直接压缩 CoT，但往往导致性能下降；(b) prompt-based 方法（如 CoD）压缩不够精准；(c) 训练-based 方法（如 TokenSkip）需要额外训练且效果有限；(d) 没有统一框架从 exponential 搜索空间中系统性地找到最优子集。
核心矛盾：CoT 中不是所有步骤都同等重要，但识别哪些步骤必要、哪些可删除是组合爆炸问题——N 个步骤有 \(2^N\) 种子集。
切入角度：将 CoT 压缩形式化为搜索问题，用 A* 算法在排序后的推理步骤上高效搜索。
核心 idea 一句话：双向重要性评分（同时考虑步骤与问题和答案的相关性）+ A* 搜索（当前路径质量 + 未来到达正确答案的估计成本），在巨大搜索空间中找最短有效推理路径。

方法详解¶

整体框架¶

两层设计：(1) 步骤级——用双向重要性评分（BIS）评估每个推理步骤的关键程度，指导搜索优先级；(2) 路径级——用 A* 搜索算法在搜索树上迭代扩展，通过代价函数找到最短且能到达正确解的推理路径。

关键设计¶

双向重要性评分 (BIS):
做什么：量化每个推理步骤 \(\mathbf{t}^{(n)}\) 的重要性
核心思路：一个好的中间步骤应同时与问题（前向）和答案（后向）高度相关
注意力层面：\(\text{ATTN}(\mathbf{q}|\mathbf{t}^{(n)})\) 和 \(\text{ATTN}(\mathbf{s}|\mathbf{t}^{(n)})\)
模型层面：\(\text{NLL}(\mathbf{q}|\mathbf{t}^{(n)})\) 和 \(\text{NLL}(\mathbf{s}|\mathbf{t}^{(n)})\)
BIS = 注意力得分加权和 / NLL 加权和，用 \(\alpha\) 控制问题 vs 答案的权重
用轻量模型（GPT-2）计算，效率高
关键观察：BIS 分布高度不均——只有少数步骤同时对问题和答案有高贡献
路径级 A* 搜索:
做什么：在 \(2^N\) 的搜索空间中高效找最短有效推理路径
初始化：按 BIS 降序排列所有步骤，构建搜索队列（best-first 策略）
每个节点：不是单个步骤，而是"步骤 + 前后邻居"的三元组 \(\mathbf{r}^{(n)} = \langle \mathbf{t}^{(n-1)}, \mathbf{t}^{(n)}, \mathbf{t}^{(n+1)} \rangle\)——缓解碎片化问题
验证：当路径深度 ≥ \(k_{min}\) 时，用验证模型检查当前路径能否导向正确答案
扩展：验证失败则从队列中取 W 个候选步骤作为子节点
代价函数设计:
总代价：\(f = g + h\)（经典 A* 框架）
当前代价 \(g\)：验证模型对当前路径的负对数似然（路径质量）
未来代价 \(h\)：给定当前路径后生成正确答案的条件自信息 \(\mathcal{I}(\mathbf{s}|\mathbf{q}, \mathbf{t}'_k) = -\frac{1}{|\mathbf{s}|}\log P_\mathcal{V}(\mathbf{s}|\mathbf{q}, \mathbf{t}'_k)\)
直觉：\(h\) 越大说明当前路径离正确答案越远，需要更多步骤补充
深度上界 \(k_{max}\) 防止搜索过深

训练与蒸馏¶

A* 搜索本身用于离线压缩 CoT 数据
压缩后的紧凑推理路径用于 SFT 蒸馏：让 LRM 学会直接生成高效推理
验证模型：s1.1-32B
训练数据：s1K-1.1 数据集的长 CoT

实验关键数据¶

主实验（QwQ-32B，不同 token 预算）¶

方法	512 Avg Acc.	512 ACU	1024 Avg Acc.	2048 Avg Acc.	4096 Avg Acc.	4096 Avg Len.
QwQ-32B baseline	12.3%	2.41	21.8%	43.8%	63.2%	2812
+ CoD	17.3%	3.34	24.3%	51.3%	69.3%	2804
+ BtC Effective	19.5%	3.80	25.0%	52.3%	68.6%	2795
+ TokenSkip	16.6%	3.20	22.8%	48.8%	64.9%	2549
*+ A-Thought**	29.4%	5.99	48.1%	58.9%	69.3%	1877

域外泛化（LiveCodeBench + MMLU）¶

预算	QwQ-32B Acc.	+ A*-Thought Acc.	+ A*-Thought ACU
512	18.8%	30.6%	6.74
1024	28.7%	41.9%	5.37
4096	45.8%	59.7%	3.16

关键发现¶

低预算提升巨大：512 token 下准确率从 12.3% → 29.4%（2.39×），ACU 从 2.41 → 5.99（2.49×）
高预算减 token 不掉点：4096 下平均长度从 2826 → 1877（-33.6%），准确率几乎不变（70.6% → 69.3%）
跨模型通用：在 QwQ-32B、R1-Distill-32B、s1.1-32B 上均有效
域外泛化：仅在数学数据上训练，LiveCodeBench 和 MMLU 上也显著提升

亮点与洞察¶

将 CoT 压缩形式化为搜索问题：从组合优化的视角看待推理压缩，比启发式删除更系统
双向重要性的关键洞察：仅考虑与问题的相关性不够，还需考虑与答案的相关性——中间步骤即使表面不相关，如果对推导答案有贡献也应保留
三元组节点设计：不是孤立地选择步骤，而是保留上下文（前后邻居），避免碎片化的推理链
A* 搜索的自然适配：代价函数设计精巧——当前代价衡量路径质量，未来代价衡量到达答案的难度

局限性 / 可改进方向¶

依赖已有完整 CoT：A* 搜索是后处理方法，需要先生成完整长 CoT 再压缩，无法减少首次推理成本
验证模型开销：A* 搜索过程中每次扩展和验证都需调用 32B 验证模型，搜索过程本身有成本
BIS 依赖最终答案：计算 BIS 需要知道正确答案 \(\mathbf{s}\)，限制了在无标注场景的直接应用
改进方向：(1) 训练一个前向 BIS 预测器（不需要答案）；(2) 探索在线 CoT 压缩（边生成边剪枝）；(3) 用更小的验证模型降低搜索成本

评分¶

新颖性: ⭐⭐⭐⭐ A* 搜索 + 双向重要性评分的组合原创且有洞察
实验充分度: ⭐⭐⭐⭐ 三个模型 × 四个预算 × 六个 benchmark，消融充分
写作质量: ⭐⭐⭐⭐ 问题定义清晰，方法推导严谨
价值: ⭐⭐⭐⭐ 对资源受限场景下的 LRM 部署有直接实用价值