acceptodds
Under review as a conference paper at ICLR 2027

MarCap: From Marginal Routing Probabilities to Risk-Bounded MoE Workspace Provisioning with Lossless Replay

30 views

Abstract

MoE kernels reserve workspace before routing loads are known. Reserving for the worst case wastes memory, while fixed capacity factors fail to quantify overflow risk. We present MarCap (ginal-based acity provisioning), which maps routing marginals and a user-specified overflow risk budget to per-rank receive-buffer capacities. It optimizes over all possible fixed top- joint routing laws consistent with the marginals, covering arbitrary within-token expert co-selection correlations. Under the IID token assumption, we formulate receive-buffer capacity bounds in terms of extremal moment-generating functions and use exact feasibility conditions to reduce their computation to a small linear program that is solved efficiently by a lower convex-hull construction. We validate MarCap on 2.737B token-level routing records from two LLMs. Analysis identifies inter-token dependence in prefill and marginal drift as sources of potential undersizing. Traffic mixing reduces dependence-related shortfalls, while sliding-window recalibration mitigates drift-related undersizing. These results clarify the theory's practical scope. We implement MarCap in \mathtt{megamoe\underline{\}replay}, our fused MoE operator with bounded workspace and lossless replay. Across 660k EP4 invocations on Ascend 950PR, \mathtt{megamoe\underline{\}replay} preserves reference outputs and reduces scratch workspace requirements by 44.1–71.4% versus full reservation across the evaluated configurations. In the tested decode workloads tested on hardware, which are well aligned with the IID model, MarCap keeps the observed frequency of overflow which would trigger additional replay rounds within the user-specified risk budget. Experimental data confirm the resulting benefit: substantial scratch workspace savings with mean latency comparable to the worst-case reservation, with a median absolute difference of 0.36% across the tested decode configurations.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
mixture of experts, expert parallelism, capacity factor, MoE inference, workspace provisioning, load balancing, routing statistics, probabilistic capacity planning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_2nKNOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes MarCap, a framework for reducing memory overhead in Mixture-of-Experts (MoE) inference while controlling buffer overflow risks. The key idea is to determine receive-buffer capacities using expert routing marginals and a user-specified overflow risk budget, rather than relying on worst-case memory reservation or heuristic capacity factors. The authors formulate a worst-case moment-generating function over all fixed top-k routing distributions consistent with the observed marginals. Under the IID token assumption, they derive probabilistic capacity bounds and introduce an exact linear programming reduction, further accelerated by an efficient lower convex-hull construction. To handle occasional overflows without dropping tokens, MarCap is integrated with a lossless multi-round replay kernel. Experiments using 2.737 billion token-level routing records from two MoE models validate the proposed capacity estimation approach and investigate its limitations under token dependence and routing distribution shifts. Overall, the paper combines theoretical capacity estimation with practical kernel implementation to improve memory efficiency in MoE inference.

Critical strengths
  • Clear motivation: The paper addresses an important systems challenge in MoE inference: allocating sufficient workspace for unpredictable expert routing loads without excessive memory reservation. The motivation is clear, and the proposed risk-aware formulation is practically relevant.

  • Solid theoretical contributions: The paper provides a mathematically grounded formulation for capacity provisioning based on routing marginals. The exact linear programming reduction and efficient lower convex-hull construction are technically interesting and substantially reduce the computational overhead of capacity estimation.

  • Practical system implementation: The integration of MarCap with the lossless replay kernel provides a practical mechanism for handling occasional buffer overflows without dropping tokens. This connects the theoretical formulation with an implementable system design.

Critical weaknesses
  • W1. Presentation and readability: Although the paper provides extensive theoretical analysis and experimental results, the overall presentation could be improved. In particular, the experimental section contains numerous configurations, metrics, and appendix results, making it difficult to identify the key findings and understand how the theoretical contributions translate into practical benefits. The authors could consider organizing the experiments around clearer research questions (RQs), highlighting the main conclusions, and providing more intuitive summaries of the theoretical and empirical results.

  • W2. Robustness of risk guarantees: The theoretical risk guarantees rely on the IID token assumption and accurate routing marginals, which may not always hold in real-world MoE serving scenarios. The paper reports substantial overflow risk violations under inter-token dependence and marginal drift, despite the specified risk budget. Although the authors investigate traffic mixing, sliding-window recalibration, and request-level dependence, the robustness of these mitigation strategies under abrupt distribution shifts remains unclear. Further analysis of capacity provisioning under marginal estimation errors and realistic routing dynamics would strengthen the practical applicability of the proposed framework.

  • W3. End-to-end system evaluation: Although the paper evaluates extensive routing traces from two MoE models, the hardware experiments are primarily conducted on Ascend 950PR with EP4 configurations and constructed inputs. Therefore, it remains unclear whether similar memory savings and latency performance can be achieved across different hardware platforms, larger expert-parallel configurations, and realistic serving workloads.

Questions for authors
  • Q1. Could the authors improve the organization of the experimental section by explicitly summarizing the key findings and explaining how the theoretical results translate into practical memory and latency benefits?

  • Q2. Could the authors extend the evaluation to more realistic end-to-end MoE serving scenarios?

2 comments

We would first like to express our sincere appreciation for the time you dedicated to reviewing our manuscript, and we would like to address your questions and concerns below. The additional results mentioned will be incorporated into the final version of the paper submission.

Q1. On Organization

We thank the reviewer for this suggestion. We will improve the organization of the experimental section around clearer research questions with concise summarizations and make the connection between the theoretical results and the measured memory and latency benefits more explicit in the final manuscript.

Q2. On Broader Evaluation and and Portability

We have extended the hardware evaluation from EP4 on Ascend 950PR to EP8 on Ascend 950DT and added independent peak HBM memory measurements. Please refer to our response to Reviewer Zqt3's Q3 for the complete memory and latency results. At EP8 and local batch size 8192, scratch workspace decreases by 85.33% while the observed process memory peak decreases by 2952 MiB per rank, and the median paired mean latency change is -0.34%.

In practical full model serving, the released workspace can increase the memory budget available for resident requests when KV capacity becomes a constraint, reducing pressure to preempt, swap, or recompute. At a fixed batch without KV induced capacity pressure, the same expert computation is performed with lower memory reservation and similar kernel latency. The resulting serving benefits depend on the model's KV layout, parallel sharding, request lengths, allocator, and scheduler. Our controlled kernel measurements quantify the memory and latency effects of capacity selection while keeping these other conditions fixed within each experiment. The relationship to dropless and dynamic capacity systems is discussed in Section 5 and Appendix J.1 and in our response to Reviewer Zqt3's Q3.

On Risk Robustness

The contiguous prefill overflow issue is substantially mitigated by the block bound in Appendix C when the scheduler restricts each request's contribution to the allowed block length. We have evaluated this with both models and block lengths 64 and 1024. All reported Sliding configurations remain within the 1% overflow budget, while Frozen has one slight exceedance at 1.111%. The EP4 hardware experiments show zero observed overflow for block MarCap while retaining 14.52%-65.62% scratch workspace savings and similar execution latency. Please refer to our response to Reviewer Zqt3's Q2 for the complete setup and results.

For marginal estimation and shift, we use large history windows and sliding recalibration from completed routing observations, as discussed in the paper and our response to Reviewer kUGN's Q2. Abrupt changes can affect the validity of an existing capacity before the next update. As discussed in our response to Reviewer kUGN's Q3, per layer planning takes approximately 1-2 ms at the tested EP4/EP8 settings and can overlap with ongoing forward computation. Hence, the planning for an early recalibration triggered by a detected shift can run in the background without adding serving waiting time, provided that the updated capacity is ready before it is needed.

Thank you for the additional experiments and clarifications. They have addressed most of my concerns and strengthened the paper’s completeness and empirical support. Overall, I appreciate the contribution and remain supportive of acceptance. I will maintain my rating of weak acceptance.

Reviewer_Zqt3OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes MarCap, a method for choosing MoE receive-buffer capacities using expert routing probabilities and a target overflow risk. It derives a worst-case bound over compatible top-k routing distributions and provides an efficient algorithm for computing the capacity. The method is combined with a replay mechanism that handles overflow without dropping tokens.

Critical strengths

The paper makes meaningful theoretical contributions, including an exact reduction of the routing problem and an efficient capacity-planning algorithm.

The theory is clearly connected to the implementation.

I appreciate that the authors openly discuss failure cases and limitations.

Critical weaknesses
  1. The practical benefit of the exact method over the simple safe bound is unclear. Much of the savings over worst-case reservation may already be achievable with the simpler bound. In Table 5, the additional reduction is at most about 1.1% in three of the four settings. A broader comparison would help establish the value of the exact modeling.

  2. The token IID assumption does not hold for contiguous prefill. Although the authors acknowledge this limitation, the proposed mitigation strategies have not been shown to restore the stated risk guarantee in this setting.

  3. The paper lacks a full-model experiment showing how much peak HBM is saved, whether this allows a larger batch size or KV cache, and how throughput, TPOT, and tail latency compare with existing dropless or dynamic-capacity methods.

Questions for authors

1.Across a broader range of settings, how much additional memory does MarCap save over the simple safe bound, and when is the difference substantial?

2.Can the request-level bound in Appendix C meet the overflow budget for contiguous prefill? How much memory saving remains when using this bound?

3.Could you provide a full-model evaluation showing the actual memory and serving benefits, including a comparison with existing dropless or dynamic-capacity methods?

4 comments

We would first like to express our sincere appreciation for the time you dedicated to reviewing our manuscript, and we would like to address your questions and concerns below. The additional results mentioned will be incorporated into the final version of the paper submission.

Q1. On Simple Bound

First of all, we would like to clarify that, given that the common practice today for advance allocation in dispatch kernels is full reservation, the simple bound we explored in Appendix A shall be regarded as a simpler, more computationally efficient variant of MarCap, where we used the rank level marginals instead of the more granular expert level marginals in the computation. As we mentioned in the appendix, the extra information in expert level marginals can further improve the tightness of the bounds and guarantees that the resulting reservation for expert level MarCap is no larger than that of “rank level” MarCap under the same risk allocation.

In terms of additional memory saving, we noted that in the extreme one-expert-per-rank case the capacities computed by the two methods would agree with each other. Furthermore, we ran numerical experiments on other configurations and report the median and maximum extra saving relative to the rank level MarCap for Qwen at different EP values with the local token batch size varying between 1 and 8192, where the overflow risk budget is fixed at 1 percent. The result is documented in the table below, where both statistics include all three captured layers, both prefill and decode, and all tested batch sizes.

EPExperts per rankMedian extra savingMax extra saving
21280.00%0.88%
4640.00%0.86%
8320.00%2.88%
16160.81%21.76%
3286.42%44.05%
6445.50%38.95%
12823.46%21.74%
25610.00%0.00%

As for computational complexity, reusing the notation in the paper, rank level MarCap takes O(E+EP)O(E+\mathrm{EP}) time to compute the rank means. Under the condition that the number of experts and the allocated overflow budgets are uniform across ranks, the common capacity is then determined by the rank with the largest mean. Because its MGF has only two support points, each evaluation only costs O(1)O(1), resulting in O(E+EP+Iθ)O(E+\mathrm{EP}+I_\theta) total time. In contrast, expert level MarCap takes O(Elog⁡E+k)O(E\log E+k) preparation time per rank to construct the extremal distribution, followed by O(k)O(k) per MGF evaluation, so its total complexity is O(EP(Elog⁡E+k)+IθEPk)O(\mathrm{EP}(E\log E+k)+I_\theta\mathrm{EP}k). We ran numerical experiments to measure the complete computation time for a more concrete picture of the actual planning cost.

The table below reports mean complete planning times when the overflow risk budget is 1% across local token batch sizes for the middle recorded layer of each model in the decode phase. Times are in milliseconds with rank level time first and expert level MarCap in parentheses. We also report the ratio of expert level MarCap versus rank level. Note that in the one-expert-per-rank case, the two variants coincide and can use the same capacity computation, so we mark these cases as "Same computation" in the table.

EPQwen L19: mean time (ms)Expert/Rank ratioDeepSeek L14: mean time (ms)Expert/Rank ratio
20.769 (0.997)1.300.769 (0.983)1.28
40.771 (1.161)1.510.770 (1.127)1.46
80.775 (1.475)1.900.775 (1.417)1.83
160.774 (2.145)2.770.773 (2.148)2.78
320.775 (3.670)4.730.774 (3.375)4.36
640.777 (6.514)8.38Same computationN/A
1280.779 (12.104)15.54Outside gridN/A
256Same computationN/AOutside gridN/A

Therefore, we do observe that rank level MarCap can capture most of the capacity reduction with only a fraction of the computation time of expert level MarCap at larger EP values. Nevertheless, in the sliding recalibration setting outlined in the paper, capacity planning is performed once per window of about 7 million tokens for decode and 524k tokens for prefill, so the planning cost can be amortized over the kernel invocations within each window. Given the millisecond planning times measured above, this additional overhead is small in realistic workloads, making expert level MarCap a practical choice for obtaining tighter memory reservations.

Furthermore, with sufficient CPU parallelism, planning can run asynchronously alongside device computation. When both variants finish before the updated capacity is needed, their planning time difference is fully hidden, allowing the additional memory savings of expert level MarCap to be obtained without additional inference waiting. In this setting, the shorter planning time of rank level MarCap provides no further inference latency benefit. Please refer to our response to Reviewer kUGN's Q3 for a more detailed analysis of this overlap.

Q2. On Block Bound for Contiguous Prefill

We have performed both simulated capacity experiments using existing routing data and timing experiments on accelerator hardware with the block bound, which we shall refer to as the "block" variant of MarCap going forward. As mentioned in the paper, using such bounds requires the scheduler to ensure that the number of tokens contributed by any request to a batch does not exceed the allowed block/chunk length. In our experiments, the block length is set to 64 or 1024, covering situations where most request lengths exceed the cap and where most fall below it. Specifically, 73%–74% of requests exceed 64 tokens, while 75%–78% fall below 1024 tokens across the two models. To quantify the resulting batch utilization, we introduce the filling rate, defined as the actual number of tokens processed in a step divided by the configured batch token capacity, averaged over the evaluated steps. With all request slots occupied, the mean filling rate ranges from 96.50% to 96.59% for Qwen and from 96.93% to 97.01% for DeepSeek at a block length of 64, and from 56.86% to 56.88% and from 61.26% to 61.29%, respectively, at a block length of 1024.

In the CPU simulated capacity experiments, we tested similar Frozen and Sliding calibration settings to those in the paper for the contiguous prefill workload. Below we report the overflow rate and savings of the block variant of MarCap for the middle recorded layer of each model, with the overflow risk budget fixed at 1%. Each entry gives the compression rate (overflow rate) in percentage.

Frozen

Model / layerBlock capLocal bsEP4EP8EP16EP32EP64
Qwen L196412816.75 (0.000)49.67 (0.000)72.13 (0.000)86.80 (0.000)89.63 (0.000)
Qwen L196451246.28 (0.000)70.11 (0.000)84.14 (0.000)92.47 (0.000)93.66 (0.006)
Qwen L1964204861.08 (0.000)79.28 (0.000)89.29 (0.000)94.83 (0.011)95.40 (0.180)
Qwen L1964819268.18 (0.000)83.51 (0.000)91.61 (0.022)95.89 (0.363)96.02 (1.111)
Qwen L191024128N/A0.00 (0.000)0.00 (0.000)35.02 (0.000)54.01 (0.000)
Qwen L1910245120.00 (0.000)7.33 (0.000)43.43 (0.000)72.37 (0.000)79.68 (0.000)
Qwen L191024204816.79 (0.000)49.69 (0.000)72.14 (0.000)86.80 (0.000)89.63 (0.000)
Qwen L191024819246.29 (0.000)70.11 (0.000)84.14 (0.000)92.47 (0.000)93.66 (0.000)
DeepSeek L146412816.70 (0.000)49.43 (0.000)66.17 (0.000)73.24 (0.000)71.75 (0.001)
DeepSeek L146451246.22 (0.000)69.91 (0.000)79.36 (0.000)82.55 (0.000)79.22 (0.005)
DeepSeek L1464204861.02 (0.000)79.11 (0.000)85.20 (0.000)86.72 (0.009)82.71 (0.019)
DeepSeek L1464819268.14 (0.000)83.36 (0.000)87.89 (0.019)88.65 (0.192)84.39 (0.392)
DeepSeek L141024128N/A0.00 (0.000)0.00 (0.000)6.15 (0.000)20.24 (0.000)
DeepSeek L1410245120.00 (0.000)7.10 (0.000)36.04 (0.000)51.91 (0.000)55.39 (0.000)
DeepSeek L141024204816.74 (0.000)49.45 (0.000)66.19 (0.000)73.26 (0.000)71.77 (0.000)
DeepSeek L141024819246.23 (0.000)69.91 (0.000)79.36 (0.000)82.56 (0.000)79.22 (0.000)

Sliding

Model / layerBlock capLocal bsEP4EP8EP16EP32EP64
Qwen L196412815.84 (0.000)48.54 (0.000)71.09 (0.000)86.06 (0.000)88.72 (0.000)
Qwen L196451245.42 (0.000)69.36 (0.000)83.54 (0.000)92.09 (0.000)93.21 (0.006)
Qwen L1964204860.46 (0.000)78.83 (0.000)88.97 (0.000)94.65 (0.011)95.16 (0.090)
Qwen L1964819267.80 (0.000)83.27 (0.000)91.45 (0.022)95.79 (0.136)95.93 (0.185)
Qwen L191024128N/A0.00 (0.000)0.00 (0.000)32.37 (0.000)50.21 (0.000)
Qwen L1910245120.00 (0.000)6.22 (0.000)41.83 (0.000)70.88 (0.000)77.64 (0.000)
Qwen L191024204815.88 (0.000)48.53 (0.000)71.04 (0.000)85.99 (0.000)88.59 (0.000)
Qwen L191024819245.37 (0.000)69.30 (0.000)83.46 (0.000)92.04 (0.000)93.10 (0.000)
DeepSeek L146412816.23 (0.000)48.80 (0.000)65.66 (0.000)72.19 (0.000)71.24 (0.001)
DeepSeek L146451245.79 (0.000)69.53 (0.000)79.06 (0.000)81.95 (0.000)78.95 (0.005)
DeepSeek L1464204860.73 (0.000)78.90 (0.000)85.04 (0.000)86.41 (0.009)82.54 (0.019)
DeepSeek L1464819267.96 (0.000)83.24 (0.000)87.81 (0.019)88.46 (0.115)84.20 (0.157)
DeepSeek L141024128N/A0.00 (0.000)0.00 (0.000)4.70 (0.000)19.11 (0.000)
DeepSeek L1410245120.00 (0.000)6.49 (0.000)35.26 (0.000)50.24 (0.000)54.43 (0.000)
DeepSeek L141024204816.26 (0.000)48.81 (0.000)65.65 (0.000)72.12 (0.000)71.19 (0.000)
DeepSeek L141024819245.77 (0.000)69.49 (0.000)79.04 (0.000)81.88 (0.000)78.90 (0.000)

Thus, block MarCap has effectively controlled overflow in the tested contiguous prefill settings by replacing the IID token assumption with a block based one, as all reported Sliding configurations remain within the 1% overflow budget, while Frozen has one slight exceedance at 1.111%.

We also tested block MarCap on Ascend 950DT for latency performance under a contiguous prefill workload. We used prompts with token lengths no less than 8192 to increase the filling rate as a stress test of kernel performance. The filling rate was approximately 99.9% with a block length of 64 and 96.6%–96.8% with a block length of 1024. The results are attached below.

Local bs capBlock capIID MarCap overflowBlock MarCap overflowBlock workspace savingWorkspace saved (MiB/rank)Block mean-latency change
512640.78%0%28.49%49.16+3.87%
2048641.95%0%52.83%259.57-1.11%
81926417.58%0%65.62%1159.13+0.69%
2048102449.22%0%14.52%71.35+0.73%
8192102425.39%0%44.55%786.87+0.08%

We clearly observed that the proposed block MarCap can realize substantial memory reduction while maintaining similar latency.

Q3. On Memory and Serving Benefits

We address actual memory savings through controlled kernel measurements of expert level MarCap while keeping other conditions identical between Full and MarCap within each experiment.. In the new independent EP4 measurements on Ascend 950PR, Torch peak allocated HBM decreases by 76.09, 312.00, and 1260.27 MiB per rank at local batch sizes 512, 2048, and 8192. The reductions closely align with the scratch workspace reduction due to MarCap. We additionally measured the performance of expert level MarCap with EP8 parallelization on Ascend 950DT at local batch sizes 128, 512, 2048, and 8192. Scratch workspace decreases by 37.16%–85.33%, while the observed process memory peak decreases by 44–2952 MiB per rank, corresponding to reductions of 8.68%–62.80%. These reductions again closely track the scratch workspace savings from MarCap. The median paired mean latency changes across five process repetitions are −2.66%, +1.79%, −4.33%, and −0.34%, respectively.

In practical full model serving, MarCap's value would be that it increases the memory budget available for resident requests. At a fixed batch with no KV induced capacity pressure, our kernel performs the same expert computation with lower memory reservation and similar execution latency. When KV capacity limits residency, the additional workspace released by MarCap can accommodate additional cached tokens and reduce pressure to preempt, swap, or recompute. Our kernel measurements show that the workspace savings can be obtained while retaining similar kernel latency. We believe that a kernel level snapshot of the combined memory and latency benefits is the most appropriate for isolating MarCap's contribution, as differences in KV layout, parallel sharding, request lengths, page rounding, and metadata across models would introduce confounding variables in full model measurements. Thus, we summarize the results mentioned above in the table below.

HardwareEPLocal bsFull → MarCap peak (MiB/rank)HBM reduction (MiB/rank)MarCap scratch reduction (MiB/rank)Peak reductionMedian paired mean latency change
950PR4512374.57 → 298.4876.0976.0920.31%−1.04%
950PR42048706.14 → 394.14312.00311.4844.18%+0.22%
950PR481922028.79 → 768.521260.271260.6462.12%+0.08%
950DT8128506.75 → 462.7544.0044.278.68%−2.66%
950DT8512702.75 → 520.75182.00181.3925.90%+1.79%
950DT820481492.75 → 758.75734.00733.7649.17%−4.33%
950DT881924700.75 → 1748.752952.002950.9862.80%−0.34%

Section 5 and Appendix J.1 describe the relationship to existing dropless systems. MegaBlocks, Tutel, and DeepSpeed-MoE support execution based on realized load through their respective layouts and capacity mechanisms. MarCap chooses a receive reservation before the current batch's routing is observed and handles excess assignments by replay in that space. These approaches can be combined, including using MarCap to size a device-resident part of an elastic buffer. Cross-system throughput also depends on the expert kernels, communication backend, and scheduler. Our same-kernel Full comparison measures the contribution of capacity selection directly, and we will make this connection to serving memory pressure more explicit.

We will include those updates in the final submission version of the manuscript.

Reviewer_kUGNOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces MarCap, a method to provision per-rank receive-buffer capacity for Mixture-of-Experts (MoE) inference using only expert selection marginals and a user-specified overflow risk budget. It derives worst-case moment-generating function (MGF) bounds over all top-k joint routing distributions consistent with the marginals, yielding a risk-bounded capacity via Chernoff/union bounds under an IID token assumption, and provides an exact reduction to an at-most k+1 variable linear program along with a lower convex-hull algorithm that eliminates repeated LP solves. The authors validate the approach with 2.7B routed tokens and a fused, lossless-replay MoE kernel (megamoe_replay), demonstrating large scratch-memory savings and latency comparable to full reservation when the IID assumption approximately holds, and further analyze and mitigate undersizing due to inter-token dependence and marginal drift.

Critical strengths

Novelty

  • Reduces the intractable extremal MGF optimization (over all top-k couplings consistent with marginals) to an exact small LP over per-card counts using necessary and sufficient feasibility conditions (Theorem 1) derived via majorization-style inequalities and a max-flow/min-cut construction.
  • Proves existence of a universal MGF maximizer independent of θ (Theorem 2) and shows it is obtainable by a lower convex-hull construction over explicit bounds UsU_s, connecting MGF maximization to convex order on discrete tail integrals CsC_s.
  • Provides an efficient, LP-free algorithm with large practical speedups (≈95–110× vs naive), reusable across batch sizes and risk budgets.

Experimental rigorisity

  • Evaluates on extensive routing logs (2.737B tokens) from two different LLMs across multiple layers, EP values, and batch sizes; performs stress tests (decode/shuffled/contiguous prefill), and robustness checks across risk budgets 1e-2 to 1e-6.
  • Includes hardware experiments with a custom lossless-replay kernel on Ascend 950PR, showing substantial scratch reductions (44–71%) and close-to-full-reservation latency in IID-aligned workloads.
  • Diagnoses and mitigates practical deviations from theory (temporal dependence, marginal drift) via traffic mixing and sliding-window recalibration; confirms effectiveness under Poisson arrivals and full-batch decode stress.

Clarity of presentation

  • Clear problem framing (workspace provisioning under stochastic routing) and motivation for using marginals that are already logged in production systems.
  • Mathematical development is crisp with intuitive sketches and precise constraints; algorithmic speedups and complexity are well explained.
  • Metrics and experimental setup are explicitly defined, with comprehensive appendices and an open dataset for reproducibility.

Significance

  • Addresses a pressing systems challenge for MoE inference: quantifying and controlling overflow risk while reducing expensive HBM reservation.
  • Bridges theory (extremal couplings under marginal constraints) and systems (lossless replay) in a deployable capacity planning workflow.
  • Offers actionable insights for production serving (risk budgeting, recalibration cadence, effects of batching/mixing), potentially informing broader MoE inference stacks.
Critical weaknesses

Technical details

  • The IID token assumption is central; while decode and shuffled prefill align, contiguous prefill often violates it, causing undersizing without mitigations. The strength and generality of the “independent blocks” extension (Appendix C) are not empirically validated.
  • The Chernoff/union-bound approach may introduce looseness (both the per-rank union bound and MGF-based tail bound), potentially leaving capacity on the table in some regimes; no quantification of bound tightness vs empirical tails is provided.

Experimental gaps or methodological issues

  • Hardware validation is limited to EP4 and a specific accelerator; cross-hardware generality (e.g., common GPU stacks) and multi-EP hardware runs would strengthen claims.
  • Planning-time overhead impact in end-to-end serving scenarios: especially with frequent recalibration is important. It is not profiled in a live system context (though algorithmic speedups are shown).
  • Missing are: (i) a tighter benchmark against empirical tail estimates with confidence intervals (to illustrate data demand vs risk target), (ii) ablations on union-bound splitting strategies, and (iii) multi-EP hardware results.

Clarity

  • Some core ideas (e.g., the convex-order perspective implicit in Theorem 2, relation to sharp risk aggregation bounds) could be more explicitly connected to known literature to aid intuition.
  • The practical recipe for choosing recalibration window sizes and reacting to detected marginal drift is scattered; a concise deployment guide would help practitioners.

Missing related work or comparisons

  • More explicit contrast with empirical-risk calibration approaches (e.g., extreme value tail modeling from telemetry, uncertainty-aware quantile estimation) would clarify when MarCap dominates vs complements those methods.
  • Works like MegaBlocks/Tutel/DeepSpeed-MoE adapt to realized loads or use additional communication to achieve dropless execution; MarCap instead makes a priori allocations respecting a user risk budget with only marginal telemetry. This is complementary; MarCap could serve as a planning layer even for systems with elastic buffers (e.g., to size GPU- vs CPU-backed elastic spill).
Questions for authors
  1. Can you quantify the conservativeness of the Chernoff/union bound in representative settings (e.g., ratio Wreq/WmarW_req/W_mar or slack to empirical quantiles) and whether a data-driven θ\theta selection or refined tail bound (e.g., Bennett/Bernstein using extremal variance) could systematically reduce capacity further?
  2. How sensitive is overflow risk to non-uniform ϵ\epsilon allocation across ranks (e.g., proportional to marginal variance or extremal MGF), and does optimizing ϵc\epsilon_c over ranks further reduce W without violating the global budget?
  3. What is the end-to-end planning cost when sliding-window recalibration is performed at production cadences (e.g., every N tokens/seconds) for a multi-layer, multi-EP deployment, and how does it scale with E, k, and the number of ranks?
  4. Beyond EP4 on Ascend 950PR, do you have results on GPUs and at larger EP factors to assess the generality of scratch and latency gains, and to cross-check portability of megamoe_replay?
5 comments

We would first like to express our sincere appreciation for the time you dedicated to reviewing our manuscript, and we would like to address your questions and concerns below. The additional results mentioned will be incorporated into the final version of the paper submission.

Q1. On Bound Tightness

The relative excess can be readily computed from existing data as the statistics in terms of CF gaps have already been reported in the paper. It can be written as both WMar−WreqWreq\frac{W_{Mar}-W_{req}}{W_{req}} and −ΔCFCFreq\frac{-\Delta CF}{CF_{req}}. We observe that it decreases towards zero as batch size grows in these settings as expected. In particular, when the risk budget is set at 1%, we report the table below for the decode workload relative excess in the middle recorded layer for each model.

Local bsQwen L19 / EP8Qwen L19 / EP16Qwen L19 / EP32Qwen L19 / EP64DeepSeek L14 / EP8DeepSeek L14 / EP16DeepSeek L14 / EP32DeepSeek L14 / EP64
12821.02%21.99%16.78%5.39%21.04%14.87%8.05%4.81%
51210.85%11.15%7.00%2.49%10.74%7.81%4.40%2.55%
20485.43%5.46%3.05%1.17%5.37%3.99%2.23%1.22%
81922.68%2.41%1.42%0.46%2.73%2.05%1.07%0.60%
32768Outside gridOutside gridOutside gridOutside grid1.37%0.98%0.46%0.27%
131072Outside gridOutside gridOutside gridOutside grid0.68%0.44%0.14%0.10%

We also computed simultaneous 95% confidence intervals for the empirical quantiles using the separate ten million batch decode study. At the 1% risk budget, these intervals span at most one assignment row across the tested configurations.

Data driven or empirical capacity selection faces limitations beyond the ones mentioned in the paper. In the paper, we mentioned that a large amount of data would be needed when the risk budget is set to be very small, and recomputing the capacity after expert rearrangement is difficult if only histogram statistics are preserved. One might argue that collecting sufficient data for a realistic risk budget and retaining detailed routing records are practical in actual serving. Nevertheless, real world serving presents another challenge for the data driven approach, as the actual request arrival process is also time dependent, so the number and composition of requests contributing to each batch can change over time. The empirical load distribution then depends on the batch occupancy and request mix as well as the expert placement. Capacity estimates would need to account for these changing conditions through separate calibration or reconstruction from sufficiently detailed routing records. The relative excess result for the current version of MarCap has already demonstrated that it provides tight capacity estimates at large batch sizes, leaving limited room for further savings through empirical capacity selection in these settings, and it achieves this using only expert marginals.

On the possibility of deploying Bennett/Bernstein bounds using extremal variance, the universal maximizing distribution in Theorem 2 already gives the largest variance among routing distributions consistent with the supplied marginals. These inequalities use the variance and support to bound the MGF from above, while MarCap shall compute the exact extremal MGF directly. Consequently, with the same marginal and risk allocation, the resulting Bennett/Bernstein capacity bounds would not be tighter than the current MarCap bound. They could give simpler expressions or lead to cheaper computation. Further capacity savings can be explored through additional information about the joint routing distribution or a refinement of the risk allocation, which we discuss below.

Q2. On Nonuniform Risk Budget Allocation

We thank the reviewer for raising this issue. It is indeed possible to further improve the tightness of the bounds once nonuniform risk budgets across different ranks are allowed. Denoting each rank's overflow risk upper bound when the capacity on each rank is set to WW by εc(W)\varepsilon_c(W), originally we had εc(W)≤εEP\varepsilon_c(W) \leq \frac{\varepsilon}{EP}, while for nonuniform budget reservation we would need only to satisfy ∑cEPεc(W)≤ε,\displaystyle \sum_c^{EP} \varepsilon_c(W) \leq \varepsilon, where ε\varepsilon is the layer level risk budget. While the general MGF argument and Theorems 1 and 2 in the paper can be reused, nonuniform risk budget allocation needs extra search for the smallest feasible common integer capacity. Let r+,cr_{+,c} be the largest count with positive probability in rank cc's extremal count distribution. For W<Br+,cW<Br_{+,c}, the optimized risk bound for each rank can be expressed as εc(W)=inf⁡θ≥0exp⁡(Blog⁡Mext,c(θ)−θW),\varepsilon_c(W)=\inf_{\theta\ge0}\exp\left(B\log M_{\mathrm{ext},c}(\theta)-\theta W\right), using the same argument. For W≥Br+,cW\ge Br_{+,c}, we set εc(W)=0\varepsilon_c(W)=0 because the rank load cannot exceed this support limit. The capacity WallocW_{\mathrm{alloc}} is then given by Walloc=⌈min⁡{W∈R+:∑c=1EPεc(W)≤ε}⌉.W_{\mathrm{alloc}}=\lceil \min\{W\in\mathbb{R}^{+}:\sum_{c=1}^{\mathrm{EP}}\varepsilon_c(W)\le\varepsilon\}\rceil. Notice here that this construction shall guarantee the capacity WallocW_{\mathrm{alloc}} calculated from this nonuniform risk budget allocation to be no larger than that calculated under the previous uniform allocation.

In terms of computation, the lower convex hull construction can be reused. For each WW, if the minimum for rank cc is attained at a finite positive θc\theta_c, setting the derivative to zero gives Bψc′(θc)=W,ψc(θ)=log⁡Mext,c(θ).B\psi_c'(\theta_c)=W,\qquad \psi_c(\theta)=\log M_{\mathrm{ext},c}(\theta). Thus, nonuniform MarCap needs an additional outer capacity search, which can be done efficiently with binary search. In terms of algorithmic complexity, both the uniform and nonuniform versions require O(EP(Elog⁡E+k))O(\mathrm{EP}(E\log E+k)) for the lower hull construction, and the nonuniform one would have O(IWIθEPk)O(I_W I_\theta\mathrm{EP}k) for the scalar solves compared to the uniform version's O(IθEPk)O(I_\theta\mathrm{EP}k), where the II's are the iteration counts for the respective variables.

The table below reports mean complete planning times when the overflow risk budget is 1% across local token batch sizes for the middle recorded layer of Qwen in the decode phase. Times are in milliseconds with uniform time first and nonuniform MarCap in parentheses. We also report the ratio of nonuniform MarCap versus uniform.

EPQwen L19: mean time (ms)Nonuniform/Uniform ratio
21.079 (5.928)5.49
41.263 (6.364)5.04
81.594 (7.023)4.41
162.332 (8.106)3.48
323.941 (10.139)2.57
646.978 (14.885)2.13
12812.871 (24.278)1.89
25624.652 (43.185)1.75

With sufficient CPU parallelism and asynchronous updates, the additional planning time of nonuniform MarCap can also overlap with device computation. When both allocations finish before their updated capacities are needed, the planning time difference is fully hidden and the additional capacity saving is obtained without additional inference waiting.

In terms of additional memory saving, we report the median and maximum extra saving relative to uniform MarCap for Qwen at different EP values with the local token batch size varying between 1 and 8192, where the overflow risk budget is fixed at 1 percent. Both statistics include all three captured layers, both prefill and decode, and all tested batch sizes.

EPExperts per rankMedian extra savingMax extra saving
21280.00%1.56%
4640.02%1.85%
8320.07%1.54%
16160.40%3.03%
3281.24%8.57%
6442.28%8.62%
12822.52%15.56%
25612.05%16.67%

We tested similar Frozen and Sliding calibration settings to those in the paper for the IID decode workload. Below we report the overflow rate and savings of nonuniform MarCap for the middle recorded layer of Qwen, with the overflow risk budget fixed at 1%. Each entry gives the compression rate (overflow rate) in percentage.

Frozen

Local bsEP2EP4EP8EP16EP32EP64EP128EP256
1621.88 (0.000)54.88 (0.000)75.68 (0.000)87.40 (0.000)94.09 (0.000)94.21 (0.000)89.65 (0.100)80.49 (0.000)
12839.84 (0.000)68.19 (0.000)83.57 (0.000)91.69 (0.000)95.97 (0.000)94.95 (0.050)90.54 (0.200)81.69 (0.000)
51244.91 (0.000)71.64 (0.000)85.58 (0.000)92.74 (0.000)96.44 (0.000)95.14 (0.100)90.78 (0.200)82.01 (0.400)
819248.73 (0.000)74.17 (0.000)87.03 (0.000)93.50 (0.000)96.71 (0.000)95.28 (0.450)90.95 (1.900)82.25 (5.200)

Sliding

Local bsEP2EP4EP8EP16EP32EP64EP128EP256
1621.88 (0.000)54.88 (0.000)75.68 (0.000)87.40 (0.000)94.09 (0.000)94.21 (0.024)89.64 (0.089)80.45 (0.162)
12839.84 (0.000)68.19 (0.000)83.57 (0.000)91.69 (0.000)95.97 (0.000)94.94 (0.011)90.52 (0.067)81.65 (0.179)
51244.91 (0.000)71.64 (0.000)85.57 (0.000)92.74 (0.000)96.43 (0.000)95.13 (0.045)90.76 (0.000)81.97 (0.000)
819248.73 (0.000)74.16 (0.000)87.02 (0.000)93.49 (0.000)96.70 (0.000)95.27 (0.051)90.93 (0.102)82.22 (0.203)

The over budget Frozen cases reflect potential marginal shift, which sliding recalibration effectively mitigates. Thus, nonuniform MarCap provides additional memory savings, while sliding recalibration effectively controls overflow in the tested settings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.