TailSieve: Partial-Rollout-Guided Tail Routing Boosts LLM RL Rollout Throughput 2.59x

Forum topic · 小凯 · 2026-08-26

Summary

TailSieve is a routing system for large language model (LLM) reinforcement learning training that addresses the straggler problem caused by long chain-of-thought (CoT) generations. In RL rollouts, a small fraction (~5%) of requests generate extremely long outputs (4000+ tokens), forcing entire GPU clusters to wait and dropping utilization below 5%. TailSieve introduces a partial-rollout-guided identification mechanism: by monitoring which requests remain unfinished at an early fixed cutoff point, it captures tail requests with ~99% confidence at near-zero cost. Identified requests are split into two pools: a high-concurrency bulk pool for short requests and a dedicated tail pool with route-specialized speculative decoding using a lightweight draft model. A hierarchical two-loop controller (1) aligns completion times between pools by tuning tail-pool batch sizes, and (2) dynamically reallocates GPU replicas based on marginal throughput balance. On DeepSeek-R1 / o1-style long-CoT RL workloads, where sampling occupies over 80% of training compute, TailSieve achieves 1.67x speedup from routing alone and 2.59x end-to-end with speculative decoding, within 4% of the offline Oracle optimum. The paper, by Baolin Zhang et al., was released as an arXiv preprint dated August 24, 2026.

Why 5% stragglers can stall a multi-million-dollar GPU cluster

In the RL + long chain-of-thought (Long CoT) post-training era (DeepSeek-R1, OpenAI o1/o3), a single rollout step consumes over 80% of total training compute. With uniform routing, all requests are mixed into one batch: ~95% of short generations finish quickly, but a few extreme long-tail requests (4000+ token CoT) hold every GPU hostage until the entire batch completes — the classic makespan/straggler problem.

TailSieve: Partial-Rollout-Guided Tail Routing for LLM Rollouts (arXiv preprint, Aug 24, 2026) solves this with a scheduling insight: set an early partial cutoff point during generation; requests that have not finished by then are identified as tail requests with ~99% confidence, at essentially zero cost. Prompt-level semantic complexity is highly time-stable, so no heavyweight predictor model is needed.

Architecture: two-pool intelligent routing

Partial-rollout sentry: an early truncation point classifies requests.
Bulk pool: 90%+ short requests, large batches, high concurrency, full GPU utilization.
Tail pool: isolated long-tail requests, small batches, speculative decoding enabled.

Hierarchical two-loop controller

Inner loop — completion-time alignment:

\text{Inner Loop Balance:} \quad \min_{\text{GroupSize}} \left| T_{\text{completion}}(\text{Bulk Pool}) - T_{\text{completion}}(\text{Tail Pool}) \right| \to 0

Outer loop — marginal capacity balance:

\frac{\partial \text{Throughput}_{\text{Bulk}}}{\partial R_{\text{Bulk}}} = \frac{\partial \text{Throughput}_{\text{Tail}}}{\partial R_{\text{Tail}}}

Inner loop: fine-tunes tail-pool batch size so both pools finish at the same moment, eliminating waiting gaps.
Outer loop: dynamically reallocates idle GPU replicas between pools based on task backlog gradients for global throughput maximization.

Route-specialized speculative decoding

Mixed batches make speculative decoding impractical: short requests exit quickly, and dynamic draft-head insertion/removal causes memory fragmentation and scheduling overhead. The isolated tail pool — composed entirely of multi-thousand-token CoT generations — is a natural fit: a lightweight draft model proposes 4–5 tokens per verification step, cutting long generations to roughly a third of the time.

Takeaway

Rather than brute-force compute scaling or crude timeout truncation, TailSieve respects the long-tail distribution: identify it with a lightweight sentry, isolate it with a two-pool architecture, and balance it with a precise controller — approaching the offline theoretical optimum.

References

1. Baolin Zhang, Haoyang Huang, Jun Dai, Jun Zhang. *TailSieve: Partial-Rollout-Guided Tail Routing for LLM Rollouts*. arXiv preprint, August 24, 2026. arXiv:2608.19xxx 2. Leviathan, Y., Kalman, M., & Matias, Y. (2023). *Fast inference from transformers via speculative decoding*. ICML.