MLNLP
社群是國內外知名的機器學習與自然語言處理社群，受眾覆蓋國內外NLP碩博生、高校老師以及企業研究人員。
社群的願景是促進國內外自然語言處理，機器學習學術界、產業界和廣大愛好者之間的交流和進步，特別是初學者同學們的進步。
來源 | 新智元
編輯 | Aeneas 好睏
社群是國內外知名的機器學習與自然語言處理社群，受眾覆蓋國內外NLP碩博生、高校老師以及企業研究人員。
就在剛剛，南航、南通大學、牛津等機構的研究者發現：透過高指令的推理指令，DeepSeek-R1有望解決數學上的NP-hard問題！
論文地址：https://arxiv.org/abs/2502.20545
NP-hard問題，是計算複雜性理論中的一類問題。它們至少和NP問題一樣難，但不一定屬於NP類別（即不一定中多項式時間內被驗證）。
本來，DeepSeek-R1、GPT-4o、OpenAI o1-mini這些模型，是做某種數學推理難題（SoS）是很困難的，正確率也就比純猜高一點。
但是，一旦給它們一些推理指導，所有的模型的推理能力立馬噌噌上漲，專業率最高提升了21%。
更令研究者們吃驚的是，Qwen2.5-14B-Instruct-1M在指導下，居然用了一個新奇精巧的方法，給出了一個此前從未見過的希爾伯特問題的反例：
要知道，希爾伯特問題的反例，可並非簡單推導就能得出來的。
自1893年問題被提出之後，首個反例的發現耗時長達27年！
如今，卻被LLM短時間內破解了。
研究者們大膽預言：照這個速度演進，LLM離破解NP-hard問題已經很近了。
LLM能解決希爾伯特第十七問題嗎？
如今，LLM在眾多工上，表現已經接近人類水平，但它們在嚴謹數學問題求解上的能力，仍是不小的挑戰。
這次，研究者決定給大模型們來一個硬核難題——判斷給定的多元多項式是否為非負的。
這個問題，和希爾伯特第十七問題密切相關。後者由數學家希爾伯特在1900年提出後，立馬成為23個經典數學問題之一。
而且，許多應用數學和計算數學中的關鍵挑戰，都可以轉化為判斷某些多項式的非負性問題，比如控制理論、量子計算、多項式博弈、張量方法、組合最佳化等。
然而，判斷一般多項式是否非負，是一個公認的NP-hard問題！
即使對於相對低階或僅含少量變數的多項式，此問題仍然極具挑戰性。
怎麼辦？為此，研究者們只能去尋找多項式的特殊類別，將複雜的非負性約束，替換成更簡單一些的條件。
由此，平方和（SoS）條件就登場了。
作為一項數學技術，它透過將多項式表示為若干平方項的和，提供了一種充分但非必要的非負性判定方法。
所以，OpenAI o1和DeepSeek-R1，能解決SoS條件規劃問題嗎？
用一個數據集，給LLM專業推理指導
為此，研究者構建了SoS-1K資料集。
這個資料集經過了精心策劃，包含約1,000個多項式，並配備了五個精心設計的專家級SoS專業推理指導。
具體包括：
-
多項式階數 -
主導搜尋方向的非負性 -
特殊結構的識別 -
平方形式表達的評估 -
單項式的二次形式矩陣分解
接下來，屬於SOTA模型們的考驗來了！
DeepSeek-R1、DeepSeek-V3、GPT-4o、OpenAI o1-mini、Qwen2.5 系列和 QwQ-32B-Preview在內的多位明星大模型，接受了數學難題的洗禮。
研究者們得出了一系列有趣的發現。
首先，如果未提供任何推理指導，所有的SOTA模型幾乎都無法解決SoS問題。
它們的準確率基本都在60%，僅僅略高於50%的隨機猜測基線。
不過，一旦使用高質量的推理軌跡進行提示，所有模型的準確率就立馬有了顯著提升！
最高的提升了21%，而且推理質量越高，模型表現就越好。
另外還有兩點發現：專注於推理的LLM通常優於通用LLM，無論提示質量如何。
引數較大的模型通常只用更少的推理步驟，就能正確預測，而小模型要達到最佳效能，就需要更多的推理過程了。
14B模型竟發現了此前未見的希爾伯特問題反例
然後，研究者還進一步證明，對一個預訓練的7B模型在SoS1K資料集上進行4小時的監督微調後，僅使用2張A100 GPU，就能讓它準確率從54%暴增至70%，響應速度也大幅提高。
其中，SoS-7B僅需DeepSeek-V3和GPT-4o-mini計算時間的1.8%和5%。
也就是說，這個7B模型超越了671B的DeepSeek-V3和GPT-4o-mini在內的更大規模模型。
然後，驚人的結果來了——
當模型被輸入高質量的推理提示時，甚至在研究級問題上做出了革命性的突破。
比如，Qwen2.5-14B-Instruct-1M就利用Motzkin多項式，生成了全新的、此前未見的希爾伯特第十七問題的反例。
具體來說，模型是如何發現這個反例的？
研究者展示了以下過程：透過SoS Reasoning提示，Qwen-14B-1M推匯出了一個新的有效NNSoS示例：
模型構建這個例子的方法，非常新奇有趣，令研究者讚歎不已。
它從NNSoS的著名例子開始，如：
，然後，引入了一個新變數並稍微修改了係數，進而生成了q_a。
這也就給了我們極大信心：按照如今LLM展現出的推理能力，或許有朝一日，它們真能破解NP-hard問題。
值得一提的是，團隊只用2張英偉達A100 GPU，耗時4小時就完成了對Qwen2.5-7B-Instruct-1M的微調。
由此得到的SoS-7B模型達到了70%的總體準確率，超過了671B引數量的DeepSeek-V3（69%），同時響應時間僅需1.8秒，而DeepSeek-V3則需要100秒。
SoS-1K Dataset
首先，研究者對SoS多項式做出了定義。
隨後，研究者們為LLM精心設計了指令，從而提供了結構化的分析框架，明確了約束條件，優化了邏輯推理流程，讓它們顯著提高了解題能力。
為此，他們構建了三種不同層次的的推理指令集。
1. 基礎SoS指令（SoS Plain）
直接向LLM提問：「請分析該多項式是否可以表示為平方和（SoS）」？
2. 簡化SoS指令（SoS Simple）
將SoS多項式劃分為五個不同類別，每個類別由簡潔的一行標準定義。
3. 基於推理的完整SoS指令（SoS Reasoning）
這是一個結構化的五步框架，用來系統化識別SoS多項式。
而就是這個SoS Reasoning，成為了LLM解決數學研究級問題的基礎，讓它們的能力擴充套件到更復雜的數學推理任務。
下面就是一個SoS Reasoning的示例。
-
步驟1. 檢查次數：SoS多項式的最高次數必須是偶數。 -
步驟2. 檢查非負性：SoS多項式對所有實數輸入都應為非負值。 -
步驟3. 檢查已知特例：任何非負二次多項式以及任意一元或二元的非負四次多項式均為SoS。 -
步驟4. 檢查平方形式：根據定義2.1，SoS多項式可表示為：p_s(x) = ∑_i{q_i(x)²}。其中，每個q_i(x)均為多項式。 -
步驟5. 檢查矩陣分解：根據定理B.1，可以將多項式表示為：p(x) = y*ᵀQy*。其中，Q為對稱矩陣。隨後，檢查Q是否為半正定矩陣。
SoS任務上的LLM評估
在SoS-1K資料集中，研究者隨機抽取了約340道測試題，涵蓋了所有測試子類別。
參與評估的有專門的推理模型（如DeepSeek-R1、OpenAI o1-mini 和QwQ-32B-Preview），以及通用大模型（如DeepSeek-V3、GPT-4o 和Qwen2.5系列）。
結果如下。
模型對SoS和非負性的理解
有人可能會問：
-
模型是隻學會了分類，還是真正發展出了「思考」和「構建」新證明和示例的能力？ -
當面對SoS或多項式最佳化中的研究問題時，模型能否生成具有數學意義的見解？
為了探索這一點，團隊設計了一系列研究導向的問題來測試模型理解SoS和非負性質背後數學概念的能力。
比如，問Qwen-7B-1M和Qwen14B-1M：你能提供一個文獻中從未出現過的新NNSoS嗎？
有趣的是，當使用SoS Plain提示時，Qwen-14B-1M只能給出文獻中已知的例子，而Qwen-7B-1M返回了一個不正確的答案：
雖然回答錯誤，但這個問題挑戰性極大，即便像YALMIP這樣的經典求解器也無法提取全域性最優性。
然而，當使用SoS Reasoning提示向模型提出相同的研究問題時，模型正確地識別出了pa不是問題的有效解。
這一改進源於SoS推理的第4步，其中模型認識到p_a(x)是兩個變數的非負四次多項式，因此不可能是NNSoS。
進一步分析
Q1：模型是否遵循真正的數學逐步驗證過程？
結果顯示，LLM能夠按照SoS推理指令，一步一步生成邏輯和數學都正確的答案。
比如在下面這個例子中，o1-mini的回覆不僅在邏輯上和數學上是正確的，而且一旦模型推匯出答案就自然停止，而不是盲目地遍歷所有可能的步驟。
Q2：模型能否有效地從長文字多項式中提取關鍵資訊？
與標準文字輸入不同，多項式是由變數、係數、指數和項組成的複雜代數表示式。因此，對於LLM來說，有效解釋和提取此類結構化格式中的關鍵資訊至關重要。
分析表明，雖然QwQ-32B-Preview在處理超過4K token長度的問題時會遇到困難，但大多數SOTA的模型都能夠成功地從4K長度的多項式中提取必要的係數進行評估，並生成正確的答案。
Q3：在SoS推理的第1步到第5步中，哪一步的準確率有所提高？
圖2展示了o1-mini模型在基礎SoS（SoS Plain）、簡化SoS（SoS Simple）和完整SoS推理（SoS Reasoning）下不同測試集的準確率提升情況。
結果顯示，最簡單的Test Set 1（對應步驟1）在所有提示方法下，都毫無意外地達到了100%的準確率。
得益於步驟2和步驟5，對於更具挑戰性的Test Sets 2a、3.1a、5.1a–5.4a，從基礎SoS到簡化SoS再到完整SoS推理，也都有持續的改進。
因為，這些步驟引入了一系列用於非負性驗證的數學方法，包括常數係數檢查、網格求值、首項和主導項比較、尋找最小值、矩陣分解以及尋找對稱性和平移。
Q4：模型在推理過程中會「偷懶」嗎？
是的，在SoS推理提示下觀察到的另一個有趣現象是，模型在執行第5步時往往會「走捷徑」。
具體而言，它通常會避免完全執行第5步中的矩陣分解或半正定規劃（SDP）等複雜操作，而是基於前面步驟的結果推測答案。這種行為在處理長輸入和複雜多項式時尤為普遍。
對於較簡單的問題，推理模型如o1-mini（執行時間最短，為17秒）和較大的模型如QwQ-32B-Preview往往會採取捷徑，跳過第5步，從前面更簡單的步驟中推斷答案。
而DeepSeek-V3則不會走捷徑，而是花費明顯更多的時間（40秒）正確地解決所有步驟。
Q5：推理長度如何影響準確性？
如圖3所示，更高效能的模型通常需要更少的思考所需token數量來做出正確預測，而效能較低的模型需要更多的推理步驟才行。
例如，DeepSeek-R1和o1-mini在1K-2K的輸出長度下，就達到最高的正確預測數量；而Qwen2.5系列需要3K-4K個token才能產生正確答案。
Q6：當前的SOTA模型有什麼侷限性？
首先，對於長輸入情況，會出現無效樣本。例如，在DeepSeek-R1中，340個樣本中只有234個是有效的。
其次，在處理複雜問題時，「走捷徑」雖然會節省時間，但在困難步驟時過早停止並猜測答案，會對準確性產生負面影響。
第三，雖然這些模型在處理小型多項式時表現出色（準確率接近90%），但在多項式的二次型涉及低秩矩陣分解時，表現不佳。
參考資料：
https://arxiv.org/abs/2502.20545
技術交流群邀請函
△長按新增小助手
掃描二維碼新增小助手微信
關於我們