{"id":"ea1d9ef6-258b-4148-85f9-045d6785dc81","arxiv_id":"2607.17880","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"A new theoretical framework for MoE serving with an O(√log k)-competitive online algorithm, an offline constant-factor approximation, and NP-hardness results.","lead":"The paper builds a mathematical model of how to assign GPUs to different experts in a mixture-of-experts language model over time, trading off response speed against the cost of moving capacity around. It proves the first worst-case performance guarantees for this task, including an online algorithm whose quality degrades only slowly as the number of GPUs grows.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main theorems hold within the stated model; the load-bearing weakness is the linear-speedup latency assumption, which is acknowledged but unvalidated.","rationale":"I re-read the proof chain for Theorem 4.1: the KL-regularized update, dual construction with scaled beta variables, the objective comparison via sublinearity of the conjugate, Lemma 4.3 bounding reconfiguration by latency, and Lazy Threshold Rounding's factor-3 latency and expected reconfiguration preservation. All steps check out, including the beta bounds from eta = max(1, ln(k+1)), nonnegativity of alpha_t, and the telescoping argument. The static 2-approximation, the integrality gap, and the DkS reduction are also internally consistent within the stated cost model. I found no algebraic or logical error that would compromise the formal claims. The strongest caveat is external validity: the theorem's practical meaning depends on the exact r/(1+x) latency law, which real MoE inference is unlikely to satisfy exactly. The authors acknowledge this abstraction explicitly, so it does not invalidate the paper as a theoretical contribution. The reader's weakest-assumption identification matches this concern, and the verdict should remain unchanged.","tokens_in":17041,"tokens_out":36570,"duration_ms":333887,"concrete_test":"Build a small MoE serving testbed, or a simulator calibrated to published DeepSeek-V3-style decoding traces, with m experts and k spare GPUs; fix a request mix and measure steady-state per-expert latency L_i(x_i) as x_i varies from 1 to k+1. Compare L_i with r_i/(1+x_i). If a least-squares fit of L_i = a_i/(1+x_i)^p yields p significantly below 1, or if L_i exhibits an overhead floor, then the linear-speedup assumption fails and the guarantees of Theorem 4.1 do not transfer quantitatively to that system.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.1's guarantees are proved for the formal model where per-expert latency is exactly r_{t,i}/(1+x_{t,i}) and total latency is the max over experts (Section 2). This functional form is used at every load-bearing step: the smoothness and sublinearity lemmas (Lemma 3.3), the Fenchel dual and the Omega(sqrt(log k)) barrier (Section 5), the Regularized Greedy analysis (Lemma 4.2), and the rounding cost bounds (Lemma 4.4). The assumption asserts that each additional GPU linearly reduces that expert's service time with no overheads, no communication or memory-bandwidth limits, no batching effects, and no shared experts. If actual MoE deployment latency flattens or exhibits overhead-dominated scaling, the O(sqrt(log k)) competitive ratio and the O(1) approximation are statements about a stylized problem, not about the serving system the paper motivates. The paper explicitly disclaims low-level details in Section 1.1 and footnote 1, so this is an external-validity boundary rather than an internal inconsistency; it is nevertheless the least secure condition on which the central claim's practical relevance depends.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes a dynamic resource-allocation problem for Mixture-of-Experts serving. There are m experts and n GPUs, with k = n - m spare GPUs; at each step a workload vector r_t arrives, the system chooses an integer allocation x_t with total k, and pays a latency cost max_i r_{t,i}/(1+x_{t,i}) plus an L1 reconfiguration cost. The main result (Theorem 4.1) is a polynomial-time online algorithm that is O(sqrt(log k))-competitive, obtained by combining a KL-regularized fractional greedy update with a new Lazy Threshold Rounding scheme, together with a polynomial-time O(1)-approximation for the offline dynamic problem. Section 5 proves an Omega(sqrt(log k)) lower bound for the online dual problem that underlies the primal-dual analysis. Section 6 analyzes the static variant, giving a 2-approximation, an integrality gap of 2 - 1/m, and NP-hardness plus ETH-based FPTAS inapproximability via a reduction from Densest k-Subgraph. The paper is a theory paper motivated by systems such as DeepSeek-V3, and it explicitly abstracts away low-level deployment details.","tokens_in":17254,"tokens_out":31995,"duration_ms":296705,"significance":"This is a solid theoretical contribution. The positive result is non-trivial: by exploiting smoothness of the latency function and sublinearity of its conjugate, the authors improve the standard logarithmic competitive ratio of regularized-greedy online primal-dual algorithms to O(sqrt(log k)). The Lazy Threshold Rounding scheme is simple, polynomial-time, and preserves both latency and reconfiguration costs up to constant factors. The lower bound for the online dual is an honest information-theoretic barrier for the primal-dual framework, and the offline results including the ETH-based FPTAS hardness are clean. All main proofs are present and internally consistent; the regularization parameter eta is chosen analytically rather than tuned, so the bounds are parameter-free in that sense. The principal caveat is external validity: the entire analysis is for the exact latency model max_i r_{t,i}/(1+x_{t,i}), which asserts linear speedup with no memory-bandwidth, communication, batching, or shared-expert effects. The paper partly acknowledges this in Section 1.1 and footnote 1, but the caveat deserves more prominence because it delimits the practical reading of the main theorems.","major_comments":[],"minor_comments":[{"comment":"The bound Primal <= 2 sqrt(eta) (OPT + m + k) bounds the convex-program value Primal = sum_t f_t(x_t) + sum_t y_t, whereas the online algorithm's actual cost is sum_t f_t(x_t) + 2 sum_t y_t. The missing factor of 3 (via Lemma 4.3) is harmless for the O(sqrt(log k)) claim, but the transition from the relaxation value to the true objective should be stated explicitly so the reader can verify the constant-factor bookkeeping.","section":"Section 4.1, proof of Lemma 4.2"},{"comment":"The one-sentence derandomization assertion before Theorem 5.1 is terse for a theorem that claims to rule out all online algorithms, including randomized ones. Because the adversary is adaptive, the deterministic lower bound can be lifted to randomized algorithms by fixing the random seed and applying the adversary's deterministic strategy to the resulting deterministic execution; please spell out this argument in full.","section":"Section 5, first paragraph"},{"comment":"The notation in Section 2 has rendering issues (for example, 'Z >0' and 'R m>=0' appear as separate tokens rather than as subscripted sets), and the symbol k is reused in Section 6.3 for the Densest k-Subgraph parameter after being defined as the number of spare GPUs. Please clean up the notation and add a remark when k is reused.","section":"Section 2 and Section 6.3"},{"comment":"Please add a sentence in the introduction or conclusion stating explicitly that the results are for the idealized latency model r/(1+x) with no memory-bandwidth, communication, batching, or shared-expert effects. Footnote 1 currently mentions only shared experts and placement optimizations; a more explicit statement about the latency model would set reader expectations about external validity.","section":"Section 1.1 and footnote 1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a clean theory contribution with no concerns about novelty or attribution; the related-work discussion covers online convex optimization, metrical task systems, and MoE placement. The theoretical claims are internally consistent. The only substantive caveat is the idealized latency assumption, which I do not think should block publication in a theory venue, but it should be stated more prominently and the minor clarifications above should be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuine algorithmic contribution. The MoE Serving model is new enough, the main theorems are substantial, and I checked the parts that matter — the KKT conditions, the dual scaling, the sublinearity lemma, the rounding bounds, and the lower-bound argument — and they are internally consistent. The paper should go to a serious referee.\n\nWhat is actually new: the cost function max_i r_{t,i}/(1+x_{t,i}) plus L1 switching cost, and the observation that the conjugate is sublinear, which lets regularized primal-dual beat the generic log k bound. The O(sqrt(log k)) competitive ratio, the dual lower bound, and the offline constant-factor approximation plus DkS-hardness for the static case are all real results. The rounding scheme is simple and polynomial-time, and the analysis via smoothness is clean. I did not find a load-bearing internal error. The lower bound is only for the online dual problem, not the original primal, and the paper says so; that is an honest limitation, not a hidden one.\n\nSoft spots, in proportion. The biggest is the latency model: per-expert latency exactly r/(1+x), max over experts. That asserts linear speedup with no overheads, no communication or memory-bandwidth limits, no batching. The paper acknowledges this in Section 1.1 and footnote 1, and all theorems are statements about that model. If real MoE latency is flatter or overhead-dominated, the guarantees apply to a stylized problem. That is an external-validity boundary, not a flaw in the math. Second, the static 2-approximation uses floor-and-arbitrary-round, and the DkS reduction assumes wlog x_i in {0,1}; that is fine when k <= m, but the degenerate k=m case is not spelled out. Minor. Third, the competitive ratio has additive terms in m and k; that is standard for this literature and not a real weakness. The citation pattern seems fair: prior smoothed online convex optimization work is credited, and the new structural condition is clearly identified.\n\nWho this is for: theorists in online algorithms, and anyone designing principled heuristics for MoE placement. It is not a systems paper and it does not validate the model against a real deployment. As a theory contribution, it deserves refereeing. I would accept it for a theory venue with the model caveat left as an acknowledged limitation. Send it to peer review.","headline":"Clean theoretical paper: O(sqrt(log k)) online algorithm and O(1) offline approximation for a stylized but well-defined MoE serving model; proofs check out, main caveat is external validity of the latency model.","tokens_in":17759,"tokens_out":5349,"would_cite":true,"duration_ms":47580,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W25","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces a formal model for Mixture-of-Experts serving and proves that a polynomial-time online algorithm can keep total cost within $O(\\sqrt{\\log k})$ of the optimal hindsight schedule, where $k$ is the number of GPUs beyond…","keywords":["Mixture-of-Experts","online algorithm","competitive ratio","GPU allocation","convex optimization","primal-dual","reconfiguration cost","NP-hardness"],"falsifier":"Measure the end-to-end latency of a single expert in a deployed MoE system with $1,2,4,\\ldots$ GPUs and fixed workload: if the latency does not decrease roughly as $1/(1+x)$ (e.g., it plateaus due to communication or bandwidth limits), then the cost model that the theorem optimizes does not describe the real system, and the competitive guarantee may not transfer.","tokens_in":16856,"feed_emoji":"🧠","tokens_out":2826,"duration_ms":27602,"temperature":0.7,"pith_summary":"The paper formalizes the problem of dynamically assigning GPUs to experts in a Mixture-of-Experts language model, balancing per-step latency against the cost of moving GPUs between experts. It establishes that this online problem admits a polynomial-time algorithm whose total cost is within $O(\\sqrt{\\log k})$ of the best schedule chosen with full knowledge of the future, where $k$ is the number of spare GPUs beyond one per expert. For the offline version, it gives a constant-factor approximation and proves that no fully polynomial-time approximation scheme exists unless the Exponential Time Hypothesis fails. A sympathetic reader would care because this turns an engineering heuristic (periodic rebalancing in deployed MoE systems) into a problem with provable guarantees and a clear performance barrier.","feed_headline":"Online MoE serving balanced within sqrt(log k) of optimal","feed_subtitle":"A polynomial-time algorithm provably matches the best hindsight GPU schedule up to a factor that grows only logarithmically in the number…","key_machinery":"The load-bearing object is the latency cost function $f_t(x_t) = \\max_i r_{t,i}/(1 + x_{t,i})$, which expresses the time for the busiest expert to finish its workload. The argument runs through its signed Fenchel conjugate $\\hat f_t(\\gamma_t) = \\inf_{x_t \\ge 0} (f_t(x_t) + \\langle x_t, \\gamma_t\\rangle)$, whose sublinearity $\\hat f_t(\\theta\\gamma_t) \\ge \\sqrt{\\theta}\\,\\hat f_t(\\gamma_t)$ is what improves the competitive ratio from the standard logarithmic bound to $O(\\sqrt{\\log k})$. The fractional algorithm is Regularized Greedy, which at each step minimizes the current latency cost plus a Kullback-Leibler divergence from the previous configuration; the rounding procedure, Lazy Threshold Rounding, uses per-coordinate random thresholds to preserve both expected allocation and reconfiguration cost up to constant factors.","core_discovery":"The central discovery is the pair of algorithmic results for the Dynamic MoE Serving problem: there is a fractional online algorithm, Regularized Greedy, that is $O(\\sqrt{\\log k})$-competitive, and it can be converted into a feasible integral schedule by Lazy Threshold Rounding while losing only a constant factor in both latency and reconfiguration cost. The competitive ratio is proved through a primal-dual analysis using an offset Fenchel dual, exploiting two structural properties of the latency cost function: a smoothness condition (adding GPUs can only reduce the cost in a controlled way) and a sublinearity condition on its conjugate. The paper also proves an $\\Omega(\\sqrt{\\log k})$ lower bound for the online dual problem, showing that the analysis is tight for the primal-dual approach, and for the static (no-reconfiguration) version it gives a 2-approximation and shows that the problem is NP-hard and admits no FPTAS under ETH.","pith_inferences":["Editorial inference: The smoothness and sublinearity properties are likely to hold for other latency models where doubling resources at best halves cost, so the $O(\\sqrt{\\log k})$ technique may transfer to resource allocation problems beyond MoE serving.","Editorial inference: The lower bound for the dual suggests that the $\\sqrt{\\log k}$ factor is not an artifact of the proof but an intrinsic price of not knowing the stopping time; whether a different relaxation could evade it remains open.","Editorial inference: A testable consequence is that in real deployments, the benefit of frequent rebalancing should diminish as $k$ grows, so systems with many spare GPUs can rely on simpler static or rarely-updated placements.","Editorial inference: The model ignores shared experts and communication costs; incorporating those would likely make the problem harder but the constant-factor approximation could still serve as a first-order placement strategy."],"forward_implications":["If the central theorem is correct, MoE serving systems can dynamically reallocate GPUs with a provable worst-case guarantee that grows only as the square root of the logarithm of the number of spare GPUs, rather than accepting heuristic performance.","The $O(1)$-approximation for the offline problem gives a principled baseline for capacity planning and placement that does not depend on forecasting future workload popularity.","The $\\Omega(\\sqrt{\\log k})$ lower bound for the online dual problem means that any primal-dual algorithm using this dual formulation cannot beat the stated competitive ratio, so improved ratios require a different analytical approach.","The NP-hardness of the static version implies that finding the exact fixed configuration is intractable in general, but the 2-approximation provides a simple practical fallback.","The model's dependence on only two cost components, latency and reconfiguration, suggests that adding more realistic constraints (e.g., communication overhead or shared experts) would change the guarantees but the framework may extend."],"supporting_citations":[{"why":"Provides the regularized greedy framework that the paper adapts, establishing the standard primal-dual competitive analysis via KL-divergence regularization.","marker":"[14]"},{"why":"Extends projection-based online algorithms to the k-server setting, supplying techniques for bounding divergence and dual feasibility.","marker":"[15]"},{"why":"Shows pure entropic regularization for metrical task systems, a basis for the choice of KL divergence in the online algorithm.","marker":"[18]"},{"why":"Supplies the online randomized rounding approach for generalized caching that Lazy Threshold Rounding adapts to preserve expected latency and reconfiguration cost.","marker":"[6]"},{"why":"Offers a finely-competitive paging algorithm whose rounding scheme is referenced as an alternative that is not computationally efficient.","marker":"[10]"},{"why":"Provides the Densest k-Subgraph hardness result used to rule out an FPTAS for the static problem under ETH.","marker":"[40]"},{"why":"Motivates the problem by reporting the DeepSeek-V3 deployment with periodic heuristic reconfiguration, grounding the model in a real serving system.","marker":"[38]"}],"fun_headline_variants":["MoE serving: online algorithm within sqrt(log k) of optimal","Online MoE scheduling: provable sqrt(log k) competitive ratio","MoE serving: polynomial-time online algorithm with sqrt(log k) guarantee","Serving MoE models: online algorithm matches optimal up to sqrt(log k)","MoE serving: dynamic GPU allocation with sqrt(log k) online bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The strongest assumption is that adding one more GPU to an expert reduces that expert's latency exactly according to $r_{t,i}/(1+x_{t,i})$, with no overhead from memory bandwidth, communication, or other interaction effects.","fun_headline_variants_meta":{"raw":{"variants":["MoE serving: online algorithm within sqrt(log k) of optimal","Online MoE scheduling: provable sqrt(log k) competitive ratio","MoE serving: polynomial-time online algorithm with sqrt(log k) guarantee","Serving MoE models: online algorithm matches optimal up to sqrt(log k)","MoE serving: dynamic GPU allocation with sqrt(log k) online bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000398,"raw_usage":{"total_tokens":2051,"prompt_tokens":881,"completion_tokens":1170,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":497,"completion_tokens_details":{"reasoning_tokens":1075}},"tokens_in":497,"tokens_out":1170,"duration_ms":10139,"temperature":1.0,"reasoning_tokens":1075,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:36:15.076961+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure the end-to-end latency of a single expert in a deployed MoE system with $1,2,4,\\ldots$ GPUs and fixed workload: if the latency does not decrease roughly as $1/(1+x)$ (e.g., it plateaus due to communication or bandwidth limits), then the cost model that the theorem optimizes does not describe the real system, and the competitive guarantee may not transfer.","supporting_citations":[{"cited_title":"Competitive analysis via regularization","cited_arxiv_id":null,"evidence_quote":"Provides the regularized greedy framework that the paper adapts, establishing the standard primal-dual competitive analysis via KL-divergence regularization."},{"cited_title":"k-servers with a smile: Online algorithms via projections","cited_arxiv_id":null,"evidence_quote":"Extends projection-based online algorithms to the k-server setting, supplying techniques for bounding divergence and dual feasibility."},{"cited_title":"Pure entropic regularization for metrical task systems","cited_arxiv_id":null,"evidence_quote":"Shows pure entropic regularization for metrical task systems, a basis for the choice of KL divergence in the online algorithm."},{"cited_title":"Randomized competitive algorithms for generalized caching.SIAM Journal on Computing, 41(2):391–414, 2012","cited_arxiv_id":null,"evidence_quote":"Supplies the online randomized rounding approach for generalized caching that Lazy Threshold Rounding adapts to preserve expected latency and reconfiguration cost."},{"cited_title":"Finely-competitive paging","cited_arxiv_id":null,"evidence_quote":"Offers a finely-competitive paging algorithm whose rounding scheme is referenced as an alternative that is not computationally efficient."},{"cited_title":"Almost-polynomial ratio eth-hardness of approximating densest k- subgraph","cited_arxiv_id":null,"evidence_quote":"Provides the Densest k-Subgraph hardness result used to rule out an FPTAS for the static problem under ETH."}],"review_version":2}