Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling
作者: Fanzeng Xia, Yidong Luo, Tinko Sebastian Bartels, Yaqi Xu, Tongxin Li
分类: cs.AI, cs.CL, cs.LG
发布日期: 2025-05-28
💡 一句话要点
结合上下文搜索与测试时缩放，显著提升LLM在超难推理任务上的性能
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大型语言模型 上下文学习 推理能力 测试时缩放 NP-hard问题
📋 核心要点
- 现有评估方法未能充分挖掘LLM的推理潜力，尤其是在超难推理任务上，简单提示限制了LLM的性能。
- 论文提出结合上下文搜索提示和测试时缩放，以增强LLM的推理能力，从而突破现有性能瓶颈。
- 实验表明，该方法在NP-hard任务和真实世界规划基准上，成功率提升高达30倍，并扩展了可解决问题的复杂性。
📝 摘要（中文）
最近的研究表明，即使经过训练能够生成扩展的长推理步骤，大型语言模型(LLM)在困难的推理问题上仍然面临重大挑战。然而，现有文献大多依赖于直接提示和简单的上下文学习示例进行评估，这在很大程度上忽略了在得出结论之前引发LLM进行审慎推理的先进技术，从而导致LLM的性能达到上限。在本文中，我们系统地探索了上下文搜索和测试时缩放在超难推理任务上的组合潜力。我们发现，通过采用先进的上下文搜索提示来增强具有内部缩放的LLM，可以在先前被认为是“无法解决”的任务上实现变革性的性能突破（例如，报告的成功率低于5%）。我们提供了经验结果和理论分析，说明这种组合如何释放LLM的推理能力：i) 在受控的NP-hard任务和复杂的真实世界规划基准上，与之前报告的结果相比，我们的方法在没有任何外部机制的情况下，成功率提高了30倍；ii) 从理论上讲，我们表明，上下文搜索提示与内部缩放相结合，显著扩展了可解决推理问题的复杂性类别。这些发现挑战了关于LLM在复杂任务上的局限性的普遍假设，表明当前的评估范式系统地低估了它们的真正潜力。我们的工作呼吁对LLM推理的基准测试方式进行批判性重新评估，并提出一种更强大的评估策略，以充分捕捉当代LLM的真实能力，从而更好地理解它们在实际部署中的操作推理边界。
🔬 方法详解
问题定义：论文旨在解决大型语言模型(LLM)在超难推理任务上的性能瓶颈问题。现有方法，如直接提示和简单的上下文学习，无法充分激发LLM的推理能力，导致其在复杂问题上的表现不佳。这些方法忽略了LLM在推理过程中的审慎思考和探索，使得评估结果低估了LLM的真实潜力。
核心思路：论文的核心思路是结合上下文搜索提示和测试时缩放，以增强LLM的推理能力。上下文搜索提示旨在引导LLM探索不同的推理路径，而测试时缩放则通过调整LLM的内部参数来提高其推理能力。通过这种组合，LLM可以更有效地解决复杂的推理问题。
技术框架：整体框架包含两个主要组成部分：上下文搜索提示和测试时缩放。首先，使用上下文搜索提示引导LLM生成多个可能的推理路径。然后，对每个推理路径进行评估，并选择最佳路径。最后，使用测试时缩放来优化LLM的内部参数，以进一步提高推理性能。该框架无需外部机制，完全依赖于LLM自身的推理能力。
关键创新：最重要的技术创新点在于将上下文搜索提示和测试时缩放相结合，从而显著提升了LLM在超难推理任务上的性能。与现有方法相比，该方法能够更有效地激发LLM的推理能力，并突破了现有性能瓶颈。此外，论文还从理论上证明了该方法可以扩展可解决推理问题的复杂性类别。
关键设计：上下文搜索提示的具体实现方式包括：使用不同的提示模板、调整提示的长度和复杂度、以及使用不同的搜索算法。测试时缩放的具体实现方式包括：调整LLM的温度参数、调整LLM的采样策略、以及使用不同的优化算法。论文还详细描述了如何选择合适的参数设置，以最大化推理性能。
🖼️ 关键图片
📊 实验亮点
实验结果表明，在受控的NP-hard任务和复杂的真实世界规划基准上，该方法与之前报告的结果相比，成功率提高了高达30倍。这一显著的性能提升表明，结合上下文搜索提示和测试时缩放可以有效提升LLM在超难推理任务上的能力，并挑战了现有评估范式对LLM能力的低估。
🎯 应用场景
该研究成果可应用于各种需要复杂推理的领域，如智能规划、问题求解、决策支持等。通过提升LLM在复杂任务上的性能，可以实现更智能、更高效的自动化系统，例如，在医疗诊断、金融分析、法律咨询等领域提供更准确的建议。
📄 摘要（原文）
Recent research has highlighted that Large Language Models (LLMs), even when trained to generate extended long reasoning steps, still face significant challenges on hard reasoning problems. However, much of the existing literature relies on direct prompting with simple in-context learning examples for evaluation, which largely overlooks advanced techniques to elicit LLMs' deliberate reasoning before drawing conclusions that LLMs hit a performance ceiling. In this paper, we systematically explore the combined potential of in-context search and test-time scaling on super hard reasoning tasks. We find that by employing advanced in-context search prompting to LLMs augmented with internal scaling, one can achieve transformative performance breakthroughs on tasks previously deemed "unsolvable" (e.g., reported success rates below 5%). We provide both empirical results and theoretical analysis of how this combination can unleash LLM reasoning capabilities: i) Empirically, on controlled NP-hard tasks and complex real-world planning benchmarks, our approach achieves up to a 30x improvement in success rates compared to previously reported results without any external mechanisms; ii) Theoretically, we show that in-context search prompting, when combined with internal scaling, significantly extends the complexity class of solvable reasoning problems. These findings challenge prevailing assumptions about the limitations of LLMs on complex tasks, indicating that current evaluation paradigms systematically underestimate their true potential. Our work calls for a critical reassessment of how LLM reasoning is benchmarked and a more robust evaluation strategy that fully captures the true capabilities of contemporary LLMs, which can lead to a better understanding of their operational reasoning boundaries in real-world deployments.