Balanced Sparse Tree: A Scalable Network Topology for Large Language Models平衡稀疏樹：一種適用於大型語言模型的可擴展網路拓樸

1. Where this paper sits1. 這篇論文的位置

The Chapter 6, section 1 (Panel 2), derives the two-tier limit: a spine spends one port on every leaf, so radix $k$ caps the fabric at $k$ leaves and $k^2/2$ hosts, and the next step is a third tier with two more switch hops. Section 5 gives Dragonfly one hedged paragraph and notes that no paper in the primer uses it for LLM training. BST is a SIGCOMM paper that compares Clos, HyperX, Dragonfly+ and Zettafly on LLM collectives, though only in simulation. Rail-only deletes the spine and loses cross-rail paths, and ZCube moves the sparsity into multi-port NICs. BST leaves the NICs alone, keeps full reach, and makes the spine wiring sparse instead.

第 6.1 節（面板 2）推導兩層的上限：spine 在每台 leaf 上花一個埠，所以基數 $k$ 把網路限制在 $k$ 台 leaf、$k^2/2$ 台主機，再往上就要第三層、多兩個交換器跳。第 5 節只用保守的一段介紹 Dragonfly，並指出入門中沒有論文把它用在 LLM 訓練。BST 是一篇在 LLM 集體通訊上比較 Clos、HyperX、Dragonfly+ 與 Zettafly 的 SIGCOMM 論文，不過只在模擬中比較。Rail-only 刪掉 spine、失去跨 rail 的路徑，ZCube 把稀疏性移到多埠 NIC。BST 不改動 NIC、保留完整的觸及範圍，改讓 spine 的接線變稀疏。

2. The problem, in numbers2. 問題，用數字說明

The paper's motivation has no traffic measurement; it is analysis. LLM traffic is collectives (All2All, AllReduce), which favor symmetric fabrics, not arbitrary point-to-point flows. Each extra Clos tier adds switches, optics and hops, while direct graphs such as Dragonfly are asymmetric and sit far from the Moore bound, the largest network that a given degree and diameter allow ($r^2 + 1$ nodes for degree $r$ at diameter 2). Switch radix stops at about 256. So the question is how many ToRs a spine port can serve. In a Clos stage the answer is one per spine port, and every ToR pair shares all the spines:

論文的動機沒有流量量測，而是來自分析。LLM 的流量是集體通訊（All2All、AllReduce），它們偏好對稱的網路，而不是任意的點對點流。Clos 每多一層就多出交換器、光模組與跳數，而 Dragonfly 這類直接圖不對稱，而且離 Moore 上限（給定度數與直徑時網路的最大規模；度數 $r$、直徑 2 時為 $r^2 + 1$ 個節點）很遠。交換器基數大約到 256 為止。所以問題是一個 spine 埠能服務幾台 ToR。在 Clos 的一級中，答案是每個 spine 埠一台，而每一對 ToR 共用全部的 spine：

3. The design3. 設計

3.1 One spine per ToR pair3.1 每對 ToR 一台 spine

BST is a two-level bipartite graph of spines (upper nodes) and ToRs (lower nodes). Each spine has degree $\delta$ inside a group of $\omega$ ToRs; the sparsity factor $\lambda = \delta/\omega$ is 1 for a Clos stage. Read the spines as hyperedges over the ToRs. The rule is that every pair of ToRs in a group lies in exactly one hyperedge: a Steiner system, or balanced incomplete block design. Then each pair has one deterministic two-hop path with no hash choice, and collective load spreads evenly. Construction has four steps, which Figure 3 of the paper shows for $\omega = 4$, $\delta = 2$:

BST 是由 spine（上層節點）與 ToR（下層節點）構成的兩層二分圖。每台 spine 在一個 $\omega$ 台 ToR 的群組中度數為 $\delta$；稀疏係數 $\lambda = \delta/\omega$ 在 Clos 的一級中為 1。把 spine 看成 ToR 上的超邊。規則是群組中每一對 ToR 恰好落在一條超邊裡：這是 Steiner 系統，也就是平衡不完全區組設計。於是每一對都有一條確定的兩跳路徑，不需雜湊選擇，集體通訊的負載也平均分散。建構分四步，論文 Figure 3 以 $\omega = 4$、$\delta = 2$ 示範：

With $\delta = 2$ (the paper's Hiddenfly) every pair gets its own spine. A $\delta$-merge combines pairwise spines into larger blocks: $\{1,2\}$, $\{1,4\}$ and $\{2,4\}$ become $\{1,2,4\}$, and seven ToRs end with the seven blocks of the Fano plane. Counting each ToR's blocks and all blocks of a group gives

$\delta = 2$（論文稱為 Hiddenfly）時，每一對都有自己的 spine。$\delta$-合併把成對的 spine 合成更大的區組：$\{1,2\}$、$\{1,4\}$ 與 $\{2,4\}$ 合成 $\{1,2,4\}$，七台 ToR 最後得到 Fano 平面的七個區組。計算每台 ToR 所屬的區組數與一個群組的區組總數，得到

where $r_{up}$ is each ToR's uplink count and $b$ the spines per group. Both must be integers. For $\delta = 3$ that gives $(\omega-1)/2$ and $\omega(\omega-1)/6$, so a design exists only if $\omega \equiv 1$ or $3 \pmod 6$: 7, 9, 13, 15 and so on. Finding a merge in general is an exact clique-cover problem.

其中 $r_{up}$ 是每台 ToR 的上行數，$b$ 是每個群組的 spine 數。兩者都必須是整數。$\delta = 3$ 時即 $(\omega-1)/2$ 與 $\omega(\omega-1)/6$，所以只有 $\omega \equiv 1$ 或 $3 \pmod 6$ 時設計才存在：7、9、13、15 等等。一般情況下找合併是精確團覆蓋問題。

3.2 How wide it grows3.2 它能長多寬

A spine with radix $R$ spends $\delta$ ports per group, so it serves $\lfloor R/\delta \rfloor$ groups. Theorem 1 counts the ToRs when a merge exists for $\omega = r_{up}(\delta-1)+1$:

基數 $R$ 的 spine 每個群組花 $\delta$ 個埠，所以能服務 $\lfloor R/\delta \rfloor$ 個群組。當 $\omega = r_{up}(\delta-1)+1$ 的合併存在時，定理 1 數出 ToR 數：

Our worked example uses 64-port switches with 32 NPU ports and 32 uplinks per ToR, one question per row. Every BST row keeps the two-tier path of 3 switches:

我們的算例用 64 埠交換器，每台 ToR 32 個 NPU 埠、32 條上行，逐列計算如下。每一列 BST 都保持兩層的 3 台交換器路徑：

Larger $\delta$ is not automatically larger: number theory decides which $\omega$ exist, and the paper states the choice of $\delta$ as an optimization (its Problem 1). Adding spine planes in proportion to ToR uplinks is the paper's spine-fabric scaling. From such analysis the authors claim a three-tier Clos's scale at about half its cost and 1.7× Zettafly's scale; those are analysis results, not measurements.

$\delta$ 越大不一定越大：哪些 $\omega$ 存在由數論決定，論文把 $\delta$ 的選擇寫成最佳化問題（Problem 1）。按 ToR 上行的比例增加 spine 平面，是論文的 spine 層擴充。作者根據這類分析主張以約一半的成本達到三層 Clos 的規模、並達到 Zettafly 的 1.7 倍規模；這些是分析結果，不是量測。

3.3 Routing a sparse fabric: DiffR3.3 在稀疏網路上選路：DiffR

One shared spine per ToR pair means one minimal path. For skewed traffic, a ToR may use a detour through a third ToR: ToR, spine, ToR, spine, ToR, 4 links instead of 2. Detours cost capacity under uniform traffic. In the paper's 4-ToR full-mesh example of All2All, each link with detours carries 5 flows of 3 types, so a pair gets

每對 ToR 共用一台 spine，代表只有一條最短路徑。遇到偏斜的流量，ToR 可以經第三台 ToR 繞路：ToR、spine、ToR、spine、ToR，共 4 條鏈路而非 2 條。在均勻流量下，繞路會耗掉容量。論文以 4 台 ToR 的全連接網示範 All2All：加上繞路後每條鏈路承載 3 類共 5 條流，所以一對得到

DiffR (differentiated routing) therefore gates detours with a threshold $t_q$ below $T_{max}$, the PFC threshold or port buffer (or $t_c$ below the maximum credit count). A port whose queue is below $t_q$ carries minimal and detour traffic; otherwise only minimal traffic. Locally, a ToR skips detour ports that are busy. Remotely, a ToR whose downstream queue passes $t_q$ tells its upstream ToRs, which stop detouring through it to the congested destinations. The paper recommends $t_q = T_{max}/2$ or $T_{max}/4$, with packet spraying.

因此 DiffR（差異化路由）以低於 $T_{max}$（PFC 門檻或埠緩衝）的門檻 $t_q$ 控制繞路（或以低於最大 credit 數的 $t_c$）。佇列低於 $t_q$ 的埠可承載最短路徑與繞路流量；否則只承載最短路徑流量。在本地，ToR 會略過忙碌的繞路埠。在遠端，下游佇列超過 $t_q$ 的 ToR 會通知上游 ToR，讓它們停止經它繞往受影響的目的地。論文建議 $t_q = T_{max}/2$ 或 $T_{max}/4$，並搭配封包噴灑。

3.4 Deadlock and collectives3.4 死結與集體通訊

Minimal flows go strictly up, then down, so they form no cycle; the paper proves that a credit-loop deadlock needs at least three detour flows. The fix is two virtual lanes per port: a detour that enters a ToR from a spine and leaves toward another spine moves to VL2 and stays there. For collectives, BST prefers one-shot All2All, where each NPU sends to all others at once, and runs AllReduce as two All2All rounds. Ring AllReduce needs rank placement: HCCL's Ranktable lays out six congestion-free rings over four ToRs.

最短路徑的流嚴格先上後下，所以不會形成迴圈；論文證明 credit 迴圈死結至少需要三條繞路流。解法是每個埠兩條虛擬通道：從 spine 進入 ToR 再往另一台 spine 離開的繞路流改走 VL2，並一直留在 VL2。在集體通訊上，BST 偏好一次發送的 All2All（每顆 NPU 同時送給所有其他 NPU），並把 AllReduce 做成兩輪 All2All。環狀 AllReduce 需要 rank 擺放：HCCL 的 Ranktable 在四台 ToR 上排出六個無壅塞的環。

4. Implementation4. 實作

Simulations use Netisim, the authors' in-house packet simulator with spraying, ECMP and DiffR, cross-checked on the open-source Open-usim; the paper gives no line counts. The testbed has 4 Ascend 910B servers, 6 of 8 NPUs used in each (24 NPUs), each NPU on a 200G port to its ToR. The switches have 32 ports of 400G and are split into logical switches by VPN-based port isolation. Clos uses 3 spines that each reach all 4 ToRs; BST is bst(4,2,1), 6 spines named after ToR pairs. Current switches cannot run DiffR, so detours are static routing-table entries; hardware DiffR is planned for next-generation chips. Tests use the HCCL test tool and the MindIE inference engine.

模擬使用 Netisim，作者自行開發的封包模擬器，支援噴灑、ECMP 與 DiffR，並在開源的 Open-usim 上交叉驗證；論文沒有給出程式行數。測試平台有 4 台 Ascend 910B 伺服器，每台用 8 顆 NPU 中的 6 顆（共 24 顆），每顆 NPU 以一個 200G 埠接到它的 ToR。交換器有 32 個 400G 埠，以 VPN 式的埠隔離切成邏輯交換器。Clos 用 3 台各接全部 4 台 ToR 的 spine；BST 是 bst(4,2,1)，6 台以 ToR 配對命名的 spine。現有交換器無法執行 DiffR，所以繞路是靜態路由表項；硬體 DiffR 預計放進下一代晶片。測試使用 HCCL 測試工具與 MindIE 推論引擎。

5. What was measured5. 量到了什麼

All hardware results come from this 24-NPU testbed with $\delta = 2$. Collectives (Table 3 of the paper) move 1 GB, averaged over 1,000 iterations; Clos uses the default Ranktable and BST a load-balanced one:

所有硬體結果都來自這個 $\delta = 2$ 的 24 顆 NPU 測試平台。集體通訊（論文 Table 3）搬移 1 GB，取 1,000 次迭代的平均；Clos 用預設的 Ranktable，BST 用負載平衡的 Ranktable：

The paper credits the faster ring to fewer ECMP hash collisions on BST's unique paths. Note that the two fabrics also ran different Ranktables. For inference, Qwen3-30B-A3B (128 experts, TP and EP across two servers, oasst1 prompts) ran on MindIE with differentiated routing enabled:

論文把環較快歸因於 BST 唯一路徑上的 ECMP 雜湊碰撞較少。要注意兩個網路用的 Ranktable 也不同。推論方面，Qwen3-30B-A3B（128 個專家、TP 與 EP 跨兩台伺服器、oasst1 提示）在 MindIE 上執行，並開啟差異化路由：

Point-to-point traffic exposes the sparsity. The authors split the 4 ToRs into two groups of two and let 50%, 75% or 100% of the NPUs send to the other group (Table 4). Clos stays near 26.3–27.0 ms. The slowdowns, one question per row:

點對點流量會暴露稀疏性。作者把 4 台 ToR 分成兩組各兩台，讓 50%、75% 或 100% 的 NPU 送往另一組（Table 4）。Clos 維持在約 26.3–27.0 ms。減速逐列計算如下：

Why detours cannot reach 1.0× at full load: count the spine links that cross between the two halves. In Clos each of 3 spines has 2 links on each side, 6 in all. In bst(4,2,1) only spines 13, 14, 23 and 24 join both halves, 4 links; spines 12 and 34 stay inside one half. At 100% load the cut bound is $6/4 = 1.5\times$, and the measured 1.60× sits just above it.

為什麼滿載時繞路也到不了 1.0 倍：數一數跨越兩半的 spine 鏈路。Clos 中 3 台 spine 每台在每一側有 2 條鏈路，共 6 條。bst(4,2,1) 中只有 spine 13、14、23 與 24 連接兩半，共 4 條；spine 12 與 34 都在同一半之內。100% 負載時切口下界是 $6/4 = 1.5$ 倍，實測的 1.60 倍恰好在它上方。

The panel below generalizes this count to other $\delta$. Minimal routing can be worse than the cut bound when the pairs are unbalanced: if each sending ToR talks to one ToR only, it uses one of its three uplinks. The measured minimal-path slowdowns lie between the balanced and the one-partner bounds. Everything else in the evaluation is simulation: Netisim at 320 and 2,560 NPUs, where BST is reported 3.9–13.4% better than other topologies; this page does not show those numbers.

下面的面板把這個計數推廣到其他 $\delta$。配對不平衡時，最短路徑可能比切口下界更差：如果每台發送的 ToR 只和一台 ToR 通訊，它只用到三條上行中的一條。實測的最短路徑減速落在平衡與單一夥伴兩個下界之間。評估的其餘部分都是模擬：320 與 2,560 顆 NPU 的 Netisim，其中報告 BST 比其他拓樸好 3.9–13.4%；本頁不展示這些數字。

6. Limits and open questions6. 限制與未解的問題

• What was built. The hardware BST is $\delta = 2$ over 4 ToRs, the pairwise case that OFT and MLFM already describe. No Steiner design with $\delta \ge 3$ and no full DiffR ran on hardware; detours were static routes.實際建了什麼。硬體上的 BST 是 4 台 ToR、$\delta = 2$，也就是 OFT 與 MLFM 早已描述的成對情況。$\delta \ge 3$ 的 Steiner 設計與完整的 DiffR 都沒有在硬體上執行；繞路是靜態路由。
• Confounds and scale. The Ring result compares different Ranktables. The testbed has 24 NPUs; everything larger is simulation with one 8-NPU server model, and no comparison with rail-optimized Clos or rail-only is given.干擾因素與規模。環的結果比較的是不同的 Ranktable。測試平台只有 24 顆 NPU；更大的一切都是使用單一 8 顆 NPU 伺服器模型的模擬，也沒有與 rail-optimized Clos 或 rail-only 比較。
• Sparsity costs. Adversarial P2P loses bandwidth (Table 4), collectives need topology-aware placement, and number theory restricts $\omega$, which complicates expansion and strands some ports.稀疏的代價。對抗性的點對點會損失頻寬（Table 4），集體通訊需要感知拓樸的擺放，而數論限制了 $\omega$，讓擴充變複雜、也會閒置部分埠。
• Dependencies and review. Detours rely on PFC or credit-based lossless fabrics, and interaction with congestion control is not evaluated. The appendix, including the pair-bandwidth derivation and deployment examples, is not peer-reviewed.依賴與審查。繞路依賴 PFC 或 credit 式的無損網路，與壅塞控制的互動沒有評估。附錄（包括配對頻寬的推導與部署範例）未經同儕審查。

7. How it connects7. 與其他內容的關聯

• Chapter 6: section 1's $k^2/2$ limit is what BST raises at the same hop count; section 5's Dragonfly paragraph now has an LLM-era comparison, in simulation.第 6 章：BST 在相同跳數下提高的正是第 1 節的 $k^2/2$ 上限；第 5 節的 Dragonfly 段落現在有了 LLM 時代的比較（在模擬中）。
• ZCube also cuts Clos cost with a two-level static fabric, but by search and multi-port NICs. Rail-only removes cross-rail reach, which BST keeps.ZCube 也以兩層靜態網路降低 Clos 的成本，但靠的是搜尋與多埠 NIC。Rail-only 拿掉跨 rail 的觸及，BST 則保留它。
• DiffR builds on ECMP and spraying (Chapter 8) and on PFC (Microsoft RoCE); the Ranktable rings are the rank placement of the Chapter 4.DiffR 建立在 ECMP 與噴灑（第 8 章）以及 PFC（Microsoft RoCE）之上；Ranktable 的環就是第 4 章中的 rank 擺放。

Key numbers關鍵數字

Terms used on this page本頁用到的術語

BST

Balanced Sparse Tree: two switch levels where each spine joins $\delta$ ToRs of a group and every ToR pair shares one spine.

平衡稀疏樹：兩層交換器，每台 spine 接一個群組中的 $\delta$ 台 ToR，每對 ToR 共用一台 spine。

Steiner system / block design

Blocks of $\delta$ points such that every pair of points lies in exactly one block.

由 $\delta$ 個點組成的區組，使每一對點恰好落在一個區組中。

Hiddenfly / $\delta$-merge

The $\delta = 2$ case with one spine per pair / merging pairwise spines into larger blocks.

每對一台 spine 的 $\delta = 2$ 情況 / 把成對的 spine 合併成更大的區組。

DiffR

Minimal paths always; detours through a third ToR only on ports with queues below $t_q$.

永遠走最短路徑；只有在佇列低於 $t_q$ 的埠才經第三台 ToR 繞路。

Virtual lane

A separate buffer and credit class on a port; BST moves detours to VL2.

埠上獨立的緩衝與 credit 類別；BST 把繞路流移到 VL2。

Ranktable

HCCL's map from collective ranks to devices.

HCCL 中集體通訊 rank 對應到裝置的表。