An Information-Geometric Framework for OCS-Reconfigurable Interconnect Topology in Large-Scale AI Clusters

An Information-Geometric Framework for OCS-Reconfigurable Interconnect Topology in Large-Scale AI Clusters Shintaro Yoshizawa

arXiv:2610.25173v1 [cs.DC] 18 Oct 2026

Nagoya Mathematical and Information Science Research shintaro.yoshizawa.net@gmail.com

Abstract The interconnects of large AI training clusters, exemplified by NVIDIA’s GB200 NVL72 systems, are built from static and symmetric fabrics: an NVLink domain within the rack and a Fat-Tree between racks. Optical circuit switches render the inter-pod wiring programmable, and thereby raise three design questions that static fabrics never pose: which wiring to deploy, how far it should depart from the symmetric reference, and when it should be changed. This paper answers them within a single information-geometric framework. A wiring is a point of the probability simplex over candidate circuits, constrained to a degree polytope, and its departure from a symmetric prior encoding the uniform logical capacity of a non-blocking Fat-Tree is measured by the Kullback–Leibler divergence. The cost is a smoothed critical-path length of the training-iteration DAG; it is convex with explicit smoothness constants, and its gradient is given by the marginals of a Gibbs distribution over DAG paths, computable by a forward–backward recursion. For the free energy Fβ1 = U + β1−1 DKL (· ∥ q) we establish well-posedness, monotone dependence on the inverse temperature β1 with quantitative limits at both ends, a lower bound on the gain of adaptation by the Jeffreys divergence between the static and the adaptive wiring, and a symmetry principle that characterises exactly when static wiring is optimal. The associated entropic proximalgradient method reduces each step to a multiplicative update followed by a KL projection with a |V |-dimensional dual, and converges linearly in KL divergence, also in the presence of inexact projections. √ For time-varying traffic, a threshold policy attains regret O( ΓCV1 T ) against the switching-free dynamic optimum, with a finite-sample counterpart whose radius depends on the support size rather than the ambient dimension; the KL indicator of traffic change is identified as the multinomial generalised likelihood-ratio statistic, which yields an adaptive-lag GLR–CUSUM detector with a non-asymptotic false-alarm bound. For clusters shared by several jobs, generalised-mean fairness of slowdowns is convex, coincides in its maximisers with α-fairness of throughputs for α ≥ 2, and leads to a Gibbs-form optimality condition. Synthetic experiments on pipeline-, data- and expert-parallel workloads confirm the theory and delineate its scope, including the regime in which exact integer programming remains preferable.

Keywords: information geometry, optical circuit switching, Fat-Tree, large language model training, Bregman proximal gradient, KL projection, change detection, fairness.

Contents 1 Introduction 1.1 The Communication Bottleneck in LLM Training . . . . . . . . . . . . . . . . . . 1.2 Fat-Tree as the Dominant Paradigm and Its Limitations . . . . . . . . . . . . . . 1.3 Optical Circuit Switching: Promise and Open Problems . . . . . . . . . . . . . . 1.4 Contributions and Their Relation to Known Results . . . . . . . . . . . . . . . .

2 2 2 2 2

2 Background 2.1 Fat-Tree, Blackwell, and OCS Fabrics . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Information Geometry of the Simplex . . . . . . . . . . . . . . . . . . . . . . . .

3 3 3

3 Model: Wiring Manifold, Prior, and DAG Cost 3.1 Wirings and the Degree Polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The Symmetric Prior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Workload, DAG, and Smoothed Critical Path . . . . . . . . . . . . . . . . . . . .

5 5 6 6

4 Free Energy and Temperature

7

5 Entropic Proximal-Gradient Algorithm and Convergence 5.1 The Update as a KL Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Integer Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9 10 12

6 When to Reconfigure: Regret and Likelihood-Ratio Detection 6.1 Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Threshold Policies and Regret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 The KL Indicator as a Likelihood-Ratio Statistic . . . . . . . . . . . . . . . . . .

12 12 13 15

7 Multi-Tenant Clusters 7.1 Shared Port Budget and the KL Chain Rule . . . . . . . . . . . . . . . . . . . . . 7.2 Fairness Functionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Reconfiguration with Externalities . . . . . . . . . . . . . . . . . . . . . . . . . .

15 15 16 17

8 Synthetic Experiments 8.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Convergence and Temperature . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Integer Circuits Against an Exact MILP . . . . . . . . . . . . . . . . . . . . . . . 8.4 Dynamic Reconfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Multi-Tenant Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 17 18 18 19 21

9 Discussion

22

10 Conclusion

23

A Deferred Proofs

23

1

1

Introduction

1.1

The Communication Bottleneck in LLM Training

Large language models (LLMs) now reach hundreds of billions to trillions of parameters [6, 7, 28], and training them requires tens of thousands of accelerators operating in concert. The interconnect is a first-order determinant of throughput and of reliability: during a 54-day snapshot of Llama 3 405B pre-training, 35 of 419 unexpected interruptions (8.4%) were attributed to network switches and cables [18]. A training job is decomposed along tensor (TP), pipeline (PP), data (DP) and, for mixtureof-experts (MoE) models, expert (EP) parallelism [12, 24]. Each dimension induces a distinct collective: TP issues latency-critical collectives that normally stay inside the scale-up domain, PP sends activations and gradients between adjacent stages, DP performs gradient all-reduce, and EP performs all-to-all exchanges whose volume depends on token routing. The resulting traffic is strongly structured, phase-dependent, and—for MoE—time-varying.

1.2

Fat-Tree as the Dominant Paradigm and Its Limitations

The k-ary Fat-Tree [1, 15] is the de facto standard for HPC and AI clusters. NVIDIA’s DGX SuperPOD reference architecture uses a multi-tier InfiniBand Fat-Tree [20]; the Blackwell generation adds a rack-scale NVLink domain (GB200 NVL72: 72 GPUs, fifth-generation NVLink, 1.8 TB/s per GPU and 130 TB/s in aggregate) with an InfiniBand or Ethernet Fat-Tree between racks [21]. A non-blocking Fat-Tree offers the same logical capacity to every host pair and is therefore optimal for worst-case (uniform) traffic. For structured LLM traffic it is overprovisioned in some directions and cannot be re-shaped when the parallelism layout changes: the only remaining degree of freedom is routing, constrained by fixed wiring.

1.3

Optical Circuit Switching: Promise and Open Problems

Optical circuit switches establish reconfigurable point-to-point light paths that bypass electrical packet switching. Google’s TPU v4 [14] interconnects 4,096 chips through a 3D torus whose slices are composed per job by 48 OCS units, and Google’s data-centre networks use OCS at scale [23, 29]. Topology engineering for such fabrics is typically posed as an integer or mixed-integer programme: COUDER [27] optimises over sets of traffic matrices and reports, on Facebook traces, about 20% higher throughput and 32% lower average hop count than cost-equivalent static topologies; ATRO [13] jointly optimises topology and routing, finding the global optimum for one-hop routing and alternating updates for multi-hop routing; TopoOpt [30] co-optimises topology and parallelisation for training jobs; DELTA [11] encodes the training DAG in a MILP and reports up to 17.5% lower communication time and at least 20% fewer optical ports than traffic-matrix baselines; and InfiniteHBD [25] builds a data-centre-scale high-bandwidth domain from OCS transceivers, reporting a cost of 31% of NVL72. What is missing is a continuous theory that (a) states what a reasonable departure from the symmetric Fat-Tree reference is, (b) admits provable, low-complexity updates, (c) incorporates the causal structure of the training DAG, and (d) gives a statistically principled rule for when to reconfigure.

1.4

Contributions and Their Relation to Known Results

We develop such a theory by combining elementary information geometry [2, 3, 9] with first-order methods in Bregman geometry [4, 17] and classical sequential analysis [16, 26]. The tools are standard; the contribution lies in the formulation they make possible and in the results specific to it. We regard the following three as the principal contributions. (I) A temperature-controlled design principle (Section 4). Wirings are points of a simplex restricted to a degree polytope, and their departure from a symmetric Fat-Tree2

like prior is penalised by the KL divergence with weight β1−1 . We prove well-posedness and strict positivity (Theorem 4.2), monotone and quantitative limits in β1 (Theorem 4.3), a lower bound on the gain of adaptation by the Jeffreys divergence between static and adaptive wirings (Theorem 4.4), and a symmetry principle identifying exactly when static wiring is optimal (Theorems 4.5 and 4.7). (II) A differentiable DAG cost (Section 3). The iteration time is a smoothed critical path of the training DAG; it is convex with explicit smoothness constants (Theorem 3.3), and its gradient is the vector of path criticalities of a Gibbs distribution over DAG paths, computed by a forward–backward recursion (Theorem 3.4). (III) Guarantees for reconfiguration (Section 6). A threshold policy has regret √ O( ΓCV1 T ) against the switching-free dynamic optimum (Theorem 6.3), with a KLthreshold variant (Theorem 6.5) and a finite-sample version whose radius scales with the support size (Theorem 6.7); the GLR–CUSUM detector obtained from the likelihood-ratio form of the KL indicator controls false alarms (Theorem 6.9). Two further components apply established results to the present model and are included to make the framework complete and verifiable: the convergence analysis of the entropic proximalgradient method (Section 5; Theorems 5.4 and 5.5), which specialises the theory of Bregman proximal gradient methods under relative smoothness, and the multi-tenant extension (Section 7), which combines the KL chain rule with generalised-mean fairness and identifies the range α ≥ 2 in which fairness and convexity are compatible (Theorems 7.2, 7.4 and 7.5). Synthetic experiments (Section 8) verify every bound and compare against static, demand-proportional and exact integer baselines. We have not carried out an exhaustive priority search, and make no claim that the individual inequalities are new as abstract statements; their interest lies in what they assert about reconfigurable fabrics.

2

Background

2.1

Fat-Tree, Blackwell, and OCS Fabrics

A k-ary Fat-Tree has (k/2)2 core switches and k pods, each with k/2 aggregation and k/2 edge switches; every edge switch serves k/2 hosts, for k 3 /4 hosts and k 3 /2 inter-switch links in total. Its automorphism group permutes pods and the hosts below an edge switch, and with full bisection bandwidth (k 3 /4)(c/2) it offers the same logical capacity to every host pair. Figure 1(a) shows k = 4. In Blackwell NVL72 systems [21] the 72 GPUs of a rack are connected through NVSwitch trays; each GPU also has a NIC to the scale-out InfiniBand or Ethernet Fat-Tree (Figure 1(b)). All layers are static. An OCS device establishes point-to-point optical circuits between transceivers; switching takes milliseconds for MEMS devices, while end-to-end reconfiguration including transceiver and NIC re-initialisation is reported in the range of seconds [11, 22]. We work at pod granularity: a pod is a scale-up domain (e.g. a rack) with r OCS uplinks; the OCS layer realises any multigraph on the pods in which every pod has degree at most r and the total number of circuits does not exceed the OCS port budget µ (Figure 1(c)).

2.2

Information Geometry of the Simplex

P Let E be a finite set and ∆ = {w ∈ RE : e we = 1}, with relative interior ∆◦ . With the ≥0 P ◦ Fisher metric gij = e p−1 e ∂i pe ∂j pe , ∆ is a dually flat manifold [2, 3]: the m-affine coordinates are η = w and the e-affine coordinates P are θe = log we − log we0 . The canonical divergence is the KL divergence DKL (x ∥ w) = e xe log(x P e /we ) (with 0 log 0 = 0), which is the Bregman divergence of the negative entropy h(w) = e we log we restricted to ∆. 3

(a) Fat-Tree (k=4)

(b) Blackwell NVL72

Static, symmetric

NVLink (intra-rack) + InfiniBand Fat-Tree (inter-rack)

Core

C

C

C

C

Agg

A

A

A

A

A

A

A

A

Edge

E

E

E

E

E

E

E

E

Leaf

Spine

Spine

Leaf

Leaf

NVSwitch pod 1

pod 2

pod 3

IB

Leaf

···

Host pod 0

IB

···

NVSwitch

NVL72 rack

NVLink

NVL72 rack

InfiniBand

(c) OCS-Reconfigurable

(d) Topology manifold Mtopo

Logical 2D/3D torus, re-wired per job

Information-geometric view Mtopo

w0∗

OCS W

GPU

HammingMesh ŵ

KL proj.

Dragonfly+ Jellyfish

proximal steps

qW (static, FT/BW)

torus link

OCS circuit

Figure 1: Four views of interconnect topology. (a) A k=4 Fat-Tree with 4 pods, (k/2)2 =4 core switches, 8 aggregation switches, 8 edge switches, and k 3 /4=16 hosts. All links are fixed at deployment. (b) NVIDIA Blackwell NVL72: GPUs are fully meshed within each rack via NVSwitch (blue links), and racks are interconnected through a hierarchical InfiniBand Fat-Tree reached through per-GPU NICs (red links). Only 6 of the 72 GPUs per rack are drawn. The topology is static. (c) An OCS-reconfigurable fabric realizes a logical torus (dashed orange; arrows indicate wrap-around links) whose wiring is reprogrammed per job. The thick orange circuit is an example cross-connect set inside the OCS, turning otherwise idle fibres into a longrange link. (d) Schematic information-geometric view (not to scale): wirings are points of the simplex Mtopo , and the degree polytope W is m-convex. The static symmetric wiring sits at the prior; an iterate w0∗ outside W (e.g. the multiplicative step (15)) is mapped back by the KL projection ŵ = arg minW DKL (· ∥ w0∗ ) (Theorem 5.1). Other topology families are shown only for orientation; families with different switch sets are not, in general, points of the same simplex (Theorem 3.2).

4

A set W ⊆ ∆ is m-convex if it is convex in η-coordinates (e.g. a polytope cut out by linear inequalities in w), and m-flat if it is the intersection of ∆ with an affine subspace. For a closed m-convex W and q ∈ ∆◦ we call qW = arg min DKL (w ∥ q)

(1)

w∈W

the KL projection (Csiszár’s I-projection [9]) of q onto W. In Amari’s terminology the minimiser over the first argument onto an m-flat set is reached along an e-geodesic and is called the eprojection; to avoid the ambiguity present in parts of the literature we use the explicit form (1) throughout. Lemma 2.1 (Positivity). Let C ⊆ ∆ be closed and convex and contain a point with all coordinates positive. Let φ(w) = c h(w)+ψ(w) with c > 0 and ψ convex and continuously differentiable on a neighbourhood of ∆. Then every minimiser of φ over C has all coordinates positive. Proof. Let w̄ minimise φ over C and suppose w̄e = 0 for some e. Pick x ∈ C with x > 0 and set wt = w̄ + t(x − w̄) ∈ C for t ∈ (0, 1]. For coordinates with w̄f > 0, the map t 7→ wt,f log wt,f is d differentiable at 0; so is ψ(wt ). For the coordinate e, dt (txe ) log(txe ) = xe (log(txe ) + 1) → −∞ as t ↓ 0. Hence the right derivative of t 7→ φ(wt ) at 0 is −∞, so φ(wt ) < φ(w̄) for small t > 0, a contradiction. Theorem 2.2 (Generalised Pythagorean inequality [9]). Let W ⊆ ∆ be closed, m-convex and contain a positive point, and let q ∈ ∆◦ . Then qW exists, is unique, is positive, and for every x ∈ W, DKL (x ∥ q) ≥ DKL (x ∥ qW ) + DKL (qW ∥ q), (2) with equality for all x ∈ W when W is m-flat. Proof. w 7→ DKL (w ∥ q) = h(w) − ⟨log q, w⟩ is continuous and strictly convex on the compact set W, so the minimiser exists and is unique; it is positive by Theorem 2.1. At a positive minimiser the first-orderPcondition reads ⟨log(qW /q) + 1, x − qW ⟩ ≥ 0 for all x ∈ W; since ⟨1, x − qW ⟩ = 0 this is e (xe − qW,e ) log(qW,e /qe ) ≥ 0. Direct expansion gives the identity X qW,e DKL (x ∥ q) − DKL (x ∥ qW ) − DKL (qW ∥ q) = (xe − qW,e ) log , (3) qe e which proves (2). If W is m-flat, qW lies in its relative interior (it is positive), so qW ±s(x−qW ) ∈ W for small s > 0 and the first-order condition holds with equality. We repeatedly use Pinsker’s inequality DKL (x ∥ w) ≥ 21 ∥x − w∥21 [8] and the following threepoint identity, valid for x ∈ ∆ and w, q ∈ ∆◦ , which is (3) with qW replaced by any positive w: DKL (x ∥ q) = DKL (w ∥ q) + ⟨log(w/q), x − w⟩ + DKL (x ∥ w). (4)

3

Model: Wiring Manifold, Prior, and DAG Cost

3.1

Wirings and the Degree Polytope

Let V be the set of pods, |V | = N , each with r OCS uplinks of bandwidth c, and let µ ≤ N r/2 be the number of circuits the OCS layer can establish (its port budget). Let E be the set of
N candidate pod pairs (in the experiments all 2 pairs). Definition 3.1 (Wiring, capacity, degree polytope). A wiring is w ∈ ∆; it places µwe circuits on pair e. The capacity of pair e is κe (w) = b0 + B we , 5

B = µc,

(5)

where b0 > 0 is the bandwidth available to each pair through the static (electrical) fabric, used in parallel with the circuits. With the incidence matrix A ∈ {0, 1}V ×E , the degree polytope is  W = w ∈ ∆ : Aw ≤ (r/µ) 1 . (6) W is a closed m-convex polytope (not, in general, m-flat). Integrality of the circuit counts is relaxed here and restored in Section 5.3. Assumption A1 (Strict feasibility). W contains a point with all coordinates positive. For E the complete graph, the uniform wiring has degree 2µ/N ≤ r, so Assumption A1 holds whenever µ ≤ N r/2.

3.2

The Symmetric Prior

The reference wiring is a positive q ∈ ∆◦ . Our default is the uniform distribution on E: at pod granularity this is the logical capacity a non-blocking Fat-Tree offers to uniform traffic, namely an equal share for every pod pair, and it is invariant under all permutations of pods. We write qW for its KL projection (1) onto W; when q ∈ W (as for the uniform prior under Assumption A1 with complete E), qW = q. Remark 3.2 (Priors with restricted support). If one wishes to use a prior supported on a subset E0 ⊊ E (for instance the links of a physical Fat-Tree), then DKL (w ∥ q) = +∞ for every wiring that puts mass outside E0 , so the penalty forbids any departure from the support. The smoothed prior qϵ = (1 − ϵ) Unif(E0 ) + ϵ Unif(E \ E0 ), ϵ ∈ (0, 1), is positive and all results below apply to it; the bounds depend on ϵ through DKL (· ∥ qϵ ) ≤ log(|E|/ϵ).

3.3

Workload, DAG, and Smoothed Critical Path

One training iteration is described by a DAG G = (N , A) whose nodes are either compute nodes v with fixed duration cv ≥ 0 or communication nodes executing a phase s(v) ∈ S. Phase s moves volume ds,e ≥ 0 over pair e; Es = {e : ds,e > 0} and ns = |Es |. A phase lasts as long as its slowest pair: ds,e Ts (w) = max . (7) e∈Es κe (w) Let P be the set of paths from a source (node P without predecessors) to a sink of G, H = maxP ∈P |{v ∈ P : v communication}|, and ℓP = v∈P durv . The iteration time is the criticalpath length J(w) = maxP ∈P ℓP (w). Assumption A2 (Modelling assumptions). (i) Traffic of a phase uses the direct circuits of each pair together with the static fabric (single-hop routing, capacities add as in (5)); (ii) phases that may run concurrently in G do not contend for the same pair, or such contention is neglected; (iii) each node starts as soon as all its predecessors have finished. P With LSEτ (z1 , . . . , zn ) = τ log i ezi /τ , which satisfies maxi zi ≤ LSEτ (z) ≤ maxi zi +τ log n, we smooth both maxima:  
d (8) Tsτs (w) = LSEτs κes,e , U (w) = Jτ (w) = LSEτ ℓP (w) P ∈P , (w) e∈Es

τs where communication durations in ℓP are Ts(v) . Although |P| may be exponential, U and its P gradient are computed in O(|N | + |A| + s ns ) time (Theorem 3.4).

Lemma 3.3 (Convexity, smoothness, approximation). Under Assumption A2, U is convex and ¯ ¯ 2 nonincreasing in every coordinate on RE ≥0 . With ds = maxe ds,e , Gs = B ds /b0 and Ms = 6

P P 2B 2 d¯s /b30 + G2s /τs , set GH = maxP v∈P Gs(v) and MH = maxP v∈P Ms(v) , the sums running over the communication nodes of P . Then for all w ≥ 0 and v ∈ RE , ∥∇U (w)∥∞ ≤ GH ,

v⊤ ∇2 U (w) v ≤ L ∥v∥21 ,

L = MH +

G2H . τ

(9)

Consequently U (y) ≤ U (x)+⟨∇U (x), y−x⟩+L DKL (y ∥ x) for all x, y ∈ ∆ (relative smoothness), and 0 ≤ U (w) − J(w) ≤ τ log |P| + Hτs log maxs ns . The proof is in Section A. Note that GH ≤ HG and MH ≤ HM for G = maxs Gs , M = maxs Ms ; the bound is conservative and in practice we use backtracking (Section 5). Proposition 3.4 (Soft criticality and forward–backward gradient). Let στ (P ) = exp((ℓP − U )/τ ), a Gibbs distribution on P, and γv = στ ({P ∋ v}) the soft criticality of node v. Then ∂U/∂durv = γv and ∇U (w) =

X

τs (w), γv ∇Ts(v)

v comm.

ds,e B ∂Tsτs = − πs,e , ∂we κe (w)2

(10)

where πs,· is the softmax over Es of ds,e /(τs κe ). The quantities av = durv + LSEτ (au )u∈pred(v) (forward, av = durv at sources) satisfy the backward recursion t )t sink P , and γ obeys P U = LSEτ a(a a /τ (a −U )/τ ′ /τ u t u . If the critical path is / u′ ∈pred(v) e γt = e for sinks plus γu = v∈succ(u) γv e unique, γv → 1 on it and γv → 0 elsewhere as τ → 0. P Proof. U = τ log P eℓP /τ gives ∂U/∂ℓP = στ (P ) and ∂ℓP /∂durv = 1[v ∈ P ], hence ∂U/∂durv = γv ; (10) follows from the chain of LSE. By inP rule and the derivative ℓQ /τ , because eav /τ = e duction over a topological order, eav /τ = paths Q from a source to v P edurv /τ u∈pred(v) eau /τ ; summing over sinks gives U . The backward recursion is reverse-mode differentiation of the forward P recursion, and γu equals the στ -probability that the path passes u because each factor eau /τ / u′ eau′ /τ is the conditional probability that the path enters v from u. Remark 3.5 (The DAG as an exponential family). Phase durations are consequences of the wiring rather than free decision variables, so precedence constraints are not imposed on a separate schedule; they enter the problem exactly through the critical-path functional J. The geometric object that the DAG induces is the exponential family {στ } on P, with sufficient statistic the path length and natural parameter 1/τ ; the criticalities γv are its marginals, and the forward– backward recursion is the familiar sum–product computation of these marginals.

4

Free Energy and Temperature

Definition 4.1 (OCS free energy). For an inverse temperature β1 ∈ (0, ∞) and λ = 1/β1 , let Fβ1 (w) = U (w) +

1 DKL (w ∥ q), β1

wβ⋆ 1 = arg min Fβ1 (w).

(11)

w∈W

As in statistical mechanics, β1−1 multiplies the entropic (KL) term, so β1 → 0 (high temperature) pins the wiring to the prior and β1 → ∞ (low temperature) yields pure cost minimisation (Table 1). Theorem 4.2 (Well-posedness). Under Assumptions A1 and A2, for every β1 > 0 the minimiser w⋆ = wβ⋆ 1 exists, is unique and has all coordinates positive, and for all x ∈ W Fβ1 (x) ≥ Fβ1 (w⋆ ) + λ DKL (x ∥ w⋆ ). 7

(12)

Table 1: Role of the inverse temperature β1 (cf. Theorem 4.3). β1 → 0 (λ → ∞)

β1 → ∞ (λ → 0)

Optimal wiring

qW (static symmetric prior)

min-KL minimiser of U on W

Cost U (wβ⋆ 1 )

U (qW )

minW U

Linear rate of Theorem 5.4

fast, (1 + ηλ)−1 small

slow, tends to sublinear

Proof. Fβ1 is continuous on the compact set W, so a minimiser exists; it is positive by Theorem 2.1 with c = λ and ψ = U − λ⟨log q, ·⟩. By convexity, U (x) ≥ U (w⋆ ) + ⟨∇U (w⋆ ), x − w⋆ ⟩, and by (4), DKL (x ∥ q) = DKL (w⋆ ∥ q) + ⟨log(w⋆ /q), x − w⋆ ⟩ + DKL (x ∥ w⋆ ). Adding, Fβ1 (x) ≥ Fβ1 (w⋆ ) + ⟨∇Fβ1 (w⋆ ), x − w⋆ ⟩ + λDKL (x ∥ w⋆ ) (the constant in ∇h = log w + 1 is orthogonal to x − w⋆ ). The first-order optimality condition at the positive point w⋆ makes the inner product nonnegative, giving (12); uniqueness follows since DKL (x ∥ w⋆ ) > 0 for x ̸= w⋆ . Theorem 4.3 (Temperature: monotonicity and limits). Let Umin = minW U and let w◦ be the unique minimiser of DKL (· ∥ q) over the convex set arg minW U . (i) β1 7→ U (wβ⋆ 1 ) is nonincreasing and β1 7→ DKL (wβ⋆ 1 ∥ q) is nondecreasing.
(ii) (High temperature) DKL (wβ⋆ 1 ∥ qW ) ≤ β1 U (qW ) − Umin ; hence wβ⋆ 1 → qW as β1 → 0. (iii) (Low temperature) 0 ≤ U (wβ⋆ 1 ) − Umin ≤ β1−1 DKL (w◦ ∥ q) and DKL (wβ⋆ 1 ∥ q) ≤ DKL (w◦ ∥ q); hence wβ⋆ 1 → w◦ as β1 → ∞. ⋆ , w′ = w⋆ Proof. Write K(w) = DKL (w ∥ q) and, for λ > λ′ , w = w1/λ 1/λ′ . ′ ′ (i) Optimality gives U (w) + λK(w) ≤ U (w ) + λK(w ) and U (w′ ) + λ′ K(w′ ) ≤ U (w) + λ′ K(w). Adding them, (λ − λ′ )(K(w) − K(w′ )) ≤ 0, so K(w) ≤ K(w′ ); the second inequality then gives U (w′ ) − U (w) ≤ λ′ (K(w) − K(w′ )) ≤ 0. (ii) Comparing with qW ∈ W: U (w) + λK(w) ≤ U (qW ) + λK(qW ). By Theorem 2.2, K(w) ≥ DKL (w ∥ qW ) + K(qW ). Hence λDKL (w ∥ qW ) ≤ U (qW ) − U (w) ≤ U (qW ) − Umin . Convergence follows from Pinsker’s inequality. (iii) Comparing with any wm ∈ arg minW U : U (w) + λK(w) ≤ Umin + λK(wm ) ≤ U (w) + λK(wm ), which gives both U (w) − Umin ≤ λK(wm ) and K(w) ≤ K(wm ); take wm = w◦ . Let w̄ be a limit point as λ → 0. By continuity, U (w̄) = Umin and K(w̄) ≤ K(w◦ ); since w◦ is the unique KL-minimal element of the convex set arg minW U (K is strictly convex), w̄ = w◦ , and compactness gives convergence of the whole family.

Theorem 4.4 (Gain of adaptation). For every β1 > 0, with w⋆ = wβ⋆ 1 , U (qW ) − U (w⋆ ) ≥

 1 DKL (w⋆ ∥ qW ) + DKL (qW ∥ w⋆ ) . β1

(13)

That is, the reduction of the iteration cost obtained by departing from the static prior is at least β1−1 times the Jeffreys (symmetrised KL) divergence between the static and the adaptive wiring. Proof. Apply (12) with x = qW : U (qW ) + λK(qW ) ≥ U (w⋆ ) + λK(w⋆ ) + λDKL (qW ∥ w⋆ ). Rearranging and using K(w⋆ ) − K(qW ) ≥ DKL (w⋆ ∥ qW ) (Theorem 2.2) gives (13). Proposition 4.5 (Symmetry inheritance). Let G be a group of permutations of E acting by (gw)e = wg−1 e . If U (gw) = U (w), gW = W and gq = q for all g ∈ G, then gwβ⋆ 1 = wβ⋆ 1 for all g and β1 ; i.e. the optimal wiring is constant on the G-orbits of E. Proof. DKL (gw ∥ gq) = DKL (w ∥ q), so Fβ1 (gw⋆ ) = Fβ1 (w⋆ ) with gw⋆ ∈ W; uniqueness (Theorem 4.2) gives gw⋆ = w⋆ . 8

Corollary 4.6 (Uniform traffic). If E is complete, q is uniform, and the workload is invariant under all permutations of pods (e.g. uniform all-to-all phases), then wβ⋆ 1 = q for every β1 : the static symmetric wiring is optimal. Proof. The symmetric group on pods acts transitively on pairs, so by Theorem 4.5 w⋆ is constant on E, i.e. uniform. Proposition 4.7 (When is the static prior optimal?). If qW minimises U over W, then wβ⋆ 1 = qW for all β1 > 0. If moreover q ∈ W (so qW = q), the converse holds: wβ⋆ 1 = q for some β1 > 0 if and only if q ∈ arg minW U . Proof. The optimality condition of w ∈ W for Fβ1 is ⟨∇U (w) + λ log(w/q), x − w⟩ ≥ 0 for all x ∈ W. At w = qW the KL-projection condition gives ⟨log(qW /q), x − qW ⟩ ≥ 0; if also ⟨∇U (qW ), x − qW ⟩ ≥ 0, the sum is nonnegative. If q ∈ W the log term vanishes at w = q, so the condition for Fβ1 coincides with the optimality condition for U . Remark 4.8. Taken together, Theorems 4.4, 4.5 and 4.7 delimit the role of the symmetric reference precisely: the static wiring is optimal exactly when it already minimises the cost, which symmetric workloads guarantee, and otherwise the loss incurred by retaining it is bounded below by a divergence between the two wirings. Figure 3 illustrates Theorem 4.3. Remark 4.9 (Scope: the continuous relaxation). Theorems 4.2 to 4.4 concern the continuous relaxation, in which µwe need not be an integer. Deployable wirings consist of integer numbers of circuits, and the properties established here are not inherited automatically by integer optima; the relation between the two problems is quantified in Theorem 5.7 and examined empirically in Section 8.3.

5

Entropic Proximal-Gradient Algorithm and Convergence

5.1

The Update as a KL Projection

Given wk ∈ W with positive coordinates, gk = ∇U (wk ) and a step ηk > 0, the Bregman proximal-gradient step [4, 17] with the entropy as reference function is n o wk+1 = arg min ⟨gk , w⟩ + λDKL (w ∥ q) + η1k DKL (w ∥ wk ) . (14) w∈W

Lemma 5.1 (Closed form). Let ak = 1/(1+ηk λ) and bk = ηk /(1+ηk λ), and define the geometric mixture k (wek )ak qe1−ak e−bk ge k ŵe = P (15) k. k )ak q 1−ak e−bk gf (w f f f Then wk+1 = arg minw∈W DKL (w ∥ ŵk ), the KL projection of ŵk onto W. In particular, without degree constraints the update is the multiplicative rule wk+1 = ŵk . Proof. With c = λ + 1/ηk , the objective of (14) equals, up to a constant, X X
c we log we − we λ log qe + ηk−1 log wek − gek . e

e

Dividing by c, the bracket becomes log ŵek +log Z with Z the normaliser in (15); since the objective is c DKL (w ∥ ŵk ) − c log Z.

9

P

e we = 1,

Algorithm 1 Entropic proximal gradient for minW U + β1−1 DKL (· ∥ q) 1: Input: prior q > 0, λ = 1/β1 ≥ 0, initial step η0 > 0 2: w0 ← qW ▷ static symmetric wiring; = q if q ∈ W 3: for k = 0, 1, 2, . . . do 4: gk ← ∇U (wk ) by the forward–backward pass (Theorem 3.4) 5: η ← 2ηk−1 ▷ η−1 = η0 /2 6: repeat 7: form ŵ by (15) with step η; w+ ← arg minW DKL (· ∥ ŵ) via Theorem 5.2 8: if U (w+ ) > U (wk ) + ⟨gk , w+ − wk ⟩ + η −1 DKL (w+ ∥ wk ) then η ← η/2 9: until the test in the previous line passes 10: ηk ← η, wk+1 ← w+ 11: end for Lemma 5.2 (Dual of the KL projection). Let ŵ > 0 and W as in (6) with b = (r/µ)1, satisfying Assumption A1. For y ∈ RV≥0 let we (y) ∝ ŵe exp(−(A⊤ y)e ) and ϕ(y) = − log

X

⊤

ŵe e−(A y)e − ⟨b, y⟩.

(16)

e

Then ϕ is concave and smooth with ∇ϕ(y) = Aw(y) − b, the problem maxy≥0 ϕ(y) attains its maximum at some y⋆ , strong duality holds, and w(y⋆ ) = arg minW DKL (· ∥ ŵ), with complementary slackness yv⋆ (Aw(y⋆ ) − b)v = 0. Proof. For fixed y ≥ 0, minimising the Lagrangian DKL (w ∥ ŵ) + ⟨y, Aw − b⟩ over ∆ is a Gibbs variational problem with unique solution w(y) and value ϕ(y); ϕ is a pointwise infimum of affine functions of y, hence concave, and its gradient follows by Danskin’s theorem. The primal is convex with affine inequality constraints and, by Assumption A1, has a feasible point in the relative interior of the domain ∆ of DKL (· ∥ ŵ); the refined Slater condition [5, §5.2.3] gives strong duality and dual attainment. Since the Lagrangian minimiser is unique, w(y⋆ ) is the primal solution. The dual has only |V | variables and is solved by a quasi-Newton method with bound constraints; each evaluation costs O(|E|).

5.2

Convergence

Lemma 5.3 (Three-point property). For the step (14), wk+1 is positive and for every x ∈ W, ⟨gk , x⟩ + λDKL (x ∥ q) + η1k DKL (x ∥ wk ) ≥ ⟨gk , wk+1 ⟩ + λDKL (wk+1 ∥ q) + η1k DKL (wk+1 ∥ wk )   + λ + η1k DKL (x ∥ wk+1 ). (17) Proof. The objective φ of (14) has the form c h+ψ with c = λ+ηk−1 and ψ linear, so its minimiser is positive by Theorem 2.1. For linear ψ the Taylor expansion of φ around the positive point wk+1
is exact: φ(x) = φ(wk+1 )+⟨∇φ(wk+1 ), x−wk+1 ⟩+c h(x)−h(wk+1 )−⟨∇h(wk+1 ), x−wk+1 ⟩ , and the last bracket equals DKL (x ∥ wk+1 ) on ∆. The first-order optimality condition makes the inner product nonnegative. Theorem 5.4 (Monotone descent and linear convergence). Let Assumptions A1 and A2 hold, let w⋆ be the minimiser of F = Fβ1 on W and F ⋆ = F (w⋆ ). Suppose every step satisfies the acceptance test of Algorithm 1, U (wk+1 ) ≤ U (wk ) + ⟨gk , wk+1 − wk ⟩ + ηk−1 DKL (wk+1 ∥ wk ), 10

(18)

which holds in particular whenever ηk ≤ 1/L (Theorem 3.3); backtracking therefore terminates with ηk ≥ ηmin := min{η0 , 1/(2L)}. Then for all k: (a) F (wk+1 ) ≤ F (wk ) − (λ + ηk−1 )DKL (wk ∥ wk+1 ); (b) F (wk+1 ) − F ⋆ ≤ ηk−1 DKL (w⋆ ∥ wk ) − (λ + ηk−1 )DKL (w⋆ ∥ wk+1 ), hence DKL (w⋆ ∥ wk+1 ) ≤ (1 + ηk λ)−1 DKL (w⋆ ∥ wk ); Q (c) consequently DKL (w⋆ ∥ wk ) ≤ i<k (1+ηi λ)−1 DKL (w⋆ ∥ w0 ) ≤ (1+ηmin λ)−k DKL (w⋆ ∥ w0 ) −1 and F (wk+1 ) − F ⋆ ≤ ηmin (1 + ηmin λ)−k DKL (w⋆ ∥ w0 ); (d) if λ = 0 and ηk ≡ η ≤ 1/L, then F (wK ) − F ⋆ ≤ DKL (w⋆ ∥ w0 )/(Kη). With w0 = q uniform, DKL (w⋆ ∥ w0 ) ≤ log |E|. Proof. Fix x ∈ W. Convexity of U gives U (x) ≥ U (wk ) + ⟨gk , x − wk ⟩. Combining (18), the three-point property (17) and this inequality, F (wk+1 ) ≤ U (wk ) + ⟨gk , wk+1 − wk ⟩ + ηk−1 DKL (wk+1 ∥ wk ) + λDKL (wk+1 ∥ q) ≤ U (wk ) + ⟨gk , x − wk ⟩ + λDKL (x ∥ q) + ηk−1 DKL (x ∥ wk ) − (λ + ηk−1 )DKL (x ∥ wk+1 ) ≤ F (x) + ηk−1 DKL (x ∥ wk ) − (λ + ηk−1 )DKL (x ∥ wk+1 ). Taking x = wk gives (a). Taking x = w⋆ gives the first part of (b); since F (wk+1 ) ≥ F ⋆ , the left side is nonnegative, which gives the contraction. Iterating gives the first part of (c); the bound on F follows fromP(b) and ηk ≥ ηmin . For (d), summing (b) with λ = 0 over k ⋆ ⋆ 0 k = 0, . . . , K − 1 telescopes to K k=1 (F (w ) − F ) ≤ DKL (w ∥ w )/η, and by (a) the left side is K ⋆ at least K(F (w ) − F ). If ηk ≤ 1/L, (18) follows from Theorem 3.3; halving from any η > 1/L P stops at some η ∈ (1/(2L), 1/L]. Finally, DKL (w⋆ ∥ q) = e we⋆ log(|E|we⋆ ) ≤ log |E| for uniform q. In practice the KL projection, and hence the step (14), is computed only approximately. The following result quantifies the effect. Theorem 5.5 (Inexact steps). Suppose that, instead of (17), the computed iterate wk+1 ∈ W satisfies (18) and the three-point inequality (17) with x = w⋆ up to an additive error δk ≥ 0 on its right-hand side. Then DKL (w⋆ ∥ wk+1 ) ≤

DKL (w⋆ ∥ wk ) + ηk δk . 1 + ηk λ

(19)

In particular, if λ > 0, ηk ≥ ηmin and δk ≤ δ, then DKL (w⋆ ∥ wk ) ≤ (1+ηmin λ)−k DKL (w⋆ ∥ w0 )+ δ/λ whenever ηk ≡ ηmin , and in general lim supk DKL (w⋆ ∥ wk ) ≤ δ supk ηk /(ηmin λ). If P ⋆ k k ηk δk < ∞, then DKL (w ∥ w ) → 0. Proof. Repeating the chain of inequalities in the proof of Theorem 5.4 with x = w⋆ and the perturbed three-point inequality gives F (wk+1 ) − F ⋆ ≤ ηk−1 DKL (w⋆ ∥ wk ) + δk − (λ + ηk−1 )DKL (w⋆ ∥ wk+1 ). Since the left-hand side is nonnegative, multiplying by ηk yields (19). Writing ak = DKL (w⋆ ∥ wk ) and ρk = (1 + ηk λ)−1 , we have ak+1 ≤ ρk ηk δk . For constant Pρk ak + −1 k j ηk = ηmin and ρ = (1+ηmin λ) , unrolling gives ak ≤ ρ a0 +ηmin δ j≥1 ρ = ρk a0 +ηmin δ ρ/(1− ρ) = ρk a0 + δ/λ. In general, put ρ̄ = (1 + ηmin λ)−1 ≥ ρk and η̄ = supk ηk . Since η 7→ η/(1 + ηλ) η̄δ(1+ηmin λ) η̄δ η̄ δ is increasing, ρk ηk δk ≤ η̄δ/(1 + η̄λ), whence lim supk ak ≤ (1+η̄λ)(1−ρ̄) = (1+η̄λ) ηmin λ ≤ ηmin λ . P Finally, if k ηk δk < ∞, the recursion ak+1 ≤ ρ̄ak + ηk δk with ρ̄ < 1 and summable forcing gives ak → 0. Theorem 5.5 is a conditional error-propagation result: it asserts what follows if the computed iterates satisfy the perturbed three-point inequality with defects δk . We do not derive δk from 11

the stopping rule of the dual solver. Whether the implementation meets the hypothesis is instead verified numerically: for the runs of Figure 2 we evaluated the defect of the three-point inequality at a reference optimum after every step, and obtained maxk ηk δk ≤ 1.6 × 10−10 and P −9 over 400 iterations, with degree-constraint residuals below 2.4 × 10−8 . By k ηk δk ≤ 1.0 × 10 (19) the resulting error floor lies several orders of magnitude below the accuracies reported in Section 8. Remark P 5.6 (Complexity and scope). Each iteration costs one forward–backward pass (O(|N |+ |A| + s ns )), one mixture (15) (O(|E|)) and a |V |-dimensional concave maximisation; by (c) an
ε-accurate solution needs O (1+Lβ1 ) log(log |E|/(ηmin ε)) iterations. These guarantees concern the continuous relaxation; the integer topology problem is treated next and compared with an exact MILP in Section 8.3. Theorem 5.4 is an instance of the analysis of Bregman proximal gradient methods under relative smoothness [4, 17]; its role here is to certify the algorithm actually used, not to contribute new convergence theory.

5.3

Integer Circuits

⊤ A deployable wiring has integer circuit counts x ∈ ZE ≥0 with Ax ≤ r1 and 1 x ≤ µ; its capacity is b0 + cxe , i.e. that of w = x/µ. Let W ′ = {w ≥ 0 : 1⊤ w ≤ 1, Aw ≤ (r/µ)1} ⊇ W.

Proposition 5.7 (Relaxation bound and floor rounding). Let JZ⋆ be the optimal iteration time over integer wirings and w′ ∈ arg minW ′ J. Then J(w′ ) ≤ JZ⋆ , and the floor rounding x = ⌊µw′ ⌋ is feasible and satisfies   c c ⋆ J(x/µ) ≤ 1 + J(w′ ) ≤ 1 + J . (20) b0 b0 Z Proof. Every integer-feasible x gives x/µ ∈ W ′ , hence the first inequality. Flooring preserves the degree and budget constraints. For each pair, b0 + c⌊µwe′ ⌋ ≥ max{b0 , κe (w′ ) − c}, so κe (w′ )/κe (x/µ) ≤ max{κe /(κe − c) if κe − c ≥ b0 ; κe /b0 otherwise} ≤ 1 + c/b0 . Each transfer time, hence each phase duration, grows by at most this factor; compute durations are unchanged, so every path length and therefore J grows by at most 1 + c/b0 . When the pod bandwidth rc is fixed and the number of ports r grows, c/b0 → 0 and floor rounding becomes asymptotically exact. For small r we improve the rounded solution by a first-improvement local search over additions and degree-preserving 2-swaps {(i, j), (k, l)} → {(i, k), (j, l)}, accepting moves on a smoothed objective with an annealed temperature (smoothing removes the plateaus of the hard maximum). The local search carries no guarantee; Section 8.3 quantifies its gap to the exact optimum.

6

When to Reconfigure: Regret and Likelihood-Ratio Detection

6.1

Setting

Time is indexed by training iterations t = 1, . . . , T . The workload of iteration t is described by a distribution Pt over cells (s, e), s ∈ S, e ∈ E, with ds,e,t = V Pt (s, e) for a known total volume V (bytes per iteration are available from counters; their distribution must be estimated). Let M be the number of cells, Ut (w) = U (w; Pt ), Ft = Ut + λDKL (· ∥ q) and Ft⋆ = minW Ft . A policy keeps the deployed wiring wt unchanged or reconfigures it at cost C > 0 (downtime in seconds); a wiring computed at time s is εopt -optimal if Fs (ws ) ≤ Fs⋆ + εopt . The regret against the zero-switching-cost dynamic optimum is RT =

T X

Ft (wt ) − Ft⋆ + C NT ,

t=1

12

(21)

where NT is the number of reconfigurations, and the workload path length is P V1 = Tt=2 ∥Pt − Pt−1 ∥1 . Assumption A3 (Workload sensitivity). |U (w; P) − U (w; P′ )| ≤ Γ ∥P − P′ ∥1 for all w ∈ W. Lemma 6.1. For the smoothed critical-path cost (8), Assumption A3 holds with Γ = V /b0 . P Proof. ∂Tsτs /∂ds,e = πs,e /κe ≤ πs,e /b0 with e πs,e = 1, so |Tsτs (d) − Tsτs (d′ )| ≤ b−1 0 maxe |ds,e − ′ ′ ds,e |. LSEτ is 1-Lipschitz in the sup-norm of its arguments, so |U (d)−U (d )| ≤ maxP |ℓP −ℓ′P | ≤ P −1 ′ ′ ′ b−1 0 s maxe |ds,e − ds,e | ≤ b0 ∥d − d ∥1 = (V /b0 ) ∥P − P ∥1 . Lemma 6.2 (Holding regret). If ws is εopt -optimal for Fs , then for every t, Ft (ws ) − Ft⋆ ≤ 2Γ ∥Pt − Ps ∥1 + εopt .

(22)

Proof. Let wt⋆ minimise Ft . The KL terms do not depend on t, so Ft (ws ) − Ft⋆ = [Ut (ws ) − Us (ws )] + [Fs (ws ) − Fs (wt⋆ )] + [Us (wt⋆ ) − Ut (wt⋆ )]; the outer brackets are at most Γ ∥Pt − Ps ∥1 each, the middle one at most εopt .

6.2

Threshold Policies and Regret

Theorem 6.3 (Regret of the TV-threshold policy). Consider the policy that, with s the time of the last reconfiguration (initially s = 1, with an εopt -optimal initial wiring), reconfigures at t to an εopt -optimal wiring for Ft if and only if ∥Pt − Ps ∥1 > ϑ. Then NT < V1 /ϑ and RT ≤ T (2Γϑ + εopt ) + With ϑ⋆ =

C V1 . ϑ

(23)

p √ CV1 /(2ΓT ), RT ≤ 2 2Γ C V1 T + T εopt .

Proof. At reconfiguration times the excess is at most εopt ; otherwise ∥Pt − Ps ∥1 ≤ ϑ and Theorem 6.2 bounds the excess by 2Γϑ+εopt . Let 1 = t0 < t1 < · · · < tN be the reconfiguration times. Ptj ∥Pu − Pu−1 ∥1 ; the ranges By the triangle inequality for ∥·∥1 , ϑ < Ptj − Ptj−1 1 ≤ u=t j−1 +1 ⋆ are disjoint, so summing over j gives N ϑ < V1 . The choice of ϑ balances the two terms. Remark 6.4 (On the comparator). The benchmark in RT is the dynamic optimum that pays nothing for switching; it is a demanding comparator, and RT therefore also contains the unavoidable cost of tracking a moving optimum. The theorem does not compare the policy with the best policy that accounts for switching costs, and it treats the computation of an εopt -optimal wiring as instantaneous: computation time enters only through εopt (a wiring computed with a limited iteration budget) and, if it causes downtime, through C. The counting argument rests on the triangle inequality, which total variation satisfies and the KL divergence does not. KL statistics can nevertheless be employed by means of Pinsker’s inequality and its reverse, provided the reference distribution is bounded away from zero. Corollary 6.5 (KL-threshold policy). Assume that every reference distribution Ps used by the policy satisfies mini Ps,i ≥ pmin > 0, and that the policy reconfigures at t if and only if DKL (Pt ∥ Ps ) > ϑ2 /2. Then NT <

V1 ϑ (pmin /2)1/2

and

RT ≤ T (2Γϑ + εopt ) +

13

C V1 . ϑ (pmin /2)1/2

(24)

Proof. (i) Holding steps. If no reconfiguration occurs at t, then DKL (Pt ∥ Ps ) ≤ ϑ2 /2, and p Pinsker’s inequality gives ∥Pt − Ps ∥1 ≤ 2DKL (Pt ∥ Ps ) ≤ ϑ; by Theorem 6.2 the excess is at most 2Γϑ + εopt .
(ii) Reconfiguration steps. Since log(1 + x) ≤ x, DKL (Pt ∥ Ps ) ≤ log 1 + χ2 (Pt ∥Ps ) ≤ P P 2 −1 2 χ2 (Pt ∥Ps ), where χ2 (Pt ∥Ps ) = i (Pt,i − Ps,i )2 /Ps,i ≤ p−1 i (Pt,i − Ps,i ) ≤ pmin ∥Pt − Ps ∥1 . min 2 −1 2 1/2 Hence a reconfiguration implies ϑ /2 < pmin ∥Pt − Ps ∥1 , that is, ∥Pt − Ps ∥1 > ϑ (pmin /2) . (iii) Counting. The argument of Theorem 6.3, with the threshold ϑ (pmin /2)1/2 in place of ϑ, gives the bound on NT ; combining it with (i) yields the bound on RT . Only the reference distributions need to be bounded away from zero; in practice this is ensured by additive smoothing of the reference estimate. In practice Pt is estimated from n sampled packets per iteration. We first record a deviation bound whose dimension dependence is through the support size only. Lemma 6.6 (ℓ1 deviation of the empirical distribution). Let P̂ be the empirical distribution of p n i.i.d. samples from P, whose support has meff cells. Then E P̂ − P ≤ meff /n and, for 1 p
2 /2 −nu . every u > 0, Pr P̂ − P ≥ meff /n + u ≤ e 1

p p Proof. For a cell i, E|P̂i −Pi | ≤ (Var P̂i )1/2 = Pi (1 − PiP )/n√≤ Pp i /n; cells P outside√the support contribute nothing. By the Cauchy–Schwarz inequality, i Pi ≤ meff i Pi = meff , which gives the bound on the mean. Replacing one of the n samples changes P̂ − P

1

by at most 2/n,

so McDiarmid’s bounded-differences inequality [31] gives Pr( P̂ − P − E P̂ − P ≥ u) ≤ 1 1
2 exp −2u2 /(n · 4/n2 ) = e−nu /2 . Theorem 6.7 (Sampled traffic). Let P̂t be the empirical distribution of n i.i.d. samples from Pt , let meff bound the support sizes of all Pt , and let the policy reconfigure (to a wiring εopt -optimal for the estimated workload P̂t ) when P̂t − P̂s r ε=

meff + n

1

r

> ϑ. For δ ∈ (0, 1) put 2 log(T /δ) . n

(25)

Then, with probability at least 1 − δ, if ϑ > 2ε,
C V1 RT ≤ T 2Γ(ϑ + ε) + εopt + . (26) ϑ − 2ε p Proof. By Theorem 6.6 with u = 2 log(T /δ)/n, Pr( P̂t − Pt ≥ ε) ≤ δ/T for each t; a union 1

bound gives the event E = { P̂t − Pt

1

< ε ∀t} with probability at least 1 − δ. On E: the

wiring deployed at s is εopt -optimal for P̂s , so by Theorem 6.2 applied with P̂s in place of Ps , Ft (ws ) − Ft⋆ ≤ 2Γ Pt − P̂s

+ P̂t − P̂s ) + εopt ≤ 2Γ(ε + ϑ) + εopt 1 1 whenever no reconfiguration occurs (and ≤ 2Γε + εopt when it does). A reconfiguration implies ∥Pt − Ps ∥1 ≥ P̂t − P̂s

1

1

+ εopt ≤ 2Γ( Pt − P̂t

−2ε > ϑ−2ε, and the counting argument gives NT < V1 /(ϑ−2ε).

The radius (25) depends on the number of cells only through the support size meff , not through the ambient number M of cells. In the experiment of Section 8 (n = 2 × 105 , T = 600, δ = 0.05, meff ≤ 120 occupied cells) it gives ε ≈ 0.034, so the guarantee is non-vacuous for thresholds ϑ > 0.07.

14

6.3

The KL Indicator as a Likelihood-Ratio Statistic

Let Pref be the reference distribution at the last reconfiguration and let n = (n1 , . . . , nM ) be cell counts of N samples with empirical distribution P̂. Proposition 6.8 (GLR identity). For the multinomial model, the log generalised likelihood ratio of H0 : P = Pref against H1 : P ∈ ∆ equals Q supP∈∆ i Pini Q ni log = N DKL (P̂ ∥ Pref ). (27) i Pref,i Proof. The supremum is attained at the maximum-likelihood estimate P̂ = n/N , and P P i ni log(P̂i /Pref,i ) = N i P̂i log(P̂i /Pref,i ).

Hence a KL indicator of traffic change acquires a precise statistical meaning once its reference is the distribution at the time of configuration and it is weighted by the sample size: it is then the log generalised likelihood ratio. The identity is classical; its use here is to fix the reference and the weighting that a principled detector must employ. If a change may have occurred at an unknown time τ ∈ (s, t], the GLR statistic maximises over τ [16, 26]: Λt = max Nτ :t DKL (P̂τ :t ∥ Pref ), s<τ ≤t

â(t) = t − τ̂ + 1,

(28)

where P̂τ :t pools the Nτ :t samples of iterations τ, . . . , t and τ̂ is the maximiser. The lag â(t) is thus selected by maximum likelihood rather than by a heuristic, and the pooled estimate P̂τ̂ :t is the natural input for re-optimisation. Theorem 6.9 (False-alarm control). Suppose that no change occurs, i.e. all samples in iterations s + 1, . . . , t are i.i.d. from Pref , and the maximisation in (28) ranges over at most W windows, each with at most Nmax samples. Then for every h > 0, Pr(Λt ≥ h) ≤ W (Nmax + 1)M e−h .

(29)

In particular the threshold h = M log(Nmax + 1) + log(T W/δ) yields at most δ probability of any false alarm over T iterations. Proof. Fix a window with N samples. By the method of types [8, 10], the probability of observing a particular type Q is at most e−N DKL (Q ∥ Pref ) , and there are at most (N + 1)M types. Summing over types with N DKL (Q ∥ Pref ) ≥ h gives Pr(N DKL (P̂ ∥ Pref ) ≥ h) ≤ (N + 1)M e−h . A union bound over windows (and, for the second claim, over iterations) completes the proof. Remark 6.10. The bound is non-asymptotic but conservative when M is large; asymptotically 2N DKL (P̂ ∥ Pref ) is χ2M ′ −1 -distributed under H0 (Wilks), with M ′ the support size, which gives practical thresholds. When Pref is itself estimated we use additive smoothing; we do not analyse the resulting plug-in effect. The sequential statistic (28) and the regret analysis are complementary: the former controls false alarms, the latter quantifies the cost of any threshold.

7

Multi-Tenant Clusters

7.1

Shared Port Budget and the KL Chain Rule

(1) (K) . Since there is no traffic between jobs, the Let K jobs occupy disjoint pod F sets V , . . . , V candidate circuitsP are E = k Ek with Ek the pairs inside V (k) . The jobs share the OCS port budget µ < k |V (k) |r/2 through the simplex constraint, and W is the degree polytope P (k) (6). Write ρk = e∈Ek we (the share of job k) and we = we /ρk for e ∈ Ek , and similarly q 7→ (ρq , q(k) ).

15

P (k) ∥ q(k) ). Lemma 7.1 (Chain rule). DKL (w ∥ q) = DKL (ρ ∥ ρq ) + K k=1 ρk DKL (w (k) P P P (k) (k) e Proof. Expand k e∈Ek ρk we log ρkqw(k) and use e∈Ek we = 1. ρk qe

The prior thus penalises separately the allocation of the budget across jobs and the shape of each job’s wiring, corresponding to the mixed coordinates (ρ, {w(k) }) of the simplex.

7.2

Fairness Functionals

Let Jk (w) be the smoothed iteration time of job k (it depends only on the block Ek ), Jkref > 0 a reference time (e.g. job k alone with all its ports), and sk = Jk /Jkref the slowdown. Following the fairness families of network resource allocation [19], for weights ω ∈ ∆K−1 , ω > 0, and p ∈ [1, ∞) define X 1/p Φp (s) = ωk spk (30) , Φ∞ (s) = max sk (smoothed by LSEτf ), k

k

and the multi-tenant free energy F (K) (w) = Φp (s(w)) + λDKL (w ∥ q). Proposition 7.2 (Convexity; relation to α-fairness). For p ∈ [1, ∞], w 7→ Φp (s(w)) is convex on W, and it is L-smooth in ℓ1 for some finite L when p < ∞ or when Φ∞ is smoothed, so Theorems 4.2 and 5.4 apply to F (K) . Moreover, let the normalised throughput of job k be xk (w) = 1/sk (w) and uα (x) = x1−α /(1− α) (α ̸= 1). For α = p + 1 ≥ 2 the identity X

p 1 ωk up+1 xk (w) = − Φp s(w) (w ∈ W) (31) p k

holds. Consequently, for λ = 0 the set of wirings maximising the α-fair utility of throughputs over W coincides with the set minimising Φp ◦ s; the two objectives are related by a strictly decreasing transformation and their values differ. For λ > 0, the problems min Φp ◦ s + λDKL (· ∥ q) and min p1 (Φp ◦ s)p + λDKL (· ∥ q) are both convex but have different minimisers in general. Proof. Each sk is convex and positive (Theorem 3.3); Φp is a weighted p-norm on RK ≥0 , hence convex and nondecreasing in each argument, and so is LSEτf ; the composition of a convex nondecreasing function with convex functions is convex. On the compact set W the slowdowns lie in [smin , smax ] with smin > 0, where Φp is C 2 ; the chain rule and Theorem 3.3 bound the Hessian of the composition, giving aP finite L. For (31), up+1 (1/s) = (1/s)−p /(−p) = −sp /p, and summing with weights ωk gives − p1 k ωk spk = − p1 Φpp . Since t 7→ −tp /p is strictly decreasing on R>0 , maximisers of the left-hand side are exactly minimisers of Φp . With λ > 0 the transformation acts on one term of the objective only, so the minimisers need not coincide; convexity of p1 Φpp = p 1P p k ωk sk follows as above since t 7→ t is convex and nondecreasing on R≥0 . p Remark 7.3 (The range α ≥ 2). Two cautions apply. First, α-fair utilities must be applied to throughputs, not to costs: U 7→ U 1−α /(1 − α) has second derivative −αU −α−1 < 0 and is therefore concave in the cost. Second, for α < 2 the α-fair problem in throughputs need not be convex in the wiring: with the convex cost J(w) = 1 + w2 , the throughput 1/J fails to be concave at w = 1. Theorem 7.2 thus singles out α ≥ 2 as the range in which fairness and convexity are compatible for this model. Theorem 7.4 (Gibbs form of the fair optimum). Let w⋆ minimise F (K) over W and let πk = 1−p ⋆ ⋆ V ∂Φp /∂sk at s(w⋆ ) (for p < ∞, πk = ωk sp−1 k Φp ). Then w > 0 and there exist y ∈ R≥0 with ⋆ ⋆ yv (Aw − (r/µ)1)v = 0 such that, for e ∈ Ek ,  π ∂ s (w⋆ ) + (A⊤ y⋆ )  1 e k e k we⋆ = qe exp − . (32) Z λ Conversely, any w ∈ W satisfying (32) with such y⋆ is the minimiser. 16

Proof. Positivity follows from Theorem 2.1. The constraints are affine, so the KKT conditions are necessary and sufficient for the convex problem (Abadie’s constraint qualification holds for affine constraints). Stationarity at the positive point reads ∇(Φp ◦ s)(w⋆ ) + λ(log(w⋆ /q) + 1) + A⊤ y⋆ + ν1 = 0, with the multipliers of w ≥ 0 vanishing by complementary slackness. The chain rule gives ∂e (Φp ◦ s) = πk ∂e sk for e ∈ Ek , since sj does not depend on we for j ̸= k. Solving for w⋆ gives (32). The fairness weights πk ∝ ωk sp−1 increase with the slowdown, so jobs that are worse off k pull the shared wiring towards themselves, increasingly so as p grows; as p → ∞ the weight concentrates on the most slowed-down jobs. Proposition 7.5 (Pareto optimality). If ω
> 0 and p < ∞, the minimiser of F (K) is Pareto optimal for the vector s1 , . . . , sK , DKL (· ∥ q) over W; for p = ∞ it is weakly Pareto optimal. ⋆ Proof. For p < ∞, Φp is strictly increasing in each coordinate on RK >0 ; a point dominating w would have strictly smaller F (K) . For p = ∞ only weak monotonicity holds.

Remark 7.6 (Structure of the Pareto set). The Pareto set is not, in general, the convex hull of the single-job optima: the shape w(k) that is optimal for job k depends on its share ρk through the degree constraints, so mixtures of single-job optima computed with the full budget are typically infeasible or dominated.

7.3

Reconfiguration with Externalities

Reconfiguring job k only within its block, i.e. changing w(k) with ρ fixed, touches no circuit of any other job, because blocks are disjoint. For such block-restricted reconfigurations Theorems 6.3 and 6.7 apply job by job (with constants Γk , Ck , V1,k ), relative to the dynamic optimum with the shares held fixed; the regrets add. Changing ρ moves circuits between jobs and disturbs all jobs whose P blocks change; applying Theorem 6.3 to the aggregate objective with the social cost Csoc = k Ck 1[block k changes] internalises this externality.

8

Synthetic Experiments

8.1

Setup

All experiments use the model of Section 3, implemented in Python/NumPy; the KL projection is computed through the dual of Theorem 5.2 with a bound-constrained quasi-Newton method, global optima of the continuous problem are cross-checked with CVXPY and the Clarabel conic solver, and integer optima are computed with the HiGHS MILP solver through SciPy. Table 2 lists the parameters. Volumes are per iteration and aggregated over micro-batches; they are chosen to make pipeline, all-reduce and all-to-all phases comparable, not to reproduce a particular model. Table 2: Default experimental parameters. Fabric Job Compute Volumes

DAG Smoothing

N = 16 pods, r = 8 OCS ports/pod, c = 50 GB/s per circuit, b0 = 10 GB/s, µ = 56 (7/8 of the ports) S = 4 pipeline stages × D = 4 data-parallel replicas, one pod per (stage, replica) forward 80 ms, backward 160 ms per stage, optimiser 20 ms PP 3 GB per stage boundary and replica; ring all-reduce 10 GB per ring edge; MoE all-to-all 4 GB × max(πj , πj ′ ) between replicas j, j ′ of a stage, expert popularity π = (0.4, 0.3, 0.2, 0.1) unless stated forward chain, backward chain, all-reduce of stage i after its backward pass
τ = τs = 1 ms; prior q uniform over all 16 2 = 120 pairs

17

(b) distance to w ⋆ ; dotted: Thm. bound

(a) objective gap (monotone) 10 0

¸ = 0:02 (¯1 = 50)

DKL (w ⋆ kw k ) [nats]

10

0

¸ = 0:2 (¯1 = 5)

F(w k ) ¡ F ⋆ [s]

10 −2

10 −2

¸ = 1 (¯1 = 1)

10 −4

10 −4

10 −6

10 −6

10 −8

10 −8 0

100

200

300

400

0

100

iteration k

200

300

400

iteration k

Figure 2: Convergence of Algorithm 1 for λ =Q1/β1 ∈ {0.02, 0.2, 1}. (a) Objective gap (log scale). (b) DKL (w⋆ ∥ wk ) (solid) and the bound i<k (1 + ηi λ)−1 DKL (w⋆ ∥ q) of Theorem 5.4(c) (dotted, same colour).

8.2

Convergence and Temperature

Figure 2 runs Algorithm 1 from q for three temperatures. The free energy decreases monotonically in every run, and the KL distance to the optimum stays below the bound of Theorem 5.4(c) evaluated with the step sizes ηk actually accepted by backtracking (dotted). The bound is valid but conservative: the accepted steps are small (median ηk between 1.6 × 10−2 and 6.3 × 10−2 ) because the curvature of the smoothed maxima is large, while the observed contraction is much faster. Table 3 reports the checks; the final iterate agrees with the CVXPY/Clarabel optimum to within solver accuracy wherever Clarabel returned an optimal status. Table 3: Checks of Theorem 5.4 (400 iterations from q). “Bound viol.” is the largest excess of DKL (w⋆ ∥ wk ) over its bound; the last column is the difference to the CVXPY/Clarabel optimum. β1 λ = 0.02 λ = 0.2 λ=1

50 5 1

monotone yes yes yes

bound viol. 0 0 0

final gap [s] −4

1.5 × 10 9.3 × 10−8 2.2 × 10−10

|FMD − FCVX | 4.4 × 10−9 solver failed < 10−12

Figure 3 sweeps β1 from 0.1 to 104 . As predicted by Theorem 4.3, U (wβ⋆ 1 ) decreases and DKL (wβ⋆ 1 ∥ q) increases monotonically, between the static value U (q) and minW U ; both quantitative bounds hold at every grid point, and so does the Jeffreys bound of Theorem 4.4. The hard iteration time falls from 2.204 s for the static symmetric wiring to 1.384 s for the fully adaptive one (37% lower). Most of the gain is obtained for β1 ≳ 10, at a KL departure of about one nat; the curve thus indicates how much asymmetry a given gain requires, which is the design information β1 is meant to provide.

8.3

Integer Circuits Against an Exact MILP

We compare, for N ∈ {16, 24, 32} pods (S ∈ {4, 6, 8}, D = 4), dense and MoE workloads, and r ∈ {4, 8, 16, 32} ports per pod at fixed pod bandwidth rc = 200 GB/s (µ = N r/2): (i) Algorithm 1 (300 iterations, λ = 10−3 ) followed by floor rounding with greedy filling, (ii) the same followed by the local search of Section 5.3, and (iii) the exact MILP, in which each pair’s circuit count is encoded by binary variables and transfer times by their exact values at each count. Results are normalised by the relaxation bound minW ′ J of Theorem 5.7 (computed with CVXPY). 18

iteration time U [s]

2.2

(b) KL departure from the symmetric prior departure from prior [nats]

(a) communication cost vs. temperature U(w ¯⋆1 ) static prior U(q)

2.0

fully adaptive min U W

bound min U + DKL (w ± kq)=¯1

1.8 1.6 1.4 10 −1

10 0

10 1

10 2

10 3

1.50 1.25 1.00 0.75 0.50

DKL (w ¯⋆1 kq)

0.25

bound ¯1 (U(q) ¡ min U) DKL (w ± kq)

0.00

10 4

10 −1

10 0

temperature ¯1 = 1=¸

10 1

10 2

10 3

10 4

temperature ¯1 = 1=¸

iteration time / relaxation bound

Figure 3: Temperature sweep. (a) Smoothed iteration time of wβ⋆ 1 with the static and fully adaptive levels and the bound of Theorem 4.3(iii). (b) KL departure from the prior with the bound of Theorem 4.3(ii) and its limit DKL (w◦ ∥ q). N = 16 pods (MoE)

N = 24 pods (MoE) MD + rounding MD + rounding + local search MILP optimum

1.6

1.6

1.5 1.4

1.2

1.0 4

8

16

N = 32 pods (MoE) 1.6 1.5

1.4

1.4

1.3

1.3

1.2

1.2

1.1

1.1

1.0

1.0

32

OCS ports per pod r

4

8

16

OCS ports per pod r

32

4

8

16

32

OCS ports per pod r

Figure 4: Integer wirings for MoE workloads: iteration time divided by the relaxation lower bound, as a function of the number of OCS ports per pod at fixed pod bandwidth. Figure 4 and Table 4 lead to three observations, which we report without qualification. First, the exact MILP is fast on all instances (at most 4.5 s with HiGHS) and always finds the best integer wiring; on these sizes the continuous method therefore does not replace integer programming. Second, the relaxation bound of Theorem 5.7 is tight once pods have several ports: for r ≥ 8 the MILP optimum is within 3.3% of the bound (within 0.6% for r = 32), so the continuous problem solved by Algorithm 1 accurately predicts the achievable iteration time, whereas for r = 4 the integrality gap reaches 40%. Third, plain rounding loses up to 37% at r ≤ 8, and the local search recovers most of it: Algorithm 1 with rounding and local search is within 1.5–14.1% of the MILP for r = 4 and within 0–4.4% for r ≥ 8, the gap shrinking with r as Theorem 5.7 predicts. The running times of Algorithm 1 (14–57 s for 300 iterations) and especially of the local search reflect an unoptimised Python implementation; they are not competitive with a compiled MILP solver at this scale, and we make no runtime claim.

8.4

Dynamic Reconfiguration

The MoE expert popularity of each stage follows a random walk on its logits (standard deviation 0.03 per iteration) with abrupt routing shifts at t = 120 and t = 440; at t = 280 the job is re-placed onto a random permutation of the pods. The workload distribution is defined on the

19

Table 4: Integer wirings. LB: relaxation bound; Rnd: Algorithm 1 + rounding; LS: + local search; MILP: exact (opt. = proven optimal). Times in seconds (single core, Python implementation for MD and LS). N

workload

r

LB

Rnd

LS

16 16 16 16 24 24 24 24 32 32 32 32 16 16 16 16 24 24 24 24 32 32 32 32

dense dense dense dense dense dense dense dense dense dense dense dense MoE MoE MoE MoE MoE MoE MoE MoE MoE MoE MoE MoE

4 8 16 32 4 8 16 32 4 8 16 32 4 8 16 32 4 8 16 32 4 8 16 32

1.307 1.307 1.307 1.307 1.898 1.898 1.898 1.898 2.487 2.487 2.487 2.487 1.692 1.692 1.692 1.692 2.517 2.517 2.517 2.517 3.341 3.341 3.341 3.341

1.979 1.800 1.326 1.334 2.568 2.395 2.003 2.010 3.157 2.984 2.599 2.503 2.790 1.751 1.781 1.704 4.110 2.585 2.644 2.530 5.430 3.418 3.473 3.369

1.650 1.358 1.314 1.313 2.239 2.006 2.003 1.913 2.828 2.605 2.597 2.498 2.193 1.745 1.742 1.704 3.513 2.578 2.571 2.530 4.833 3.412 3.399 3.368

MILP tMD 1.447 (opt.) 1.339 (opt.) 1.314 (opt.) 1.313 (opt.) 2.064 (opt.) 1.960 (opt.) 1.919 (opt.) 1.908 (opt.) 2.670 (opt.) 2.549 (opt.) 2.508 (opt.) 2.498 (opt.) 2.160 (opt.) 1.707 (opt.) 1.707 (opt.) 1.694 (opt.) 3.418 (opt.) 2.540 (opt.) 2.540 (opt.) 2.519 (opt.) 4.664 (opt.) 3.374 (opt.) 3.369 (opt.) 3.345 (opt.)

26.4 40.3 27.1 44.7 37.5 14.1 14.5 27.5 44.2 39.1 27.7 24.7 57.4 20.9 26.0 18.5 24.3 15.0 20.8 16.9 22.3 31.4 36.0 34.6

tLS

tMILP

9.4 12.0 18.4 28.4 18.3 26.8 26.9 98.9 40.2 102.9 110.4 230.7 22.1 33.4 34.7 47.2 53.6 128.5 175.8 194.3 175.9 316.3 395.2 584.4

0.09 0.27 0.35 1.97 0.22 0.63 1.56 4.51 0.22 0.87 3.18 4.18 0.12 0.05 1.02 0.64 0.29 0.11 2.01 1.11 0.85 0.13 2.78 1.77

M = 18 × 120 cells (phase slot, pair); each iteration n = 2 × 105 cell samples are observed. A reconfiguration costs C = 1 s and re-optimises by 40 iterations of Algorithm 1 on the estimated workload, started from 21 (wcurrent + q). Mixing with the prior matters: multiplicative updates recover slowly from coordinates that are nearly zero (after a re-placement the previously unused pairs are needed), and since w0 ≥ q/2 coordinatewise, DKL (w⋆ ∥ w0 ) ≤ log 2 + DKL (w⋆ ∥ q), so the bound of Theorem 5.4 does not depend on the previous wiring. The dynamic oracle re-optimises the true workload every iteration at no cost (25 warm-started iterations, and 400 iterations from both q and the previous wiring at t = 0 and at the three change points). We compare the static prior, a wiring optimised once, periodic re-optimisation, the TV-threshold policy of Theorem 6.7, and the GLR–CUSUM detector (28) with windows of at most 30 iterations, where the re-optimisation uses the pooled estimate P̂τ̂ :t . Table 5 and Figure 5 summarise the results (workload path length V1 = 4.7). Optimising once and never reconfiguring is the worst policy (regret 1282.0 s): after the re-placement at t = 280 the old wiring serves pairs that no longer carry traffic, and it is then far worse than even the static prior (525.0 s), which illustrates why a symmetric fallback is valuable. Every adaptive family shows the trade-off of Theorem 6.3 between holding excess and switching cost, with an interior optimum (Figure 5(b)). The best periodic schedule (k = 10) attains 142.1 s; the best TV threshold (ϑ = 0.05) attains 116.2 s with 9 reconfigurations; the GLR–CUSUM detector attains the lowest regret, 103.2 s with 16 reconfigurations at h = 104 , and is within 4% of it over h ∈ [104 , 3 × 104 ]. The conservative threshold of Theorem 6.9 for δ = 0.05, h = M log(Nmax + 1) + log(T W/δ) ≈ 3.4 × 104 , lies in this good range. Two caveats are visible. Large TV thresholds (ϑ ≥ 0.2) react only to the re-placement and miss the routing shifts, and very small GLR thresholds (h ≤ 103 ) fire at every iteration, because sampling noise in the estimated reference already produces statistics of that size. Moreover, all policies retain an excess of roughly 0.1 s per iteration after re-optimisation (Figure 5(a)); this is the εopt and estimation term of Theorem 6.7, caused by the limited budget of 40 iterations per reconfiguration and by the pooled estimate, and it bounds what any detector can achieve here.

20

(b) trade-off (dashed: regret = const)

excess Ut (w t ) ¡ Ut ⋆ [s]

10 1

optimise once

TV threshold (best)

periodic (best)

GLR--CUSUM (best)

cumulative excess [s]

(a) per-iteration excess (9-pt moving avg.)

10 0

10 −1

10 −2

10 3

10 2 periodic TV threshold GLR--CUSUM

10 1

10 −3 0

100

200

300

400

500

600

optimise once

10 0

iteration t

10 1

10 2

10 3

number of reconfigurations NT

Figure 5: Dynamic workload (T = 600, C = 1 s). (a) Excess iteration time over the dynamic oracle (log scale, 9-point moving average; vertical lines: abrupt changes). (b) Cumulative excess versus number of reconfigurations for each policy family; dashed lines have constant regret excess + CNT . Table 5: Dynamic reconfiguration: number of reconfigurations, cumulative excess over the oracle and regret = excess + CNT (seconds; oracle total 853.7 s). Best regret per family in bold.

8.5

Policy

parameter

NT

excess

regret

static prior q

–

0

525.0

525.0

periodic k

3 10 30 100 ∞ (once)

199 59 19 5 0

84.1 83.1 129.8 182.4 1282.0

283.1 142.1 148.8 187.4 1282.0

TV threshold ϑ

0.05 0.1 0.2 0.3 0.4 0.6

9 3 1 1 1 1

107.2 117.5 224.1 224.1 224.1 224.1

116.2 120.5 225.1 225.1 225.1 225.1

GLR–CUSUM h

300 1000 3000 10000 30000 100000

599 599 39 16 9 3

79.7 79.7 79.1 87.2 98.0 117.2

678.7 678.7 118.1 103.2 107.0 120.2

Multi-Tenant Fairness

Three jobs share an OCS layer: a dense pipeline job (4 × 2 pods), a skewed MoE job (2 × 4, all-to-all 6 GB) and a smaller MoE job (2 × 3, 3 GB), 22 pods with r = 8. The reference times Jkref (each job alone with all of its own ports) are 1.119 / 0.771 / 0.659 s. We solve the fair problem for p ∈ {1, 2, 4, 8, ∞} (λ = 10−3 , τf = 0.01) with port budgets µ = 52 and µ = 36, and compare with a static partition of the budget in proportion to the number of pods, each job optimised alone in its partition. Table 6 and Figure 6 show the predicted behaviour of the fairness weights of Theorem 7.4. As p increases, the maximum slowdown decreases monotonically (from 1.114 to 1.084 for µ = 52 and from 1.215 to 1.199 for µ = 36) while the mean slowdown increases slightly (from 1.080 to 21

(a) per-job slowdown under a shared OCS budget

slowdown Jk =Jkref

1.4

dense-PP

MoE-A

MoE-B

(b) efficiency vs. fairness (dotted: partition) max slowdown mean slowdown

1.28

1.3

1.26

1.2

1.24

1.1 1.22 1.0 1.20

0.9 p=1

p=2

p=4

p=8

p=1

static partition

p=1

p=2

p=4

p=8

p=1

Figure 6: Multi-tenant OCS budget (µ = 36). (a) Slowdown of each job for increasing fairness exponent p and for a static proportional partition. (b) Maximum and mean slowdown; dotted lines show the static partition. Table 6: Multi-tenant results: per-job slowdowns sk , maximum and mean slowdown, and budget shares ρk (dense / MoE-A / MoE-B). µ

p

s1

s2

s3

max

mean

shares ρ

52

1 2 4 8 ∞ static partition

1.114 1.110 1.105 1.099 1.084 1.050

1.062 1.065 1.068 1.071 1.081 1.119

1.063 1.065 1.067 1.071 1.080 1.104

1.114 1.110 1.105 1.099 1.084 1.119

1.080 1.080 1.080 1.080 1.082 1.091

0.26 / 0.42 / 0.32 0.27 / 0.42 / 0.31 0.27 / 0.42 / 0.31 0.28 / 0.41 / 0.31 0.30 / 0.40 / 0.30 0.36 / 0.36 / 0.27

36

1 2 4 8 ∞ static partition

1.205 1.204 1.203 1.202 1.199 1.122

1.215 1.212 1.209 1.205 1.199 1.285

1.174 1.178 1.183 1.188 1.198 1.230

1.215 1.212 1.209 1.205 1.199 1.285

1.198 1.198 1.198 1.198 1.199 1.212

0.26 / 0.42 / 0.32 0.26 / 0.42 / 0.31 0.26 / 0.43 / 0.31 0.27 / 0.43 / 0.31 0.27 / 0.43 / 0.30 0.36 / 0.36 / 0.27

1.082 and from 1.198 to 1.199): the budget moves towards the job that is currently worst off, at a small cost in aggregate efficiency. All runs decreased the free energy monotonically. Sharing the budget dominates the static proportional partition on both metrics: for µ = 36 the partition leaves the skewed MoE job at a slowdown of 1.285 while over-provisioning the dense job (1.122), whereas every shared solution keeps all slowdowns at or below 1.215. The effect of p is modest in this instance because the three jobs respond similarly to additional circuits; larger differences arise when jobs differ more strongly in their sensitivity to bandwidth.

9

Discussion

What the geometry contributes. The information-geometric structure is used for three concrete purposes. (i) The KL penalty to a symmetric prior gives a convex, strictly positive and symmetry-respecting interpolation between static and adaptive wirings whose two ends are characterised exactly (Theorem 4.3), and the Pythagorean inequality turns this into a quantitative gain bound (Theorem 4.4). (ii) Entropic Bregman geometry makes the proximal step a multiplicative update followed by a KL projection with a |V |-dimensional dual, and the three-point property delivers linear convergence without Euclidean projections onto the simplex. (iii) Exponential families appear twice more: the Gibbs distribution over DAG paths whose marginals 22

are the criticalities, and the multinomial likelihood whose GLR statistic is the KL indicator. Limitations. • Model. Routing is single-hop on direct circuits in parallel with a static fabric, and concurrent phases are assumed not to contend (Assumption A2). Multi-hop routing (as in ATRO [13]) would add a flow block coupled to the wiring through capacity constraints; the joint convexity of perspective functions κ ϕ(f /κ) makes this a natural extension, but its analysis is not done here. • Integrality. The theory concerns the continuous relaxation. On our instances an exact MILP solved by HiGHS is fast and, for few ports per pod, clearly better than rounding plus local search (Section 8.3); the continuous method is competitive when the number of ports per pod is large, where Theorem 5.7 predicts small rounding loss. We therefore do not claim that the method replaces integer programming. • Constants. L in Theorem 3.3 and Γ in Theorem 6.1 are worst-case and conservative; backtracking avoids needing L, but the regret bounds are loose in absolute terms and should be read as scaling laws. • Statistics. The false-alarm bound grows with the number of cells M ; pooling cells (e.g. by pod pair) reduces M at the cost of resolution. The effect of estimating the reference distribution is not analysed. • Evaluation. All experiments are synthetic. Validation on production traces and on real OCS hardware, including the cost and duration of reconfiguration, is required.

10

Conclusion

Optical circuit switching turns the wiring of an AI cluster from a fixed datum into a decision variable. We have argued that the appropriate language for this decision is the geometry of the probability simplex. In that language a single inverse temperature measures how far a deployment departs from the symmetric Fat-Tree reference; the limits of this departure, the gain it can buy and the circumstances in which it buys nothing admit exact statements; the causal structure of a training iteration becomes an exponential family over DAG paths whose marginals drive a convex and efficiently differentiable cost; and the decision to reconfigure becomes a likelihood-ratio test whose consequences are quantified by a regret bound. The same language accommodates clusters shared by several jobs, where convex fairness is available precisely in the range α ≥ 2. The experiments indicate both the value and the limits of this view. The continuous theory predicts the achievable iteration time accurately once pods have several optical ports, and likelihood-ratio detection gives the best reconfiguration policy among those examined; exact integer programming, however, remains preferable for small instances. Extending the framework to multi-hop routing and contention, and validating it on production traces and optical hardware, are the natural next steps.

A

Deferred Proofs

Lemma A.1 (Smoothed maximum of convex functions). Let ϕ1 , . . . , ϕn be convex and C 2 on an open convex set O with ∥∇ϕi ∥∞ ≤ G and v⊤ ∇2 ϕi v ≤ M ∥v∥21 . Then f = LSEτ (ϕ1 , . . . , ϕn ) is convex on O, ∥∇f ∥∞ ≤ G and v⊤ ∇2 f v ≤ (M + G2 /τ ) ∥v∥21 .

23

P Proof. With softmax weights σi ∝ eϕi /τ , ∇f = i σi ∇ϕi and X  X ⊤ ∇2 f = σi ∇2 ϕi + τ −1 σi ∇ϕi ∇ϕ⊤ . i − ∇f ∇f i

i

The bracket is a covariance matrix, positive semidefinite and dominated by Hence ∇2 f ⪰ 0 and X
2 ≤ (M + G2 /τ ) ∥v∥21 v ⊤ ∇2 f v ≤ σi M ∥v∥21 + τ −1 (∇ϕ⊤ i v)

⊤ i σi ∇ϕi ∇ϕi .

P

i

since |∇ϕ⊤ i v| ≤ ∥∇ϕi ∥∞ ∥v∥1 . The gradient bound is immediate. Proof of Theorem 3.3. Work on the open set O = {w : b0 +Bwe > b0 /2 ∀e} ⊃ RE ≥0 and evaluate E the bounds on R≥0 . The transfer time ts,e (w) = ds,e /(b0 + Bwe ) depends on one coordinate, is convex and decreasing, with |t′s,e | = ds,e B/κ2e ≤ Gs and t′′s,e = 2ds,e B 2 /κ3e ≤ 2B 2 d¯s /b30 for w ≥ 0; thus v⊤ ∇2 ts,e v = t′′s,e ve2 ≤ (2B 2 d¯s /b30 ) ∥v∥21 . By Theorem A.1, Tsτs is convex with ∥∇Tsτs ∥∞ ≤ Gs and curvature constant Ms . P A path length ℓP is a sum of such terms P and constants, so it is convex with gradient bound v∈P Gs(v) ≤ GH and curvature constant v∈P Ms(v) ≤ MH . A second application of Theorem A.1 gives convexity of U and (9). Monotonicity holds because each ts,e is nonincreasing and LSE is nondecreasing in each argument. For x, y ∈ ∆, Taylor’s theorem with integral remainder and (9) give U (y) ≤ U (x) + ⟨∇U (x), y − x⟩ + L2 ∥y − x∥21 , and Pinsker’s inequality 12 ∥y − x∥21 ≤ DKL (y ∥ x) yields relative smoothness. For the approximation bound, Ts ≤ Tsτs ≤ Ts + τs log ns , so ℓhard ≤ ℓP ≤ P ℓhard + Hτ log max n , and max ℓ ≤ U ≤ max ℓ + τ log |P|. s s s P P P P P

References [1] M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In Proc. ACM SIGCOMM, pages 63–74, 2008. [2] S. Amari and H. Nagaoka. Methods of Information Geometry, volume 191 of Translations of Mathematical Monographs. American Mathematical Society, 2000. [3] S. Amari. Information Geometry and Its Applications, volume 194 of Applied Mathematical Sciences. Springer, 2016. [4] H. H. Bauschke, J. Bolte, and M. Teboulle. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330–348, 2017. [5] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. [6] T. B. Brown et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877–1901, 2020. [7] A. Chowdhery et al. PaLM: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1–113, 2023. [8] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 2nd edition, 2006. [9] I. Csiszár. I-divergence geometry of probability distributions and minimization problems. The Annals of Probability, 3(1):146–158, 1975. [10] I. Csiszár. The method of types. IEEE Transactions on Information Theory, 44(6):2505– 2523, 1998. 24

[11] N. Ye, J. Liu, G. Zhu, W. Sun, and W. Hu. Beyond traffic matrix: DELTA—a DAG-aware OCS logical topology optimization for AIDCs. arXiv preprint arXiv:2603.28096, 2026. [12] Y. Huang et al. GPipe: Efficient training of giant neural networks using pipeline parallelism. In Advances in Neural Information Processing Systems, volume 32, 2019. [13] Y. Mao, Q. Zhai, X. Liu, X. Han, F. Li, S. Zhao, Y. Zhou, Z. Yao, and X. Zhu. ATRO: A fast algorithm for topology engineering of reconfigurable datacenter networks. arXiv preprint arXiv:2507.13717, 2025. [14] N. P. Jouppi, G. Kurian, S. Li, P. Ma, R. Nagarajan, L. Nai, N. Patil, S. Subramanian, A. Swing, B. Towles, C. Young, X. Zhou, Z. Zhou, and D. Patterson. TPU v4: An optically reconfigurable supercomputer for machine learning with hardware support for embeddings. In Proc. 50th Annual International Symposium on Computer Architecture (ISCA), 2023. [15] C. E. Leiserson. Fat-trees: Universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers, C-34(10):892–901, 1985. [16] G. Lorden. Procedures for reacting to a change in distribution. The Annals of Mathematical Statistics, 42(6):1897–1908, 1971. [17] H. Lu, R. M. Freund, and Y. Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28(1):333–354, 2018. [18] Llama Team, AI @ Meta. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. [19] J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, 8(5):556–567, 2000. [20] NVIDIA Corporation. DGX SuperPOD reference architecture. Technical documentation, 2024. [21] NVIDIA Corporation. GB200 NVL72. Product documentation, https://www.nvidia.c om/en-us/data-center/gb200-nvl72/, accessed October 2026. [22] G. Patronas et al. Optical switching for data centers and advanced computing systems. Journal of Optical Communications and Networking, 17(1):A87–A95, 2025. [23] L. Poutievski et al. Jupiter evolving: Transforming Google’s datacenter network via optical circuit switches and software-defined networking. In Proc. ACM SIGCOMM, 2022. [24] M. Shoeybi, M. Patwary, R. Puri, P. LeGresley, J. Casper, and B. Catanzaro. Megatron-LM: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.08053, 2019. [25] C. Shou, G. Liu, H. Nie, H. Meng, Y. Zhou, Y. Jiang, W. Lv, Y. Xu, Y. Lu, Z. Chen, Y. Yu, Y. Shen, Y. Zhu, and D. Jiang. InfiniteHBD: Building datacenter-scale high-bandwidth domain for LLM with optical circuit switching transceivers. arXiv preprint arXiv:2502.03885, 2025. [26] D. Siegmund and E. S. Venkatraman. Using the generalized likelihood ratio statistic for sequential detection of a change-point. The Annals of Statistics, 23(1):255–271, 1995. [27] M. Y. Teh, S. Zhao, P. Cao, and K. Bergman. COUDER: Robust topology engineering for optical circuit switched data center networks. arXiv preprint arXiv:2010.00090, 2020.

25

[28] H. Touvron et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023. [29] R. Urata et al. Mission Apollo: Landing optical circuit switching at datacenter scale. arXiv preprint arXiv:2208.10041, 2022. [30] W. Wang, M. Khazraee, Z. Zhong, M. Ghobadi, Z. Jia, D. Mudigere, Y. Zhang, and A. Kewitsch. TopoOpt: Co-optimizing network topology and parallelization strategy for distributed training jobs. In Proc. USENIX NSDI, 2023. [31] C. McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989.

26

Related documents

• Fault Detection and Bit-Error Rate Diagnostics in Optical Wireless Links Using Edge-AI#1356738
• RingStitch: Demand-Aware Optical Stitching for Fragmented TPU Clusters#1141941
• RingStitch: Demand-Aware Optical Stitching for Fragmented TPU Clusters#1122238
• On the physical origins of switching diversity in Cu-embedded SiO$_x$ memristive devices#997787
• Bringing AI to Autonomous Systems -- From Cognition to Collective Intelligence#1104490