acceptodds
Under review as a conference paper at ICLR 2027

ChunkBalance: Chunk Redistribution for Data-Parallel Balancing in MoE Prefill

Abstract

Mixture-of-Experts (MoE) models are typically deployed with data parallelism (DP) and expert parallelism (EP). In real-world MoE prefill scenarios, where requests are long and exhibit substantial variation in arrival rates and sequence lengths, DP-EP deployment can suffer from severe DP imbalance caused by two synchronous all-to-all communication barriers, leading to degraded system performance. To address this problem, we propose ChunkBalance, a data-parallel balancing method based on chunk redistribution for MoE prefill. ChunkBalance is built on two-chunk splitting and compute-communication overlap. We observe that: (1) unlike EP workloads, which are bound to specific ranks, DP workloads can be flexibly redistributed across the DP group; and (2) synchronization occurs only at the boundaries between the DP and EP stages, while there is no synchronization barrier within the DP stage. Based on these observations, ChunkBalance redistributes the DP workloads of the second chunk across the DP group, allowing workloads across chunks to compensate for one another and thereby improving load balance. ChunkBalance operates offline and can be combined with request-level scheduling algorithms and heterogeneous parallelism configurations. Its communication overhead is nearly 2/3 smaller than the total intermediate-state size, while the remaining overhead can be effectively hidden through self-overlapping. Experiments across various workload and system configurations show that ChunkBalance reduces MoE prefill end-to-end latency by up to 40%.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Machine Learning Systems, Mixture-of-Experts Model, Inference Acceleration

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_BxR8OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduce a technique for reducing dp imbalance problem in real world DP-EP deployment. Particularly when sequence length is heterogeneous. Since EP requires an all-reduce, the imbalance in dp can cause exessive Given that the dp workload can be redistributed between ranks, the authors propose to chunk DP workload into two chunks, keep chunk 0 in place while sending chunk 1 other ranks to reduce imbalance. Theorem 1 shows that pairing ascending chunk-0 loads with descending chunk-1 loads is optimal. Experiments is performed on Qwen3-30B-A3B, Moonlight-16B-A3B and Qwen3-235B-A22B, with a single 8×A800 node with synthetic log-normal request lengths. The authors report mean-TTFT reductions of up to 40%.

Critical strengths
  1. The paper studies a practical and clearly defined problem: with DP-EP deployment, there can be imbalances between dp ranks with existing inference frameworks such as vllm.
  2. the method is very simple and should be easy to implement in practice
  3. the method can be combined with request scheduling and TP/PP to achieve further improvements
Critical weaknesses
  1. The author seem to pad longbench text to a synthetic length distribution. I am not sure if this is valid experiment, as this could potentially distort MOE routing and skew the benchmark results. I also don't know if the padded tokens are attention masked or not. If it's attention masked, then in layers where dp imbalance matters, the workload isn't really following the requested distribution

  2. Generalization across workload. The method is validated on completely synthetic distribution based off longbench, with synthetic log-normal length(and padded to that) with no arrival process, and requests of batch uniformly sampled from [d,2d] occurs. While synthetic experiments are good for analysis, the paper requires real experiments to be more convincing. One obvious target might be longbench but without padding, with poisson arrival process. The author could also benchmark with public production traces and length and arrival time to analyze how much DP imbalance is a problem in real world, and how much improvement the method could bring in more realistic scenarios. (e.g. Mooncake FAST'25 traces, ServeGen, Azure LLM Inference Trace, BurstGPT)

  3. Adding P50/P99 TTFT and throughput would be more informative than just "Mean TTFT per execution step".

  4. The method is much less effective for modern llms (e.g. qwen3-next) with hybrid/linear attention. The state required for chunk-1 is only available after the owner have processed the r10 part of chunk-0 rather than just K/V, which introduces block waiting. This is prominent when r10 is long. The author also didn't discuss how the method applies to llms with linear attention.

Questions for authors
  1. Does the W/O chunkBlanace baseline use the same two-chunk pipelining, so only lack of redistribution is only difference?
  2. Is the padded tokens attended or masked in attention?
  3. With prefix caching, is the kv of chunk-1 tokens computed on other ranks returned to owner or they are kept on other ranks? This matters as this could have effects on either total communication volume or efficiency of kv cache.
7 comments

We sincerely thank you for the review!

Does the W/O chunkBlanace baseline use the same two-chunk pipelining, so only lack of redistribution is only difference?

Yes. The only difference between w/ and w/o ChunkBalance is whether the chunks are redistributed (σ∗\sigma* vs. the identity σ(i)=i\sigma(i)=i). All other experimental configurations are identical, so the measured gap is entirely attributable to redistribution.

The author seem to pad longbench text to a synthetic length distribution. I am not sure if this is valid experiment, as this could potentially distort MOE routing and skew the benchmark results. I also don't know if the padded tokens are attention masked or not. If it's attention masked, then in layers where dp imbalance matters, the workload isn't really following the requested distribution. Is the padded tokens attended or masked in attention?

The padded tokens are attended (not masked), so the measured cost reflects the workload at the target length. As you stated, padding affects end-to-end latency because padded tokens are also routed to experts, changing the routing distribution from that of the original sequence. However, the DP workload, which is where the performance gain comes from, remains a faithful function of the sequence length. Since the baseline uses the same padding and experiences the same skew, the comparison is still fair.

With prefix caching, is the kv of chunk-1 tokens computed on other ranks returned to owner or they are kept on other ranks? This matters as this could have effects on either total communication volume or efficiency of kv cache.

KV that is not involved in redistribution is stored as usual. For KV transferred during redistribution, ChunkBalance supports two storage strategies; neither adds communication volume or memory use.

  1. Store the full sequence on the last-chunk rank. The final chunk’s attention requires the request’s full KV prefix, so the KV ends up on the rank that owns the last chunk. Other ranks that participated in computing the request discard their KV after transferring it.

  2. Store each chunk’s KV on its assigned rank. The KV of preceding chunks at layer ii will temporarily reside in the current chunk's DP rank for attention computation, and discarded after proceeding to layer i+1i+1. This policy is intended for prefill-decode disaggregation, a common technique in LLM serving. The distributed KV is later transferred to the decode instance to form the complete sequence.

Generalization across workload. The method is validated on completely synthetic distribution based off longbench, with synthetic log-normal length(and padded to that) with no arrival process, and requests of batch uniformly sampled from [d,2d] occurs. While synthetic experiments are good for analysis, the paper requires real experiments to be more convincing. One obvious target might be longbench but without padding, with poisson arrival process. The author could also benchmark with public production traces and length and arrival time to analyze how much DP imbalance is a problem in real world, and how much improvement the method could bring in more realistic scenarios. (e.g. Mooncake FAST'25 traces, ServeGen, Azure LLM Inference Trace, BurstGPT) Adding P50/P99 TTFT and throughput would be more informative than just "Mean TTFT per execution step".

ChunkBalance targets acceleration within the model, so our original experiments used synthetic log-normal lengths to isolate this effect from request scheduling and to control the mean and variance when quantifying DP imbalance. ChunkBalance is orthogonal to request-routing mechanisms, and the two can provide additive benefits in serving. TTFT percentiles reflect both factors, so scheduling can influence the measured effect of ChunkBalance.

We agree that serving experiments help clarify the method’s practical impact. Following your suggestion, we evaluated ChunkBalance on the Mooncake FAST’25 production trace, which includes two real-world workload profiles (conversation and toolagent) as well as a synthetic trace with a Poisson arrival process. We report P50 and P90 TTFT below. The results show that DP imbalance is significant in these workloads and that ChunkBalance mitigates it.

Moonlight-16B

Trace / arrivalP50 TTFT(s) w/o CBP50 TTFT(s) w/ CBP90 TTFT(s) w/o CBP90 TTFT(s) w/ CB
conversation1.541.203.373.12
toolagent1.601.423.383.31
synthetic (poisson)2.181.514.053.21

Qwen3-30B

Trace / arrivalP50 TTFT(s) w/o CBP50 TTFT(s) w/ CBP90 TTFT(s) w/o CBP90 TTFT(s) w/ CB
conversation3.333.189.196.57
toolagent4.603.819.978.33
synthetic (poisson)6.625.3716.4713.33

The method is much less effective for modern llms (e.g. qwen3-next) with hybrid/linear attention. The state required for chunk-1 is only available after the owner have processed the r10 part of chunk-0 rather than just K/V, which introduces block waiting. This is prominent when r10 is long. The author also didn't discuss how the method applies to llms with linear attention.

ChunkBalance also applies to hybrid and linear attention, theoretically and empirically.

Linear attention commonly uses an affine associative recurrence. Formally, the state update can be written as St=At⊙St−1+BtS_t = A_t ⊙ S_{t−1} + B_t. Each token therefore defines an affine transformation ft(S)=At⊙S+Bt.f_t(S) = A_t \odot S + B_t.

For two tokens, composing their transformations gives ft+2∘(ft+1(Sin))=At+2⊙∘(At+1⊙Sin+Bt+1)+Bt+2f_{t+2}\circ(f_{t+1}(S_{{in}}))=A_{t+2} \odot \circ(A_{t+1} \odot S_{\mathrm{in}} + B_{t+1}) + B_{t+2}

Thus, the two-token chunk's local transformation is

\qquad \bar{B} = A_{t+2} \odot B_{t+1} + B_{t+2},$$ and its output state can be written as $$S_{\mathrm{out}} = \bar{A} \odot S_{\mathrm{in}} + \bar{B}.$$ Similarly, for a chunk of $n$ tokens, composing the transformations gives $$f_{t+n} \circ \cdots \circ f_{t+1}(S_{\mathrm{in}}) = \bar{A} \odot S_{\mathrm{in}} + \bar{B}.$$ The chunk can compute $\bar{A}$ and $\bar{B}$ from its own tokens **without knowing the incoming state $S_{\mathrm{in}}$**. Once the initial state arrives from the preceding chunk, it applies that state to the precomputed transformation: $$S_{\mathrm{out}} = \bar{A} \odot S_{\mathrm{in}} + \bar{B}.$$ Precomputing the chunk's local transformation takes $O(n)$ work and can proceed **without waiting for the preceding chunk transferring $S_{\mathrm{in}}$.** Applying the incoming state takes $O(1)$ work. ChunkBalance redistributes the dominant $O(n)$ workload to effectively mitigate DP imbalance. The $O(1)$ work of state updating does require to be sequential, while the transfer process starts when chunk 0's preprocess ends, and it can therefore be fully hidden behind chunk 1's preprocess. Thus, the required state is ready when chunk 1 starts state updating (even if not, the overhead is never dominant). We validated the empirical effectiveness of ChunkBalance on Qwen3.5-35B-A3B, a hybrid model with three linear-attention layers for every full-attention layer. | Trace / arrival | P50 TTFT(s) w/o CB | P50 TTFT(s) w/ CB | P90 TTFT(s) w/o CB | P90 TTFT(s) w/ CB | |---|---|---|---|---| | conversation | 1.87 | 1.67 | 3.93 | 3.72 | | toolagent | 2.08 | 1.68 | 4.47 | 3.28 | | synthetic (poisson) | 2.59 | 1.66 | 4.38 | 3.19 | We appreciate your thoughtful and insightful review, which greatly helps us in clarifying and improving our paper. Thank you again!

Thank you for the detailed response and for running the additional experiments on the Mooncake FAST'25 traces and the hybrid-attention model (Qwen3.5-35B-A3B). These results, together with the clarifications on the baseline configuration and padding, address most of my initial concerns. Could the authors address two remaining items:

  1. Interaction with prefix caching (Q3) and Mooncake replay setup. The response explains where newly com puted KV blocks reside across chunks, but does not address prefix caching itself (e.g., SGLang's RadixAttention). Multi-turn conversation and toolagent workloads in the Mooncake trace rely heavily on prefix KV reuse (hash_ids). Was prefix caching enabled in your Mooncake experiments? More generally, when a request is routed to an owner rank because it hits a cached prefix there, does migrating its second chunk to another DP rank require transferring that cached prefix KV across ranks as well (increasing communication volume), or leave the newly appended KV relocated away from the prefix holder for subsequent turns? Please also clarify the DP request-routing policy and arrival-rate scaling used in the Mooncake replay.

  2. Revised manuscript PDF. All of the new experiments (Mooncake traces, hybrid/linear attention, additional routing policies, and k > 2 chunks), the per-rank compute/communication stream schedule, and the broken appendix reference/caption fixes currently exist only in the rebuttal comments. Please upload an updated PDF incorporating these additions and clarifications.

Reviewer_BRN6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses DP load imbalance in DP-EP MoE prefill, where uneven request lengths cause replicas to wait at per-layer dispatch and combine barriers. The key idea behind ChunkBalance is that DP work can move across replicas because non-expert parameters are replicated. In a two-chunk pipeline, it reassigns the second chunk so that replicas with more work in the first chunk get less in the second. The paper proves this pairing is optimal; when the two chunks have similar workloads, it amounts to reversing the assignment. The main communication cost is transferring the prefix KV of the request that crosses the chunk boundary, which the authors argue is small and can overlap with computation. Experiments on three MoE models using 8× A800 GPUs report 20–29% TTFT reductions and claim up to 40%.

Critical strengths

S1. The paper offers a practical way to rebalance DP work. Moving only one request’s prefix KV keeps the overhead low and allows the approach to work alongside request-level scheduling.

S2. The design is simple and the results are consistent. It needs no extra GPUs, expert replication, or changes to EP kernels, and shows gains across three models, including with TP/PP enabled.

Critical weaknesses

W1. Baselines and attribution. What exactly does “w/o ChunkBalance” run—is it the same two-chunk pipeline with the identity permutation? Adding an external baseline, such as Preble’s scheduling or SGLang’s DP router, along with a lower bound, would help clarify how much of the gain comes from redistribution. Also, which setting yields the reported 40% reduction? I couldn’t find it in the figures.

W2. Schedule and objective. Could you walk through the per-rank schedule? If chunk 1’s DP work overlaps with chunk 0’s EP work, it seems the barriers would be determined by max w0 and max w1, neither of which changes under the permutation. If both chunks’ DP work instead runs before a shared barrier, how is the overlap achieved? It would help to connect Eq. (2) to the actual execution schedule and explain how w_i is measured.

W3. Migration cost and KV handling. I’m particularly interested in the implementation details, as implementation choices and interference between components could affect performance. The paper mentions asynchronous transfers overlapping with attention or chunk postprocessing, but this description seems rather vague. Could you clarify how this overlap is implemented, how much migration latency remains exposed, and whether the split request’s KV needs any further transfer before decode?

Questions for authors
  1. What exactly does "w/o ChunkBalance" run—the same two-chunk pipeline with the identity permutation? Please clarify the baseline setup, better isolate the gains from redistribution, and identify the setting behind the reported 40% reduction.
  2. How does Eq. (2) map to the actual per-rank schedule, and how is w_i measured?
  3. How is the KV migration implemented and overlapped, and what exposed time remains per step? What happens to the split request's KV before decode? Does moving chunk 1 away from the prefix holder affect prefix-cache reuse or duplicate KV?
7 comments

We sincerely thank you for the review!

What exactly does "w/o ChunkBalance" run—the same two-chunk pipeline with the identity permutation? Please clarify the baseline setup, better isolate the gains from redistribution

Yes. "w/o ChunkBalance" runs exactly the same two-chunk pipeline, with identical experimental configurations. The only difference is chunk redistribution — the baseline uses the identity permutation σ(i)=iσ(i)=i, while ChunkBalance uses the balanced permutation σ∗σ* from Eq. (2). Therefore the performance gap is totally attribute to chunk redistribution.

Also, which setting yields the reported 40% reduction? I couldn't find it in the figures.

In some cases with significant DP imbalance, TTFT reduction reaches approximately 40%. For example, in Fig. 2, Qwen3-30B with (μ,σ)=(8.0,1.0)(\mu,\sigma)=(8.0,1.0) achieves a reduction from 1.2 to 0.8, and with (8.0,1.5)(8.0,1.5), from 1.4 to 1.0.

ChunkBalance also effectively reduces TTFT in the real-world trace experiments. We provide some additional numbers in our response to Reviewer BxR8.

Adding an external baseline, such as Preble's scheduling or SGLang's DP router, along with a lower bound, would help clarify how much of the gain comes from redistribution.

ChunkBalance is orthogonal to request routing: the router decides where to place a request, while ChunkBalance redistributes workloads within model execution. Fig. 2 already includes SGLang DP router’s round-robin and balanced (least-workload) policies. To further clarify the interaction, we evaluated ChunkBalance on top of two additional SGLang DP router policies:

  • Random: route uniformly at random.
  • Power-of-Two-Choices (P2C): sample two ranks uniformly and pick the one with lower current workload.

Moonlight-16B-A3B-Instruct

req_schmu8.0_sigma1.0 w/o CBmu8.0_sigma1.0 w/ CBmu9.0_sigma1.0 w/o CBmu9.0_sigma1.0 w/ CB
random0.45430.32650.86870.5852
round_robin0.31280.25770.64390.5156
balanced0.29980.25620.61670.5141
power_of_two_choices0.34140.29380.68680.5731

Qwen3-30B-A3B-Instruct-2507

req_schmu8.0_sigma1.0 w/o CBmu8.0_sigma1.0 w/ CBmu9.0_sigma1.0 w/o CBmu9.0_sigma1.0 w/ CB
random0.78410.57281.67731.1478
round_robin0.58680.48351.24270.9944
balanced0.55990.47921.18770.9907
power_of_two_choices0.62300.51271.32371.0208

Qwen3.5-35B-A3B

req_schmu8.0_sigma1.0 w/o CBmu8.0_sigma1.0 w/ CBmu9.0_sigma1.0 w/o CBmu9.0_sigma1.0 w/ CB
random0.56740.44251.41470.7825
round_robin0.42580.35450.79050.6360
balanced0.40630.34820.75510.6265
power_of_two_choices0.47690.38350.84860.6723

Across all three models and routing policies, ChunkBalance provides a consistent additional gain. Since the remaining experimental settings are held constant, this gain comes completely from chunk redistribution.

How does Eq. (2) map to the actual per-rank schedule, and how is w_i measured? Could you walk through the per-rank schedule? If chunk 1's DP work overlaps with chunk 0's EP work, it seems the barriers would be determined by max w0 and max w1, neither of which changes under the permutation. If both chunks' DP work instead runs before a shared barrier, how is the overlap achieved? It would help to connect Eq. (2) to the actual execution schedule and explain how w_i is measured.

The overlap in two-chunk pipelining is computation with communication, using separate CUDA streams—not between two computation workloads. Both chunks’ DP (attention) work runs on the compute stream sequentially. The all-to-all communications run on a separate stream and are overlapped with computation.

Per-rank schedule (one MoE layer). Each rank runs a compute stream and a communication stream. DP_c = attention of chunk c, EP_c = expert/MoE of chunk c, disp_c/comb_c = the dispatch/combine all-to-all of chunk c:

   time ─────────────────────────────────────────────────────────────►

   Compute stream :  [ DP0 ][ DP1 ][ EP0 ][ EP1 ]
                                    ▲
                                    │  shared DP→EP barrier:
                                    │  every rank must finish DP0 AND DP1,
                                    │  so its cost = max_i ( w0_i + w1_i )   ◄── Eq.(2) minimizes this
                                    │
   Comm   stream :   [  ~  ][disp0][disp1][comb0][comb1]
                             └─ each all-to-all is hidden behind the compute of the OTHER chunk ─┘

Walk-through of the schedule:

  1. Compute stream executes DP0 → DP1 → EP0 → EP1. On rank i, DP0 costs w0_i and DP1 costs w1_i (after redistribution, w1_σ(i)).
  2. Comm stream is offset by one block: while the GPU computes DP1, the communication engine issues disp0; while it computes EP0, it issues disp1; while it computes EP1, it issues comb0.

Our core insight is indeed on this part: prior works generally consider collective communication as introducing a barrier, resulting in a workload of max⁡(w0)+max⁡(w1)\max(w_0) + \max(w_1). We observe that with compute-communication overlap, inter-chunk workloads inside one DP stage need no synchronization. The effective workload is therefore max⁡(w0+w1)\max(w_0 + w_1), allowing the redistribution max⁡(w0+wσ(1))\max(w_0 + w_{\sigma(1)}) to take effect.

How w_i is measured. w_i is the DP (attention) workload of a chunk on a rank, measured as the sum of the token sequence lengths of the request pieces assigned to that rank in that chunk.

How is the KV migration implemented and overlapped, and what exposed time remains per step?

Implementation. KV migration uses point-to-point send/receive between the DP rank that produced the state and the rank that will consume it (NCCL P2P over NVLink in our experiments).

Overlap. We split each chunk’s DP attention into preprocessing and postprocessing at the point where the intermediate state—the split request’s KV—becomes available. Chunk 0’s preprocessing produces the state, which is consumed during chunk 1’s attention. The transfer is issued asynchronously on the communication stream and overlaps with chunk 0’s postprocessing and chunk 1’s preprocessing, the same mechanism as used in DP-EP overlapping.

   chunk 0 (on source rank):   [ preprocess0 ]──►[ postprocess0 ]
                                 produces r10 KV   ╲
                                                    ╲  state transfer (r10 KV → dest rank)
                                                     ╲  P2P, async, on comm stream
   chunk 1 (on dest rank):                          [ preprocess1 ]──►[ postprocess1 ]
                                                     (independent of the    ╲ consumes
                                                      transferred state)     transferred KV

The transfer overhead can be effectively hidden behind computations, with essentially no overhead exposed. For example, for (μ,σ)=(9.0,1.0)(\mu, \sigma)=(9.0, 1.0), the measured end-to-end execution time and exposed communication times are:

MeasurementMoonlight-16BQwen3-30B
End-to-end time22.88 s42.81 s
Exposed communication time18 ms0.6 ms

What happens to the split request's KV before decode? Does moving chunk 1 away from the prefix holder affect prefix-cache reuse or duplicate KV? ... whether the split request's KV needs any further transfer before decode?

KV that is not involved in redistribution is stored as usual. For KV transferred during redistribution, ChunkBalance supports two storage strategies; neither adds communication volume or memory use.

  1. Store the full sequence on the last-chunk rank. The final chunk’s attention requires the request’s full KV prefix, so the KV ends up on the rank that owns the last chunk. Other ranks that participated in computing the request discard their KV after transferring it.

  2. Store each chunk’s KV on its assigned rank. The KV of preceding chunks at layer ii will temporarily reside in the current chunk's DP rank for attention computation, and discarded after proceeding to layer i+1i+1. This policy is intended for prefill-decode disaggregation, a common technique in LLM serving. The distributed KV is later transferred to the decode instance to form the complete sequence.

We will add these clarifications and the corresponding experiments to the revised version.

Reviewer_sNMpOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes a method to resolve bottlenecks occurring in MoE. The authors define MoE as consisting of data parallelization and expert parallelization, and that a bottleneck exists in expert parallelization where specific GPUs must wait for other GPUs to finish their tasks due to varying lengths. To address this, the authors propose ChunkBalance. ChunkBalance first divides each request into two chunks; if a GPU becomes overloaded while processing the first chunk, the second chunk is passed to another idle GPU to evenly distribute the workload. As a result, overall latency was reduced by up to 40%.

Critical strengths
  1. Problem Definition and Solution
  • The authors clearly identified and defined the bottleneck problem occurring during MoE inference. At the same time, their insight—connecting the fact that EPs are tied to specific nodes while DPs are replicas that move freely, and that there are no synchronization barriers within the DP stage—is highly intuitive.
  1. Theoretical Proof
  • They proved that a greedy approach using inverse workload matching is optimal.
  1. Significant Performance Improvement
  • Through experiments, they significantly increased efficiency by resolving the bottleneck occurring in LLM inference.
Critical weaknesses
  1. Novelty Although this study effectively resolves LLM bottlenecks, it lacks novelty because the solution is purely engineering-based.

  2. Baselines They demonstrated ChunkBalance's effects across various models, but they lack comparisons with other models.

  3. Scalability This study applies only to 2-chunk pipelining structures. Therefore, it lacks scalability.

  4. Completeness The appendix lacks completeness. The reference on line 684 and the Figure 5 caption are broken.

Questions for authors
  1. Extension to k>2k > 2: How does ChunkBalance perform if chunked prefill requires 4 or more chunks? Do you have an approximation algorithm, and does the zero-overhead claim still hold?
5 comments

We sincerely thank you for the review!

How does ChunkBalance perform if chunked prefill requires 4 or more chunks? Do you have an approximation algorithm? Scalability: This study applies only to 2-chunk pipelining structures. Therefore, it lacks scalability.

ChunkBalance is not limited to two chunks. We presented two-chunk pipelining because it is a common prefill configuration, but ChunkBalance also supports larger chunk counts.

Given k chunks with DP workloads w(0),⋯ ,wk−1∈Rdw^{(0)}, \cdots, w^{k−1} \in R^d, we fix chunk 0 and choose permutations σ1,...,σk−1\sigma_1, ..., \sigma_{k−1} to minimize the maximum aggregate workload across ranks: Wi=Σc=0k−1wσc(i)(c)W_i = \Sigma_{c=0}^{k−1} w^{(c)}_{\sigma_c(i)} with σ0\sigma_0 = id.

For k = 2, Theorem 1 gives the exact solution: sort one chunk’s workloads in ascending order and pair them with the other chunk’s workloads in descending order.

For k ≥ 3, we apply this two-chunk rule iteratively. We first pair chunk 1 against chunk 0. For each subsequent chunk jj, we pair it against the accumulated workload vector Σc=0j−1wσc(i)(c)\Sigma_{c=0}^{j−1} w^{(c)}_{\sigma_c(i)}, assigning its largest piece to the rank with the smallest accumulated workload, and so on. The procedure runs in polynomial time and reduces to Theorem 1 when k = 2. The joint optimization over all k−1 permutations is a multidimensional assignment problem, so this procedure is a heuristic for k ≥ 3, rather than a global optimum.

We evaluated the heuristic with 3- and 4-chunk prefill:

Moonlight-16B-A3B-Instruct

chunkmu8.0_sigma1.0 w/o CBmu8.0_sigma1.0 w/ CBmu9.0_sigma1.0 w/o CBmu9.0_sigma1.0 w/ CB
30.33030.28540.63540.4942
40.37110.34370.64960.5238

Qwen3-30B-A3B-Instruct-2507

chunkmu8.0_sigma1.0 w/o CBmu8.0_sigma1.0 w/ CBmu9.0_sigma1.0 w/o CBmu9.0_sigma1.0 w/ CB
30.61430.51441.22260.9347
40.67910.60391.25450.9663

Qwen3.5-35B-A3B

chunkmu8.0_sigma1.0 w/o CBmu8.0_sigma1.0 w/ CBmu9.0_sigma1.0 w/o CBmu9.0_sigma1.0 w/ CB
30.46540.43800.78080.6262
40.53440.53140.80260.6754

The results show that ChunkBalance’s gains persist with 3 and 4 chunks. We will include this generalization in the main text.

does the zero-overhead claim still hold?

The redistribution decision requires only computing permutations over DP ranks, which can efficiently run on the CPU with negligible overheads. As demonstrated below, the measured median latency is approximately 0.01–0.04 ms for 2–8 chunks, which is negligible compared to model execution time of about 1 second. The cost scales linearly with the number of chunks.

num_chunksredistribution decision latency (ms)per-chunk (µs)
20.01005.00
30.01464.86
40.01924.79
80.03724.65

Baselines. They demonstrated ChunkBalance's effects across various models, but they lack comparisons with other models.

We have also evaluated ChunkBalance across several additional model and scheduling settings.

  1. Linear/Hybrid attention model. The results on Qwen3.5-35B-A3B (with hybrid attention) are above and in the response to Reviewer BxR8.

  2. Additional request-routing algorithms. Besides 'roung-robin' and 'balanced', we extensively evaluated 2 algorithms for the SGLang DP router, namely 'random' and 'power-of-two-choices'. The results are in the reply to Reviewer BRN6.

The results demonstrate that ChunkBalance remain robustly effective under various experimental configurations. If you have any further concerns upon other conditions, please feel free to let us know.

Completeness. The appendix lacks completeness. The reference on line 684 and the Figure 5 caption are broken.

Thank you for pointing out this typo. It will be fixed in later versions.

Novelty. Although this study effectively resolves LLM bottlenecks, it lacks novelty because the solution is purely engineering-based.

We believe ChunkBalance makes a well-motivated system-engineering contribution. Its insights and contributions relative to prior work are as follows:

  1. A different dimension of load balancing. Prior DP balancing primarily focuses on request-level scheduling, which determines placement before execution. ChunkBalance addresses a complementary problem: redistributing DP workloads across DP ranks between chunks within execution.

  2. Synchronization-free workloads between chunks. Prior work generally treats collective communication as introducing a barrier, resulting in a workload of max⁡(w0)+max⁡(w1)\max(w_0) + \max(w_1). Importantly, we observe that with compute-communication overlap, inter-chunk workloads inside one DP stage need no synchronization. The effective workload is therefore max⁡(w0+w1)\max(w_0 + w_1), allowing the redistribution max⁡(w0+wσ(1))\max(w_0 + w_{\sigma(1)}) to take effect.

  3. A theoretical characterization. We prove in Theorem 1 that the optimal redistribution is a closed-form*sort-and-pair permutation, giving a globally optimal offline plan.

We will strengthen the discussion of these contributions and their relationship to prior work in the revised paper.

Area_Chair_DwUQOpenReview ↗

Author-reviewer discussion period is ending soon

Dear Reviewer sNMp,

If you haven't done so, please read through authors' response and let authors know if you need further clarification or have more questions. Beginning 11/19, authors are not allowed to respond any more, so this is good time to review the response and ask more.

Thank you.

-AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.