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

機(jī)器之心報道

編輯：Panda

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

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

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

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

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

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

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

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

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

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

整體而言，這項研究做出了兩大貢獻(xiàn)：

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

測試用例生成

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

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

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

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

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

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

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

為了嚴(yán)格評估該團(tuán)隊的測試用例生成框架，他們建立了兩個不同的基準(zhǔn)。

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

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

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

該團(tuán)隊的評估基于三個關(guān)鍵指標(biāo)：

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

與其他基準(zhǔn)的比較

該團(tuán)隊在包含 7538 個問題的基準(zhǔn)上，將 AutoCode 與四個領(lǐng)先的基準(zhǔn)進(jìn)行了評估。

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

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

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

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

該團(tuán)隊也通過消融實驗驗證了方法的有效性。

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

問題生成

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

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

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

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

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