SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers

📄 arXiv: 2502.20545v1 📥 PDF

作者: Kechen Li, Wenqi Zhu, Coralia Cartis, Tianbo Ji, Shiwei Liu

分类: cs.LG

发布日期: 2025-02-27

💡 一句话要点

SoS1：类O1和R1推理的LLM是平方和求解器，显著提升多项式非负性判定能力。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 数学推理 多项式优化 平方和 数据集 微调 推理指令

📋 核心要点

  1. 判定多元多项式非负性是数学难题，现有LLM在此任务上表现不佳，缺乏有效推理能力。
  2. 论文提出SoS-1K数据集和专家设计的推理指令，引导LLM进行结构化数学推理。
  3. 微调后的7B模型SoS-7B在准确率上超越了更大的模型，且计算成本更低，验证了方法的有效性。

📝 摘要（中文）

大型语言模型（LLM）在各种任务中都达到了人类水平的熟练程度，但它们执行严格的数学问题求解的能力仍然是一个开放的挑战。本文研究了一个基本但计算上难以解决的问题：确定给定的多元多项式是否非负。这个问题与希尔伯特第十七问题密切相关，在全球多项式优化中起着关键作用，并在各个领域都有应用。首先，我们引入了SoS-1K，这是一个精心策划的包含约1000个多项式的的数据集，以及基于五个渐进式挑战性标准设计的专家推理指令。评估多个最先进的LLM后，我们发现，在没有结构化指导的情况下，所有模型的性能仅略高于随机猜测基线50%。然而，高质量的推理指令显著提高了准确性，将性能提高到81%。此外，我们基于SoS-1K微调仅4小时的7B模型SoS-7B，在准确性方面优于671B DeepSeek-V3和GPT-4o-mini，同时分别仅需要后两者1.8%和5%的计算时间。我们的发现突出了LLM在推动数学推理边界和解决NP-hard问题方面的潜力。

🔬 方法详解

问题定义：论文旨在解决判定多元多项式是否非负的问题，这是一个NP-hard问题，与全局多项式优化密切相关。现有LLM在解决此类问题时，缺乏有效的数学推理能力，性能接近随机猜测，难以满足实际应用需求。

核心思路：论文的核心思路是通过提供高质量的推理指令，引导LLM进行结构化的数学推理。通过将复杂问题分解为更小的、可管理的步骤，并提供明确的推理路径，使LLM能够更好地理解和解决问题。此外，通过在专门构建的数据集上进行微调，进一步提升LLM在该任务上的性能。

技术框架：论文的技术框架主要包括以下几个部分：1) 构建SoS-1K数据集，包含约1000个多项式样本；2) 设计专家推理指令，基于五个渐进式挑战性标准；3) 使用SoS-1K数据集和推理指令对LLM进行微调；4) 评估微调后的LLM在判定多项式非负性任务上的性能。

关键创新：论文的关键创新在于：1) 提出了SoS-1K数据集，为LLM的数学推理能力评估和训练提供了新的基准；2) 设计了专家推理指令，有效引导LLM进行结构化数学推理，显著提升了性能；3) 证明了通过少量数据微调的小型LLM可以超越大型LLM，表明了数据质量和推理指导的重要性。

关键设计：SoS-1K数据集包含不同难度级别的多项式样本，推理指令的设计遵循由易到难的原则，逐步引导LLM进行推理。微调过程中，使用了标准的反向传播算法和交叉熵损失函数。模型的选择和参数设置可能根据具体实验有所调整，但论文中未详细说明。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，在没有结构化指导的情况下，现有LLM在SoS-1K数据集上的准确率仅略高于50%。然而，通过高质量的推理指令，LLM的准确率可以提升至81%。更重要的是，经过SoS-1K微调的7B模型SoS-7B，在准确率上超越了671B DeepSeek-V3和GPT-4o-mini，同时计算成本显著降低，分别仅为后两者的1.8%和5%。

🎯 应用场景

该研究成果可应用于全局多项式优化、控制理论、机器人学等领域。通过提升LLM的数学推理能力，可以更有效地解决实际工程问题，例如优化控制系统的性能、设计更安全的机器人运动轨迹等。未来，该方法有望扩展到其他NP-hard问题，推动人工智能在科学计算领域的应用。

📄 摘要（原文）

Large Language Models (LLMs) have achieved human-level proficiency across diverse tasks, but their ability to perform rigorous mathematical problem solving remains an open challenge. In this work, we investigate a fundamental yet computationally intractable problem: determining whether a given multivariate polynomial is nonnegative. This problem, closely related to Hilbert's Seventeenth Problem, plays a crucial role in global polynomial optimization and has applications in various fields. First, we introduce SoS-1K, a meticulously curated dataset of approximately 1,000 polynomials, along with expert-designed reasoning instructions based on five progressively challenging criteria. Evaluating multiple state-of-the-art LLMs, we find that without structured guidance, all models perform only slightly above the random guess baseline 50%. However, high-quality reasoning instructions significantly improve accuracy, boosting performance up to 81%. Furthermore, our 7B model, SoS-7B, fine-tuned on SoS-1K for just 4 hours, outperforms the 671B DeepSeek-V3 and GPT-4o-mini in accuracy while only requiring 1.8% and 5% of the computation time needed for letters, respectively. Our findings highlight the potential of LLMs to push the boundaries of mathematical reasoning and tackle NP-hard problems.