在人工智能的諸多分支中，“神經(jīng)算法推理”（Neural Algorithmic Reasoning，簡稱 NAR）是一個既年輕又野心勃勃的方向。它的核心思想很直接——讓神經(jīng)網(wǎng)絡(luò)不僅學(xué)會“看”數(shù)據(jù)，還能像經(jīng)典算法那樣一步步推理、執(zhí)行中間步驟，從而具備可解釋、可泛化的解題能力。

與傳統(tǒng)的端到端預(yù)測不同，NAR 會在訓(xùn)練中顯式模仿算法的中間狀態(tài)，例如動態(tài)規(guī)劃表、搜索樹節(jié)點或排序過程，讓模型在結(jié)構(gòu)化的推理軌道上前進。

在學(xué)術(shù)界，CLRS-30 基準(zhǔn)是 NAR 研究的試金石。它涵蓋了 30 種多項式時間可解的經(jīng)典算法，從排序、最短路徑到圖遍歷，應(yīng)有盡有。

然而，這個基準(zhǔn)有一個顯著的空白——它沒有覆蓋那些時間復(fù)雜度依賴于輸入數(shù)值大小的“偽多項式”問題。換句話說，CLRS-30里的算法大多在輸入規(guī)模（n）增大時才變慢，而在容量、權(quán)重等數(shù)值放大時依然穩(wěn)定。但現(xiàn)實世界中，很多優(yōu)化問題的難度恰恰來自這些數(shù)值的膨脹。

0-1 背包問題就是這種弱 NP-hard 問題的代表。它的動態(tài)規(guī)劃解法在理論上是多項式時間，但復(fù)雜度是 O(n?C)，其中 C 是容量的數(shù)值大小，而不是它的位長。

這意味著，當(dāng)容量從 16 增加到 64 時，問題規(guī)模會成倍膨脹，即便物品數(shù)量不變。對于神經(jīng)網(wǎng)絡(luò)來說，這種“數(shù)值尺度變化”是一個天然的泛化陷阱：在小容量上學(xué)得很好，換到大容量就可能完全失靈。

正因如此，技術(shù)團隊選擇了 Knapsack 作為切入點。他們想回答一個關(guān)鍵問題：NAR 能否學(xué)會解決偽多項式問題，并在數(shù)值尺度大幅變化時依然保持性能？這不僅是對 NAR 泛化能力的嚴(yán)苛檢驗，也為未來將神經(jīng)推理器應(yīng)用到金融優(yōu)化、資源分配等實際場景提供了參考。

圖1：背包問題及其動態(tài)規(guī)劃解決方案的可視化。左：輸入項目及其權(quán)重和值。中間：動態(tài)規(guī)劃表和決策表。正確的選定項目的最佳解決方案。dp[i][c]——容量為c的前i個項目的最優(yōu)值。

這支團隊本身也頗具看點。來自薩格勒布大學(xué)的 Stjepan Po?gaj 和 Marin ?ili? 帶來了算法與系統(tǒng)工程的學(xué)術(shù)積累；Graphcore 的 Dobrik Georgiev 則代表了硬件加速與高性能 AI 部署的產(chǎn)業(yè)視角；而 Google DeepMind 的 Petar Veli?kovi? 是 NAR 概念的重要推動者，也是 Graph Attention Networks（GAT）的首位技術(shù)團隊。學(xué)術(shù)與產(chǎn)業(yè)、算法與工程的交匯，使得這項研究既有理論深度，又考慮到落地可行性。

1.相關(guān)工作

CLRS-30 基準(zhǔn)的提出，為 NAR 提供了一個統(tǒng)一的訓(xùn)練與評測平臺。它的 30 個任務(wù)覆蓋了排序、圖算法、動態(tài)規(guī)劃等多種類型，且每個任務(wù)都配有算法執(zhí)行的中間狀態(tài)（hints），方便模型在監(jiān)督下學(xué)習(xí)推理過程。

這些任務(wù)幾乎都是多項式時間可解的，且輸入規(guī)模和數(shù)值范圍都受到嚴(yán)格限制。這讓模型在“結(jié)構(gòu)泛化”上得到了鍛煉，卻沒有經(jīng)歷過“數(shù)值泛化”的考驗。

在組合優(yōu)化領(lǐng)域，NAR 已經(jīng)被用于旅行商問題（TSP）、最短路徑、匹配等任務(wù)，通常通過圖神經(jīng)網(wǎng)絡(luò)（GNN）來捕捉結(jié)構(gòu)關(guān)系，并在訓(xùn)練中模仿經(jīng)典算法的步驟。

這些探索證明了 NAR 在結(jié)構(gòu)化推理上的潛力，但也暴露了一個問題：當(dāng)任務(wù)的狀態(tài)空間隨數(shù)值放大而急劇膨脹時，模型往往會失去方向感。

現(xiàn)有方法在數(shù)值尺度變化下的泛化問題，歸根結(jié)底是因為神經(jīng)網(wǎng)絡(luò)對數(shù)值大小缺乏不變性。它們可能在容量為 16 的背包上學(xué)會了“記憶”某些模式，但當(dāng)容量變成 64 時，這些模式不再適用。如何讓模型學(xué)會與數(shù)值尺度無關(guān)的推理規(guī)則，是這篇論文試圖回答的核心挑戰(zhàn)之一。

2.方法框架：Construction–Reconstruction 雙階段

研究的核心創(chuàng)新，是將神經(jīng)算法推理器的訓(xùn)練拆分為兩個相對獨立的階段：Construction（構(gòu)建）和Reconstruction（重構(gòu)）。前者負責(zé)像經(jīng)典動態(tài)規(guī)劃那樣，逐步填充出完整的狀態(tài)表；后者則在這個表的基礎(chǔ)上，回溯出最終的最優(yōu)解。

這樣的分工，不僅讓模型在學(xué)習(xí)過程中有了清晰的中間目標(biāo)，也為泛化到更大規(guī)模、更大數(shù)值范圍的任務(wù)打下了基礎(chǔ)。

DP 表構(gòu)建（Construction）

在構(gòu)建階段，模型的任務(wù)是預(yù)測出動態(tài)規(guī)劃的值表 dp[i][c] 以及對應(yīng)的決策表 decision[i][c]。為了讓神經(jīng)網(wǎng)絡(luò)能夠“看懂”這個表，技術(shù)團隊在輸入表示上做了多層設(shè)計。

圖2：n=16，C=16（分布中）構(gòu)建的DP表的比較。使用分類邊長編碼可以銳化預(yù)測表并實現(xiàn)推理。

首先是權(quán)重整數(shù)化與 one-hot 編碼。背包問題的物品權(quán)重被限制在一個最大值 w_max 以內(nèi)，并轉(zhuǎn)換為整數(shù)，再用 one-hot 形式編碼。這既避免了極端容量導(dǎo)致的稀疏狀態(tài)，也讓模型在容量變化時保持輸入分布的穩(wěn)定。

其次，整個問題被嵌入到CLRS-30 圖表示框架中。物品、容量、以及它們之間的關(guān)系被建模為圖的節(jié)點和邊，節(jié)點特征、邊特征和全局特征共同構(gòu)成了輸入的多通道信息流。

一個關(guān)鍵的增強是Edge Length Encoding。在容量節(jié)點之間的邊上，技術(shù)團隊添加了一個類別特征，表示兩個容量節(jié)點之間的距離 |i-j|（截斷到 M=10）。這讓模型在信息傳遞時，能夠顯式感知“跳回去多少格”才能找到相關(guān)的歷史狀態(tài)，大幅提升了 DP 表預(yù)測的準(zhǔn)確性。

在模型架構(gòu)上，技術(shù)團隊引入了Homogeneous Processor。它去掉了偏置項、LayerNorm 和門控機制，使得網(wǎng)絡(luò)對數(shù)值縮放保持不變性（scale-invariant）。這是為了解決 OOD（分布外）泛化時常見的數(shù)值漂移問題——在容量變大時，DP 值的絕對大小可能成倍增加，但它們之間的相對關(guān)系才是解題的關(guān)鍵。

訓(xùn)練時，模型會顯式接收到當(dāng)前物品的索引作為 hint，但這些 hint 不直接參與解碼損失，只是幫助模型在構(gòu)建表格時定位上下文。

解重構(gòu)（Reconstruction）

當(dāng) DP 表構(gòu)建完成后，第二階段的任務(wù)是回溯出最優(yōu)的物品集合。這里，技術(shù)團隊刻意設(shè)計了一個雙步回溯流程：第一步判斷當(dāng)前物品是否被選中，第二步根據(jù)決策更新容量指針。這種拆分比“一步到位”的回溯更容易泛化，因為它明確了決策與狀態(tài)轉(zhuǎn)移的順序。

圖3：背包問題NAR構(gòu)建過程的可視化。在每一步中，根據(jù)當(dāng)前的潛在嵌入預(yù)測DP值表和決策表的下一行。

與標(biāo)準(zhǔn)的CLRS-30方法不同，在標(biāo)準(zhǔn)的CLRS-30方法中，輸出是使用額外的節(jié)點/邊/圖特征單獨預(yù)測的，我們的模型會累積決策表的預(yù)測行，然后將其傳遞給NAR重建。

在輸入特征上，回溯階段的圖包含容量節(jié)點和物品節(jié)點，邊特征中不僅有容量差的編碼，還有來自構(gòu)建階段預(yù)測的決策表。值得注意的是，這里不使用物品的價值信息，以防模型走捷徑直接猜測最終解，而不是依賴 DP 表進行推理。

技術(shù)團隊實現(xiàn)了兩種回溯變體：

• Regular Reconstruction：完全由神經(jīng)網(wǎng)絡(luò)執(zhí)行回溯。
• Deterministic Reconstruction：基于預(yù)測的概率決策表，進行可微分的軟回溯，將所有可能路徑的概率累積起來。這種方式在理論上更穩(wěn)定，也允許端到端的梯度傳播。

3.實驗設(shè)計與評估

為了驗證方法的有效性，技術(shù)團隊在 CLRS-30 框架下構(gòu)建了專門的背包任務(wù)數(shù)據(jù)集。訓(xùn)練集是in-distribution的，即物品數(shù)量n≤16n，容量 C≤16C；測試集則包含更大規(guī)模的 OOD 場景，例如 n=64,C=64n=64, C=64，用來檢驗數(shù)值尺度變化下的泛化能力。

評估指標(biāo)分為兩類：

• micro-F1：節(jié)點級別的分類準(zhǔn)確率，衡量模型在每個狀態(tài)上的預(yù)測質(zhì)量。
• Exact Match：實例級的完全匹配率，只有當(dāng)整個物品集合預(yù)測正確時才算成功。

對比方法包括：

• No-hint baseline：直接從輸入預(yù)測最優(yōu)子集，不使用中間 DP 表。
• 不同的Construction–Reconstruction 組合，例如常規(guī)構(gòu)建+常規(guī)回溯（reg. c. + reg. r.）、同質(zhì)構(gòu)建+常規(guī)回溯（homo. c. + reg. r.）、同質(zhì)構(gòu)建+確定性回溯（homo. c. + det. r.）。

這樣的設(shè)計既能比較雙階段方法與端到端方法的差異，也能分析 Homogeneous Processor、Edge Length Encoding、雙步回溯等設(shè)計在泛化性能上的貢獻。

4.實驗結(jié)果與分析

在in-distribution（分布內(nèi)）測試中，KNARsack 的表現(xiàn)幾乎是“教科書級”的。雙階段的Construction–Reconstruction 框架讓模型在物品數(shù)量和容量都處于訓(xùn)練范圍內(nèi)時，能夠穩(wěn)定地重現(xiàn)動態(tài)規(guī)劃的推理過程。

圖4：給定訓(xùn)練和推理過程中的真實決策表，在輸入中有和沒有項目值的情況下，NAR重建性能的比較。在輸入中包含項目的值可以防止NAR重建模型推廣到更大的實例。

micro-F1 節(jié)點級準(zhǔn)確率接近滿分，Exact Match 實例級匹配率也維持在高位，說明模型不僅能在局部狀態(tài)上做出正確判斷，還能在全局上拼出完整的最優(yōu)解。

真正的考驗來自O(shè)OD（分布外）泛化。當(dāng)容量和物品數(shù)量同時放大到訓(xùn)練集的四倍時，傳統(tǒng)端到端方法的性能急劇下滑，甚至出現(xiàn)“完全迷路”的情況。而 KNARsack在引入 Homogeneous Processor 后，表現(xiàn)出顯著的韌性——micro-F1 和 Exact Match 都遠高于常規(guī)處理器版本。

這種優(yōu)勢來自它對數(shù)值縮放的免疫力：去掉偏置、LayerNorm 和門控，使得網(wǎng)絡(luò)在容量數(shù)值成倍增長時，依然能保持對狀態(tài)間相對關(guān)系的敏感度，而不是被絕對數(shù)值的變化干擾。

在回溯階段，技術(shù)團隊比較了 確定性回溯（Deterministic Reconstruction）與 神經(jīng)回溯（Regular Reconstruction）。結(jié)果顯示，兩者在分布內(nèi)的表現(xiàn)相差無幾，但在極端 OOD 情況下，確定性回溯略有優(yōu)勢。這種優(yōu)勢來自它的可微分軟回溯機制——在不確定時保留多條可能路徑的概率累積，而不是一次性做出硬決策，從而減少了錯誤傳播的風(fēng)險。

表1：不同型號的進出分銷性能。最好的結(jié)果是粗體顯示的，但研究團隊在執(zhí)行過程中使用oracle將模型分開。

消融實驗進一步揭示了各個設(shè)計的價值。移除Edge Length Encoding 后，DP 表的預(yù)測明顯模糊，尤其是在容量跨度較大的狀態(tài)轉(zhuǎn)移中，模型難以準(zhǔn)確定位需要回溯的歷史狀態(tài)。

將雙步回溯改為單步回溯，則導(dǎo)致泛化性能下降，因為模型失去了對“決策”和“容量更新”這兩個邏輯步驟的明確分離。更有意思的是，當(dāng) hints 中加入物品價值信息時，模型在訓(xùn)練集上表現(xiàn)更好，但在 OOD 測試中反而退步——顯然，它學(xué)會了依賴價值直接猜解，而不是遵循 DP 表的推理路徑。

為了驗證方法的可遷移性，技術(shù)團隊還將框架應(yīng)用到其他偽多項式問題，如Subset Sum 和 Partition。只需調(diào)整采樣器，模型就能在這些任務(wù)上重現(xiàn)背包問題中的優(yōu)勢，顯著優(yōu)于無 hint 的端到端基線。這說明，Construction–Reconstruction并不是為背包量身定制的“特例”，而是一種可推廣的 NAR 訓(xùn)練范式。

5.主要貢獻

這項研究的意義，不僅在于它讓 NAR 首次跨入了偽多項式問題的領(lǐng)域，更在于它提出了一套可遷移的解決思路。通過將推理過程拆分為 Construction–Reconstruction 兩個階段，模型能夠在中間狀態(tài)上獲得明確的監(jiān)督，從而在數(shù)值尺度變化時依然保持穩(wěn)定。

在技術(shù)細節(jié)上，Edge Length Encoding 讓模型在容量節(jié)點之間的跳轉(zhuǎn)有了明確的“距離感”，而 Homogeneous Processor 則為數(shù)值泛化提供了結(jié)構(gòu)性保障。這兩個設(shè)計的結(jié)合，使得 KNARsack 在 OOD 場景下的表現(xiàn)遠超傳統(tǒng)方法。

最后，技術(shù)團隊用系統(tǒng)化的消融實驗和跨任務(wù)驗證，證明了這些設(shè)計并非偶然奏效，而是具有普適性的工程與算法原則。這不僅為 NAR 在更復(fù)雜的優(yōu)化問題上鋪平了道路，也為未來構(gòu)建可解釋、可泛化的神經(jīng)推理系統(tǒng)提供了可借鑒的范式。

6.對人工智能發(fā)展的影響

KNARsack 的方法論，顯然可以擴展到更多偽多項式與數(shù)值敏感的組合優(yōu)化問題。無論是多維背包、資源分配，還是帶有復(fù)雜約束的調(diào)度問題，只要存在動態(tài)規(guī)劃解法，這種雙階段策略都能派上用場。

Homogeneous Processor 與距離編碼的設(shè)計原則，也完全可以推廣到其他 DP 類任務(wù)中。對于那些狀態(tài)值隨輸入規(guī)模變化而劇烈波動的算法，這種數(shù)值不變性和顯式的狀態(tài)距離感知，都是提升泛化能力的有效手段。

雙階段訓(xùn)練與軟回溯機制，還為端到端可微分推理提供了新思路。通過在回溯階段保留多條可能路徑的概率累積，模型不僅能更穩(wěn)健地做出決策，還能在訓(xùn)練中實現(xiàn)梯度的全程傳遞。這為未來構(gòu)建可解釋、可優(yōu)化的神經(jīng)推理系統(tǒng)打開了新的大門。

從基準(zhǔn)建設(shè)的角度看，技術(shù)團隊建議在 NAR 基準(zhǔn)中加入偽多項式任務(wù) track。這將迫使模型面對數(shù)值尺度變化的挑戰(zhàn)，推動研究者探索更具魯棒性的推理架構(gòu)。

在應(yīng)用層面，這項研究的潛力同樣令人期待。金融優(yōu)化中的投資組合選擇、資源分配中的容量規(guī)劃、運籌學(xué)中的路徑與調(diào)度問題，都與背包類問題有著天然的結(jié)構(gòu)相似性。一個能夠跨數(shù)值尺度泛化的神經(jīng)推理器，意味著在這些領(lǐng)域中，我們或許可以擁有既快速又可解釋的 AI 決策助手。

參考資料：???https://arxiv.org/pdf/2509.15239??

本文轉(zhuǎn)載自??波動智能??，作者：FlerkenS