Codeforces難題不夠刷？謝賽寧等造了AI出題機，能生成原創(chuàng)編程題

機器之心報道

編輯：Panda

Rich Sutton 曾說過：「AI 只能在可以自我驗證的范圍內創(chuàng)造和維持知識。」愛因斯坦與英費爾德在合著的《物理學的進化》中也寫道：「提出一個問題往往比解決問題更重要，后者或許僅僅是數(shù)學或實驗技巧的問題。而提出新的問題、新的可能性，從新的角度審視舊的問題，則需要創(chuàng)造性的想象力，并標志著科學的真正進步。」

隨著大型語言模型（LLM）朝著通用能力邁進，并以通用人工智能（AGI）為最終目標，測試其生成問題的能力也正變得越來越重要。尤其是在將 LLM 應用于高級編程任務時，因為未來 LLM 編程能力的發(fā)展和經(jīng)濟整合將需要大量的驗證工作。

首先，為編程競賽出題需要比解決問題更深刻的算法理解

例如，基礎問題可能會被歸結為可識別的模板，用簡單的技巧就能解決；許多標準的編程問題也常常允許提交部分正確或樣板化的解決方案，這可能會掩蓋錯誤的推理過程。而競賽編程問題有著嚴格的標準，旨在評估對底層算法設計原則、數(shù)據(jù)結構和復雜性權衡的更深層次理解。驗證數(shù)量龐大的可能解法，并充分覆蓋各種捷徑或邊界情況是極具挑戰(zhàn)性的，但這對于競賽編程問題而言是必需的。因此，出題不僅包含了解決問題的所有挑戰(zhàn)，甚至還超越了它。

其次，更好的出題能力將帶來更嚴謹?shù)母傎惥幊袒鶞蕼y試。由于像 Codeforces 和 AtCoder 這類頂級平臺的官方測試數(shù)據(jù)并不公開，研究人員目前依賴于合成的數(shù)據(jù)集，如 CodeContests+、TACO 和 HardTests。

然而，分析表明，現(xiàn)有的測試數(shù)據(jù)集可能同時存在高誤報率（FPR）和高漏報率（FNR)。例如，一個時間復雜度不佳的貪心算法可能會通過一系列小規(guī)模的隨機測試，但卻會在旨在暴露其缺陷的對抗性構造案例面前失敗。這一關鍵弱點造成了一個扭曲的評估環(huán)境，獎勵了那些能發(fā)現(xiàn)捷徑的模型。

第三，成功地提出新穎的挑戰(zhàn)可能為模型的自我完善和 AGI 鋪平道路，同時也能驗證模型在復雜軟件棧中的部署情況

那么，我們能否像訓練 AI 解決問題一樣，訓練它提出高質量、甚至是人類想不到的新問題呢？最近，LiveCodeBench Pro 團隊給出了一個響亮的回答：AutoCode。這是一個系統(tǒng)性的框架，可在一個閉環(huán)、多角色的系統(tǒng)中使用 LLM，以自動化競賽編程問題創(chuàng)建和評估的整個生命周期。

• 論文標題：AutoCode: LLMs as Problem Setters for Competitive Programming
• 論文地址：https://arxiv.org/abs/2510.12803v1
• 項目頁面：https://livecodebenchpro.com/projects/autocode/overview

值得注意的是，該團隊包含來自十個機構的研究者，共有 5 位共同一作。此外，作者名單中還包括謝賽寧等著名研究者。

整體而言，這項研究做出了兩大貢獻：

• 一個增強的驗證器-生成器-檢查器（Validator-Generator-Checker）框架，它在測試用例生成方面實現(xiàn)了最先進的可靠性。
• 一個用于生成高質量新問題的創(chuàng)新過程。該過程是從一個「種子問題」開始，以在一個有前景的方向上啟發(fā) LLM。

測試用例生成

該團隊的測試用例生成過程是一個結構化的框架，旨在實現(xiàn)最大程度的嚴謹性和覆蓋率。

如圖 1 所示，該框架始于驗證器（Validator)，它是整個系統(tǒng)的基石。其功能是確保任何給定的輸入都嚴格遵守問題描述中指定的所有約束。一個驗證器對于最小化漏報率（FNR）至關重要，因為它能防止正確的程序在格式錯誤的數(shù)據(jù)上失敗。

接下來，生成器采用多樣化的策略來創(chuàng)建廣泛的輸入，旨在減少誤報率（FPR)，即錯誤或低效的程序被錯誤地判定為正確。生成器產(chǎn)生的任何無效案例都會被驗證器過濾掉，從而確保該團隊獲得一套高質量的輸入。

最后，為了評估參賽者的輸出，檢查器會將其與參考解法的輸出進行比較。

而對于交互式任務，交互器（Interactor）會與參賽者的程序進行多輪對話以給出最終判決。

由于該團隊的一個突出目標是為 RLVR（Reinforcement Learning from Verified Results）提供高質量的驗證器，該團隊特別關注降低誤報率（FPR)。該團隊將測試用例（test cases)（輸入 - 答案對）與測試數(shù)據(jù)（test data）區(qū)分開來，后者還包括評估所需的檢查器和交互器程序。

基準測試：測試用例的穩(wěn)健性

為了嚴格評估該團隊的測試用例生成框架，他們建立了兩個不同的基準。

主要基準包含 7538 個問題，來源于著名現(xiàn)有數(shù)據(jù)集的交集：CodeContests+、CodeContests、HardTests 和 TACO。

值得注意的是，這個大規(guī)模集合不包含交互式問題，并且由于這些數(shù)據(jù)集固有的篩選，其測試數(shù)據(jù)生成的平均難度略低于典型的 Codeforces 比賽。

為了解決這個問題并在更具挑戰(zhàn)性的真實條件下測試新系統(tǒng)，該團隊創(chuàng)建了第二個基準，包含了 720 個來自 Codeforces 的近期、有評分的比賽問題。這個集合是完全未經(jīng)過濾的，包括了那些以難以處理著稱的交互式問題和需要復雜、結構化測試數(shù)據(jù)的問題。該團隊表示，無法在這個較新的基準上評估先前的方法，因為它們的數(shù)據(jù)生成代碼庫并未公開。

該團隊的評估基于三個關鍵指標：

• 一致性（Consistency）衡量該團隊的測試得出的判決與官方判決之間一致的總體百分比。該團隊進一步將不一致的情況分解為兩個關鍵的錯誤率。
• 誤報率（FPR）定義為被該團隊的生成測試錯誤地接受的官方不正確解法的比例。
• 漏報率（FNR）是被該團隊的測試錯誤地拒絕的官方正確解法的比例。

與其他基準的比較

該團隊在包含 7538 個問題的基準上，將 AutoCode 與四個領先的基準進行了評估。

如表 1 所示，該團隊的框架與官方判決的一致性達到了 91.1%。這標志著一個重大的飛躍，因為之前的方法的一致性未能超過 81.0%。至關重要的是，AutoCode 將誤報率（FPR）大幅降低至僅 3.7%，漏報率（FNR）降低至 14.1%，這代表著這兩項指標相較于當前最先進技術均減少了約 50%。

圖 2 展示了錯誤判決的分布，顯示了大多數(shù)問題的判決與地面真實判決是一致的。

為了進一步測試該系統(tǒng)的穩(wěn)健性，該團隊還整理了一個更具挑戰(zhàn)性的基準，包含了 720 個近期的、未經(jīng)過濾的 Codeforces 問題，包括復雜的交互式任務。

如表 2 所示，AutoCode 保持了其卓越的性能，實現(xiàn)了 98.7% 的一致性。這一結果驗證了該團隊的方法在現(xiàn)代、困難問題上的有效性，而先前的方法無法在這些問題上進行評估。

該團隊也通過消融實驗驗證了方法的有效性。

在建立起如此強大的測試用例生成能力之后，研究人員便將目光投向了更具創(chuàng)造性的任務：直接生成全新的高質量問題

問題生成

該團隊新提出的問題生成框架建立在前述的穩(wěn)健測試生成框架（如圖 1 所示）之上，但引入了一個關鍵的雙重驗證協(xié)議，以確保在沒有人工干預的情況下實現(xiàn)正確性。

每個生成的問題都由頂尖的人類競賽程序員根據(jù)一個 6 級量表進行評分。該團隊咨詢 8 位人類專家出題人，他們都表示在創(chuàng)作新問題時，常常會基于某個特定的現(xiàn)有問題。通過對這樣一個「種子問題」的某些條件進行添加、刪除或修改，他們可以創(chuàng)造出新的、通常更困難的、需要新穎洞察力的問題。

受他們見解的啟發(fā)，該團隊的方法是首先隨機選擇一個 Codeforces 問題（難度評分低于 2200）作為「種子問題」。LLM 的任務是通過增、刪、改這個種子問題的某些條件來生成一個新問題，并同時提供一個高效的參考解法（std.cpp）和一個暴力解法（brute.cpp)

brute.cpp 通常時間復雜度更高，但基本不可能出錯，因此該團隊利用它來壓力測試問題的有效性。使用該團隊增強的測試用例生成技術，該團隊構建了一套全面的測試數(shù)據(jù)，完全覆蓋了小規(guī)模案例。然后 brute.cpp 和 std.cpp 都在這個數(shù)據(jù)集上運行。只有當對于每一個測試用例，兩個程序的輸出（其中暴力解法可能因超時而合法地無法完成）都被檢查器成對地驗證為一致的答案和輸出時，一個問題才被認為是正確的。

這種設計的巧妙之處在于，它利用了「雖然慢但幾乎絕不會錯」的暴力解法，為「雖然快但可能存在邏輯漏洞」的高效解法提供了一個無需人工干預的、絕對可靠的「事實標準」，從而實現(xiàn)了自動化的正確性校驗。

這個雙重驗證協(xié)議（其中 brute.cpp 作為初始的地面真實，并且經(jīng)過驗證的參考解法還要再經(jīng)過一個完整的測試生成周期）成功地過濾掉了 27% 的易錯問題，將 LLM 提供的參考解法的正確率從 86% 提高到了 94%。

經(jīng)過篩選后，超過 80% 的問題被標注為具有足夠的質量，可以作為模型的訓練數(shù)據(jù)，并且 23% 的問題涉及新穎或創(chuàng)造性的設計。該團隊在圖 3 中展示了詳細的評分標準和分數(shù)分布。

接下來，該團隊總結了關于 LLM 在問題生成方面表現(xiàn)的幾個關鍵發(fā)現(xiàn)。

• 發(fā)現(xiàn) 1：LLM 能夠生成它們自己無法解決的可解問題。
• 發(fā)現(xiàn) 2：LLM 傾向于通過組合現(xiàn)有問題框架和強調知識與實現(xiàn)來創(chuàng)造新問題。也就是說，LLM 更擅長「知識重組」，而非原創(chuàng)創(chuàng)新。
• 發(fā)現(xiàn) 3：新問題的難度增幅往往大于種子問題，且當相應種子問題難度適中時，生成問題的質量最高。
• 發(fā)現(xiàn) 4：人類專家和 LLM 在對問題質量和新穎性的判斷上幾乎沒有相關性。
• 發(fā)現(xiàn) 5：生成問題的難度和相較于種子問題的難度增益，是比 LLM 自我評估更好的問題質量指標。

總而言之，這些發(fā)現(xiàn)為我們描繪了當前 LLM 在創(chuàng)造性任務上的清晰畫像：LLM 是強大的「知識重組者」，而非一個真正的「原創(chuàng)思想家」

總結

在這項工作中，LiveCodeBench Pro 團隊提出了AutoCode，一個利用 LLM 作為競賽編程出題人的閉環(huán)多角色框架。

通過將驗證器-生成器-檢查器（及交互器）框架與雙重驗證協(xié)議相結合，AutoCode 在測試用例生成方面實現(xiàn)了最先進的可靠性，并超越了先前的方法，能夠生成全新的、達到競賽質量的問題。

在超過 7,500 個問題和近期的 Codeforces 基準上的大量實驗表明，AutoCode 大大減少了誤報和漏報，與官方判決的一致性超過 98%，并成功地產(chǎn)生了經(jīng)專家程序員驗證的全新問題。除了測試生成，該團隊的分析還揭示了 LLM 在創(chuàng)造性問題創(chuàng)作方面的優(yōu)勢和劣勢。

雖然模型擅長算法知識的重組，但它們難以引入真正新穎的推理范式或無懈可擊的樣例設計。

盡管如此，該團隊表明，難度和難度增益可以作為問題質量的可靠智能體信號，為實現(xiàn)自我博弈提供了一條可擴展的路徑。