LLM通过结构化推理可解决多项式非负性问题，准确率达81%。
SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers
- 设计五级递进的推理指令，引导LLM解决多项式非负性判断
- 7B模型微调4小时后准确率81%，远超671B大模型
- 适合数学推理、优化算法研究者，推动LLM在硬核数学应用
大型语言模型在多种任务中已达到人类水平，但在严谨的数学问题求解方面仍面临挑战。本文研究一个基本但计算上难以处理的问题：判断给定多元多项式是否非负。该问题与希尔伯特第十七问题密切相关，在全局多项式优化中具有关键作用，且在多个领域有广泛应用。我们首次构建了约1000个多项式的精心标注数据集SoS-1K，配合基于五种逐步提升难度标准的专家设计推理指令。评估多个前沿LLM发现，无结构引导下所有模型表现仅略高于随机基线50%；而高质量推理指令可使准确率提升至81%。此外，我们的7B模型SoS-7B仅用4小时微调，便在准确率上超越671B的DeepSeek-V3和GPT-4o-mini，计算时间分别为其1.8%和5%。结果表明LLM具备突破数学推理边界、应对NP难问题的潜力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。