ICML 2026：從輸入輸出樣例中自動生成程序——強(qiáng)化學(xué)習(xí)為大模型Programming-By-Example任務(wù)提供推理過程監(jiān)督

Programming-by-Example的核心目標(biāo)，是從少量輸入輸出樣例中推斷用戶真正想要的程序邏輯。傳統(tǒng)PBE系統(tǒng)通常依賴預(yù)定義DSL，通過符號搜索、遞歸分解或神經(jīng)網(wǎng)絡(luò)引導(dǎo)搜索完成程序合成。隨著大語言模型的發(fā)展，PBE不再必須受限于特定DSL，模型可以直接基于自然語言提示、輸入輸出樣例和推理鏈生成通用語言程序。

然而，論文指出，當(dāng)前LLM-based PBE方法仍存在一個關(guān)鍵缺陷：模型主要學(xué)習(xí)輸入與輸出之間的表層映射，而缺少對中間歸納過程的監(jiān)督。對于復(fù)雜PBE任務(wù)，僅憑樣例進(jìn)行端到端生成容易產(chǎn)生兩類錯誤。一類是模型推斷出完全錯誤的邏輯，例如把“多個列表相同位置元素相等的索引”錯誤理解為簡單集合交集。另一類是模型生成只覆蓋部分樣例的程序，例如任務(wù)要求降序排序，模型卻只執(zhí)行反轉(zhuǎn)操作，從而在部分樣例上看似正確，但無法表達(dá)真實(shí)規(guī)則。

這些失敗說明，PBE的難點(diǎn)并不只是最終代碼是否通過測試，而在于模型是否能夠在推理過程中逐步接近樣例背后的潛在意圖。若缺少對推理步驟的顯式監(jiān)督，模型很容易沿著錯誤歸納方向繼續(xù)生成，并最終得到看似合理但邏輯不完整的程序。

針對PBE中間推理過程難以監(jiān)督的問題，論文提出反饋引導(dǎo)的推理樹構(gòu)建方法。推理樹中的每個節(jié)點(diǎn)表示一個自然語言形式的中間推理步驟，模型從輸入輸出樣例出發(fā)，逐步采樣后繼推理節(jié)點(diǎn)，直到形成完整推理路徑。由于這些中間節(jié)點(diǎn)本身不能直接執(zhí)行，系統(tǒng)會在路徑終止后將其轉(zhuǎn)化為完整程序，并通過執(zhí)行測試判斷其是否滿足所有樣例。

在此基礎(chǔ)上，論文用后續(xù)路徑的成功比例衡量節(jié)點(diǎn)質(zhì)量。若某個節(jié)點(diǎn)的大部分后續(xù)路徑都能導(dǎo)向正確程序，說明該推理狀態(tài)較為可靠。若某個推理前綴的所有后繼路徑都失敗，系統(tǒng)則將其視為潛在邏輯偏離點(diǎn)，并引入外部自然語言指令進(jìn)行定向修復(fù)，從而生成更多高質(zhì)量正樣本，緩解PBE過程監(jiān)督數(shù)據(jù)中正樣本稀疏的問題。

在完成推理樹構(gòu)建后，論文進(jìn)一步訓(xùn)練Process Reward Model來評估中間推理步驟的質(zhì)量。PRM并不直接判斷最終程序是否正確，而是為每個推理狀態(tài)分配獎勵分?jǐn)?shù)，用來估計該狀態(tài)繼續(xù)生成正確程序的可能性。

具體而言，論文將節(jié)點(diǎn)的后繼成功率作為偏好信號。如果節(jié)點(diǎn)A的后續(xù)采樣路徑更容易生成正確程序，而節(jié)點(diǎn)B的后續(xù)路徑更容易失敗，訓(xùn)練目標(biāo)就要求PRM給節(jié)點(diǎn)A更高分?jǐn)?shù)。相比簡單的正負(fù)樣本分類，這種偏好學(xué)習(xí)能夠更細(xì)致地區(qū)分不同推理狀態(tài)的可靠程度，使模型學(xué)會識別更可能通向正確程序的歸納方向。

獲得PRM后，論文將其接入強(qiáng)化學(xué)習(xí)框架，用過程級獎勵優(yōu)化程序合成模型。為提升訓(xùn)練穩(wěn)定性，研究團(tuán)隊設(shè)計了按失敗模式組織的三階段課程學(xué)習(xí)策略，使模型從基礎(chǔ)可執(zhí)行性逐步過渡到復(fù)雜邏輯正確性。

第一階段關(guān)注語法錯誤和運(yùn)行時錯誤，訓(xùn)練模型生成能夠正常執(zhí)行的程序。第二階段關(guān)注可執(zhí)行但與目標(biāo)行為完全不一致的程序，引導(dǎo)模型學(xué)習(xí)輸入輸出樣例中的核心約束。第三階段處理只能通過部分樣例的程序，幫助模型減少對有限樣例的過擬合。在每個階段中，PRM對中間推理狀態(tài)提供獎勵，并通過PPO更新策略模型，從而讓模型逐步學(xué)習(xí)更可靠的程序歸納路徑。