A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

• URL: http://arxiv.org/abs/2608.16947v1
• Date: Sat, 15 Aug 2026 03:51:27 GMT
• Title: A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
• Abstract summary: Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem.<n>We prove that the randomized primal competitive ratio is in fact Theta(1) for arbitrary numbers of experts.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem, where k is the number of replica GPUs beyond the mandatory copy of each expert. Their matching lower barrier applies to an auxiliary dual and leaves the primal order open. We prove that the randomized primal competitive ratio is in fact Theta(1) for arbitrary numbers of experts. The upper bound reduces reciprocal-max service costs to chasing positive bodies with covering row sparsity two. A finite tangent envelope approximates each reciprocal epigraph within a constant factor, summable positive resets convert accumulated service into movement, and a nonexpansive balanced projection removes the positive-body algorithm's resource augmentation. Combining the resulting fractional path with Lazy Threshold Rounding gives E[ALG] <= 10 C_PB OPT + (5 C_PB + 2) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. The full reduction, rounding composition, and quantified main theorem are machine-checked in Lean 4 relative to exact formal interfaces for the two cited source theorems. Deterministic rational controls and a fresh independent replay accompany the formal proof.

Related papers

• A Note on Scaling in Randomly Rotated Quantization and Its Connection to the CDEF +1 Pythagorean Relation [3.841157091833951]
  We point out the connection to classical results in statistical signal processing and communication theory.<n>The two reconstruction scales used in the EDEN line of work admit a natural interpretation as finite-dimensional, realization-dependent counterparts of the Wiener and unbiased coefficients.
  arXiv  Detail & Related papers  (2026-09-08T13:55:15Z)
• Entanglement Quantification via Symmetric Extensions: A Resource Theory Hierarchy [3.662037602213926]
  We introduce a hierarchy of entanglement measures Ek based on k-symmetric PPT extensions.<n>Each Ek, defined via a minimal eigenvalue shift, is faithful, convex, and monotone under free operations.<n>The hierarchy strictly refines PPT-robustness at k = 1, detects bound entanglement at k = 2, and converges exactly to the separability measure as k -> infinity.
  arXiv  Detail & Related papers  (2026-07-18T20:39:35Z)
• Exact ReLU realization of tensor-product refinement iterates [0.0]
  We prove that for every compactly supported continuous piecewise linear seed g:R2->R, the iterates Vn g admit exact ReLU realizations of fixed width and depth O(n)<n>This gives a first genuinely two-dimensional extension of the exact realization theory for refinement cascades.
  arXiv  Detail & Related papers  (2026-05-05T16:12:32Z)
• Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions [0.8307668828380427]
  Uniform random rotations are a useful primitive in applications such as fast Johnson-Lindenstrauss embeddings, kernel approximation, communication-efficient learning, and recent AI compression pipelines.<n>A common practical replacement is repeated structured random rotations built from Walsh-Hadamard transforms and random signs.<n>Applying the structured random rotation twice has been shown empirically to be useful, but the supporting theory is still limited.
  arXiv  Detail & Related papers  (2026-04-25T19:22:42Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms [8.636513507553504]
  We analyze two classical algorithms for solving additively composite convex optimization problems.<n>We focus on the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates.<n>Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.
  arXiv  Detail & Related papers  (2026-02-05T09:50:06Z)
• An hybrid stochastic Newton algorithm for logistic regression [0.0]
  We make use of a new hybrid Newton algorithm that includes two weighted components in the Hessian matrix estimation.<n>We show a surprising result on the almost sure convergence of the cumulative excess risk.
  arXiv  Detail & Related papers  (2025-12-01T15:27:40Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.