Source-linked AI summary
TailSieve: Partial-Rollout-Guided Tail Routing for LLM Rollouts
Tianqi Xu, Lu Lv, Haoyang Huang, Wenjie Huang, Zhanming Shen, Yuhao Shen, Baolin Zhang, Xinyi Hu, Shuang Ge, Jun Dai, Tianyu Liu, Suorong Yang, Zhikai Li, Ye Bai, Jun Zhang, Lei Chen, Yue Li, Mingchen Wan
TL;DR
Synchronous LLM rollouts can be stalled by a few long generations, and uniform routing may place them in high-concurrency batches. TailSieve uses partial rollouts to identify likely tails and jointly adapts their isolation and replica allocation. It achieves up to 1.67× routing-only speedup and up to 2.59× with route-specialized speculative decoding while preserving on-policy generation.
Problem
A few long generations can dominate synchronous rollout makespan, while the optimal replica routing strategy remains unclear.
Method
TailSieve uses partial-rollout tail signals and hierarchical control to jointly adapt isolated workload and replica split using workload and throughput information.
Results
Across evaluated models and workloads, TailSieve achieves up to 1.67× routing-only speedup over uniform group routing and up to 2.59× with route-specialized MTP or DFlash.
Takeaways & Limitations
TailSieve provides a practical complement to speculative decoding for synchronous LLM rollouts while preserving on-policy generation without additional routing-induced length bias.
Takeaways & Limitations
SuffixDecoding has modest average accepted length and ragged verification queries that prevent full-batch CUDA-graph replay without extra graphs and GPU memory.
Abstract
from arXiv · showhide
Large-scale rollouts have become a core component of modern LLM systems, spanning reinforcement learning (RL) post-training, on-policy distillation (OPD), and sampling-heavy evaluation pipelines. Unlike online serving, which is typically optimized for request-level latency and throughput, a small number of long-tail generations can dominate the end-to-end makespan of an entire rollout step. In practice, rollout requests are often routed uniformly across replicas, which can place extremely long generations inside high-concurrency decoding batches. To address this, we present TailSieve, a partial-rollout-guided framework that jointly controls tail routing and replica allocation for LLM rollouts. In an idealized setting with known completion lengths, we show that makespan-optimal routing in the long-tail regime combines tail isolation with load balancing, and that a simple top-k policy closely approximates this offline optimum. Leveraging the observation that long-tail prompts tend to remain long-tailed across policy updates, TailSieve uses partial rollouts as a training-free signal for identifying candidate tail groups. A hierarchical controller then jointly adapts the number of isolated groups and the replica split between the tail and bulk pools using collected response-work history and a measured concurrency-throughput model. TailSieve achieves up to 1.67x routing-only speedup over uniform group routing. The resulting low-concurrency tail pool further enables route-specialized speculative decoding with MTP or DFlash, achieving up to 2.59x speedup over uniform routing. Selected prompts are regenerated under the current policy, preserving on-policy generation and avoiding additional routing-induced length bias in steady state.
1. Introduction
Synchronous LLM rollouts are governed by step-level makespan, which can be dominated by a few long generations. TailSieve addresses this by isolating likely tail prompts, adapting replica allocation, and preserving on-policy generation.
- A few extremely long generations can dominate synchronous rollout makespan and stall the entire optimization step.
- The offline long-tail optimum isolates extreme-tail requests while adding balancing traffic so replica completion times remain aligned.
- TailSieve identifies likely tail prompts from partial rollouts and jointly adapts isolated workload and replica capacity as workloads evolve.
- The framework regenerates consumed responses under the current policy, preserving on-policy generation without additional routing-induced length bias.
2. Motivating Observations
The motivating observations establish that long-tail-aware routing should balance completion times rather than request counts, while both isolation size and replica allocation must adapt to workload conditions. Partial rollout supplies a training-free tail signal for this online control problem.
- 2.1. Optimal Routing in Long-Tailed Rollouts: Tail Isolation with Load Balancing: Uniform request-count balancing can place extreme-tail generations in high-concurrency batches, whereas optimal routing isolates tails and balances completion times.
- 2.1. Optimal Routing in Long-Tailed Rollouts: Tail Isolation with Load Balancing: The exact oracle can be computed with dynamic programming, but its cost makes it unsuitable for the rollout critical path.
- 2.2. Top-k Tail Isolation Closely Approximates the Long-Tail Optimum: A top-k policy routes the longest requests to a low-concurrency tail replica, with its best setting near the point where replica completion times match.
- 2.2. Top-k Tail Isolation Closely Approximates the Long-Tail Optimum: 54.84 s: top-k tail isolation recovers most of the improvement, and the best-k policy remains within 4% of the exact offline optimum across 100 rollout groups.
- 2.3. Partial Rollout Acts as a Training-Free Tail Filter: Partial rollout uses unfinished generations to identify likely long-tail requests without carrying trajectories across policy updates.
- 2.4. Workload-Dependent Optima Motivate Hierarchical Control: No fixed isolation size or replica split is optimal across weak-tail, measured, and strong-tail workloads.
- 2.4. Workload-Dependent Optima Motivate Hierarchical Control: The relaxed joint optimum balances pool completion times through isolation-size adjustment and marginal-capacity pressure through replica-split adjustment.
3. TailSieve Design
TailSieve identifies likely tail groups from partial-rollout status, executes tail and bulk groups in separate logical pools, and jointly adapts isolated workload and replica capacity. It preserves on-policy generation by regenerating consumed responses under the current policy while using completion-time and capacity signals for control.
- Workflow: During warm-up, unfinished groups become tail candidates; joint execution regenerates them in the tail pool while fresh groups run in the bulk pool.Both logical pools may contain multiple replicas, with round-robin dispatch within each pool.
- Workflow: TailSieve transfers only prompt identities, keeps GRPO prompt groups atomic, and regenerates every consumed response from scratch under the current policy.Generated tokens, KV-cache state, sampling state, and log-probabilities are not reused.
- Hierarchical control: The controller represents each routing configuration as (q_t, m_t), where q_t is isolated tail workload and m_t is tail-pool replica capacity.Uniform routing is the boundary configuration (q, m) = (0, 0).
- Hierarchical control: For fixed replica capacity, the inner loop adjusts q_t toward equal tail- and bulk-pool makespans using smoothed measured processing rates.It increases q_t when the bulk pool is slower and decreases q_t when the tail pool is slower.
- Hierarchical control: The outer loop uses response-work distributions and concurrency–throughput measurements to compare marginal pool capacity and select replica adjustments.It evaluates nearby splits and moves capacity only when a feasible switch exceeds the threshold.
- On-policy execution: TailSieve interleaves regenerated tail and fresh bulk responses, preserving on-policy generation without additional routing-induced length bias in steady state.Changing m_t affects execution placement, while changing q_t can cause a short composition transition before control settles.
- Route specialization: The isolated tail replica creates a low-concurrency, long-horizon stream that supports route-specific speculative decoding while avoiding delays to high-concurrency bulk requests.MTP or DFlash policies can therefore differ between tail and bulk routes.
- Route specialization: SuffixDecoding was not enabled by default because modest accepted lengths and ragged verification queries imposed CUDA-graph and GPU-memory overheads exceeding its limited acceptance gain.This limitation arose despite partial rollout naturally providing draft sequences.
4. Evaluation
TailSieve is evaluated across five model configurations using matched hardware, sampling, prompts, and replica budgets. Routing improves over uniform routing, route-specialized speculation adds further gains, controller trajectories converge, and end-to-end GRPO acceleration persists without systematic reward or response-length shifts.
- Experimental overview: TailSieve is evaluated on five dense and mixture-of-experts configurations using a fixed eight-GPU server, vLLM, matched sampling, and fixed total replica budgets.Experiments cover Qwen3.5, Qwen3, mathematical-reasoning, coding, and GRPO workloads.
- Main results: 1.670× routing-only speedup is achieved on Qwen3.5-35B-A3B over uniform group routing, while TailSieve also reaches 1.403×, 1.214×, 1.342×, and 1.442× on the other listed configurations.The fixed-replica-allocation variant reaches 1.560× on Qwen3.5-35B-A3B.
- Speculative decoding: Route-specialized speculation consistently outperforms uniform routing across evaluated budgets.Tail isolation shifts the best speculation budget upward and extends the useful range for more aggressive speculation.
- Controller convergence: All inner-loop trajectories converge to q = 4, while both outer-loop initializations converge to m = 2, a 2:2 bulk–tail replica split.The controller converges from both minimum and maximum isolation sizes and from uniform and tail-heavy replica allocations.
- End-to-end RL training: On Qwen3.5-2B, routing-only TailSieve reduces generation time from 119.34 s to 82.49 s, a 30.9% reduction and 1.45× speedup over steps 1–30.Combining routing with MTP reduces generation time to 46.61 s, a 60.9% reduction and 2.56× speedup.
- End-to-end RL training: Across both evaluated RL models, acceleration persists as policy response lengths evolve, while reward and mean response length remain comparable across runs.Final checkpoints retain broadly comparable downstream accuracy to baseline across GSM8K, MATH-500, and the 2024 and 2025 AIME sets.
5. Related Work
TailSieve differs from asynchronous, tail-batching, predictor-based, and speculative-decoding approaches by using unfinished-request status only as a training-free routing signal. It preserves synchronous mixed tail–bulk updates while jointly adapting placement and replica capacity.
- Asynchronous and tail-aware systems: Asynchronous and partial-rollout systems reduce synchronization stalls by decoupling generation or reusing unfinished trajectories, but may require policy-lag or cross-policy-reuse management.TailSieve instead regenerates responses under the current policy.
- Asynchronous and tail-aware systems: TailSieve uses cutoff-time unfinished status as a tail signal without reusing generated prefixes or moving tails into separate tail-heavy rounds.It preserves a mixed tail–bulk update stream while targeting replica-level makespan in synchronous rollout.
- Length prediction and routing: Unlike predictor-based dispatchers and learned length rankers, TailSieve does not estimate exact completion lengths.It uses partial rollout as a high-recall filter and adapts both isolation size and tail-pool replica capacity.
- Speculative decoding: Tail isolation shapes decoding concurrency, complementing speculative methods that reduce token-generation cost through drafts or multi-token prediction.The resulting low-concurrency tail route supports deeper MTP or DFlash speculation.
6. Conclusion
TailSieve jointly allocates tail workload and replica capacity to reduce long-tail stalls while preserving on-policy generation. Across evaluated models and workloads, it achieves up to 1.67× routing-only speedup and up to 2.59× with route-specialized speculative decoding.
- TailSieve jointly allocates tail workload and replica capacity to reduce long-tail stalls in synchronous LLM rollouts.Its hierarchical controller uses partial-rollout tail signals, pool completion times, response-work history, and measured decoding throughput.
- TailSieve preserves on-policy generation without introducing additional routing-induced length bias in steady state.Policy-update groups remain intact, and every consumed response is regenerated under the current policy.
- 1.67× routing-only speedup over uniform group routing is achieved across the evaluated models and workloads.
- 2.59× speedup over uniform routing is achieved when TailSieve is combined with route-specialized MTP or DFlash.The gains are strongest when long-tail requests determine baseline makespan and isolation provides a decoding concurrency advantage.
- End-to-end GRPO experiments show that the controller tracks an evolving rollout distribution while maintaining comparable training quality.
A.1. Common Experimental Setup
The experiments use fixed eight-GPU hardware and vLLM, with shared sampling configuration across step-wise and end-to-end RL experiments. Prompt templates define separate mathematical and bounded-reasoning coding workloads.
- All experiments use one node with eight NVIDIA H100 GPUs and vLLM as the rollout backend.The evaluated configurations use four TP2 replicas for two large models and eight TP1 replicas for 4B and 2B models.
- The total replica budget is fixed while TailSieve may reassign replicas between tail and bulk pools.
- The step-wise and end-to-end RL experiments share the rollout sampling configuration in Table A.1.
- Prompt templates: The mathematical workload uses a prompt requiring boxed output followed by an immediate <END> termination.
- Prompt templates: The bounded-reasoning coding workload asks for reasoning, correctness, edge cases, complexity, and exactly one complete Python function.
A.2. Step-Wise Rollout Experiments
Step-wise experiments compare routing policies and allocation strategies under controlled measurement protocols. TailSieve’s full system adds adaptive replica allocation beyond its fixed-allocation variant.
- Routing-policy implementations: Uniform group routing distributes atomic prompt groups evenly by count across homogeneous replicas, while Oracle policies use realized generation lengths before routing.Uniform Oracle balances total known generation length while keeping prompt groups atomic.
- Routing-policy implementations: The fixed-allocation TailSieve variant holds the replica split at 2:2 or 4:4, whereas full TailSieve enables the outer replica-allocation loop.
- Measurement protocol: Controller-based measurements begin after allocation k converges and average wall-clock time over the next three consecutive rounds.The unfinished-request partition initializes the following round, but generation starts from the original prompt and reuses no generated prefix or cross-round KV state.
- Measurement protocol: Ablations vary one workload property at a time while holding the request trace and total token workload fixed.Initialization studies use paired traces across all starting allocations, and component ablations use the main step-wise measurement protocol.
A.3. End-to-End Mixed-Routing RL Training
The appendix describes the end-to-end mixed-routing RL setup alongside offline routing simulation and controlled tail-workload construction. The offline comparison evaluates how closely best-k isolation approaches the exact optimum across sampled rollout groups.
- End-to-End Mixed-Routing RL Training: The end-to-end experiment trains Qwen3.5-2B using Dr. GRPO advantage normalization with mean-centering within each eight-response prompt group.Advantages are not divided by within-group reward standard deviation.
- Offline Routing Simulation Across Rollout Groups: The offline routing comparison evaluates 100 rollout groups, each containing 100 trajectories sampled from real rollout traces.The simulator’s GPU decoding characteristics are calibrated using direct measurements from Qwen3.5-35B-A3B.
- Offline Routing Simulation Across Rollout Groups: Within 4% of the exact optimum is achieved by the per-group best-k isolation policy for all 100 groups.It is within 1% for 72% of the groups, while fixed 10% isolation and random uniform routing show broader, right-shifted optimality-gap distributions.
- Tail-workload construction: The workload transformation changes only lengths above the median, preserving request ordering and leaving the lower half and median unchanged.It maps the original P90 to rM, so the resulting P90/P50 ratio equals r.
- Tail-workload construction: The weak- and strong-tail workloads use target ratios r = 1.5 and r = 6, respectively, while the real workload retains original response lengths.
- Tail-workload construction: Table A.3 summarizes construction and length statistics for the weak-, real-, and strong-tail workloads.
B. Long-Tail Prompts across Policy Updates
Tail ranking remains highly stable across policy checkpoints, and prompt identity explains most response-length variation. These findings motivate using unfinished prompt groups as noisy cross-round tail signals without assuming stationary lengths.
- Cross-checkpoint tail ranking: For each prompt and checkpoint, the analysis averages eight sampled response lengths before ranking prompts.The study uses 64 prompts, multiple checkpoints, and eight samples per prompt and checkpoint without normalizing lengths.
- Cross-checkpoint tail ranking: The source tail set contains the 7 prompts with the largest average response lengths, corresponding to the top 10% of 64 prompts.At the target checkpoint, average response length provides the ranking score.
- Cross-checkpoint tail ranking: Tail ranking achieves AUC 0.957–0.985 across adjacent checkpoints, well above the random baseline of 0.5.Using checkpoint 1 to rank checkpoints through 30 yields AUC 0.952–0.985.
- Variance contribution: Prompt identity contributes 64.8% of response-length variance, compared with 26.1% from sampling and 2.2% from checkpoints.Prompt–checkpoint interaction accounts for the remaining 6.9%.
- Interpretation: TailSieve treats unfinished prompt groups as noisy cross-round tail signals because differences between prompts tend to dominate sampling and policy-change variation.The method does not require regenerated trajectories to reproduce their previous response lengths.
- Interpretation: The stability result does not imply that sampling randomness has no effect or that individual prompts cannot enter or leave the tail.It also does not establish a stationary overall response-length distribution.
C.1. Inner-Loop Completion-Time Balance
The routing analysis characterizes optimality through completion-time balance and implements it with a controller that jointly adjusts tail workload and replica capacity. Its guarantees and proxies distinguish exact replica-level makespan from approximate tail-side diagnostics.
- Completion-time balance: In the continuous relaxation, an optimal min-max routing solution equalizes completion times across all active replicas.Shifting infinitesimal workload from a slower replica to a faster one contradicts optimality when completion times differ.
- Completion-time balance: A discrete optimum need not finish replicas simultaneously, but no movable request can reduce the maximum completion time.Indivisible requests limit balancing to the granularity of available reassignment.
- Controller updates: TailSieve dampens replica-allocation updates, bounds adjustment size, and waits for transitions to settle before making another decision.These rules prevent overlapping transitions and frequent oscillation.
- Completion-time balance: The oracle assigns a small amount of additional workload to the faster tail replica when this lowers the bottleneck without making it the new bottleneck.The objective balances completion times rather than request counts.
- Marginal-capacity balance: For homogeneous workloads, the optimal tail replica fraction reduces to the routed-work fraction, making the two pools operationally equivalent to uniform routing.The result follows when both pools have the same local elasticity.
- Controller updates: The outer controller evaluates integral group and replica allocations using predicted group work and measured concurrency–throughput curves.It searches nearby splits because batching thresholds can make the objective non-unimodal.
- Deadline feasibility: A replica transfer is feasible when the enlarged pool can absorb at least as many groups by the deadline as the reduced pool releases.Under the predicted serving model, this condition preserves the current barrier deadline.
- Exact makespan and proxy: The tail-side concurrency proxy measures aggregate exposure rather than exact wall-clock time, while reported speedups use exact replica-level makespan or measured end-to-end execution time.Routing gains weaken when the tail workload is too small, overloaded, or no longer benefits from low concurrency.
D.1. Transition to Uniform Routing during RL Training
During RL training, the joint controller selects the uniform-routing boundary after step 8 while keeping MTP enabled. Routing effects before that transition are compared against uniform-routing All-MTP.
- Transition: After step 8, the joint controller selects the uniform-routing boundary and keeps MTP enabled.
- Comparison: The pre-transition comparison uses TailSieve with MTP against an All-MTP baseline using MTP under uniform routing.
- Comparison: The comparison isolates routing’s contribution over training steps 1–8 before the controller reaches uniform routing.
E. Analysis of Routing-Induced Length Bias
The analysis shows that routing-induced length bias is absent under a stationary policy and prompt-conditioned stable allocation, while allocation changes create temporary composition transitions. With policy or selector drift, the result becomes an approximation relative to the current-policy target rather than an exact equality.
- Stationary policy: Under a fixed policy, prompt-conditioned selection and fresh regeneration preserve the population response-length distribution in expectation.The equality is population-level, so finite batches can still deviate through sampling variance.
- Stationary policy: Stable allocations maintain unbiased routed batches relative to generation under the same policy, without requiring repeated generations of a prompt to have identical lengths.The selector transfers prompt-level tail information while separating it from trajectory-level sampling noise.
- Allocation changes: Increasing the tail allocation causes a short transition, after which canonical prompt composition is restored one step later if no further adjustment occurs.The transition arises from applying the new allocation when partitioning the next pool.
- Allocation changes: Decreasing the tail allocation creates residual requests that must be drained or reassigned, restoring canonical composition two steps after the change.Because TailSieve does not drop requests, the first transition batch does not yet match the new allocation.
- Evolving policies: With policy or selector drift, the routed batch is compared with the current-policy target, and the exact stationary result no longer applies during allocation transitions.The analysis distinguishes policy-induced distribution drift from additional routing-induced bias.