在過去幾年里，大語言模型（LLM）與深度學(xué)習(xí)的浪潮席卷了幾乎所有計(jì)算領(lǐng)域。從醫(yī)學(xué)診斷到金融建模，從化學(xué)分子設(shè)計(jì)到物理模擬，這些模型在推理任務(wù)上的表現(xiàn)一次次刷新了人們的認(rèn)知。

它們不僅能處理復(fù)雜的自然語言，還能跨越模態(tài)邊界，將圖像、語音、代碼等信息融會貫通，展現(xiàn)出驚人的“多才多藝”。

然而在這股熱潮背后，一個(gè)更為基礎(chǔ)的問題卻始終懸而未決——我們究竟能否量化并刻畫人工智能推理能力的極限？

當(dāng)前的理論體系對這一問題的回答并不充分。雖然我們知道神經(jīng)網(wǎng)絡(luò)在足夠的訓(xùn)練和數(shù)據(jù)條件下具有極強(qiáng)的表達(dá)能力，但這種“能力”究竟能延伸到哪些推理類型、能否覆蓋所有可計(jì)算的算法、在復(fù)雜度上又有何代價(jià)，這些問題依然缺乏系統(tǒng)的數(shù)學(xué)刻畫。

換句話說，我們對“AI推理的邊界”缺乏一個(gè)可驗(yàn)證、可量化的理論框架。

近日，arXiv 熱文《Quantifying The Limits of AI Reasoning:Systematic Neural Network Representations of Algorithms》直面了一個(gè)核心問題：在理想化的訓(xùn)練條件下（無限完美數(shù)據(jù)與完美優(yōu)化），神經(jīng)網(wǎng)絡(luò)究竟能執(zhí)行哪些類型的推理任務(wù)？

現(xiàn)有的通用逼近定理雖然證明了神經(jīng)網(wǎng)絡(luò)可以逼近任意連續(xù)函數(shù)，但它們往往將函數(shù)視為“黑箱”映射，忽略了函數(shù)背后的算法結(jié)構(gòu)與推理鏈條。這種忽視意味著，我們無法從逼近理論中直接推導(dǎo)出網(wǎng)絡(luò)在執(zhí)行具體推理任務(wù)時(shí)的復(fù)雜度與可行性。

研究目標(biāo)是通過引入電路復(fù)雜度的視角，將推理任務(wù)視為電路計(jì)算過程，并建立一種系統(tǒng)化的方法，將任意電路精確映射為ReLU前饋神經(jīng)網(wǎng)絡(luò)。

這不僅能量化網(wǎng)絡(luò)的推理能力，還能揭示網(wǎng)絡(luò)規(guī)模與算法運(yùn)行時(shí)間之間的關(guān)系，從而為“AI推理極限”提供一個(gè)可計(jì)算的度量標(biāo)準(zhǔn)。

研究團(tuán)隊(duì)來自加拿大麥克馬斯特大學(xué)數(shù)學(xué)與統(tǒng)計(jì)系，并與向量人工智能研究院（Vector Institute）緊密合作。團(tuán)隊(duì)成員在數(shù)學(xué)邏輯、計(jì)算復(fù)雜度、神經(jīng)網(wǎng)絡(luò)理論等領(lǐng)域都有深厚積累，既具備嚴(yán)謹(jǐn)?shù)睦碚摴Φ?，又熟悉AI前沿應(yīng)用的需求。

這種跨學(xué)科背景，使他們能夠在抽象的數(shù)學(xué)框架與具體的AI推理任務(wù)之間架起橋梁。

1.相關(guān)研究與理論基礎(chǔ)

要理解這項(xiàng)工作的意義，必須先回顧通用逼近定理的歷史與局限。上世紀(jì)80年代末，Hornik、Cybenko、Funahashi等人的經(jīng)典結(jié)果證明，具有足夠隱藏單元的前饋神經(jīng)網(wǎng)絡(luò)可以在任意精度下逼近任意連續(xù)函數(shù)。

這一發(fā)現(xiàn)奠定了神經(jīng)網(wǎng)絡(luò)表達(dá)能力的理論基礎(chǔ)，也為深度學(xué)習(xí)的興起提供了信心。然而，這類定理關(guān)注的是“函數(shù)映射”層面的能力——它們并不關(guān)心函數(shù)是如何被計(jì)算出來的，更不涉及計(jì)算過程的結(jié)構(gòu)與復(fù)雜度。

圖1：比較：經(jīng)典近似理論與我們的復(fù)雜性理論改進(jìn)。

相比之下，電路復(fù)雜度理論則從另一個(gè)角度刻畫計(jì)算能力。它將算法視為由基本運(yùn)算單元（門）組成的電路，研究在給定門集下實(shí)現(xiàn)某個(gè)函數(shù)所需的最小電路規(guī)模與深度。

不同類型的電路——布爾電路（處理邏輯運(yùn)算）、算術(shù)電路（處理加法與乘法）、熱帶電路（處理最小值與加法）——對應(yīng)著不同類別的推理任務(wù)。

在形式化表示上，這些電路的計(jì)算過程可以抽象為有向無環(huán)圖（DAG）。DAG的節(jié)點(diǎn)代表計(jì)算步驟，邊表示數(shù)據(jù)流動。輸入節(jié)點(diǎn)接收原始數(shù)據(jù)，計(jì)算節(jié)點(diǎn)執(zhí)行基本運(yùn)算，輸出節(jié)點(diǎn)給出最終結(jié)果。

這種結(jié)構(gòu)化表示不僅揭示了算法的執(zhí)行順序，也為分析推理鏈條提供了天然的工具。

有趣的是，這種“推理鏈”與大語言模型中的Chain-of-Thought（CoT）概念高度契合。

LLM在多步推理時(shí)，會生成一系列中間推斷步驟，逐步逼近最終答案；而在電路模型中，這些中間步驟正對應(yīng)著DAG中的計(jì)算節(jié)點(diǎn)。由此，LLM的推理鏈可以被視為一種特殊的電路執(zhí)行過程，這為將AI推理能力映射到電路復(fù)雜度框架中提供了理論基礎(chǔ)。

圖片

圖2：主要結(jié)果總結(jié)：給定可計(jì)算函數(shù)作為電路的任何（近似）表示，我們用一個(gè)基本的ReLU神經(jīng)網(wǎng)絡(luò)（從預(yù)先指定的字典中選擇）替換每個(gè)計(jì)算節(jié)點(diǎn)，該網(wǎng)絡(luò)模擬相應(yīng)的計(jì)算。

通過將通用逼近理論與電路復(fù)雜度結(jié)合，研究團(tuán)隊(duì)為我們提供了一個(gè)新的視角：不再僅僅問“神經(jīng)網(wǎng)絡(luò)能否逼近某個(gè)函數(shù)”，而是問“神經(jīng)網(wǎng)絡(luò)能否高效地模擬計(jì)算該函數(shù)的算法過程”。這正是量化AI推理極限的關(guān)鍵所在。

2.研究方法與核心構(gòu)造

這項(xiàng)研究的核心，是一套研究團(tuán)隊(duì)稱之為“系統(tǒng)化元算法（Meta-Algorithm）”的構(gòu)造方法。它的野心很大——無論你手里拿的是布爾電路、算術(shù)電路、熱帶電路，還是混合邏輯與算術(shù)的復(fù)雜計(jì)算圖，這個(gè)方法都能將它一步步“翻譯”成一個(gè)等價(jià)的 ReLU 前饋神經(jīng)網(wǎng)絡(luò)，而且是精確模擬，不是近似。

實(shí)現(xiàn)的思路很直觀，先把算法抽象成一個(gè)有向無環(huán)圖（DAG），每個(gè)節(jié)點(diǎn)就是一個(gè)“門”（gate），執(zhí)行某種基本運(yùn)算。然后針對每種門類型，事先準(zhǔn)備一個(gè)標(biāo)準(zhǔn)化的 ReLU MLP模塊作為“模擬器”。

接下來，通過一種被研究團(tuán)隊(duì)形象地稱為“電路手術(shù)（Circuit Surgery）”的操作，把原電路中的節(jié)點(diǎn)逐一替換成對應(yīng)的 MLP 模塊，并重新接好輸入輸出的連線。這樣，原電路的計(jì)算流程就被無縫嵌入到神經(jīng)網(wǎng)絡(luò)的計(jì)算圖中。

這種“手術(shù)”有幾個(gè)關(guān)鍵要求：替換后的網(wǎng)絡(luò)必須保持原有的計(jì)算依賴關(guān)系（Graph Structure Preservation），也就是說，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)要和原電路的 DAG 一一對應(yīng)。

同時(shí)，網(wǎng)絡(luò)的規(guī)模——也就是神經(jīng)元和參數(shù)的數(shù)量——要和原電路的復(fù)雜度成比例（Complexity Mapping），實(shí)現(xiàn)空間復(fù)雜度與時(shí)間復(fù)雜度的直接映射。

為了讓這種映射在真實(shí)計(jì)算機(jī)上成立，研究團(tuán)隊(duì)還引入了數(shù)字計(jì)算模型的細(xì)節(jié)?，F(xiàn)實(shí)中的計(jì)算不是在連續(xù)實(shí)數(shù)域上進(jìn)行的，而是在有限精度的數(shù)值網(wǎng)格上運(yùn)算。

技術(shù)論文中明確了模運(yùn)算（modular arithmetic）和舍入機(jī)制（rounding scheme）的定義，并提出了“機(jī)器精度下的函數(shù)等價(jià)性”——如果兩個(gè)函數(shù)在給定精度的數(shù)值網(wǎng)格上輸出完全一致，就認(rèn)為它們是等價(jià)的。這為后續(xù)的精確模擬提供了嚴(yán)格的判據(jù)。

3.主要理論結(jié)果

Theorem 1：通用推理（Universal Reasoning） 

這是全文的基石性結(jié)論。

它斷言任意由特定門集 GG 構(gòu)成的電路，都可以通過完全無缺陷的“電路手術(shù)”轉(zhuǎn)化為一個(gè) ReLU 前饋網(wǎng)絡(luò)，并且在數(shù)字計(jì)算機(jī)上精確復(fù)現(xiàn)原電路的功能。

更重要的是，這個(gè)網(wǎng)絡(luò)的空間復(fù)雜度（神經(jīng)元數(shù)量）與原電路的時(shí)間復(fù)雜度（門數(shù)量）同階，計(jì)算圖的形狀也與原電路一致。這意味著，神經(jīng)網(wǎng)絡(luò)不僅能“算對”，還能“按原算法的節(jié)奏去算”，真正實(shí)現(xiàn)了推理過程的結(jié)構(gòu)化保真。

Theorem 2：有限精度下的通用電路設(shè)計(jì) 

如果說 Theorem 1 解決了“能不能模擬”的問題，Theorem 2 則進(jìn)一步回答了“有沒有遺漏”的疑問。

它證明在有限精度的數(shù)值空間上，任何函數(shù)都可以由一個(gè) ReLU MLP 精確實(shí)現(xiàn)。

這是一個(gè)數(shù)字計(jì)算版本的“超位定理”，與Kolmogorov–Arnold 超位定理在思想上相呼應(yīng)——后者說任何多元連續(xù)函數(shù)都可以由單變量函數(shù)的疊加表示，這里則說任何有限精度函數(shù)都可以由一個(gè)通用編碼器網(wǎng)絡(luò)加上線性解碼實(shí)現(xiàn)。

與經(jīng)典的通用逼近定理相比，這兩個(gè)結(jié)果的覆蓋面更廣。通用逼近定理只能保證在無限精度、連續(xù)域上的近似，而這里的構(gòu)造不僅涵蓋了逼近，還涵蓋了推理任務(wù)的精確執(zhí)行，包括邏輯運(yùn)算、動態(tài)規(guī)劃、甚至有限步的圖靈機(jī)模擬。

換句話說，它不僅回答了“神經(jīng)網(wǎng)絡(luò)能否學(xué)會某個(gè)函數(shù)”，還回答了“神經(jīng)網(wǎng)絡(luò)能否原封不動地執(zhí)行某個(gè)算法”。

圖片

圖3：定理2中構(gòu)造的最壞情況近似值的說明。

這種從電路到網(wǎng)絡(luò)的系統(tǒng)化映射，讓“AI 推理能力”第一次有了可計(jì)算、可驗(yàn)證的數(shù)學(xué)刻畫，也為未來在復(fù)雜推理任務(wù)中設(shè)計(jì)高效、可解釋的神經(jīng)網(wǎng)絡(luò)架構(gòu)提供了堅(jiān)實(shí)的理論支撐。

4.應(yīng)用案例分析

在理論框架奠定之后，研究團(tuán)隊(duì)用一系列推論（Corollary）展示了這一方法在不同類型推理任務(wù)中的威力。這些案例不僅是數(shù)學(xué)上的“存在性證明”，更是對神經(jīng)網(wǎng)絡(luò)推理邊界的一次次沖擊。

布爾函數(shù)實(shí)現(xiàn)復(fù)雜度優(yōu)化（Corollary 1） 

傳統(tǒng)上，某些布爾函數(shù)的神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)復(fù)雜度會呈現(xiàn)雙指數(shù)級增長，這幾乎讓直接模擬變得不可行。

研究團(tuán)隊(duì)通過系統(tǒng)化元算法，將這種復(fù)雜度壓縮到單指數(shù)級，逼近已知的理論下界。這意味著，在可計(jì)算性邊界附近，ReLU 網(wǎng)絡(luò)的表達(dá)效率被顯著提升，尤其是在需要精確邏輯推理的任務(wù)中。

隨機(jī)化邏輯電路去隨機(jī)化（Corollary 2） 

在經(jīng)典計(jì)算理論中，隨機(jī)化布爾電路常被用來簡化某些問題的實(shí)現(xiàn)。但研究團(tuán)隊(duì)證明，這些電路可以被等價(jià)的確定性 ReLU 網(wǎng)絡(luò)替代，且不損失功能。

這不僅是一次“去隨機(jī)化”的勝利，也為構(gòu)建可驗(yàn)證、可審計(jì)的推理網(wǎng)絡(luò)提供了路徑——畢竟，確定性意味著可重復(fù)性和可追溯性。

有限時(shí)間圖靈機(jī)模擬（Corollary 3） 

更具沖擊力的是，研究團(tuán)隊(duì)展示了如何用 ReLU 網(wǎng)絡(luò)精確模擬有限步運(yùn)行的圖靈機(jī)，并保留顯式的推理鏈。

這種模擬不是黑箱式的，而是結(jié)構(gòu)上對應(yīng)原圖靈機(jī)的狀態(tài)轉(zhuǎn)移與符號操作，讓網(wǎng)絡(luò)的每一步計(jì)算都能被解釋為具體的算法步驟。

動態(tài)規(guī)劃與圖計(jì)算（Corollary 4） 

在圖計(jì)算領(lǐng)域，研究團(tuán)隊(duì)以全點(diǎn)對最短路徑（All-Pairs Shortest Path, ASP）問題為例，構(gòu)造了一個(gè)立方復(fù)雜度的 ReLU 網(wǎng)絡(luò)實(shí)現(xiàn)。

這種實(shí)現(xiàn)不僅保留了動態(tài)規(guī)劃的遞推結(jié)構(gòu)，還在網(wǎng)絡(luò)中顯式編碼了圖的拓?fù)湫畔ⅲ故玖松窠?jīng)網(wǎng)絡(luò)在結(jié)構(gòu)化推理任務(wù)中的潛力。

圖4：幾何深度學(xué)習(xí)中圖形的極值示例。

推理能力蘊(yùn)含通用逼近（Corollary 5） 

最后研究團(tuán)隊(duì)指出，如果一個(gè)網(wǎng)絡(luò)能夠執(zhí)行上述推理任務(wù)，那么它在有限精度下也必然具備通用逼近能力。

換句話說，推理能力本身就涵蓋了函數(shù)逼近的能力——而且是精確的、非近似的。這為“推理優(yōu)于逼近”的觀點(diǎn)提供了堅(jiān)實(shí)的理論支撐。

5.理論意義與創(chuàng)新點(diǎn)

這項(xiàng)工作的意義，不僅在于提出了一個(gè)新的構(gòu)造方法，更在于它建立了一個(gè)統(tǒng)一的理論框架，將電路復(fù)雜度、可計(jì)算性理論與神經(jīng)網(wǎng)絡(luò)的表達(dá)能力緊密連接起來。

過去我們常用“通用逼近定理”來描述網(wǎng)絡(luò)的潛力，但那只是函數(shù)映射的視角；現(xiàn)在，我們有了一個(gè)能直接刻畫算法過程的工具。

這種方法的另一個(gè)亮點(diǎn)是推理可解釋性。由于網(wǎng)絡(luò)的計(jì)算圖與原算法的步驟一一對應(yīng)，我們可以直接在網(wǎng)絡(luò)結(jié)構(gòu)中“看到”推理鏈條。這對于需要審計(jì)、驗(yàn)證或調(diào)試的高風(fēng)險(xiǎn)應(yīng)用（如金融合規(guī)、醫(yī)療診斷）尤為重要。

在復(fù)雜度可量化方面，研究團(tuán)隊(duì)明確了網(wǎng)絡(luò)規(guī)模與算法復(fù)雜度之間的關(guān)系，使得我們可以在設(shè)計(jì)階段就預(yù)測所需的計(jì)算資源。這種可預(yù)測性為工程實(shí)現(xiàn)和硬件部署提供了堅(jiān)實(shí)的基礎(chǔ)。

最重要的是，這項(xiàng)研究超越了逼近理論的局限。它不再停留在“網(wǎng)絡(luò)能否逼近某個(gè)函數(shù)”的問題上，而是直接回答“網(wǎng)絡(luò)能否精確執(zhí)行某個(gè)算法”。這為未來構(gòu)建具備可驗(yàn)證推理能力的神經(jīng)網(wǎng)絡(luò)架構(gòu)打開了新的大門，也為 AI 推理的可計(jì)算性研究提供了新的坐標(biāo)系。

6.未來研究方向

這項(xiàng)研究雖然已經(jīng)為“神經(jīng)網(wǎng)絡(luò)能否精確執(zhí)行算法”給出了堅(jiān)實(shí)的理論答案，但研究團(tuán)隊(duì)也清楚，這只是一個(gè)起點(diǎn)。未來的探索空間，既有數(shù)學(xué)上的深水區(qū)，也有工程落地的廣闊天地。

首先，是擴(kuò)展到非歐幾里得與無限維輸入輸出的挑戰(zhàn)。當(dāng)前的構(gòu)造主要針對歐幾里得空間中的有限維向量輸入輸出，而現(xiàn)實(shí)中的許多推理任務(wù)——比如圖結(jié)構(gòu)分析、流形上的信號處理、甚至函數(shù)空間上的算子求解——都天然處于非歐幾里得或無限維環(huán)境中。

如何在這些空間中定義“電路手術(shù)”，并保持計(jì)算圖的結(jié)構(gòu)保真，將是下一步的關(guān)鍵。這不僅涉及到拓?fù)渑c幾何的嵌入問題，還可能引入譜圖理論、核方法等工具，為神經(jīng)網(wǎng)絡(luò)的推理能力開辟新的維度。

其次，是將經(jīng)典逼近構(gòu)造（如小波、樣條）轉(zhuǎn)化為電路表示。小波分解、B樣條插值等方法在信號處理和數(shù)值分析中有著成熟的理論與高效的實(shí)現(xiàn)，如果能將它們系統(tǒng)化地轉(zhuǎn)化為電路，再映射到 ReLU 網(wǎng)絡(luò)，就能把這些“人類設(shè)計(jì)的高效基”直接注入到神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)中。

這不僅可能帶來更緊湊的網(wǎng)絡(luò)規(guī)模，還能在特定任務(wù)上獲得更強(qiáng)的歸納偏置，讓網(wǎng)絡(luò)在訓(xùn)練樣本有限的情況下依然保持高精度推理。

最后是結(jié)合幾何深度學(xué)習(xí)與算子學(xué)習(xí)的應(yīng)用場景，幾何深度學(xué)習(xí)（Geometric Deep Learning）強(qiáng)調(diào)在圖、流形、群等結(jié)構(gòu)化空間中進(jìn)行學(xué)習(xí)，而算子學(xué)習(xí)（Operator Learning）則關(guān)注從函數(shù)到函數(shù)的映射，例如求解偏微分方程或模擬物理系統(tǒng)。

將本研究的“算法到網(wǎng)絡(luò)”映射方法與這兩類前沿方向結(jié)合，有望構(gòu)建出既能保留推理鏈條、又能處理復(fù)雜結(jié)構(gòu)化數(shù)據(jù)的通用推理網(wǎng)絡(luò)。例如，在分子模擬中，網(wǎng)絡(luò)可以直接嵌入化學(xué)反應(yīng)的算法流程；在氣候建模中，網(wǎng)絡(luò)可以精確執(zhí)行數(shù)值積分與邊界條件處理。

可以預(yù)見，這些方向的推進(jìn)，將讓神經(jīng)網(wǎng)絡(luò)的推理能力從“能做”走向“能解釋、能泛化、能遷移”，并最終在科學(xué)計(jì)算、工程設(shè)計(jì)、金融建模等高價(jià)值領(lǐng)域釋放出更大的潛力。（END）

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