acceptodds
Under review as a conference paper at ICLR 2027

Multi-Repacking in Asynchronous RL Post-Training

Abstract

Long-tailed trajectory lengths leave many rollout workers, or replicas, lightly occupied while a few unfinished trajectories continue. We propose multi-repacking, which jointly consolidates unfinished trajectories across multiple replicas. Under exponential service, linear cache growth, and service-preserving migration, we derive finite-system bounds and explicit hierarchy sums for the expected cumulative time that replicas remain occupied during the draining tail. Under the stated joint scaling assumptions and an explicit packing-slack condition, we prove that multi-repacking has a strictly smaller leading term than hierarchical pairwise repacking. We further establish a uniform positive gap between the corresponding hierarchy sums that dominates the lower-order errors in sufficiently large systems. The analysis allows replicas to start at different times and to enter the tail at statistically dependent times; it also permits packing decisions to adapt to observed completions and accounts for replicas that empty naturally without migration. In experiments with 1,600 replicas whose start times are independently staggered, each processing 12,800 trajectories in 3,200 parallel slots, all three tested group sizes \(m=3,4,5\) reduce mean tail occupied time on both evaluated workloads. Across 40 independent workload instances comprising 160 policy executions, the reductions are 4.74–7.59% under exponential service and 6.34–10.56% under resampled output lengths from an empirical SWE-agent coding workload. All six paired mean improvements have positive pointwise 95% confidence intervals. The trace-based runs use the same policy parameters, reserve physical cache headroom, and exhibit no overflow. These finite-system results demonstrate multi-repacking's occupied-time benefit under both the exponential model and the empirical coding-agent workload.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Large language models, Asynchronous reinforcement learning, KV cache management, Trajectory repacking, Stochastic analysis

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_sMuuOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes multi-repacking by jointly redistributing residual trajectories across multiple replicas to release workers earlier. It further proves that multi-repacking has a strictly smaller leading-order expected tail occupancy than hierarchical pairwise repacking, with a uniform asymptotic gap.

Critical strengths

The finite-system results demonstrate multi-repacking’s occupied-time benefit on both exponential and non-exponential workloads.

The theoretical analysis and proof are strong in this paper.

Critical weaknesses
  1. The experimental evaluation in this paper is relatively weak, as it does not provide any results in the main text. It only gives a deterministic comparison.

  2. The conclusion that "These finite-system results demonstrate multi-repacking’s occupied-time benefit on both exponential and non-exponential workloads", however, in the experiments, only exponential workloads and supplied lengths are evaluated, and the validity of non-exponential workloads still lacks interpretable distributional conditions.

  3. This paper is not well concluded, and the section of conclusion is also missing.

  4. Setting II utilizes data from only 15,806 forward-pass output lengths, all derived from a single internal software engineering RL workload, referred to as "SWE-bench Multilingual." Each sampling iteration generates 1600 × 12,800 = 20,480,000 simulated trajectories, obtained by repeatedly sampling from the aforementioned 15,806 observed forward-pass output lengths. This approach neither creates new, independent "real-world" tasks nor produces extreme outcomes that exceed the maximum values ​​found in the original sample set.

  5. Theorem 2, Theorem 3 and Proposition 4 compare strategies with the same-level matching, whole-block membership, the switch certificate, and terminal fallback. Appendix D.2 shows that the hierarchical variant after removing these restrictions reflects stronger empirical gains. As a result, "strategies with strict guarantees" and "strategies with more practical appeal" are still two sets of results.

  6. There is no reproducibility statement, and the code is not available. The code and the run records can be released anonymously.

  7. The end-to-end reinforcement learning (RL) throughput has not yet been evaluated in this paper.

Questions for authors
  1. There are so many assumptions in this paper. The authors should make it clear why such assumptions make sense.

  2. Why are the request dependence, input-token effects, and migration costs omitted in length resampling?

Reviewer_ySXHOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how to release replicas earlier during the tail of asynchronous RL generation by moving unfinished trajectories and their KV caches from several replicas into fewer ones. It proposes a hierarchical multi-repacking policy with slot and cache feasibility conditions, and derives a theoretical advantage over pairwise repacking under explicit stochastic assumptions. The evaluation uses single-version simulations with exponential service times and resampled agent-output lengths. Its main contribution is an analysis of how joint repacking can reduce tail occupied replica-time.

Critical strengths
  1. The idea of jointly repacking unfinished trajectories across multiple replicas is interesting.
Critical weaknesses
  1. The main paper is too long and does not show its experimental evidence. The 67-page submission presents the results in Section 5 as text, while the plots and additional comparison table appear in Appendix D. Readers should not have to search a long appendix to understand the central empirical claims. The paper would be much easier to assess if it were substantially shortened and the key results were shown and discussed in the main text.
  2. The experiments do not establish the benefit on real hardware or in an end-to-end RL system. Section 5 specifies simulator parameters and says that one workload uses output lengths from repeated SWE-agent rollouts with an internal Step-3.7-Flash checkpoint. But the evaluation is still a single-version simulation: it does not report a GPU cluster, measured GPU service times, the RL system and training configuration, or an end-to-end run. The supplied token lengths are not GPU runtimes. The model also assigns no time or resource cost to moving trajectories and their KV cache, and holds their completion times fixed. In a real system, migration can consume bandwidth and pause generation. Without measurements of migration volume and cost, it is unclear whether the reported occupancy gains translate to a net benefit.
  3. The assumptions behind the theory are not sufficiently justified or tested against realistic workloads. The analysis assumes independent exponential service times and cache growth linear in trajectory age. The non-exponential experiment independently resamples output lengths from one workload; it does not show whether the result persists with task-dependent or correlated durations, heavy tails, or measured GPU service times. The paper should explain why its assumptions are reasonable for the intended setting and test how sensitive the conclusions are to them.
Questions for authors
  1. Could the main text be substantially shortened and include the key experimental plots and tables, so readers can assess the central results without searching the appendix?
  2. Can you report an actual GPU-cluster or end-to-end asynchronous RL evaluation, including the GPU type, RL system and training configuration, measured generation service times, and migration volume/cost? How does the benefit change when migration time and bandwidth use are included?
  3. What empirical evidence motivates the independent exponential service-time and linear cache-growth assumptions? Can you report sensitivity to task-correlated or heavy-tailed durations and evaluate the policy using measured GPU service times, rather than independently resampled token lengths alone?
Reviewer_SsroOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies multi-repacking for the tail of an asynchronous rollout system in RL post-training. Under an idealized model with service-preserving migration, it derives packing conditions and compares multi-repacking hierarchies with pairwise repacking through occupied-replica-time bounds and event-driven simulations. Simulations use exponential service times and resampled output lengths; in the appendix, the authors also evaluate unrestricted policies.

Critical strengths

The paper studies an interesting problem for efficient large-scale asynchronous RL post-training executions.

Critical weaknesses

W1. Presentation and motivation. I find the abstract and introduction difficult to follow. Terms such as “hierarchy sums,” “packing-slack condition,” and “blocks” appear before the paper explains what they mean or why they matter. The scheduling terminology, such as “non-clairvoyant”, also needs an accessible explanation in context; I suggest using more technical framing. The introduction is not convincing on: (a) why the heuristic nature of existing repacking is itself a problem, and (b) whether the distinct gap can be made sufficiently clear. Section 4 is also disproportionately mathematical relative to how the contribution is explained. These issues make the contribution difficult to assess.

W2. Practical applicability to asynchronous RL. I do not think the system-model assumptions and evaluation establish practical applicability. The analysis considers a single-weight version, whereas asynchronous RL usually leverages simultaneous model versions. Staggered replica starts within one version do not establish how the approach works in that broader setting. Although Section 5 and Appendix D provide configuration and protocol details, the design choices need stronger motivation, and the evaluation remains limited. The paper acknowledges that it does not assess migration costs or end-to-end RL throughput; these omissions leave the practical benefit unclear to me.

Questions for authors

Q1. What specific gap distinguishes the proposed approach from existing repacking and scheduling work, beyond the fact that existing methods use heuristics?

Q2. What motivates the system-model assumptions and experimental choices, and how does the single-version analysis support applicability to asynchronous RL with simultaneous weight versions? In particular, can the released rollout GPUs be reallocated to training, and what benefit does the present evidence establish for that use?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.