- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes TailSieve, a framework for reducing straggler-induced delays in synchronous LLM rollouts. The authors formulate rollout scheduling as a makespan minimization problem under concurrency-dependent decoding efficiency and show that isolating a small number of long-tail requests can approximate the offline optimal assignment.
Building on the observation that prompt-level response-length tendencies persist across policy updates, TailSieve identifies candidate tail groups from unfinished partial rollouts and regenerates them under the current policy. A hierarchical controller jointly adjusts the number of isolated tail groups and their allocated replicas. The framework additionally supports route-specialized speculative decoding using MTP and DFlash.
The evaluation includes an offline routing analysis, cross-checkpoint tail-prediction studies, and vLLM experiments across five Qwen model configurations and two workloads on eight H100 GPUs. The reported speedups reach 1.67× with routing alone and 2.59× with routing and speculative decoding, relative to uniform non-speculative routing. GRPO experiments on two smaller models show reduced rollout-generation time with broadly comparable training rewards and downstream accuracy.
Critical strengths
1. Well-motivated routing formulation and effective tail-isolation strategy.
The paper provides a clear analysis of how concurrency-dependent decoding efficiency interacts with long-tail response lengths. The exact offline routing formulation and the observation that top-k isolation achieves within 4% of the oracle optimum across 100 sampled instances provide useful justification for the proposed design. The resulting approach is conceptually simple and does not require a separately trained length predictor.
2. Promising empirical performance across models and workloads.
The evaluation covers multiple model scales and architectures, mathematical and coding workloads, and both standard and speculative decoding. The cross-checkpoint analysis provides evidence that prompt-level tail behavior is persistent, while the routing experiments demonstrate meaningful speedups. The additional GRPO experiments provide preliminary evidence that these efficiency improvements can be obtained without substantial degradation in training outcomes.
Critical weaknesses
1. The evaluation does not sufficiently disentangle tail-aware routing from partial-rollout selection and cross-round deferral.
Under TailSieve, the bulk pool launches fresh groups but only accepts the first completed groups, while the remaining accepted groups come from regenerated tail prompts. In contrast, the uniform-routing baseline processes all groups to completion. Consequently, the two approaches differ not only in replica assignment but also in their completion and selection mechanisms.
This raises an important attribution concern: how much of the reported improvement comes from isolating long-tail requests, rather than deferring unfinished bulk groups across rollout steps? A baseline using the same partial-rollout cutoff, carryover policy, and regeneration mechanism, but without tail-aware routing, would be necessary to isolate the contribution of the proposed routing strategy. This directly affects the interpretation of the main results in Table 1.
2. The evidence for end-to-end practical benefits remains limited.
Most step-wise performance comparisons are conducted after the allocation controller has converged, leaving the amortized cost of initialization and adaptation insufficiently characterized. Furthermore, speculative-decoding experiments use fixed replica splits because runtime reconfiguration introduces additional costs, limiting validation of the fully adaptive design with speculation.
The headline 2.59× speedup is measured against uniform routing without speculative decoding. Appendix F.1 shows that the additional gain over uniform routing with the same speculative decoder is substantially smaller (approximately 1.05–1.34×). Finally, the GRPO experiments measure rollout-generation time rather than complete training wall-clock time. These limitations make the overall efficiency benefit in realistic, dynamically evolving training workloads less conclusive.
Questions for authors
-
Isolating the routing contribution: Could the authors provide a comparison against a uniform-routing baseline that uses exactly the same partial-rollout cutoff, unfinished-group carryover, and regeneration policy as TailSieve? This would clarify how much of the improvement comes specifically from tail isolation and adaptive replica allocation.
-
End-to-end efficiency: What is the cumulative training wall-clock improvement when accounting for controller warm-up, allocation transitions, speculative-decoding reconfiguration, and optimization time? In particular, can the authors quantify the benefit of the fully adaptive controller when speculative decoding is enabled?
-
Cross-round reliability and training-data distribution: How accurately do unfinished groups predict the longest groups in subsequent rollout steps under changing policies, particularly on coding workloads? Can the authors quantify the residual selection bias discussed in Appendix G.5 and assess whether the accepted prompt/reward distributions remain comparable to uniform routing?
3 comments
Thanks & Initial Response to Reviewer 4R6A (W2, Q2)
[W2/Q2 — Fully adaptive control and gains with speculative decoding]
There may be some misunderstanding about the use of fully adaptive controller. If we’ve misread your question, we’d be happy to discuss it further. Here, we understand the reviewer’s “fully adaptive controller” to refer to enabling both the inner loop for tail-quota adaptation and the outer loop for replica allocation. We clarify that our RL experiments already use the fully adaptive controller. We additionally report (1) an end-to-end ablation with speculative decoding enabled RL experiments. We then (2) compare per-step rollout times with Uniform using the same speculative decoder, (3) explain why the additional routing gains are smaller when speculative decoding is enabled and (4) report end-to-end timing breakdown.
(1) With speculative decoding enabled, TailSieve provides up to 1.115× additional end-to-end speedup.
We tested two ablation settings with speculative decoding: both control loops off and only the inner loop active. The results are as follows, all speedups reported relative to both loops off.
| Model | Configuration | Rollout (s) | E2E (s) |
|---|---|---|---|
| 2B | Both loops off | 1,704.29 | 3,592.87 |
| 2B | Inner-loop on | 1,524.75 (1.118×) | 3,348.76 (1.073×) |
| 2B | TailSieve | 1,410.89 (1.208×) | 3,221.43 (1.115×) |
| 4B | Both loops off | 1,720.80 | 4,096.48 |
| 4B | Inner-loop on | 1,676.85 (1.026×) | 3,977.44 (1.030×) |
| 4B | TailSieve | 1,565.65 (1.099×) | 3,848.02 (1.065×) |
(2) TailSieve speeds up rollouts by up to 1.517× over Uniform with the same speculative decoder.
We also evaluate step-wise speed-up for a convergence setting. We report speedups over Uniform with the same speculative decoder.
| Workload | Model | Decoder | TailSieve (fixed replica) | TailSieve |
|---|---|---|---|---|
| DeepScaleR | Qwen3.5-2B | MTP | 29.02 s (1.329×) | 28.76 s (1.341×) |
| DeepScaleR | Qwen3.5-35B-A3B | DFlash | 68.91 s (1.107×) | 63.54 s (1.200×) |
| DeepScaleR | Qwen3.5-35B-A3B | MTP | 62.87 s (1.152×) | 61.42 s (1.179×) |
| DeepScaleR | Qwen3.5-4B | DFlash | 47.79 s (1.119×) | 47.79 s (1.119×) |
| DeepScaleR | Qwen3.5-4B | MTP | 41.39 s (1.163×) | 39.53 s (1.218×) |
| KodCode | Qwen3.5-2B | MTP | 24.26 s (1.274×) | 24.26 s (1.274×) |
| KodCode | Qwen3.5-35B-A3B | DFlash | 37.07 s (1.117×) | 30.71 s (1.349×) |
| KodCode | Qwen3.5-35B-A3B | MTP | 34.09 s (1.232×) | 29.78 s (1.411×) |
| KodCode | Qwen3.5-4B | DFlash | 33.45 s (1.335×) | 29.43 s (1.517×) |
| KodCode | Qwen3.5-4B | MTP | 29.84 s (1.053×) | 29.84 s (1.053×) |
(3) TailSieve complements speculative decoding by targeting the remaining long tail.
As for the smaller gain relative to speculative decoding, we attribute this to speculative decoding’s tendency to “compress” the long tail: it provides greater acceleration at smaller active batch sizes, leaving less room for routing to improve the makespan. However, our approach still provides consistent gains over various workloads. We expect TailSieve to help most when a small number of long generations still determine the rollout makespan, even with speculative decoding enabled.
(4) TailSieve achieves up to 1.271× end-to-end speedup over Uniform.
We also report the RL timing breakdown. Allocation transitions are already included in the rollout times.
| Model | Configuration | Rollout (s) | Training (s) | Initial warm-up (s) | E2E (s) | E2E speedup |
|---|---|---|---|---|---|---|
| 2B | Uniform | 3,580.31 | 1,884.90 | — | 5,465.21 | — |
| 2B | TailSieve | 2,474.59 | 1,782.60 | 44.29 | 4,301.48 | 1.271× |
| 4B | Uniform | 3,242.91 | 2,275.20 | — | 5,518.11 | — |
| 4B | TailSieve | 2,866.15 | 2,094.85 | 120.06 | 5,081.06 | 1.086× |
Thanks & Initial Response to Reviewer 4R6A (Q3)
[Q3 — Cross-round reliability and accepted-data distributions]
We appreciate the reviewer’s suggestion! We address your questions in two parts. (1) We evaluate tail identification across checkpoints and across rounds during RL training. (2) We quantify the observed differences in accepted data relative to Uniform.
(1) Tail identification remains reliable across checkpoints and during actual RL training.
Following the same protocol as our math evaluation, we evaluate KodCode coding prompts. We define the source checkpoint’s longest prompt groups as the tail set and use target-checkpoint group-mean lengths as ranking scores. Adjacent-checkpoint AUC ranges from 0.895 to 0.960 for Qwen3.5-2B and 0.930 to 0.997 for Qwen3.5-4B, well above the random baseline of 0.5. These results support a persistent prompt-level length signal on coding workloads.
We next evaluate unfinished groups from each update to their regenerated responses during actual RL training process. We measure the probability that a carried group has a longer group-mean response length than a non-carried group. These results show that unfinished groups retain a strong relative-length signal after policy update.
| Model | Update transitions | Carry groups | Mean carry-length AUC |
|---|---|---|---|
| Qwen3.5-2B | 29 | 378 | 0.9093 |
| Qwen3.5-4B | 29 | 97 | 0.9311 |
A minor concern might be: what if partial-rollout guided signals fails to predict the longest groups. An important property is that partial rollout also tolerates missed tail predictions: the bulk pool accepts the first N − q of N groups, so its completion time is determined by the (1 − q/N) completion-time quantile rather than the longest stragglers.
(2) Against Uniform, the CDF gaps are below 5.3% for accepted lengths and below 2.08% for rewards.
We quantify the observed distributional differences relative to Uniform: Appendix F.3 already reports maximum empirical CDF gaps below 5.3 percentage points for mean response lengths, and we will additionally report accepted reward distributions in the revised version. Accepted prompt/reward distributions remain comparable to uniform routing. To address residual selection bias, we quantify the observed distributional differences from Uniform using the maximum empirical CDF gaps for accepted response lengths and rewards.
Regarding accepted prompt difficulty, unfinished prompts are carried forward and included in the next training update, with exactly one-step delay, so deferral does not remove harder prompts from training.
| Maximum reward-CDF gap: Uniform vs. TailSieve | 2B | 4B |
|---|---|---|
| Correctness reward, excluding length penalties | 2.08 pp | 0.99 pp |
| Training reward, including length penalties | 1.07 pp | 0.61 pp |
Thanks & Initial Response to Reviewer 4R6A (W1, Q1)
[W1/Q1 — Distinguishing routing from cross-round deferral]
This is a great suggestion! Holding deferral fixed gives us a clearer measure of what routing adds. We therefore add a uniform-routing control with the same cutoff, carryover, and regeneration mechanism, together with random-selection controls. We will include these ablation results in the updated version
We separate routing from cross-round deferral in two parts. (1) We describe the four combinations of selection and routing, including the matched Uniform control. (2) We report the contribution of tail isolation when the deferral policy is held fixed.
(1) Matched controls isolate the effect of routing while holding the deferral policy fixed.
We evaluate two selection policies (random or unfinished groups) and two routing policies (Uniform or isolation) across five models on DeepScaleR and KodCode. Random selects the q fresh groups to defer uniformly at random before generation, regardless of their completion times. Uniform distributes fresh and carried groups across all replicas without separating them into dedicated pools. Unfinished and Isolation follow TailSieve’s completion-based deferral and bulk/tail routing mechanisms, respectively (see §3, “A mixed tail–bulk pipeline”).
(2) TailSieve is the fastest configuration across all five models on both workloads, with up to 1.283× speedup over Uniform deferral.
DeepScaleR
KodCode
Deferral does improve performance in several settings, but provides no consistent speed-up. Random isolation provides no consistent benefit, and brings degeneration at some settings. With the same unfinished-group deferral policy, adding tail isolation yields a further speedup over Unfinished + Uniform of 1.108–1.276× on DeepScaleR and 1.100–1.283× on KodCode. These results indicates that tail identification and isolation are two coupled mechanisms .