復(fù)合LLM應(yīng)用 (compound LLM applications) 是一種結(jié)合大語言模型（LLM）與外部工具、API、或其他LLM的高效多階段工作流應(yīng)用。

?前，服務(wù)這些應(yīng)?任務(wù)需要?對運?時?不確定、?作流結(jié)構(gòu)不確定等問題，這對現(xiàn)有集群任務(wù)調(diào)度算法提出了極大挑戰(zhàn)，并嚴(yán)重影響任務(wù)運?效率。

為了解決上述問題，上海交通大學(xué)朱怡飛教授團隊聯(lián)合江行智能提出調(diào)度框架LLMSched，通過引入三類新節(jié)點來擴展傳統(tǒng)任務(wù)表征方法實現(xiàn)復(fù)合LLM應(yīng)用任務(wù)的有效表征，借助貝葉斯網(wǎng)絡(luò)識別可降低不確定性的關(guān)鍵節(jié)點，并以信息熵衡量節(jié)點的熵減程度。

目前論文已被IEEE ICDCS’ 25接收。

實驗結(jié)果顯示，LLMSched結(jié)合探索-利用策略來平衡調(diào)度不確定性與當(dāng)前調(diào)度收益，最終實現(xiàn)高效調(diào)度復(fù)合LLM應(yīng)用，相較現(xiàn)有調(diào)度器平均任務(wù)完成時間降低14~79%。

LLMSched：DAG模型重構(gòu)+熵減調(diào)度

團隊通過對現(xiàn)有復(fù)合LLM應(yīng)用的設(shè)計分析與實驗，總結(jié)出復(fù)合LLM應(yīng)用以下兩點不確定性：

時長不確定性：單任務(wù)耗時波動高達300秒（圖1a）。該不確定性主要來源于LLM的自回歸生成特性。

結(jié)構(gòu)不確定性：任務(wù)步驟數(shù)與運行結(jié)構(gòu)隨機波動（圖1b/c）。該不確定性主要來源于LLM在復(fù)合LLM應(yīng)用中發(fā)揮的決策與規(guī)劃功能。

復(fù)合LLM應(yīng)用這兩種不確定性極大限制了傳統(tǒng)調(diào)度的性能表現(xiàn)。如下圖實例所示，傳統(tǒng)最短任務(wù)優(yōu)先(Shortest Job First)調(diào)度因誤判耗時導(dǎo)致效率低下(任務(wù)平均完成時間6.5s)，而不確定性感知的調(diào)度器通過提前執(zhí)行高熵減階段（TA-1）降低不確定性，從而達到更有效調(diào)度(任務(wù)平均完成時間5s)。

DAG模型重構(gòu)：調(diào)度的基石

為了應(yīng)對復(fù)合LLM應(yīng)用中存在的結(jié)構(gòu)不確定性，研究團隊提出全新有向無環(huán)圖（DAG）建?？蚣?，如下圖所示。該框架引入了三種節(jié)點，常規(guī)節(jié)點（Regular Stage），LLM 節(jié)點（LLM Stage）與動態(tài)虛擬節(jié)點（Dynamic Stage）。其中，常規(guī)節(jié)點對應(yīng)外部工具、api等的調(diào)用，LLM節(jié)點對應(yīng)LLM推理任務(wù)，動態(tài)虛擬節(jié)點對應(yīng)由LLM規(guī)劃生成的子DAG。

重構(gòu)后的DAG模型能將現(xiàn)有的復(fù)合LLM應(yīng)用表征為擁有固定拓撲結(jié)構(gòu)的調(diào)度單元，為之后的調(diào)度設(shè)計建立了基礎(chǔ)。

貝葉斯分析器+熵減衡量機制：讓系統(tǒng)越算越“清醒”

團隊在研究過程中意識到復(fù)合LLM應(yīng)用的部分節(jié)點存在顯著的關(guān)聯(lián)性。這種關(guān)聯(lián)性使得在執(zhí)行完成某些前置節(jié)點后，后續(xù)節(jié)點的不確定性能夠有效降低，具體表現(xiàn)如下：

1、規(guī)劃式任務(wù)中LLM規(guī)劃節(jié)點后的工作流完全由該節(jié)點決定。完成該LLM規(guī)劃節(jié)點后，所規(guī)劃的子工作流的未知拓撲結(jié)構(gòu)可被完全揭示。

2、相當(dāng)一部分的節(jié)點在運行時長上存在較高的關(guān)聯(lián)性（下圖所示）。在完成前置節(jié)點后，后續(xù)節(jié)點的時長不確定性進一步降低。具體表現(xiàn)在后續(xù)節(jié)點的運行時長的條件分布更為緊湊、可預(yù)測。

為此，團隊為每個應(yīng)用在對應(yīng)數(shù)據(jù)集上收集了大量的運行時長數(shù)據(jù)，并在數(shù)據(jù)上基于重構(gòu)的DAG模型訓(xùn)練貝葉斯網(wǎng)絡(luò)（BN）來獲取節(jié)點的運行時長分布與節(jié)點之間的關(guān)聯(lián)性。當(dāng)BN中的一個節(jié)點存在一條或多條出邊時，該節(jié)點便與其他的節(jié)點存在關(guān)聯(lián)，調(diào)度該節(jié)點便可以降低其他節(jié)點的不確定性。

考慮到實際情況中，不同的節(jié)點能夠降低的不確定性程度大不相同，團隊引入信息論中信息熵的概念，使用互信息衡量，如下圖所示。由于信息熵與互信息均通過變量的分布進行計算，因此之前通過BN獲得分布便可以直接用于計算調(diào)度每個節(jié)點的熵減，無需額外的測量。

為了將上述的熵減思想用于優(yōu)化任務(wù)的平均完成時間，團隊使用ε-greedy算法結(jié)合最短剩余時間優(yōu)先與最大熵減優(yōu)先兩種策略，提出了一個高效的調(diào)度算法。該算法借鑒了探索-利用的思想，巧妙地在降低任務(wù)不確定性與降低任務(wù)完成時間兩個潛在的沖突目標(biāo)中達到了平衡。在調(diào)度過程中，調(diào)度算法會收集任務(wù)完成的時長信息，利用貝葉斯網(wǎng)絡(luò)動態(tài)更新每個任務(wù)的運行時長，從而獲取更精確的任務(wù)時長估計。該算法的復(fù)雜度僅為，能夠?qū)討B(tài)的負載做出快速的調(diào)度決策。

實驗結(jié)果：平均任務(wù)完成時間最低降至79%

團隊選取了六種代表性的復(fù)合LLM應(yīng)用，并基于此構(gòu)建了4種不同應(yīng)用組成的負載，如下圖所示。團隊在一臺搭載H800 GPU的ubuntu機器上使用vLLM框架與LLaMA-7B 模型進行了實驗。

實驗結(jié)果表明，LLMSched相較于現(xiàn)有的調(diào)度器最多可降低79%的平均任務(wù)完成時間。

為了進一步衡量LLMSched的可拓展性與適應(yīng)性，團隊構(gòu)建了一個簡易的LLM推理模擬器，并在上面進行了多組不同任務(wù)數(shù)量的實驗。如下圖所示，團隊展示了不同任務(wù)數(shù)量的仿真結(jié)果。

實驗結(jié)果表明，LLMSched在任意一組實驗設(shè)置上均取得領(lǐng)先的成績，同時隨著任務(wù)數(shù)量增加，LLMSched的優(yōu)勢變得更為突出，比如，與 Decima 相比，在包含 100、200、300和400個任務(wù)的混合工作負載中，LLMSched 分別降低了 38%、65%、73%和 75%的平均 JCT，這展示了 LLMSched 的可擴展性。

此外，團隊在測試平臺實驗中，在下圖中展示了每種方法的平均調(diào)度開銷（總開銷除以每種方法的調(diào)用次數(shù)，包括BN推理和熵計算）。團隊方法的平均調(diào)度開銷略高于FCFS、SJF和Fair等簡單啟發(fā)式算法，但遠低于Decima和Carbyne這兩種復(fù)雜方法。此外，LLMSched的平均開銷對于所有類型的工作負載都低于3毫秒，這表明LLMSched可以在不影響平均JCT的情況下執(zhí)行高效的實時調(diào)度。

消融研究

為了分析這兩個組件的有效性，團隊進行了消融研究，創(chuàng)建了兩種額外的方法——LLMSched w/o BN 和 LLMSched w/o uncertainty。第一種方法遵循算法1中提出的相同調(diào)度方案，但使用歷史任務(wù)平均持續(xù)時間進行估計。第二種方法使用貝葉斯網(wǎng)絡(luò)更新任務(wù)持續(xù)時間的后驗分布，但僅執(zhí)行SRTF策略。

上圖展示了在四種類型工作負載上進行的消融研究結(jié)果。團隊將兩種方法的平均JCT歸一化到LLMSched的水平。

對于LLMSched w/o BN，在四種類型工作負載上，平均JCT分別比LLMSched高18%、17%、20%和 5%。這表明BN發(fā)揮了重要作用，因為它顯著提高了任務(wù)持續(xù)時間估計的準(zhǔn)確性。借助BN，可以通過利用階段間相關(guān)性，更動態(tài)地更新和更準(zhǔn)確地預(yù)測非計劃階段的任務(wù)持續(xù)時間。

對于LLMSched w/o uncertainty，在四種類型工作負載上，平均JCT分別比LLMSched高 21%、12%、15% 和 13%。這表明不確定性感知策略在有效引導(dǎo)探索過程中至關(guān)重要。當(dāng)處理混合工作負載時，其重要性尤為突出，因為各階段的不確定性減少差異顯著。對于這種工作負載，LLMSched w/o BN的性能優(yōu)于LLMSched w/o uncertainty。

LLMSched為LLM服務(wù)優(yōu)化開辟了新方向，尤其對多模塊協(xié)作的Agent系統(tǒng)、LLM推理集群資源調(diào)度具有重要參考價值。其不確定性量化框架可擴展至其他動態(tài)任務(wù)場景，推動智能調(diào)度理論與實際系統(tǒng)的深度融合。

論文鏈接：https://arxiv.org/abs/2504.03444