title: SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers
summary: 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.
paper_authors._id: 67c51b459d5807d6674b3d3c
paper_authors.name: Kechen Li
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-03-04T08:51:29.578Z
paper_authors._id: 6742deb4d3ad4510c12da658
paper_authors.avatarUrl: /avatars/91407d854560ef9a2facd80fa8fab6ec.svg
paper_authors.fullname: Kechen Li
paper_authors.type: user
paper_authors.user: Kechen-Li
paper_authors._id: 67c51b459d5807d6674b3d3d
paper_authors.name: Wenqi Zhu
paper_authors._id: 67c51b459d5807d6674b3d3e
paper_authors.name: Coralia Cartis
paper_authors._id: 67c51b459d5807d6674b3d3f
paper_authors.name: Tianbo Ji
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-03-03T09:35:49.782Z
paper_authors._id: 64bb61e876a6e2efcc728e22
paper_authors.avatarUrl: /avatars/b0ed1c9f13fd1f2c99d202155001e39b.svg
paper_authors.fullname: Tianbo Ji
paper_authors.type: user
paper_authors.user: jitianbo
paper_authors._id: 67c51b459d5807d6674b3d40
paper_authors.name: Shiwei Liu
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-03-03T11:14:45.635Z
paper_authors._id: 65b04d2291e63920a7898c9e
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/65b04d2291e63920a7898c9e/iUHs235G4bqK-KnH_94ti.jpeg
paper_authors.fullname: Liu
paper_authors.type: user
paper_authors.user: Shiweiliuiiiiiii
paper_title: SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers
paper_summary: 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.
paper_ai_summary: LLMs are investigated for solving nonnegative polynomial problems, showing significant improvement with reasoning instructions, and suggesting potential for tackling NP-hard mathematical challenges.
paper_ai_keywords: Large Language Models LLMs nonnegative polynomials Hilbert's Seventeenth Problem global polynomial optimization SoS-1K reasoning instructions SoS-7B DeepSeek-V3 GPT-4o-mini computational intractability NP-hard problems parameter-efficient fine-tuning