Machine Learning PapersLandmark papers
← All papers
RESEARCH PAPER / 2026-11-17

TAILROLL: Tail-Aware Rollout Acceleration for RL-Based LLM Post-Training

Niloofar Gholipour, Marcos Assuncao, Timothy Yu, Gursimran Singh, Rajkumar Buyya, Julien Gascon-Samson, Zhenan Fan, Yong Zhang

Huawei Technologies, Canada +4 · IEEE Transactions on Parallel and Distributed Systems

Affiliations: École de technologie supérieure, Huawei Technologies, RBC Borealis, The University of Melbourne

Abstract

RL post-training of large language models (LLMs) is bottlenecked by rollout: heavy-tailed responses leave engines idle as each step waits for the longest response. Asynchronous training masks, but does not eliminate, idle time. We distinguish imbalance waste (uneven placement and decode contention) from straggler waste (waiting for the longest response). Tail length, not average load, often sets the step bound. We propose TAILROLL, an online scheduler integrated into an open-source RL framework. It combines stateless in-flight migration and sufficiency-gated termination. Migration moves decoding requests between engines at chunk boundaries and resumes them with one re-prefill under a freeness-based, cost-aware tail-balancing policy. Termination stops a response when its GRPO group has enough completed samples for advantage estimation, masking its partial output from the training loss. Across ten configurations, TAILROLL reduces rollout bubble ratio by 21% to 74% and cross-engine KV-cache imbalance by 44% to 79%. In end-to-end RL training, it cuts rollout time by 24% to 34%, full step time by 21% to 22% on long-CoT RL, and p95 request latency by 28% to 37%, while raising generation throughput by up to 33% with comparable or higher final reward.

The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.

Research summary

TAILROLL introduces a tail-aware scheduling mechanism combining live migration and sufficiency-gated termination to significantly accelerate RL-based LLM post-training by mitigating straggler effects. The paper presents a sophisticated systems-level solution to a well-known bottleneck in LLM reinforcement learning. By correctly identifying that tail latency, not average load, is the primary driver of step time, the authors design a scheduler that actively manages this tail through migration and early stopping. The experimental results are compelling, showing substantial speedups without sacrificing model performance. The work bridges the gap between systems optimization and ML training dynamics, offering a practical tool for scaling RL post-training. The integration into an open-source framework enhances its utility and potential for widespread adoption in the community.

Methodology

The paper proposes TAILROLL, an online scheduler for RL-based LLM post-training that addresses the "straggler" problem where step time is dominated by the longest response in a batch. The methodology is sound and well-motivated, distinguishing between "imbalance waste" (load distribution) and "straggler waste" (tail latency). The core contributions are twofold: (1) stateless in-flight migration of decoding requests between engines at chunk boundaries using a freeness-based, cost-aware policy to balance tails, and (2) sufficiency-gated termination, which stops generating a response once the GRPO group has enough samples for advantage estimation, effectively masking the partial output from the loss. The integration of live migration with early termination is a clever systems-level insight that leverages the statistical properties of RL sampling (where not all samples in a group are strictly necessary for a valid gradient step if the group size is sufficient).

Results & evaluation

The evaluation is rigorous, covering ten different configurations. The results show significant improvements: 21-74% reduction in rollout bubble ratio, 44-79% reduction in KV-cache imbalance, and 24-34% reduction in rollout time. Crucially, the paper demonstrates that these speedups do not come at the cost of model quality, reporting comparable or higher final rewards. The end-to-end metrics (full step time, p95 latency, throughput) are highly relevant to practitioners. The comparison against asynchronous baselines is appropriate.

Reproducibility

The paper states it is integrated into an open-source RL framework, which is a strong indicator of reproducibility. However, the specific code repository URL is not explicitly provided in the text snippet, though the mention of "open-source" suggests availability. The detailed description of the migration policy and termination logic provides sufficient detail for implementation.

Limitations

The primary limitation is the reliance on the specific structure of GRPO (Group Relative Policy Optimization) or similar group-based RL methods for the termination strategy. The "sufficiency-gated termination" may not apply directly to all RL algorithms (e.g., PPO with different advantage estimators). Additionally, the overhead of re-prefilling during migration is a trade-off that might not be favorable in all hardware configurations, although the paper argues the cost-aware policy mitigates this.

Broader impact

This work has high practical impact for anyone scaling RL post-training for LLMs, which is a critical bottleneck in current AI development. By reducing idle time and improving throughput, TAILROLL can significantly lower the cost of training advanced LLMs. The techniques of live migration and early termination are likely to be adopted in other RLHF/RLAIF pipelines. TAILROLL introduces a tail-aware scheduling mechanism combining live migration and sufficiency-gated termination to significantly accelerate RL-based LLM post-training by mitigating straggler effects. The paper presents a sophisticated systems-level solution to a well-known bottleneck in LLM reinforcement learning. By correctly identifying that tail latency, not average load, is the primary driver of step time, the authors design a scheduler that actively manages this tail through migration and early stopping. The experimental results are compelling, showing substantial speedups without sacrificing model performance. The work bridges the gap between systems optimization and ML training dynamics, offering a practical tool for scaling RL post-training. The integration into an open-source framework enhances its utility and potential for widespread adoption in the community.

Author of this paper? Send a correction.