Conceptio › Archive › arXiv CS

arXiv CSopen access

A Readiness-Driven Runtime for Pipeline-Parallel Training under Runtime Variability

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

A Readiness-Driven Runtime for Pipeline-Parallel Training under Runtime Variability Ruitao Liu1

Xinyang Tian1 Shuo Chen1 Tingrui Zhang1 Guang Yang1 Alan Zhao2 Wei Xu1 1 Tsinghua University 2 Scitix AI

arXiv:2605.18750v1 [cs.DC] 18 May 2026

{liurt23,tianxy22,s-chen25,zhang-tr22,yangg22}@mails.tsinghua.edu.cn [email protected], [email protected]

Pre-Committed Order Pipeline

Runtime-Readiness First

Rank 1 F1 Rank 2

F2 F1

Rank 3 F4

Bubble

F2 F2

Bubble

B1 F2

Runtime-Readiness-First Pipeline (RRFP)

Instead of waiting for B1, run ready work: F4, then F5, ...

External schedule Ready set of rank 1 (hint order) of rank 1 (available now)

Next scheduled step is B1, but its input has not arrived.

Time

F3 B2

Time Time

Forward microbatches such as F4 and F5 are already ready for rank 1, but pre-committed order execution still waits for B1, leading to pipeline bubbles.

Start Loop b)B1,B2,... No Backward f) F4,F5,... End Loop

F5 F7

F6 ...

Rank 1 F1

Rank 2

F2 F2

Rank 3

B1 is preferred but unavailable → dispatch F4; recheck, then F5; ... Key insight: Apply the hint order only after readiness filtering.

B1 F2

B1 Time

F5 B2

Time Time

Up to 1.77× faster on language-only workloads. Up to 2.77× faster on multimodal workloads. vs. fixed-order 1F1B baseline

Figure 1. RRFP overview. RRFP treats a pre-committed pipeline schedule as a non-binding hint order over currently ready work rather than as an execution sequence to wait for. By skipping unavailable tasks and dispatching ready work, RRFP reduces bubbles and stage misalignment, improving end-to-end training performance over fixed-order 1F1B by up to 1.77× on language-only workloads and 2.77× on multimodal workloads when using the BFW hint.

Abstract Pipeline parallelism is a key technique for scaling largemodel training, but modern workloads exhibit runtime variability in computation and communication. Existing pipeline systems typically consume static, profiled, or adaptively generated schedules as pre-committed execution orders. When realized task readiness diverges from the pre-committed order, stages may wait for not-yet-ready work even though other executable work is available, creating stage misalignment, idle bubbles, and reduced utilization. We present Runtime-Readiness-First Pipeline (RRFP), a readiness-driven runtime for pipeline-parallel training. RRFP changes how schedules are consumed at runtime: instead of treating a schedule as a sequence that stages must wait to follow, it treats the schedule as a non-binding hint order for ranking currently ready work. To support this model, RRFP combines message-driven asynchronous communication, lightweight tensor-parallel coordination for collective consistency, and ready-set arbitration for low-overhead dispatch. We implement RRFP in a Megatron-based training framework and evaluate it on language-only and multimodal workloads at up to 128 GPUs. RRFP improves over fixed-order pipeline baselines across all settings. Using the BFW hint,

RRFP achieves up to 1.77× speedup on language-only workloads and up to 2.77× on multimodal workloads. In crossframework comparisons, RRFP with the default BF hint outperforms the faster available external system by up to 1.84× while preserving training correctness. Keywords: pipeline parallelism, distributed training, runtime systems, readiness-driven execution, asynchronous communication, large-model training, multimodal training

Introduction

Large-scale distributed training has become the standard approach for training modern deep learning models [2, 17, 24– 26, 30, 42, 43, 47], especially large language and multimodal models [1, 3–6, 14] that exceed the memory and compute capacity of a single device, making distributed execution necessary. Among various parallelization strategies, pipeline parallelism is a key technique for scaling such models across multiple accelerators [18, 20, 23, 29, 36, 56]. However, modern distributed training workloads exhibit runtime variability in both computation and communication. Factors such as computation and communication jitter introduce temporal variations that are difficult to predict,

especially at scale [45, 54]. In addition, model- and inputdependent execution can further amplify variation across microbatches, particularly in multimodal pipelines [12, 48, 51]. As a result, latency across pipeline stages and overall system performance evolve over time during execution. This dynamic behavior exposes a fundamental limitation in how pipeline execution is currently structured. Modern systems typically organize pipeline execution around an order chosen before the corresponding work is executed. Prior work has explored both offline profiling [12, 27, 48, 49] and online adaptation [15, 16, 21, 33, 50, 51, 53] to improve pipeline execution order. These techniques provide valuable scheduling signals and can effectively reduce bubbles when their assumptions match realized execution. However, existing systems still ultimately produce or select an execution order that the runtime treats as a pre-committed execution order: stages are expected to follow the chosen sequence during execution, even when readiness has changed. Under runtime variability, this pre-commitment becomes fragile. Task readiness can change at finer granularity than scheduling decisions, so the pre-committed order may become stale and inconsistent with realized execution. When this happens, stages may wait for not-yet-ready work even though other executable work is available, creating stage misalignment, idle bubbles, and reduced utilization. Thus, the limitation does not arise from any particular scheduling strategy, but from making a planned order a requirement for runtime progress. Even a short mismatch between the planned order and the current ready set can force a stage to idle despite available executable work. To decouple runtime progress from a fixed order chosen ahead of execution, we propose a runtime-readiness-first design. At each stage, the runtime first constructs the current ready set and uses a schedule only as a non-binding hint order to rank ready candidates. If a higher-ranked task is not ready, the runtime skips it and dispatches another ready task instead of waiting. The key change is not to compute a different schedule, but to change how schedules are consumed at runtime: schedule guidance is preserved without enforcing a planned fixed execution order, broadening the space of schedules usable as runtime hints. We instantiate this design with Runtime-Readiness-First Pipeline (RRFP), a runtime system for correct out-of-order pipeline execution based on task readiness. RRFP combines three mechanisms: message-driven asynchronous communication decouples data transfer from the compute loop and updates ready buffers as messages arrive; lightweight tensorparallel coordination preserves collective consistency when tensor-parallel ranks observe different ready sets; and readyset arbitration scans the non-binding hint order over ready work and dispatches the selected task with low overhead. Together, these mechanisms preserve the benefits of schedule guidance when it matches realized readiness, while falling

back to readiness-driven progress without blocking on stale choices. RRFP extends Megatron-LM [30] as a configurable runtime layer, without modifying model definitions or training workflows. Our evaluation focuses on end-to-end performance, robustness to jitter, and runtime breakdown under dynamic execution conditions. This design lets existing schedules remain useful when their predicted order matches realized readiness, while avoiding stalls when it does not. It therefore separates schedule quality from runtime progress. Contributions. Overall, this paper makes the following contributions: • We identify a mismatch between pipeline execution orders chosen ahead of time and realized task readiness under computation and communication variability. • We introduce RRFP, a readiness-driven runtime that decouples pipeline progress from fixed global execution sequences while consuming existing schedules as nonbinding hint orders over the ready set. • We develop three mechanisms for correct, low-overhead out-of-order execution: message-driven communication decouples data transfer from computation, tensorparallel coordination preserves collective consistency, and ready-set arbitration dispatches ready work. • We show that RRFP improves end-to-end training performance. Using the BFW hint, RRFP achieves up to 1.77× speedup on language-only workloads and up to 2.77× on multimodal workloads over the fixed-order 1F1B. In representative cross-framework comparisons, RRFP’s default BF configuration outperforms the faster applicable external baseline by up to 1.84×, while preserving training correctness.

Characterizing Runtime Variability

2.1

Runtime Variability Beyond Workload Dynamicity

Execution time in distributed training is influenced by multiple sources of variability. A substantial body of prior work emphasizes workload dynamicity [41, 44, 50, 51], where input composition (e.g., sequence length or modality mix) changes per microbatch and leads to execution-time differences. In this paper, we focus on a complementary source that appears even when the workload is fixed: runtime variability, including kernel-level jitter, resource contention, and communication fluctuation [45, 54]. These effects introduce timing variation in both computation and communication under identical model and input settings. We show that this source of unpredictability challenges existing fixed-order approaches and is sufficient to disrupt pipeline execution, even under fixed configurations. Specifically, runtime variability leads to run-to-run differences in computation and communication latency, which in 2

(a) Forward Compute

(b) Backward Compute Latency (ms)

Latency (ms)

45 40 35 30 25

20 15 10

Sample 1 Sample 2 Sample 3 Sample 4

(d) Comm to Prev

Latency (ms)

Therefore, the measured spread reflects run-to-run runtime effects rather than workload or configuration differences. Figure 2 shows that noticeable latency variation remains even under these fixed conditions. The spread appears across multiple samples and across both computation and communication events, showing that jitter is not limited to a particular sample or operation type. Quantitatively, the normalized p95–p5 spread, (𝑝95 − 𝑝5)/𝑝50, reaches 0.73 for computation and 58.74 for communication, while the normalized interquartile spread, (𝑝75 − 𝑝25)/𝑝50, reaches 0.35 for computation and 50.80 for communication. These results show that runtime variability persists even when the input data and execution context are fixed. This makes it fragile to treat profiled or estimated execution times as a hard basis for runtime ordering, motivating a runtime layer that can react to realized readiness. This variability matters because pipeline decisions depend critically on when tasks become ready. Figure 3 illustrates that an order favored under planned timing, such as scheduling B1 before F3, can become suboptimal when runtime jitter changes realized timing. In the example, B1 takes longer than expected, so following the same committed order creates idle gaps. Dispatching the ready F3 task earlier instead better matches the realized execution state and reduces idle time. Such local waiting can also delay neighboring stages, amplifying bubbles through pipeline dependencies. This motivates a runtime-readiness-first design. Instead of waiting for a planned task that is not yet ready, the runtime re-evaluates the ready set as execution state evolves.

Sample 1 Sample 2 Sample 3 Sample 4

30 20 10 0

Sample 1 Sample 2 Sample 3 Sample 4

Figure 2. Run-to-run latency variability under identical training conditions. We repeat the same training procedure 300 times with the same model, input data, data order, hardware, pipeline configuration, and number of training iterations. We select 4 fixed samples and track them across all runs. Each boxplot summarizes the latency distribution of one tracked sample for one event type. Boxes span the interquartile range, from p25 to p75, with the center line indicating the median. Whiskers indicate p5 and p95 latencies. Stage 1 Stage 2

F2 F1

B1 F2

F3 B2

B2 F3 B3

Expected Execution (Optimal) Stage 1 Stage 2

Stage 1 Stage 2

F2 F1

B1 B2

B2 F3 B3

Under Runtime Variability (Suboptimal) F2 F1

F3 B1

B1 B2

B2 F3 B3

Under Runtime Variability (Optimal)

Figure 3. Effect of runtime variability on execution decisions. A planned order can be favorable under expected timing but become suboptimal when realized timing changes. Here, scheduling B1 before F3 creates idle gaps under runtime variability, while dispatching the ready F3 task earlier better matches the realized state and reduces idle time.

Method Overview

3.1

Execution Model and Constraints

We model pipeline execution within a training iteration as a dependency-constrained execution process over computation tasks. For each task 𝑣, let 𝑠 𝑣 and 𝑒 𝑣 denote its start and end time, and let 𝑝 𝑣 denote its execution time, such that 𝑒 𝑣 = 𝑠 𝑣 + 𝑝 𝑣 . We use iteration completion time, or makespan, 𝐶 max = max 𝑒 𝑣 , 𝑣 ∈𝑉

turn changes when tasks become ready and shifts favorable execution decisions. We characterize these effects below. 2.2

as the primary efficiency objective. A task can start only after all required predecessors have completed. These include inter-stage dependencies, where forward tasks depend on activations from the previous stage and backward tasks depend on gradients from the next stage, and intra-stage dependencies, where the backward task of a microbatch at a stage depends on its local forward task. We write these precedence constraints as

Runtime Variability Changes Task Readiness

To make the measurement concrete while isolating runtime variability from input and configuration changes, we repeat one fixed 1F1B training procedure 300 times under identical settings. The repeated runs use PP=8 and TP=1, and keep the model, input data, data order, hardware placement, pipeline configuration, number of training iterations, and 1F1B execution order unchanged. We select four fixed samples and track the same samples across all runs. For each sample in each run, we record four event latencies: forward computation, backward computation, communication to the next pipeline stage, and communication to the previous pipeline stage.

𝑠 𝑣 ≥ 𝑒𝑢 ,

∀(𝑢 → 𝑣) ∈ 𝐸,

where 𝐸 denotes the set of dependency edges. Each pipeline stage can execute at most one task at a time, so tasks assigned to the same stage must be serialized. 3

This model exposes the runtime decision problem faced by each stage. At any point, only a subset of tasks is executable, and this ready set changes as computation finishes and messages arrive. A fixed global order can therefore become inconsistent with the local ready set observed at runtime. 3.2

sends and receives in a predetermined sequence, such order divergence can cause stalls or deadlocks. Message-driven model. RRFP decouples data transfer from the compute loop with a message-driven communication model. When a forward or backward task completes, the produced tensor is submitted as a message carrying the microbatch identifier and direction. Receivers use this metadata to route out-of-order arrivals into per-microbatch buffers. A forward task becomes ready when its activation arrives from the previous stage. A backward task becomes ready only after the corresponding local forward task has completed and the gradient from the next stage has arrived. Thus, message arrival directly updates the local ready set.

RRFP Overview

RRFP is a readiness-driven runtime for out-of-order pipelineparallel training. Its core principle is readiness-first execution: each stage makes progress on currently executable work, while correctness and communication are handled by runtime mechanisms rather than a globally fixed step order. This execution model introduces three runtime challenges: communication-order divergence across neighboring stages, collective-order divergence across tensor-parallel ranks, and frequent arbitration among ready microbatches. RRFP addresses them with three corresponding mechanisms: (1) asynchronous message-based communication decouples data transfer from computation; (2) tensor-parallel coordination preserves collective consistency by coordinating only within each tensor-parallel group before collective-relevant computation; and (3) ready-set arbitration dispatches executable work using simple priorities while allowing external schedules to act as non-binding hint orders. Figure 4 summarizes how these mechanisms interact at one pipeline stage. Sections 4.1–4.2 describe the first two mechanisms for correct out-of-order execution, and Section 5 describes the arbitration layer.

Runtime implementation. RRFP implements the C++ communication backend with dedicated send and receive threads. At each pipeline stage, the runtime consists of a compute thread that executes forward/backward tasks and communication threads that move tensors asynchronously, decoupling computation from data transfer. Each stage maintains four buffers: forward-ready, forward-finished, backwardready, and backward-finished. The compute thread polls the ready buffers, runs F/B tasks, inserts completed tensors and metadata into the corresponding finished buffers, and wakes sender threads. Sender threads submit outgoing transfers, while receiver threads accept incoming messages, route them by microbatch identifier, and update the ready buffers. RRFP exposes the buffer-size limit as a configurable parameter and enforces it via a backpressure policy when forward computation runs far ahead of backward computation. The detailed buffer-size policy analysis and deadlock-free guarantee are provided in Appendix C. We study the effect of this buffer-size limit on training iteration time in Figure 5 using Qwen3-4B + ViT-Big [39, 52] with global batch size 192. We sweep the buffer limit over {4, 8, 16, 32, 48}. In this configuration, the worst-case demand is 192 entries if forward execution runs far ahead without backpressure. Increasing the limit gives the runtime more room to keep ready work, improving scheduling flexibility and reducing iteration time at small limits. The benefit saturates once the limit reaches 16 entries, far below the worstcase demand, indicating that a moderate limit exposes most readiness-driven opportunities without unnecessary memory growth. We choose 32 as a conservative value within the saturated range. Based on this sensitivity study, all experiments use a buffer-size limit of 32 unless otherwise stated.

Runtime Mechanisms for Correct Out-of-Order Execution

RRFP enables stages to execute microbatches according to observed readiness rather than a globally fixed order. Section 4.1 addresses communication-order divergence across neighboring stages, and Section 4.2 addresses collective-order consistency across tensor-parallel ranks. 4.1

Message-Driven Asynchronous Communication

Communication challenge. Out-of-order pipeline execution breaks the fixed send/receive order assumed by conventional pipeline communication. In a fixed schedule, neighboring stages issue sends and receives in the same predetermined microbatch order, so communication can be matched by sequence. Under readiness-driven execution, however, stages may progress on different microbatches. A sender may finish and issue transfers for several microbatches before the receiver reaches the corresponding receives, or a receiver may wait for data whose sender is still computing. Low-level communication stacks can move data efficiently, but the runtime must still match each activation or gradient to the correct microbatch and update readiness when messages arrive out of order. If the runtime instead waits for

4.2

Tensor-Parallel Coordination

Tensor-parallel constraint. Out-of-order execution introduces a correctness constraint under tensor parallelism. In Megatron-LM, ranks in the same tensor-parallel group must invoke collectives in the same microbatch order. Under 4

Async forward recv from PP stage 𝒊 − 𝟏

Async backward send to PP stage 𝒊 − 𝟏 i

iii

PP Stage 𝒊 Forward Ready Buffer

Hint Order & Computation BF Hint

Backward Finished Buffer

Repetitively Polling Backward Ready Buffer

iii

Forward Ready Buffer

ii Scan

Hint Order & Computation iv Forward Finished Buffer

Repetitively Polling

Scan

i or

Backward Ready Buffer

or ∅ each round

Sync with other TP ranks

Computation

ii Async forward send to PP stage 𝒊 + 𝟏

Async backward recv from PP stage 𝒊 + 𝟏

Figure 4. Workflow of RRFP at one pipeline stage. Asynchronous send/receive threads update forward/backward-ready buffers and drain finished buffers to neighboring pipeline stages. The arbitration layer repeatedly polls ready buffers and scans them according to a hint order, shown here with the backward-forward (BF) example, selecting only executable microbatches. Tensor-parallel ranks then synchronize the selected work item, and consistent selections proceed to computation. 15

task is deferred until readiness changes expose a common candidate. This preserves collective-order consistency without forcing a global pipeline order. We provide additional details on the coordination protocol and progress argument in Appendix D.

Avg Iter Time (s)

14 13 12 11

This section describes the local arbitration layer that selects the next microbatch to execute from the runtime ready buffer, without placing an expensive scheduler on the critical path. At each pipeline stage, local completion and message-arrival events continuously update forward/backward-ready buffers, while completed tasks enter finished buffers that feed the asynchronous communication runtime in Section 4.1. Thus, arbitration operates only over microbatches whose dependencies have actually been satisfied at runtime.

9 8 4

16 32 Buffer Size (Num Microbatches)

Ready-Set Arbitration

Figure 5. Performance sensitivity to buffer-size limit. With global batch size 192, the worst-case demand is the full batch size if forward execution runs far ahead. Iteration time saturates at a limit of 16 entries, indicating that a moderate limit exposes most readiness-driven opportunities.

Hint-based arbitration. The arbitration layer is parameterized by a hint order Π over microbatches and directions. The hint may come from a static schedule, offline profiling, or online adaptation, as long as it defines an ordered preference over candidates. When the compute thread becomes available, RRFP scans Π and dispatches the first entry that is present in the current ready buffer. If no candidate is ready, the thread waits for the next readiness event. Completed tasks are inserted into the corresponding finished buffers. In this way, schedules guide local arbitration without requiring the runtime to wait for unavailable work. The loop is lightweight because it scans bounded ready buffers under a fixed hint order rather than solving an online scheduling problem.

readiness-driven execution, however, ranks may observe different ready sets and select different microbatches, causing mismatched collective calls, incorrect results, or deadlock. Coordination protocol. RRFP enforces this constraint with a lightweight group-local coordination step. Before a forward or backward task that may invoke tensor-parallel collectives, each rank proposes its selected ready microbatch, and the group exchanges these identifiers using a scalar allgather. If all ranks agree, execution proceeds. Otherwise, the 5

Lightweight instantiation. The arbitration layer is independent of the specific hint order Π. Different schedules can be used to rank the current ready set. For analysis and evaluation, we use a simple backward-forward (BF) hint as the default lightweight instantiation. Inspired by the standard 1F1B pattern, BF first considers a backward-ready microbatch and then a forward-ready microbatch in each arbitration round, subject to runtime readiness. Within each direction, BF follows pipeline dependencies: forward prefers lower-index model chunks, while backward prefers higher-index chunks. This frees model chunks earlier and allows subsequent communication collectives to overlap with other computation work. The detailed BF hint algorithm is presented in Appendix A. Section 6 characterizes BF under a simplified setting, and Section 7.7 evaluates the effect of alternative hint orders on training performance.

This quantity lower bounds the makespan of any valid schedule, offline or online, because every schedule must execute all last-stage forward and backward computations. When the last stage is the dominant bottleneck, this lower bound is close to the relevant amount of unavoidable work, leading to the following approximation-style characterization. Corollary 6.2. Assume that for each microbatch 𝑗, the last stage is the bottleneck with probability at least 1 − 𝑝, and otherwise the deviation from the last-stage time is bounded by a constant factor 𝜌 ≥ 1. Further assume that each microbatch execution time is bounded by constants 𝑚𝑙 and 𝑚ℎ . Then C 𝑁 ≤ 1 + 2𝑝 (𝜌 − 1) + 𝑂 . E OPT 𝑀 The corollary suggests that the arbitration rule remains close to optimal when the last stage is often the bottleneck. This matches our measured workloads: across 100 iterations, the last stage is the bottleneck for 96.8% of forward microbatches in the LLM setting and 85.9% in the multimodal setting. These measurements explain why the BF hint is a reasonable default for our workloads. The full system, including communication, tensor parallelism, and runtime overhead, is evaluated in the end-to-end experiments.

Analytical Characterization

We analyze the backward-forward (BF) hint introduced in Section 5 under a simplified setting. The purpose is not to model the full RRFP runtime, but to understand the behavior of ready-set arbitration in isolation. We therefore consider a non-interleaved pipeline and ignore communication time, tensor-parallel coordination, collectives such as parameter gather, and implementation overhead. This setting lets us relate the local choices made by the BF hint to pipeline progress and stage imbalance. Proofs and detailed bottleneck statistics are provided in Appendix B. Let 𝑁 be the number of stages, 𝑀 the number of microbatches, and C the iteration completion time. For each mi𝑗 𝑗 crobatch 𝑗, let 𝐹 max and 𝐵 max denote the slowest forward and 𝑗 backward computation time across all stages, and let 𝐹 last 𝑗 and 𝐵 last denote the corresponding computation time at the last stage. We also define two reference makespans: F is the time needed to finish all forward work when the first stage initially has all forward microbatches available, and B is the time needed to finish all backward work when the last stage initially has all backward microbatches available. Both forward-only and backward-only reference executions still respect inter-stage pipeline dependencies.

𝑀 −1 ∑︁

𝑀 −2 ∑︁ 𝑗 𝑗 𝑗 𝑗 𝐹 max − 𝐹 last + 𝐵 max − 𝐵 last .

𝑗=1

𝑗=0

𝑀 −1 ∑︁

7.1

Experimental Setup

Workloads. We evaluate RRFP on both language-only and multimodal training workloads. The representative suite includes LLM (GPT3-Large [5, 22]), Mid-scale LMM (Qwen31.7B + ViT-H [11, 52]), and Heavy LMM (Qwen3-4B + ViTBig [11, 52]). We additionally evaluate larger multimodal workloads in the large-scale experiments, including LLaMA38B + ViT-5B [10], Qwen3-32B + InternViT [7–9, 13], and LLaMA3-70B + ViT-22B [10]. We denote parallel configurations as TP/PP/DP, with total GPU count TP × PP × DP. The exact TP/PP/DP configurations and global batch sizes used in each experiment are specified in Sections 7.3–7.8. Baselines. For same-codebase comparison, we evaluate 1F1B [29], ZeroBubble (ZB) [37], RRFP with the default BF hint (RRFP), and RRFP with the BFW hint variant (RRFP+BFW). RRFP uses the backward-forward (BF) hint from Sections 5 and 6: after readiness filtering, each round considers backward-ready work first. RRFP+BFW keeps the same runtime, but augments the task set with

The bound separates two effects: idealized forward and backward pipeline progress and extra delay caused by stage imbalance. To interpret this bound, we compare it with the total amount of work that must be executed at the last stage: 𝐿=

Experiments

System setup. RRFP extends a Megatron-based training framework. Our experiments run on up to 128 NVIDIA RTX 4090 GPUs across 16 nodes, with 8 GPUs per node. GPUs within each node communicate over PCIe, while nodes are connected through InfiniBand. RRFP uses shared memory for intra-node transfers and RDMA for inter-node transfers. All experiment runs use FP16 precision.

Theorem 6.1 (Upper bound for BF hint arbitration). The makespan C of RRFP under the BF hint satisfies C ≤F +B+

𝑗 𝑗 𝐹 last + 𝐵 last .

𝑗=0 6

backward/weight-update decomposition and uses the resulting B/F/W hint order. This variant is inspired by ZeroBubble’s backward/weight-update separation, but still treats the hint order as a non-binding preference over currently ready tasks. When neither backward nor forward computation is ready, RRFP+BFW dispatches an available weightupdate task and then returns to the next arbitration round. In both RRFP and RRFP+BFW, unavailable tasks are skipped rather than waited on. For cross-framework comparison, we additionally compare with DeepSpeed [2, 40] and Cornstarch [19]. DeepSpeed is a widely used distributed training framework with mature pipeline-parallel support, while Cornstarch is a recent multimodal training system with modality-aware pipeline scheduling.

under larger distributed deployments. These large-scale settings use batch size 64 and include both single-pipeline and DP-replicated hybrid-parallel configurations. For both representative and large-scale evaluations, each data point is averaged over 10 independent runs, with 50 measured iterations per run. Each table cell reports 𝑎/𝑏 (𝑥×), where 𝑎 is iteration time in seconds, 𝑏 is training throughput in s, and 𝑥× is speedup relative to 1F1B. Throughput is computed as batch size divided by iteration time. Batch size is matched across methods within each configuration. Representative results. Across all 12 representative configurations, RRFP consistently outperforms 1F1B and ZB, and RRFP+BFW further improves performance in most settings. The results show that making execution depend on realized readiness can recover utilization that fixed-order execution cannot always capture under runtime variability. Comparing RRFP and RRFP+BFW highlights the role of backward decomposition. RRFP already surpasses both 1F1B and ZB, showing that even the simple BF hint can be effective when applied after readiness filtering rather than enforced as a fixed execution sequence. At the same time, RRFP+BFW provides additional gains across almost all settings, indicating that RRFP can leverage the backward/weight-update separation idea when available. This suggests that RRFP is not tied to a specific schedule, but instead provides a flexible runtime layer for incorporating finer-grained execution hints as non-binding preferences over ready work. The benefits are greater in multimodal workloads. Compared to GPT3-Large, both Qwen3-1.7B + ViT-H and Qwen34B + ViT-Big exhibit larger improvements, which is consistent with increased runtime variability due to heterogeneous computation across stages. Under such conditions, fixed execution orders become less reliable, while RRFP dynamically adapts to changing readiness and better utilizes idle stages. We also observe that gains remain strong across both pipeline-depth and tensor-parallel settings. Under TP = 1, increasing pipeline depth from PP = 8 to PP = 16 generally provides more opportunities for runtime adaptation. The TP = 2 results show that this benefit persists when tensorparallel coordination is enabled: RRFP still outperforms 1F1B and ZB under both PP = 8 and PP = 16, although the gain can be smaller than in TP-free settings due to increased intrastage synchronization and reduced scheduling flexibility.

Metrics. We use iteration time as the primary metric across experiments. All measurements discard the first iteration and start timing from the second iteration. In RQ1, we also report throughput for completeness. For RQ2, we collect compute time, blocking time, and tensor-parallel coordination overhead for runtime breakdown. Experiment-specific details are reported in the corresponding subsections. Correctness validation. We validate training correctness by comparing RRFP with the corresponding 1F1B baseline under matched seeds and data order. RRFP follows the same loss trend without divergence, confirming that readinessdriven execution changes only runtime ordering while preserving training semantics. Detailed loss curves are provided in Appendix E. 7.2

Evaluation Questions

We evaluate RRFP using six research questions: RQ1 endto-end performance at representative and large scale, RQ2 runtime breakdown, RQ3 comparison with external systems, RQ4 robustness to runtime variability, RQ5 sensitivity to hint orders, and RQ6 scaling across conditions. We first establish end-to-end gains in both representative and largescale distributed settings (RQ1), then explain where the gains come from (RQ2), compare against strong external systems (RQ3), and finally validate robustness, hint-order sensitivity, and scaling behavior (RQ4–RQ6). 7.3

RQ1: End-to-End Performance

Protocol. RQ1 evaluates end-to-end training performance under two complementary settings. First, we evaluate all three representative workloads under four parallel configurations: TP1/PP8/DP1, TP1/PP16/DP1, TP2/PP8/DP1, and TP2/PP16/DP1. This yields 12 configurations. For each row, we compare 1F1B, ZeroBubble (ZB), RRFP, and RRFP+BFW. Global batch sizes are matched across methods within each row: GPT3-Large uses 64; Qwen3-1.7B + ViT-H uses 192; and Qwen3-4B + ViT-Big uses 192 at TP=1 and 96 at TP=2. Second, we evaluate 8 selected large-scale multimodal configurations on 32, 64, and 128 GPUs to validate that the gains persist

Large-scale results. To test whether the gains persist beyond representative configurations, we evaluate RRFP on larger multimodal workloads using 32, 64, and 128 GPUs. Table 2 covers both deep single-pipeline settings and hybrid PP/TP/DP settings with data-parallel replication. These results validate RRFP under larger distributed deployments and different parallelization choices. Across these large-scale settings from 32 to 128 GPUs, RRFP preserves the same qualitative gains observed in representative configurations. As workloads become larger and 7

Table 1. RQ1: end-to-end performance on representative settings. All settings use DP = 1. Cells report iteration time / throughput, with speedup over 1F1B shown in parentheses. Workload

Parallelism

1F1B

RRFP

RRFP+BFW

GPT3-Large

TP1/PP8/DP1 TP1/PP16/DP1 TP2/PP8/DP1 TP2/PP16/DP1

3.28/19.51 (1.00×) 2.09/30.62 (1.00×) 3.66/17.49 (1.00×) 2.34/27.35 (1.00×)

2.97/21.55 (1.10×) 1.74/36.78 (1.20×) 3.27/19.57 (1.12×) 2.03/31.53 (1.15×)

2.29/27.95 (1.43×) 1.26/50.79 (1.66×) 3.03/21.12 (1.21×) 1.63/39.26 (1.44×)

2.10/30.48 (1.56×) 1.18/54.24 (1.77×) 2.81/22.78 (1.30×) 1.57/40.76 (1.49×)

Qwen3-1.7B + ViT-H

TP1/PP8/DP1 TP1/PP16/DP1 TP2/PP8/DP1 TP2/PP16/DP1

11.49/16.71 (1.00×) 9.04/21.24 (1.00×) 12.94/14.84 (1.00×) 12.54/15.31 (1.00×)

9.91/19.37 (1.16×) 7.40/25.95 (1.22×) 11.86/16.19 (1.09×) 11.95/16.07 (1.05×)

5.98/32.11 (1.92×) 4.50/42.67 (2.01×) 7.66/25.07 (1.69×) 7.07/27.16 (1.77×)

5.68/33.80 (2.02×) 4.33/44.34 (2.09×) 7.41/25.91 (1.75×) 6.74/28.49 (1.86×)

Qwen3-4B + ViT-Big

TP1/PP8/DP1 TP1/PP16/DP1 TP2/PP8/DP1 TP2/PP16/DP1

14.05/13.67 (1.00×) 11.01/17.44 (1.00×) 7.19/13.35 (1.00×) 6.29/15.26 (1.00×)

12.61/15.23 (1.11×) 9.98/19.24 (1.10×) 6.60/14.55 (1.09×) 5.99/16.03 (1.05×)

7.84/24.49 (1.79×) 5.02/38.25 (2.19×) 4.45/21.57 (1.62×) 2.94/32.65 (2.14×)

7.52/25.53 (1.87×) 4.81/39.92 (2.29×) 4.19/22.91 (1.72×) 2.81/34.16 (2.24×)

Table 2. RQ1: end-to-end performance under large-scale distributed settings. All settings use global batch size 64. Cells report iteration time / throughput, with speedup over 1F1B shown in parentheses. GPUs

Workload

32 32 32 64 64 64 128 128

LLaMA3-8B + ViT-5B LLaMA3-8B + ViT-5B LLaMA3-8B + ViT-5B Qwen3-32B + InternViT Qwen3-32B + InternViT Qwen3-32B + InternViT LLaMA3-70B + ViT-22B LLaMA3-70B + ViT-22B

Parallelism

1F1B

RRFP

RRFP+BFW

TP1/PP32/DP1 TP2/PP16/DP1 TP2/PP8/DP2 TP1/PP64/DP1 TP2/PP32/DP1 TP2/PP16/DP2 TP2/PP64/DP1 TP2/PP32/DP2

7.62/8.40 (1.00×) 8.30/7.71 (1.00×) 4.90/13.06 (1.00×) 8.03/7.97 (1.00×) 8.39/7.63 (1.00×) 5.14/12.45 (1.00×) 8.72/7.34 (1.00×) 7.23/8.85 (1.00×)

6.58/9.73 (1.16×) 7.84/8.16 (1.06×) 4.44/14.41 (1.10×) 7.35/8.71 (1.09×) 7.66/8.36 (1.10×) 4.90/13.06 (1.05×) 7.94/8.06 (1.10×) 6.67/9.60 (1.08×)

3.38/18.93 (2.25×) 3.52/18.18 (2.36×) 3.02/21.19 (1.62×) 4.46/14.35 (1.80×) 5.19/12.33 (1.62×) 4.06/15.76 (1.27×) 5.16/12.40 (1.69×) 4.71/13.59 (1.54×)

2.75/23.27 (2.77×) 3.04/21.05 (2.73×) 2.77/23.10 (1.77×) 4.37/14.65 (1.84×) 4.66/13.73 (1.80×) 3.74/17.11 (1.37×) 4.76/13.45 (1.83×) 4.63/13.82 (1.56×)

7.4

more heterogeneous, deeper pipelines and cross-stage dependencies amplify the cost of rigid execution order. RRFP reduces this cost by dispatching currently ready work instead of waiting for unavailable tasks, while still using scheduling hints to rank ready candidates. The DP-replicated settings further show that RRFP is not limited to a single pipeline instance: even when the GPU allocation is split across dataparallel replicas, RRFP and RRFP+BFW continue to improve iteration time over fixed-order baselines. Overall, RQ1 demonstrates that RRFP is robust to runtime variability and compatible with finer-grained execution hints such as backward/weight-update separation. The representative results show consistent gains across workload types and TP/PP trade-offs. RRFP+BFW further shows that the same readiness-driven runtime can incorporate ZeroBubble’s backward and weight-update separation idea, often improving over the default BF hint. The large-scale validation confirms that these gains extend to practical hybrid-parallel deployments. Together, these results indicate that readiness-driven execution is effective both for the default BF policy and for finer-grained variants at larger scale.

RQ2: Runtime Breakdown

Breakdown setup. RQ2 determines where RRFP’s endto-end gains come from by decomposing each training iteration into major runtime components. In particular, we distinguish compute-related time, blocking time, and tensorparallel coordination overhead. This lets us separate reductions in pipeline bubbles and communication/blocking stalls from changes in compute execution, while also quantifying the extra coordination cost introduced by out-of-order execution under tensor parallelism. We use Qwen3-4B + ViT-Big with batch size 32, fixed PP=16 and DP=1, varying TP over {1, 2, 4}. TP=1 does not require tensor-parallel collectiveorder coordination, while TP>1 allows us to measure the coordination overhead that RRFP introduces to preserve collective consistency under out-of-order execution. Breakdown metrics. We report iteration time and three runtime components: • Compute: total F/B computation time across all microbatches, including GPU kernel execution and CPUside overhead such as kernel launch. • Blocking: time without useful F/B computation. For 1F1B, this is time spent issuing or waiting for pointto-point communication, including wait_on_req. For 8

RRFP, this is time spent polling or waiting when no executable microbatch is currently ready. • TP Coord: extra time spent in RRFP’s tensor-parallel metadata all-gather for preserving collective-order consistency. It is zero for 1F1B, whose fixed order already aligns collective calls, and for TP=1.

Cornstarch and RRFP because DeepSpeed’s automatic tensorparallel partitioning is not applicable to our PipelineModulewrapped model in this training setup [2, 40]. Representative results. Table 4 shows that RRFP achieves the lowest iteration time across all 12 representative settings in cross-framework comparison, with 1.07×–1.84× speedup over the faster available external baseline. As these settings match RQ1, the results show that RRFP’s gains persist across workload type, pipeline depth, and tensor parallelism. The gains are generally larger on multimodal workloads than on GPT3-Large, consistent with greater stage heterogeneity and runtime variability in multimodal training.

Table 3 reports the resulting breakdown. Across all TP settings, the dominant cost in fixed-order 1F1B is Blocking rather than Compute. Blocking accounts for 64.22–66.72% of 1F1B iteration time, indicating that a substantial fraction of time is spent without useful compute progress. This blocking arises because 1F1B follows a pre-committed execution order: each stage issues communication and computation according to the fixed schedule, and must wait when the scheduled dependency has not yet arrived. Under runtime variability, the actual completion times of computation and communication differ across stages and microbatches, so the fixed order can become misaligned with realized readiness, creating pipeline bubbles and communication stalls. RRFP reduces this cost through readiness-driven out-oforder execution. Instead of waiting for the next task in a fixed global order, each stage executes ready work as it becomes available. As a result, Blocking is consistently reduced across TP settings: from 1.722s to 0.768s under TP1/PP16/DP1, from 1.698s to 0.788s under TP2/PP16/DP1, and from 1.812s to 0.873s under TP4/PP16/DP1. This reduction is the primary source of the end-to-end speedup. This breakdown also shows that the speedup is not due to faster computation or kernel-level acceleration. Compute remains comparable between 1F1B and RRFP, and is slightly higher for RRFP in these runs due to additional CPU-side runtime overhead around computation. As TP increases from 1 to 4, RRFP introduces TP Coord overhead to preserve tensor-parallel collective-order consistency under out-of-order execution. This overhead remains small: 0.010s under TP=2 and 0.015s under TP=4, accounting for less than 1% of iteration time. Thus, the coordination cost is much smaller than the reduction in Blocking. Overall, RQ2 shows that RRFP shifts the cost structure of pipeline execution: it adds lightweight runtime polling and TP coordination, but substantially reduces blocking caused by pre-committed execution order. This supports the main runtime-system claim that readiness-driven progress reduces idle time under runtime variability. 7.5

Large-scale results. Table 5 shows that RRFP also achieves the lowest iteration time across all 8 large-scale settings, with 1.01×–1.25× speedup over the faster available external baseline. The smallest gap appears for LLaMA3-8B + ViT-5B under TP1/PP32/DP1, where Cornstarch is already competitive. The remaining cases show clearer gains, including settings with tensor parallelism and data-parallel replication, indicating that RRFP remains effective as training scales to deeper pipelines and hybrid TP/PP/DP configurations. Overall, RQ3 shows that RRFP’s gains extend beyond same-codebase schedule comparisons and hold against external systems. Across the representative and large-scale RQ1 settings, RRFP improves over both general-purpose and multimodal-specialized external training systems. This suggests that RRFP’s advantage comes from the readinessdriven runtime model rather than artifacts of a particular framework or schedule implementation. 7.6

RQ4: Robustness to Runtime Variability

Robustness under variability. We test how much performance degrades when runtime jitter increases under a controlled injection setup. We use Qwen3-4B + ViT-Big with TP2/PP8/DP1 and global batch size 96, compare 1F1B and RRFP, and keep all settings fixed except the injected jitter level. Jitter model and protocol. We inject compute-path jitter on every pipeline stage by adding random CUDA-side sleep delays to F/B compute tasks. For each task, the runtime first measures its compute time 𝑐𝑡 and updates a stage-local exponential moving average: 𝑒𝑡 = 0.9𝑒𝑡 −1 + 0.1𝑐𝑡 . With probability 𝑝 𝑗 , we inject a delay

RQ3: Cross-Framework Performance

𝑑𝑡 = 𝛼 max(𝐵, 𝑒𝑡 ) (0.5 + 𝑟𝑡 ),

Cross-framework setup. RQ3 compares the default RRFP configuration (RRFP) with DeepSpeed and Cornstarch on the same matched RQ1 settings. We use RRFP to isolate the readiness-driven runtime from the optional backward/weightupdate decomposition in RRFP+BFW. We evaluate all 12 representative configurations in Table 1 and all 8 large-scale configurations in Table 2. For TP > 1, we compare only

𝑟𝑡 ∼ Uniform(0, 1),

where 𝐵 sets the base delay and 𝛼 controls the delay scale. We evaluate four jitter levels, 𝐽0 –𝐽3 , with parameters shown in Table 6. For each level, 1F1B and RRFP use the same random seed, so they experience paired jitter patterns. Each setting is repeated 3 times with 10 measured iterations per run. We report the mean iteration time, slowdown relative to each 9

Table 3. RQ2: runtime breakdown. We evaluate 1F1B and RRFP on Qwen3-4B + ViT-Big with global batch size 32 and PP=16, varying TP over {1, 2, 4}. Values are seconds per iteration. Percentages are normalized by iteration time. Results are averaged over 3 independent runs with 10 measured iterations per run. Parallelism

Method

Iter

Compute

Blocking

TP Coord

TP1/PP16/DP1

1F1B RRFP

2.581 1.788

0.859 (33.28%) 1.020 (57.05%)

1.722 (66.72%) 0.768 (42.95%)

0.000 (0.00%) 0.000 (0.00%)

TP2/PP16/DP1

1F1B RRFP

2.644 1.824

0.946 (35.78%) 1.026 (56.25%)

1.698 (64.22%) 0.788 (43.20%)

0.000 (0.00%) 0.010 (0.55%)

TP4/PP16/DP1

1F1B RRFP

2.750 1.942

0.938 (34.11%) 1.054 (54.27%)

1.812 (65.89%) 0.873 (44.95%)

0.000 (0.00%) 0.015 (0.77%)

Table 4. Cross-framework comparison on representative settings. Settings match the corresponding RQ1 configurations. Entries report average iteration time in seconds, and speedup is computed over the faster available external baseline. Workload

Parallelism

DeepSpeed Cornstarch RRFP Speedup

GPT3-Large

TP1/PP8/DP1 TP1/PP16/DP1 TP2/PP8/DP1 TP2/PP16/DP1

2.60 1.52 N/A N/A

2.63 2.00 3.25 2.88

2.29 1.26 3.03 1.63

1.14× 1.21× 1.07× 1.77×

TP1/PP8/DP1 TP1/PP16/DP1 Qwen3-1.7B + ViT-H TP2/PP8/DP1 TP2/PP16/DP1

9.73 7.80 N/A N/A

8.65 6.71 9.88 8.16

5.98 4.50 7.66 7.07

1.45× 1.49× 1.29× 1.15×

TP1/PP8/DP1 TP1/PP16/DP1 Qwen3-4B + ViT-Big TP2/PP8/DP1 TP2/PP16/DP1

11.38 10.54 N/A N/A

10.12 9.24 6.80 4.76

7.84 5.02 4.45 2.94

1.29× 1.84× 1.53× 1.62×

Table 5. Large-scale cross-framework comparison. Settings match the corresponding RQ1 configurations. Entries report average iteration time in seconds, and speedup is computed over the faster available external baseline. GPUs Workload 32 32 32 64 64 64 128 128

LLaMA3-8B + ViT-5B LLaMA3-8B + ViT-5B LLaMA3-8B + ViT-5B Qwen3-32B + InternViT Qwen3-32B + InternViT Qwen3-32B + InternViT LLaMA3-70B + ViT-22B LLaMA3-70B + ViT-22B

Parallelism TP1/PP32/DP1 TP2/PP16/DP1 TP2/PP8/DP2 TP1/PP64/DP1 TP2/PP32/DP1 TP2/PP16/DP2 TP2/PP64/DP1 TP2/PP32/DP2

method’s no-injection baseline, and the standard deviation computed over the 30 measured iterations.

DeepSpeed Cornstarch RRFP Speedup 4.33 N/A N/A 5.97 N/A N/A N/A N/A

3.42 4.40 3.51 5.51 5.67 4.30 5.52 5.79

3.38 3.52 3.02 4.46 5.19 4.06 5.16 4.71

1.01× 1.25× 1.16× 1.24× 1.09× 1.06× 1.07× 1.23×

RRFP also shows lower variation in measured iteration time across all jitter levels. Its standard deviation remains between 0.191s and 0.228s, compared with 0.325s to 0.410s for 1F1B. Overall, RQ4 shows that RRFP is robust to runtime variability: it maintains lower iteration time across all tested jitter levels and degrades more slowly as jitter intensity increases.

Results and discussion. Table 6 shows that RRFP consistently remains faster than 1F1B across all jitter levels. More importantly, RRFP degrades more slowly as jitter increases: from 𝐽1 to 𝐽3 , RRFP’s slowdown grows from 1.81% to 11.36%, whereas 1F1B grows from 2.82% to 18.06%. This indicates that readiness-driven execution is less sensitive to compute-path perturbations than a fixed execution order. 10

Table 6. RQ4: robustness under compute-path jitter. We evaluate 1F1B and RRFP on Qwen3-4B + ViT-Big with TP2/PP8/DP1 and global batch size 96. Parentheses show slowdown relative to each method’s no-injection baseline. 1F1B Level 𝑝 𝑗

𝐵 (ms)

0 0.1 0.2 0.3

0 5 10 15

RRFP

𝛼 𝑇 (s)

𝐽0 𝐽1 𝐽2 𝐽3

ready tasks, but the small gaps among BF, FB, and B-priority indicate that the main benefit comes from readiness-driven execution rather than from a specific heuristic. Overall, RQ5 reinforces that RRFP’s gains mainly come from out-of-order, readiness-driven execution rather than from a specific heuristic. This is consistent with RQ1 and RQ2, where RRFP improves utilization by reducing blocking wait, and shows that RRFP acts as a flexible runtime layer rather than a heuristic-specific scheduler.

0.0 7.19 (0.0%) 0.5 7.39 (2.82%) 1.0 8.00 (11.27%) 1.5 8.49 (18.06%)

std (s)

𝑇 (s)

std (s)

0.339 0.325 0.410 0.390

4.45 (0.0%) 4.53 (1.81%) 4.75 (6.82%) 4.96 (11.36%)

0.191 0.191 0.210 0.228

7.8

Setup. RQ6 analyzes when RRFP helps most along three controlled axes: pipeline depth, multimodal imbalance, and global batch size. For pipeline-depth scaling, we vary PP while keeping the workload, TP/DP configuration, and global batch size fixed. For modality-imbalance scaling, we fix the language backbone and parallel configuration while increasing the vision encoder size. In the ViT rows of Table 8, L/H/g/Big denote ViT-L, ViT-H, ViT-g, and ViT-Big, and 5B/Intern/22B denote ViT-5B, InternViT, and ViT-22B. For batch-size scaling, we vary global batch size under two fixed workload settings. Table 8 lists the concrete workloads, parallel configuration, sweeps, and global batch sizes. Each configuration is run 10 times with 50 measured iterations per run, and we report speedup over 1F1B.

Table 7. RQ5: hint-order sensitivity. We evaluate RRFP on Qwen3-1.7B + ViT-H with TP1/PP8/DP1 and batch size 192.

7.7

Hint order

Avg (ms) Slowdown (%)

BF (default) FB B-priority F-priority

6007.26 6034.10 6057.79 6302.94

RQ6: Scaling Across Conditions

0.00 +0.45 +0.84 +4.92

RQ5: Sensitivity to Hint Orders

Hint-order sensitivity. We evaluate whether RRFP depends on a particular ready-set hint order. All variants run inside the same RRFP runtime loop and differ only in how they rank currently ready forward and backward candidates, while using the same readiness filtering. We compare four hint orders. BF is the default backward-forward hint from Section 5: each arbitration round first considers backwardready work and then forward-ready work, subject to runtime readiness. FB reverses this order by considering forwardready work before backward-ready work. B-priority selects backward work whenever any backward candidate is ready, while F-priority analogously prioritizes forward work whenever any forward candidate is ready.

Results and discussion. Table 8 shows that RRFP’s benefit increases when execution provides more opportunities for readiness-driven choice. For pipeline-depth scaling, speedup grows from 1.07× to 2.01× on Qwen3-1.7B + ViT-H as PP increases from 4 to 16, and from 1.79× to 2.31× on LLaMA3-8B + ViT-5B as PP increases from 8 to 32. The TP2 Qwen3-4B + ViT-Big setting follows the same trend, with speedup increasing from 1.03× to 1.72× as pipeline depth increases, indicating that the benefit consistently persists when tensorparallel coordination is enabled. For modality imbalance, speedup increases as the vision encoder becomes larger and stage costs become more uneven: from 1.73× to 2.16× on Qwen3-1.7B, and from 1.32× to 1.78× on LLaMA3-8B. This suggests that RRFP is especially beneficial when multimodal workloads introduce heterogeneous stage costs, making fixed execution orders more likely to become misaligned with realized readiness. For batch-size scaling, speedup also increases as global batch size grows across both workloads. Qwen3-4B + ViT-Big improves from 1.98× to 2.18× as global batch size increases from 64 to 192, and LLaMA3-8B + ViT-5B improves from 2.62× to 2.82×. Increasing the global batch size place more microbatches in the pipeline, exposing more scheduling opportunities and runtime variation for RRFP to exploit. Overall, RQ6 shows that RRFP helps most when fixed execution orders are more likely to become stale and more alternative executable candidates are available, such as in deeper pipelines, more imbalanced multimodal workloads,

Configuration and metric. We use Qwen3-1.7B + ViT-H with TP1/PP8/DP1, global batch size 192, and 10 measured training iterations per run. Each hint order is repeated 3 times. We report average end-to-end iteration time. Results and discussion. Table 7 shows that RRFP is largely insensitive to the specific hint order across these variants. BF, FB, and B-priority remain within 1% of the default, indicating that performance is not driven by a carefully tuned ordering rule but primarily by the underlying readiness-driven execution model. At the same time, poorly aligned hint orders can still hurt performance: F-priority incurs a noticeable slowdown of +4.92% because it keeps prioritizing forward work whenever possible, delaying backward execution and creating additional pipeline bubbles. This shows that hint orders still affect how RRFP chooses among 11

Table 8. RQ6 scaling results across pipeline depth, modality imbalance, and global batch size. We report speedup over 1F1B. Larger values indicate greater benefit from readiness-driven execution. Axis

Workload

Config

Sweep

Batch size

Speedup

PP PP PP

Qwen3-1.7B + ViT-H TP1/DP1 LLaMA3-8B + ViT-5B TP1/DP1 Qwen3-4B + ViT-Big TP2/DP1

PP4 / PP8 / PP16 PP8 / PP16 / PP32 PP4 / PP8 / PP16

192 64 64

1.07 / 1.94 / 2.01 1.79 / 2.13 / 2.31 1.03 / 1.64 / 1.72

ViT ViT

Qwen3-1.7B LLaMA3-8B

TP1/PP16/DP1 L / H / g / Big TP1/PP32/DP1 5B / Intern / 22B

192 64

1.73 / 1.89 / 2.04 / 2.16 1.32 / 1.43 / 1.78

BSZ BSZ

Qwen3-4B + ViT-Big TP1/PP16/DP1 64 / 128 / 192 LLaMA3-8B + ViT-5B TP2/PP32/DP1 64 / 128 / 192

– –

1.98 / 2.14 / 2.18 2.62 / 2.72 / 2.82

and larger batches. In these settings, selecting among ready tasks instead of waiting for the next scheduled task provides larger benefits across the tested configurations, and the gains persist when tensor-parallel coordination is enabled.

can execute independently of a planned schedule, or use an existing one as a soft ranking hint when available. Runtime adaptation. Several systems use runtime feedback to improve distributed training efficiency. ByteScheduler [35] dynamically schedules communication operations to reduce synchronization overhead, HetPipe [34] addresses heterogeneous GPU clusters through load-balancing strategies, and Pollux [38] adapts cluster resource allocation based on runtime feedback. These systems show the value of runtime information, but they target different layers of the training stack, such as communication prioritization, heterogeneous placement, or cluster-level scheduling. RRFP focuses on the pipeline execution layer. It makes decisions at the granularity of forward and backward microbatch tasks within each pipeline stage, allowing execution to react directly to realized readiness, runtime slowdowns, and communication delays. Thus, RRFP differs from prior runtimeadaptive systems not by periodically adapting a fixed schedule, but by making readiness the primary execution interface.

Related Work

Pipeline parallelism. Pipeline parallelism is widely used to train large models that exceed the memory capacity of a single device. By partitioning a model across devices and executing different microbatches concurrently, pipeline parallelism improves hardware utilization and training throughput. GPipe [18] introduced synchronous pipeline training with microbatching, and PipeDream [28] proposed the oneforward-one-backward (1F1B) schedule to reduce bubbles by overlapping forward and backward computation. This schedule has been adopted in systems such as MegatronLM [43] and is now a standard baseline for pipeline-parallel training. Later systems further improve pipeline execution: PipeDream-2BW [29] reduces memory overhead from weight versioning, while ZeroBubble [37] reduces bubbles by reordering backward-related computation. RRFP builds on these foundations but does not propose another fixed ordering of forward and backward tasks. Instead, it changes how schedules are consumed at runtime: each stage repeatedly chooses from currently ready microbatches, while existing schedules serve as non-binding hint orders.

Communication assumptions in training runtimes. Modern distributed training systems rely on high-throughput GPU communication libraries whose operations are typically issued by the application in a consistent order across participating ranks [31, 32]. This assumption fits static or synchronized pipeline schedules, where computation and communication follow an agreed sequence. Readiness-driven out-of-order execution weakens this assumption: different stages may finish microbatches in different orders, causing sends and receives to be triggered asynchronously and out of order. If communication remains tied to a fixed operation sequence, this divergence can introduce blocking or deadlock. RRFP addresses this with message-driven asynchronous communication: completed microbatches are packaged as messages, transferred independently of the compute thread, and inserted into per-microbatch ready buffers upon arrival. It also uses lightweight tensor-parallel coordination to preserve collective-order consistency when ranks in the same tensor-parallel group might otherwise select different ready microbatches. Together, these mechanisms allow RRFP to

Pipeline planning and schedule optimization. Many distributed training systems optimize pipeline execution through offline search, profiling, or cost-based planning. Representative examples include Alpa [55] and PipeWeaver [50]. Related strategies also appear in nnScaler [27] and Unity [46]. These methods construct better parallelization plans or better pipeline schedules under estimated workload and system conditions, and can be effective when those estimates remain representative at runtime. However, the resulting plans still rely on specific decisions made before the actual runtime ready set is observed. RRFP is orthogonal to such planning methods. It is not a schedule optimizer and does not require an optimized decision sequence for correctness or progress. Instead, it provides a readiness-driven runtime layer that 12

References

execute microbatches safely in an order that differs from any pre-planned schedule.

[1] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, Roman Ring, Eliza Rutherford, Serkan Cabi, Tengda Han, Zhitao Gong, Sina Samangooei, Marianne Monteiro, Jacob Menick, Sebastian Borgeaud, Andrew Brock, Aida Nematzadeh, Sahand Sharifzadeh, Mikolaj Binkowski, Ricardo Barreira, Oriol Vinyals, Andrew Zisserman, and Karen Simonyan. 2022. Flamingo: a Visual Language Model for Few-Shot Learning. arXiv:2204.14198 [cs.CV] https://arxiv.org/abs/2204.14198 [2] Reza Yazdani Aminabadi, Samyam Rajbhandari, Minjia Zhang, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Jeff Rasley, Shaden Smith, Olatunji Ruwase, and Yuxiong He. 2022. DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale. arXiv:2207.00032 [cs.LG] https://arxiv.org/abs/2207.00032 [3] Shuai Bai, Yuxuan Cai, Ruizhe Chen, Keqin Chen, Xionghui Chen, Zesen Cheng, Lianghao Deng, Wei Ding, Chang Gao, Chunjiang Ge, Wenbin Ge, Zhifang Guo, Qidong Huang, Jie Huang, Fei Huang, Binyuan Hui, Shutong Jiang, Zhaohai Li, Mingsheng Li, Mei Li, Kaixin Li, Zicheng Lin, Junyang Lin, Xuejing Liu, Jiawei Liu, Chenglong Liu, Yang Liu, Dayiheng Liu, Shixuan Liu, Dunjie Lu, Ruilin Luo, Chenxu Lv, Rui Men, Lingchen Meng, Xuancheng Ren, Xingzhang Ren, Sibo Song, Yuchong Sun, Jun Tang, Jianhong Tu, Jianqiang Wan, Peng Wang, Pengfei Wang, Qiuyue Wang, Yuxuan Wang, Tianbao Xie, Yiheng Xu, Haiyang Xu, Jin Xu, Zhibo Yang, Mingkun Yang, Jianxin Yang, An Yang, Bowen Yu, Fei Zhang, Hang Zhang, Xi Zhang, Bo Zheng, Humen Zhong, Jingren Zhou, Fan Zhou, Jing Zhou, Yuanzhi Zhu, and Ke Zhu. 2025. Qwen3-VL Technical Report. arXiv:2511.21631 [cs.CV] https://arxiv.org/abs/2511.21631 [4] Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, Humen Zhong, Yuanzhi Zhu, Mingkun Yang, Zhaohai Li, Jianqiang Wan, Pengfei Wang, Wei Ding, Zheren Fu, Yiheng Xu, Jiabo Ye, Xi Zhang, Tianbao Xie, Zesen Cheng, Hang Zhang, Zhibo Yang, Haiyang Xu, and Junyang Lin. 2025. Qwen2.5-VL Technical Report. arXiv:2502.13923 [cs.CV] https://arxiv.org/abs/2502.13923 [5] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language Models are Few-Shot Learners. arXiv:2005.14165 [cs.CL] https://arxiv.org/abs/2005.14165 [6] Mouxiang Chen, Binyuan Hui, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Jianling Sun, Junyang Lin, and Zhongxin Liu. 2025. Parallel Scaling Law for Language Models. arXiv:2505.10475 [cs.LG] https://arxiv.org/ abs/2505.10475 [7] Zhe Chen, Weiyun Wang, Yue Cao, Yangzhou Liu, Zhangwei Gao, Erfei Cui, Jinguo Zhu, Shenglong Ye, Hao Tian, Zhaoyang Liu, et al. 2024. Expanding Performance Boundaries of Open-Source Multimodal Models with Model, Data, and Test-Time Scaling. arXiv preprint arXiv:2412.05271 (2024). [8] Zhe Chen, Weiyun Wang, Hao Tian, Shenglong Ye, Zhangwei Gao, Erfei Cui, Wenwen Tong, Kongzhi Hu, Jiapeng Luo, Zheng Ma, et al. 2024. How Far Are We to GPT-4V? Closing the Gap to Commercial Multimodal Models with Open-Source Suites. arXiv preprint arXiv:2404.16821 (2024). [9] Zhe Chen, Jiannan Wu, Wenhai Wang, Weijie Su, Guo Chen, Sen Xing, Muyan Zhong, Qinglong Zhang, Xizhou Zhu, Lewei Lu, et al. 2024. Internvl: Scaling up vision foundation models and aligning for generic visual-linguistic tasks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 24185–24198.

Conclusion

Pipeline parallelism is essential for scaling large-model training, but fixed execution orders can become stale under runtime variability, as computation and communication readiness change during execution. This paper presented RRFP, a readiness-driven runtime layer for out-of-order pipelineparallel training. RRFP combines message-driven asynchronous communication, ready-set arbitration, and lightweight tensor-parallel coordination to dispatch ready work while preserving communication progress and collective-order consistency. Across language-only and multimodal workloads, RRFP reduces blocking wait, improves end-to-end performance, outperforms external systems in matched settings, remains robust to injected jitter and alternative hint orders, and is especially beneficial in deeper pipelines, more imbalanced workloads, and larger-batch settings. These results suggest that pipeline schedules should guide ready work rather than serve as fixed orders that runtime must follow.

[10] Mostafa Dehghani, Josip Djolonga, Basil Mustafa, Piotr Padlewski, Jonathan Heek, Justin Gilmer, Andreas Steiner, Mathilde Caron, Robert Geirhos, Ibrahim Alabdulmohsin, Rodolphe Jenatton, Lucas Beyer, Michael Tschannen, Anurag Arnab, Xiao Wang, Carlos Riquelme, Matthias Minderer, Joan Puigcerver, Utku Evci, Manoj Kumar, Sjoerd van Steenkiste, Gamaleldin F. Elsayed, Aravindh Mahendran, Fisher Yu, Avital Oliver, Fantine Huot, Jasmijn Bastings, Mark Patrick Collier, Alexey Gritsenko, Vighnesh Birodkar, Cristina Vasconcelos, Yi Tay, Thomas Mensink, Alexander Kolesnikov, Filip Pavetić, Dustin Tran, Thomas Kipf, Mario Lučić, Xiaohua Zhai, Daniel Keysers, Jeremiah Harmsen, and Neil Houlsby. 2023. Scaling Vision Transformers to 22 Billion Parameters. arXiv:2302.05442 [cs.CV] https://arxiv.org/abs/ 2302.05442 [11] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2020. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. arXiv:2010.11929 https: //arxiv.org/abs/2010.11929 [12] Weiqi Feng, Yangrui Chen, Shaoyu Wang, Yanghua Peng, Haibin Lin, and Minlan Yu. 2025. Optimus: Accelerating Large-Scale Multi-Modal LLM Training by Bubble Exploitation. arXiv:2408.03505 [cs.CL] https: //arxiv.org/abs/2408.03505 [13] Zhangwei Gao, Zhe Chen, Erfei Cui, Yiming Ren, Weiyun Wang, Jinguo Zhu, Hao Tian, Shenglong Ye, Junjun He, Xizhou Zhu, et al. 2024. Mini-internvl: A flexible-transfer pocket multimodal model with 5% parameters and 90% performance. arXiv preprint arXiv:2410.16261 (2024). [14] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, Danny Wyatt, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Francisco Guzmán, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Govind Thattai, Graeme Nail, Gregoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jack Zhang, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Karthik Prasad, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid ElArini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu, Kunal Bhalla, Kushal Lakhotia, Lauren Rantala-Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Mahesh Pasupuleti, Mannat Singh, Manohar Paluri, Marcin Kardas, Maria Tsimpoukelli, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoychev, Niladri Chatterji, Ning Zhang, Olivier Duchenne, Onur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar

Vasic, Peter Weng, Prajjwal Bhargava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohan Maheswari, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang, Saghar Hosseini, Sahana Chennabasappa, Sanjay Singh, Sean Bell, Seohyun Sonia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang, Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mihaylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do, Vish Vogeti, Vítor Albiero, Vladan Petrovic, Weiwei Chu, Wenhan Xiong, Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaofang Wang, Xiaoqing Ellen Tan, Xide Xia, Xinfeng Xie, Xuchao Jia, Xuewei Wang, Yaelle Goldschlag, Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song, Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aayushi Srivastava, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Amos Teo, Anam Yunus, Andrei Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchandani, Annie Dong, Annie Franco, Anuj Goyal, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leonhardi, Bernie Huang, Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Ce Liu, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Cynthia Gao, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang, Duc Le, Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Eric-Tuan Le, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smothers, Fei Sun, Felix Kreuk, Feng Tian, Filippos Kokkinos, Firat Ozgenel, Francesco Caggioni, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpern, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hakan Inan, Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harrison Rudolph, Helen Suk, Henry Aspegren, Hunter Goldman, Hongyuan Zhan, Ibrahim Damlaj, Igor Molybog, Igor Tufanov, Ilias Leontiadis, Irina-Elena Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Janice Lam, Japhet Asher, Jean-Baptiste Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, Jessica Zhong, Jian Jin, Jingyi Yang, Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Junjie Wang, Kai Wu, Kam Hou U, Karan Saxena, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kiran Jagadeesh, Kun Huang, Kunal Chawla, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A, Leandro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Miao Liu, Michael L. Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha 14

[22] Katikapalli Subramanyam Kalyan. 2023. A Survey of GPT-3 Family Large Language Models. arXiv:2310.12321 [cs.CL] https://arxiv.org/ abs/2310.12321 [23] Joel Lamy-Poirier. 2023. Breadth-First Pipeline Parallelism. arXiv:2211.05953 [cs.DC] https://arxiv.org/abs/2211.05953 [24] Shigang Li and Torsten Hoefler. 2021. Chimera: efficiently training large-scale neural networks with bidirectional pipelines. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’21). ACM, 1–14. doi:10.1145/ 3458817.3476145 [25] Xinyu Lian, Masahiro Tanaka, Olatunji Ruwase, and Minjia Zhang. 2025. SuperOffload: Unleashing the Power of Large-Scale LLM Training on Superchips. arXiv:2509.21271 [cs.LG] https://arxiv.org/abs/ 2509.21271 [26] Yanying Lin, Shijie Peng, Chengzhi Lu, ChengZhong Xu, and Kejiang Ye. 2026. FlexPipe: Adapting Dynamic LLM Serving Through Inflight Pipeline Refactoring in Fragmented Serverless Clusters. In Proceedings of the 21st European Conference on Computer Systems (EUROSYS ’26). ACM, 72–88. doi:10.1145/3767295.3769316 [27] Zhiqi Lin, Youshan Miao, Quanlu Zhang, Fan Yang, Yi Zhu, Cheng Li, Saeed Maleki, Xu Cao, Ning Shang, Yilei Yang, Weijiang Xu, Mao Yang, Lintao Zhang, and Lidong Zhou. 2024. nnScaler: Constraint-Guided Parallelization Plan Generation for Deep Learning Training. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). 347–363. [28] Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R. Devanur, Gregory R. Ganger, Phillip B. Gibbons, and Matei Zaharia. 2019. PipeDream: generalized pipeline parallelism for DNN training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (Huntsville, Ontario, Canada) (SOSP ’19). Association for Computing Machinery, New York, NY, USA, 1–15. doi:10.1145/3341301.3359646 [29] Deepak Narayanan, Amar Phanishayee, Kaiyu Shi, Xie Chen, and Matei Zaharia. 2021. Memory-Efficient Pipeline-Parallel DNN Training. arXiv:2006.09503 [cs.LG] https://arxiv.org/abs/2006.09503 [30] Deepak Narayanan, Mohammad Shoeybi, Jared Casper, et al. 2021. Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM. arXiv:2104.04473 [cs.CL] https://arxiv.org/abs/2104. 04473 [31] NVIDIA. 2025. NCCL (NVIDIA Collective Communications Library). https://github.com/NVIDIA/nccl. [32] NVIDIA Corporation. 2025. NVIDIA Collective Communications Library (NCCL) Documentation. https://docs.nvidia.com/deeplearning/ nccl/user-guide/docs/ Accessed: 2025-01-28. [33] Hyungjun Oh, Junyeol Lee, Hyeongju Kim, and Jiwon Seo. 2022. Outof-order backprop: an effective scheduling technique for deep learning. In Proceedings of the Seventeenth European Conference on Computer Systems (Rennes, France) (EuroSys ’22). Association for Computing Machinery, New York, NY, USA, 435–452. doi:10.1145/3492321.3519563 [34] Jay H. Park, Gyeongchan Yun, Chang M. Yi, Nguyen T. Nguyen, Seungmin Lee, Jaesik Choi, Sam H. Noh, and Young ri Choi. 2020. HetPipe: Enabling Large DNN Training on (Whimpy) Heterogeneous GPU Clusters through Integration of Pipelined Model Parallelism and Data Parallelism. arXiv:2005.14038 [cs.DC] https://arxiv.org/abs/2005.14038 [35] Yanghua Peng, Yibo Zhu, Yangrui Chen, Yixin Bao, Bairen Yi, Chang Lan, Chuan Wu, and Chuanxiong Guo. 2019. A generic communication scheduler for distributed DNN training acceleration. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (Huntsville, Ontario, Canada) (SOSP ’19). Association for Computing Machinery, New York, NY, USA, 16–29. doi:10.1145/3341301.3359642 [36] Shiva Kumar Pentyala, Zhichao Wang, Bin Bi, Kiran Ramnath, XiangBo Mao, Regunathan Radhakrishnan, Sitaram Asur, Na, and Cheng. 2024. PAFT: A Parallel Training Paradigm for Effective LLM FineTuning. arXiv:2406.17923 [cs.CL] https://arxiv.org/abs/2406.17923

White, Navyata Bawa, Nayan Singhal, Nick Egebo, Nicolas Usunier, Nikhil Mehta, Nikolay Pavlovich Laptev, Ning Dong, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub, Raghotham Murthy, Raghu Nayani, Rahul Mitra, Rangaprabhu Parthasarathy, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang, Russ Howes, Ruty Rinott, Sachin Mehta, Sachin Siby, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Mahajan, Saurabh Verma, Seiji Yamamoto, Sharadh Ramaswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng, Shenghao Lin, Shengxin Cindy Zha, Shishir Patil, Shiva Shankar, Shuqiang Zhang, Shuqiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyigbe, Soumith Chintala, Stephanie Max, Stephen Chen, Steve Kehoe, Steve Satterfield, Sudarshan Govindaprasad, Sumit Gupta, Summer Deng, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Koehler, Thomas Robinson, Tianhe Li, Tianjun Zhang, Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vlad Ionescu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenchen Wang, Wenwen Jiang, Wes Bouaziz, Will Constable, Xiaocheng Tang, Xiaojian Wu, Xiaolan Wang, Xilun Wu, Xinbo Gao, Yaniv Kleinman, Yanjun Chen, Ye Hu, Ye Jia, Ye Qi, Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang, Yu Zhao, Yuchen Hao, Yundi Qian, Yunlu Li, Yuzi He, Zach Rait, Zachary DeVito, Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, Zhiwei Zhao, and Zhiyu Ma. 2024. The Llama 3 Herd of Models. arXiv:2407.21783 [cs.AI] https://arxiv.org/abs/2407.21783 [15] Jihu Guo, Tenghui Ma, Wei Gao, Peng Sun, Jiaxing Li, Xun Chen, Yuyang Jin, and Dahua Lin. 2025. AdaPtis: Reducing Pipeline Bubbles with Adaptive Pipeline Parallelism on Heterogeneous Models. arXiv:2509.23722 [cs.DC] https://arxiv.org/abs/2509.23722 [16] Ryubu Hosoki, Toshio Endo, Takahiro Hirofuchi, and Tsutomu Ikegami. 2024. AshPipe: Asynchronous Hybrid Pipeline Parallel for DNN Training. In Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region (Nagoya, Japan) (HPCAsia ’24). Association for Computing Machinery, New York, NY, USA, 117–126. doi:10.1145/3635035.3635045 [17] Jun Huang, Zhen Zhang, Shuai Zheng, Feng Qin, and Yida Wang. 2024. DISTMM: Accelerating Distributed Multimodal Model Training. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24). USENIX Association, Santa Clara, CA, 1157–1171. https: //www.usenix.org/conference/nsdi24/presentation/huang [18] Yanping Huang, Youlong Cheng, Ankur Bapna, et al. 2019. GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism. arXiv:1811.06965 [cs.CV] https://arxiv.org/abs/1811.06965 [19] Insu Jang, Runyu Lu, Nikhil Bansal, Ang Chen, and Mosharaf Chowdhury. 2025. Efficient Distributed MLLM Training with Cornstarch. arXiv:2503.11367 [cs.DC] https://arxiv.org/abs/2503.11367 [20] Byungsoo Jeon, Mengdi Wu, Shiyi Cao, Sunghyun Kim, Sunghyun Park, Neeraj Aggarwal, Colin Unger, Daiyaan Arfeen, Peiyuan Liao, Xupeng Miao, Mohammad Alizadeh, Gregory R. Ganger, Tianqi Chen, and Zhihao Jia. 2025. GraphPipe: Improving Performance and Scalability of DNN Training with Graph Pipeline Parallelism. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 (Rotterdam, Netherlands) (ASPLOS ’25). Association for Computing Machinery, New York, NY, USA, 557–571. doi:10.1145/3669940.3707220 [21] Lijuan Jiang, Xingjian Qian, Zhenxiang Ma, et al. 2025. A Flexible Programmable Pipeline Parallelism Framework for Efficient DNN Training. arXiv:2510.05112 [cs.DC] https://arxiv.org/abs/2510.05112

[37] Penghui Qi, Xinyi Wan, Guangxing Huang, and Min Lin. 2023. Zero Bubble Pipeline Parallelism. arXiv:2401.10241 [cs.DC] https://arxiv. org/abs/2401.10241 [38] Aurick Qiao, Sang Keun Choe, Suhas Jayaram Subramanya, Willie Neiswanger, Qirong Ho, Hao Zhang, Gregory R. Ganger, and Eric P. Xing. 2021. Pollux: Co-adaptive Cluster Scheduling for GoodputOptimized Deep Learning. arXiv:2008.12260 [cs.DC] https://arxiv.org/ abs/2008.12260 [39] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021. Learning Transferable Visual Models From Natural Language Supervision. arXiv:2103.00020 [cs.CV] https://arxiv.org/abs/2103.00020 [40] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. 2020. ZeRO: Memory Optimizations Toward Training Trillion Parameter Models. arXiv:1910.02054 [cs.LG] https://arxiv.org/abs/1910.02054 [41] Isabelly Rocha, Nathaniel Morris, Lydia Y. Chen, Pascal Felber, Robert Birke, and Valerio Schiavoni. 2020. PipeTune: Pipeline Parallelism of Hyper and System Parameters Tuning for Deep Learning Clusters. In Middleware ’20: 21st International Middleware Conference, Delft, The Netherlands, December 7-11, 2020, Dilma Da Silva and Rüdiger Kapitza (Eds.). ACM, 89–104. doi:10.1145/3423211.3425692 [42] Alexander Sergeev and Mike Del Balso. 2018. Horovod: fast and easy distributed deep learning in TensorFlow. arXiv:1802.05799 [cs.LG] https://arxiv.org/abs/1802.05799 [43] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. 2020. Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism. arXiv:1909.08053 [cs.CL] https://arxiv.org/abs/1909.08053 [44] Ao Sun, Weilin Zhao, Xu Han, Cheng Yang, Xinrong Zhang, Zhiyuan Liu, Chuan Shi, and Maosong Sun. 2024. Seq1F1B: Efficient SequenceLevel Pipeline Parallelism for Large Language Model Training. arXiv:2406.03488 [cs.DC] https://arxiv.org/abs/2406.03488 [45] Sahil Tyagi and Prateek Sharma. 2020. Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching. In 2020 IEEE International Conference on Autonomic Computing and Self-Organizing Systems (ACSOS). IEEE, Washington, DC, USA, 188–194. doi:10.1109/ acsos49614.2020.00041 [46] Colin Unger, Zhihao Jia, Wei Wu, Sina Lin, Mandeep Baines, Carlos Efrain Quintero Narvaez, Vinay Ramakrishnaiah, Nirmal Prajapati, Pat McCormick, Jamaludin Mohd-Yusof, Xi Luo, Dheevatsa Mudigere, Jongsoo Park, Misha Smelyanskiy, and Alex Aiken. 2022. Unity: Accelerating DNN Training Through Joint Optimization of Algebraic Transformations and Parallelization. In Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’22). Usenix Assoc, Carlsbad, CA, USA, 455–469. [47] Huizheng Wang, Zichuan Wang, Hongbin Wang, Jingxiang Hou, Taiquan Wei, Chao Li, Yang Hu, and Shouyi Yin. 2025. WATOS: Efficient LLM Training Strategies and Architecture Co-exploration for Waferscale Chip. arXiv:2512.12279 [eess.SP] https://arxiv.org/abs/2512. 12279 [48] Yujie Wang, Shenhan Zhu, Fangcheng Fu, Xupeng Miao, Jie Zhang, Juan Zhu, Fan Hong, Yong Li, and Bin Cui. 2025. Spindle: Efficient Distributed Training of Multi-Task Large Models via Wavefront Scheduling. arXiv:2409.03365 [cs.DC] https://arxiv.org/abs/2409.03365 [49] Zerui Wang, Qinghao Hu, Ana Klimovic, Tianwei Zhang, Yonggang Wen, Peng Sun, and Dahua Lin. 2025. Semantic-Aware Scheduling for GPU Clusters with Large Language Models. arXiv:2510.03334 [cs.LG] https://arxiv.org/abs/2510.03334 [50] Zhenliang Xue, Hanpeng Hu, Xing Chen, Yimin Jiang, Yixin Song, Zeyu Mi, Yibo Zhu, Daxin Jiang, Yubin Xia, and Haibo Chen. 2025. PipeWeaver: Addressing Data Dynamicity in Large Multimodal Model Training with Dynamic Interleaved Pipeline. arXiv:2504.14145 [cs.DC] https://arxiv.org/abs/2504.14145

[51] Zhenliang Xue, Hanpeng Hu, Xing Chen, Yimin Jiang, Yixin Song, Zeyu Mi, Yibo Zhu, Daxin Jiang, Yubin Xia, and Haibo Chen. 2026. DIP: Efficient Large Multimodal Model Training with Dynamic Interleaved Pipeline. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. ACM, Rotterdam, Netherlands, 618–632. doi:10.1145/3779212.3790154 [52] An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. 2025. Qwen3 Technical Report. arXiv:2505.09388 [cs.CL] https: //arxiv.org/abs/2505.09388 [53] Bowen Yang, Jian Zhang, Jonathan Li, Christopher Ré, Christopher R. Aberger, and Christopher De Sa. 2020. PipeMare: Asynchronous Pipeline Parallel DNN Training. arXiv:1910.05124 [cs.DC] https: //arxiv.org/abs/1910.05124 [54] Xing Zhao, Aijun An, Junfeng Liu, and Bao Xin Chen. 2019. Dynamic Stale Synchronous Parallel Distributed Training for Deep Learning. arXiv:1908.11848 [cs.DC] https://arxiv.org/abs/1908.11848 [55] Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P. Xing, Joseph E. Gonzalez, and Ion Stoica. 2022. Alpa: Automating Inter- and Intra-Operator Parallelism for Distributed Deep Learning. arXiv:2201.12023 [cs.LG] https://arxiv.org/abs/2201.12023 [56] Guangyao Zhou, Wenhong Tian, Rajkumar Buyya, and Kui Wu. 2025. UMPIPE: Unequal Microbatches-Based Pipeline Parallelism for Deep Neural Network Training . IEEE Transactions on Parallel & Distributed Systems 36, 02 (Feb. 2025), 293–307. doi:10.1109/TPDS.2024.3515804

Backward-Forward Hint Algorithm

Algorithm 1 Backward-forward event-driven execution loop at stage 𝑠

This section gives the detailed instantiation of the backwardforward (BF) hint used by RRFP. The BF hint is a deterministic priority rule over currently ready work. It does not prescribe a fixed global execution order. Instead, it ranks only the microbatches that are already present in the local ready buffers. The BF hint defines the priority order used by the arbitration layer as follows.

𝑓

1: State: forward-ready buffer L𝑟 , backward-ready buffer 𝑓

L𝑟𝑏 , forward-finished buffer L 𝑓 𝑖𝑛 , backward-finished buffer L𝑏𝑓 𝑖𝑛 2: Hint order: Π: forward uses smaller model-chunk index first; backward uses larger model-chunk index first; ties use smaller microbatch index 3: Target: 𝑁 target completed executions 4: 𝑛 done ← 0 5: while 𝑛 done < 𝑁 target do ⊲ Each arbitration round first checks backward-ready work. 6: if L𝑟𝑏 ≠ ∅ then 7: 𝑚𝑏★ ← NextByPriority(L𝑟𝑏 , Π) 8: Execute(𝑚𝑏★) 9: 𝑛 done ← 𝑛 done + 1 10: L𝑏𝑓 𝑖𝑛 ← L𝑏𝑓 𝑖𝑛 ∪ {𝑚𝑏★ } 11: end if ⊲ The same round then checks forward-ready work if more work is needed. 𝑓 12: if L𝑟 ≠ ∅ and 𝑛 done < 𝑁 target then 𝑓 13: 𝑚★𝑓 ← NextByPriority(L𝑟 , Π) 14: Execute(𝑚★𝑓 ) 15: 𝑛 done ← 𝑛 done + 1 𝑓 𝑓 16: L 𝑓 𝑖𝑛 ← L 𝑓 𝑖𝑛 ∪ {𝑚★𝑓 } 17: end if 18: end while

• Direction-level priority. Arbitration proceeds in repeated rounds. In each round, the runtime first checks whether the backward-ready buffer L𝑟𝑏 contains executable work. If so, it selects and executes one backward microbatch. The runtime then checks whether 𝑓 the forward-ready buffer L𝑟 contains executable work. If so, it selects and executes one forward microbatch. Thus, when both backward and forward work are ready, the BF hint follows a 1F1B-like order by giving backward work the first opportunity in each round and then considering forward work. When only one direction has ready work, the runtime simply executes the ready direction rather than waiting for work from the other direction. • Within-direction priority. When multiple ready microbatches exist in the same direction, the BF hint prioritizes the microbatch that corresponds to earlier progress within the stage. For forward-ready work, this means choosing the smaller model-chunk index, and for backward-ready work, this means choosing the larger model-chunk index. This rule is useful for interleaved pipeline schedules, where each physical stage may own multiple model chunks. Prioritizing earlier-progress model chunks helps them finish earlier and enter subsequent collective operations, such as gradient reduction, earlier. • Tie breaking. If multiple ready microbatches have the same direction and the same model-chunk index, the BF hint breaks ties by choosing the smaller microbatch index. This makes arbitration deterministic and preserves a simple in-order preference within each model chunk.

into the corresponding finished buffers for downstream communication. In the algorithm, NextByPriority(·, Π) implements the within-direction priority rule described above: for forward-ready work, it selects the ready microbatch with the smallest model-chunk index, and for backward-ready work, it selects the ready microbatch with the largest model-chunk index. Remaining ties are broken by the smallest microbatch index.

Importantly, the BF hint never blocks on unavailable work: it does not force the runtime to wait for a higher-priority but unready microbatch. If the backward-ready buffer is empty in a round, the runtime immediately considers forward-ready work. Similarly, within a direction, the hint only ranks microbatches that are already present in the corresponding ready buffer. Algorithm 1 summarizes the event-driven execution loop at stage 𝑠 using this BF hint. Ready microbatches are inserted into the ready buffers by the communication runtime, and the arbitration layer repeatedly selects executable microbatches from these buffers. Completed microbatches are inserted

Proofs and Bottleneck Statistics

This section provides the detailed proof of Theorem 6.1 and Corollary 6.2 in the main paper, together with bottleneck statistics showing how often the last-stage-dominance condition holds in our workloads. We analyze RRFP under the same simplified setting as in the main paper: a noninterleaved pipeline, computation-only latency, and no tensorparallel coordination or implementation overhead. Communication time is ignored, while inter-stage pipeline dependencies are still respected. 17

B.1

Preliminaries

Now consider 𝑖 > 0 and 𝑗 > 0, and assume the claim holds for all pairs (𝑖 ′, 𝑗 ′ ) with 𝑖 ′ + 𝑗 ′ < 𝑖 + 𝑗. Let

Let 𝐹𝑖𝑗 denote the forward computation time of microbatch

−1 𝑅𝑖,𝑗 = max{𝑒 𝑖𝑓−1,𝑗 , 𝑒 𝑖,𝑗 } 𝑓

𝑗 at pipeline stage 𝑖, where 𝑖 ∈ {0, 1, . . . , 𝑁 − 1} and 𝑗 ∈ {0, 1, . . . , 𝑀 − 1}. We define 𝐵𝑖𝑗 analogously for backward computation time. For each microbatch 𝑗, define 𝑗 𝐹 max = max 𝐹𝑖𝑗 ,

be the time at which the inter-stage and local forward predecessors of task (𝑖, 𝑗) have both completed under RRFP. If stage 𝑖 is idle at time 𝑅𝑖,𝑗 , then forward task (𝑖, 𝑗) can be dispatched immediately. Otherwise, the only reason it does not start immediately is that stage 𝑖 is executing a backward task that was selected before (𝑖, 𝑗) became ready. Under the BF hint, after this backward task completes, the runtime probes forward-ready work again. Since (𝑖, 𝑗) is then ready, no additional backward task can be inserted before (𝑖, 𝑗). Therefore, after both predecessors are complete, forward task (𝑖, 𝑗) can be delayed by at most one additional backward task. Let Δ𝑖,𝑗 ≥ 0 denote the execution time of this possible additional backward task, and set Δ𝑖,𝑗 = 0 if no such task exists. Then according to the above deduction

𝑗 𝐵 max = max 𝐵𝑖𝑗 .

0≤𝑖 ≤𝑁 −1

We also define the last-stage computation times 𝑗 𝐹 last = 𝐹 𝑁𝑗 −1,

𝑗 𝐵 last = 𝐵 𝑁𝑗 −1 .

Let C denote the iteration makespan. Let F be the completion time of the forward-only pipeline, where all forward work is initially ready at stage 0 and inter-stage forward dependencies are respected. Let B be the completion time of the backward-only pipeline, where all backward work is initially ready at stage 𝑁 − 1 and inter-stage backward dependencies are respected. B.2

−1 𝑠 𝑖,𝑗 ≤ max{𝑒 𝑖𝑓−1,𝑗 , 𝑒 𝑖,𝑗 } + Δ𝑖,𝑗 , 𝑓 𝑓

Proof of Theorem 6.1

We first bound the delay that backward work can introduce to forward execution.

and combining with the fact that −1 = max{𝑒˜𝑖𝑓−1,𝑗 , 𝑒˜𝑖,𝑗 }, 𝑠˜𝑖,𝑗 𝑓 𝑓

Lemma B.1. Let 𝑠 𝑖,𝑗 be the start time of the forward task 𝑓

we obtain

of microbatch 𝑗 at stage 𝑖 under RRFP, and let 𝑠˜𝑖,𝑗 be the cor𝑓 responding start time in the forward-only schedule. Let 𝐾𝑖,𝑗 denote the set of backward microbatches executed on stage 𝑖 before forward task (𝑖, 𝑗) starts under RRFP. Then ∑︁ 𝑖,𝑗 ˜ 𝑠 𝑖,𝑗 ≤ 𝑠 + 𝐵𝑘max . 𝑓 𝑓

−1 −1 𝑠 𝑖,𝑗 − 𝑠˜𝑖,𝑗 ≤ max{𝑒 𝑖𝑓−1,𝑗 , 𝑒 𝑖,𝑗 } − max{𝑒˜𝑖𝑓−1,𝑗 , 𝑒˜𝑖,𝑗 } + Δ𝑖,𝑗 𝑓 𝑓 𝑓 𝑓 −1 −1 ≤ max{𝑒 𝑖𝑓−1,𝑗 − 𝑒˜𝑖𝑓−1,𝑗 , 𝑒 𝑖,𝑗 − 𝑒˜𝑖,𝑗 } + Δ𝑖,𝑗 𝑓 𝑓 −1 −1 = max{𝑠 𝑖𝑓−1,𝑗 − 𝑠˜𝑖𝑓−1,𝑗 , 𝑠 𝑖,𝑗 − 𝑠˜𝑖,𝑗 } + Δ𝑖,𝑗 , 𝑓 𝑓

using the fact that

𝑘 ∈𝐾𝑖,𝑗

𝑒 𝑖,𝑗 − 𝑠 𝑖,𝑗 = 𝑒˜𝑖,𝑗 − 𝑠˜𝑖,𝑗 = 𝐹𝑖𝑗 , ∀𝑖, 𝑗 𝑓 𝑓 𝑓 𝑓

Proof. Define 𝐷 𝑖,𝑗 = 𝑠 𝑖,𝑗 − 𝑠˜𝑖,𝑗 . 𝑓 𝑓 𝑓

and that 𝑎 + 𝑏 − 𝑐 − 𝑑 |𝑎 − 𝑏 | − |𝑐 − 𝑑 | + 2 2 𝑎 − 𝑐 + 𝑏 − 𝑑 |𝑎 − 𝑏 − (𝑐 − 𝑑)| ≤ + 2 2 = max{𝑎 − 𝑐, 𝑏 − 𝑑 }

max{𝑎, 𝑏} − max{𝑐, 𝑑 } =

We prove 𝐷 𝑖,𝑗 ≤ 𝑓

∑︁

𝐵𝑘max

𝑘 ∈𝐾𝑖,𝑗

by induction on 𝑖 + 𝑗. In the forward-only schedule,

given that 𝑎 ≥ 𝑐, 𝑏 ≥ 𝑑. Therefore we arrive at

  0, 𝑖 = 0, 𝑗 = 0,    𝑖 −1,0  ˜ 𝑒 , 𝑖 > 0, 𝑗 = 0,   𝑓 𝑠˜𝑖,𝑗 = 0,𝑗 𝑒˜𝑖,𝑗 = 𝑠˜𝑖,𝑗 +𝐹𝑖𝑗 . −1 𝑓 𝑓 𝑓  ˜ 𝑒 , 𝑖 = 0, 𝑗 > 0,  𝑓     max{𝑒˜𝑖 −1,𝑗 , 𝑒˜𝑖,𝑗 −1 }, 𝑖 > 0, 𝑗 > 0, 𝑓 𝑓  If 𝑗 = 0, no backward task can execute before the first forward microbatch reaches any stage. Hence 𝐾𝑖,0 = ∅ and 𝐷 𝑖,0 = 0. 𝑓 If 𝑖 = 0, stage 0 has no upstream forward dependency. Therefore the delay of forward task (0, 𝑗) under RRFP is exactly the local backward work executed before it on stage 0, which is at most ∑︁ 𝐵𝑘max .

−1 𝐷 𝑖,𝑗 ≤ max{𝐷 𝑖𝑓−1,𝑗 , 𝐷 𝑖,𝑗 } + Δ𝑖,𝑗 . 𝑓 𝑓

Equivalently, −1 𝐷 𝑖,𝑗 ≤ max{𝐷 𝑖𝑓−1,𝑗 + Δ𝑖,𝑗 , 𝐷 𝑖,𝑗 + Δ𝑖,𝑗 }. 𝑓 𝑓

By the induction hypothesis, ∑︁ 𝐷 𝑖𝑓−1,𝑗 ≤ 𝐵𝑘max, 𝑘 ∈𝐾𝑖 −1,𝑗

−1 𝐷 𝑖,𝑗 ≤ 𝑓

∑︁

𝐵𝑘max .

𝑘 ∈𝐾𝑖,𝑗 −1

It remains to account for Δ𝑖,𝑗 . If Δ𝑖,𝑗 > 0, let 𝑞 be the backward microbatch executed on stage 𝑖 after both forward predecessors of (𝑖, 𝑗) have completed but before (𝑖, 𝑗) starts. This microbatch is not contained in 𝐾𝑖,𝑗 −1 , because it is executed after forward task (𝑖, 𝑗 − 1) has completed, whereas

𝑘 ∈𝐾0,𝑗 18

For backward execution, the base stage is stage 𝑁 − 1. In the backward-only schedule, all backward work is initially ready at stage 𝑁 − 1. However, backward work at stage 𝑁 − 1 can be delayed by forward-side progress needed to make backward tasks ready, including possible idle gaps after a backward task while waiting for the next forward task. We capture this base-case difference using an augmented forward-side delay term 𝐹ˆ𝑖𝑘 . For stages 𝑖 < 𝑁 − 1, let 𝐹ˆ𝑖𝑘 = 𝐹𝑖𝑘 . For the last stage, we let 𝐹ˆ𝑁𝑘 −1 = 𝑒 𝑓𝑁 −1,𝑘 − 𝑒𝑏𝑁 −1,𝑘 −1 if 𝑘 > 0 which is no less than 𝑒 𝑁 −1,𝑘 − 𝑠 𝑁 −1,𝑘 = 𝐹 𝑘 , and 𝐹ˆ0 =

𝐾𝑖,𝑗 −1 only contains backward microbatches executed before (𝑖, 𝑗 − 1) starts. It is also not contained in 𝐾𝑖 −1,𝑗 : if 𝑞 ∈ 𝐾𝑖 −1,𝑗 , then the backward task of 𝑞 on stage 𝑖 − 1 would have executed before forward task (𝑖 − 1, 𝑗) starts. By the backward dependency, the corresponding backward task on stage 𝑖 must have completed even earlier, contradicting the fact that this stage-𝑖 backward task is still the extra work executed after both predecessors of (𝑖, 𝑗) are ready. Thus 𝑞 is not counted in either predecessor-delay term. We next relate the predecessor-delay sets to 𝐾𝑖,𝑗 . Clearly, 𝐾𝑖,𝑗 −1 ⊆ 𝐾𝑖,𝑗 , because any backward microbatch executed on stage 𝑖 before forward task (𝑖, 𝑗 − 1) starts is also executed before the later forward task (𝑖, 𝑗) starts. For 𝐾𝑖 −1,𝑗 , the inclusion also holds by the direction of backward propagation. If 𝑘 ∈ 𝐾𝑖 −1,𝑗 , then the backward task of 𝑘 on stage 𝑖 − 1 executes before forward task (𝑖 − 1, 𝑗) starts. Since backward execution at stage 𝑖 − 1 depends on the corresponding backward execution at stage 𝑖, the backward task of 𝑘 on stage 𝑖 must have completed even earlier. Because forward task (𝑖, 𝑗) cannot start before forward task (𝑖 − 1, 𝑗) completes, this stage-𝑖 backward task is executed before (𝑖, 𝑗) starts. Hence 𝑘 ∈ 𝐾𝑖,𝑗 . Finally, if such an extra backward task 𝑞 exists, then by definition it is executed on stage 𝑖 before forward task (𝑖, 𝑗) starts, so 𝑞 ∈ 𝐾𝑖,𝑗 and

𝑓

𝑁 −1

𝑓

𝑁 −1

𝐹 𝑁0 −1 . Further define 𝑘 𝐹ˆmax = max 𝐹ˆ𝑖𝑘 ,

𝑘 𝐹ˆlast = 𝐹ˆ𝑁𝑘 −1 .

𝑖

Lemma B.2. Set the time origin to the moment when stage 𝑁 − 1 starts the backward computation of microbatch 0, so 𝑠𝑏𝑁 −1,0 = 0. Let 𝑠𝑏𝑖,𝑗 be the start time of the backward task of microbatch 𝑗 at stage 𝑖 under RRFP, and let 𝑠˜𝑏𝑖,𝑗 be the corresponding start time in the backward-only schedule, with the same time origin 𝑠˜𝑏𝑁 −1,0 = 0. Let 𝐽𝑖,𝑗 denote the set of forward microbatches 𝑘 ≥ 1 whose forward task is incurred on stage 𝑖 before backward task (𝑖, 𝑗) starts under RRFP. Then 𝐽𝑁 −1,0 = ∅, and ∑︁ 𝑘 𝑠𝑏𝑖,𝑗 ≤ 𝑠˜𝑏𝑖,𝑗 + 𝐹ˆmax . 𝑘 ∈ 𝐽𝑖,𝑗

Δ𝑖,𝑗 ≤ 𝐵 max . 𝑞

Proof. The proof follows similarly to that of Lemma B.1. Define 𝐷𝑏𝑖,𝑗 = 𝑠𝑏𝑖,𝑗 − 𝑠˜𝑏𝑖,𝑗 . We prove ∑︁ 𝑘 𝐷𝑏𝑖,𝑗 ≤ 𝐹ˆmax

Therefore, the predecessor-delay terms are accounted for by elements of 𝐾𝑖,𝑗 , and the only additional delay Δ𝑖,𝑗 is accounted for by the new element 𝑞 ∈ 𝐾𝑖,𝑗 . Since 𝑞 ∉ 𝐾𝑖 −1,𝑗 ∪ 𝐾𝑖,𝑗 −1 , there is no double counting. Hence,    ∑︁ 

≤ max 𝐷 𝑖,𝑗 𝑓 

𝑘 ∈𝐾𝑖 −1,𝑗  This proves the lemma.

 

∑︁

𝐵𝑘max,

𝑘 ∈𝐾𝑖,𝑗 −1

 𝑞  𝐵𝑘max +𝐵 max ≤   

∑︁

𝑘 ∈ 𝐽𝑖,𝑗

𝐵𝑘max .

by induction on (𝑁 − 1 − 𝑖) + 𝑗. In the backward-only schedule,

𝑘 ∈𝐾𝑖,𝑗

□

𝑖 = 𝑁 − 1, 𝑗 = 0, 𝑖 < 𝑁 − 1, 𝑗 = 0, 𝑖,𝑗 𝑠˜𝑏𝑖,𝑗 = 𝑏𝑁 −1,𝑗 −1 𝑒˜𝑏 = 𝑠˜𝑏𝑖,𝑗 +𝐵𝑖𝑗 .  ˜ 𝑒 , 𝑖 = 𝑁 − 1, 𝑗 > 0,  𝑏    max{𝑒˜𝑖+1,𝑗 , 𝑒˜𝑖,𝑗 −1 }, 𝑖 < 𝑁 − 1, 𝑗 > 0,  𝑏 𝑏  0,     𝑒˜𝑖+1,0, 

Applying Lemma B.1 to stage 𝑁 − 1 and microbatch 𝑀 − 1 gives 𝑀 −2 ∑︁ 𝑗 𝑠 𝑓𝑁 −1,𝑀 −1 ≤ 𝑠˜𝑓𝑁 −1,𝑀 −1 + 𝐵 max .

We first consider the boundary stage 𝑖 = 𝑁 − 1. Since stage 𝑁 − 1 has no downstream backward dependency, the delay of backward task (𝑁 − 1, 𝑗) under RRFP comes only from the augmented local forward work executed before it on stage 𝑁 − 1. By the definition of 𝐽𝑁 −1,𝑗 , this delay is exactly ∑︁ 𝑘 𝐹ˆmax .

𝑗=0

We let Clast denote the time from the start of the iteration until pipeline stage 𝑁 − 1 completes the backward computation of microbatch 𝑀 − 1. Moreover let G = C − Clast be the cooldown bubble. Since 𝑒˜𝑓𝑁 −1,𝑀 −1 = F , we obtain 𝐶 last ≤ F +

𝑀 −2 ∑︁

𝑗 𝑀 −1 𝐵 max + 𝐵 last .

𝑘 ∈ 𝐽𝑁 −1,𝑗

Thus the induction hypothesis holds for 𝑖 = 𝑁 − 1. Next consider the boundary microbatch 𝑗 = 0 and 𝑖 < 𝑁 − 1. In the backward-only schedule, task (𝑖, 0) can start once backward task (𝑖 + 1, 0) finishes. Under RRFP, after 𝑒𝑏𝑖+1,0 , if stage 𝑖 is free, task (𝑖, 0) is dispatched immediately. Otherwise, by the BF hint, task (𝑖, 0) can be delayed by at

𝑗=0

We next bound the remaining backward cooldown G. The backward direction is not exactly symmetric to Lemma B.1, because the induction base changes. For forward execution, the base stage is stage 0, where delayed forward starts can be charged directly to backward work inserted before them. 19

Proof. Set the time origin to the moment when stage 𝑁 − 1 starts the backward computation of microbatch 0. The remaining backward cooldown is determined by the completion time of the last backward task at stage 0, namely 𝑒𝑏0,𝑀 −1 , after subtracting the portion already accounted for on the stage 𝑁 − 1 timeline. By Lemma B.2,

most one forward microbatch at stage 𝑖. Let this additional delay be Δ𝑖,0 . Then 𝑠𝑏𝑖,0 ≤ 𝑒𝑏𝑖+1,0 + Δ𝑖,0 . Subtracting 𝑠˜𝑏𝑖,0 = 𝑒˜𝑏𝑖+1,0 gives 𝐷𝑏𝑖,0 ≤ 𝐷𝑏𝑖+1,0 + Δ𝑖,0 . By the induction hypothesis, ∑︁

𝐷𝑏𝑖+1,0 ≤

𝑠𝑏0,𝑀 −1 − 𝑠˜𝑏0,𝑀 −1 ≤

𝑘 𝐹ˆmax .

∑︁

𝑘 𝐹ˆmax ≤

𝑘 ∈ 𝐽0,𝑀 −1

𝑀 −1 ∑︁

𝑘 𝐹ˆmax .

𝑘=1

𝑘 ∈ 𝐽𝑖+1,0

Since both executions use the same local backward time for task (0, 𝑀 − 1), we have

Moreover, the microbatch contributing Δ𝑖,0 is not included in 𝐽𝑖+1,0 , but both 𝐽𝑖+1,0 and this block are contained in 𝐽𝑖,0 . Therefore, ∑︁ ∑︁ 𝑘 𝑘 𝐷𝑏𝑖,0 ≤ 𝐹ˆmax + Δ𝑖,0 ≤ 𝐹ˆmax . 𝑘 ∈ 𝐽𝑖+1,0

𝑒𝑏0,𝑀 −1 − 𝑒˜𝑏0,𝑀 −1 = 𝑠𝑏0,𝑀 −1 − 𝑠˜𝑏0,𝑀 −1 . Moreover, in the backward-only schedule, 𝑒˜𝑏0,𝑀 −1 = B.

𝑘 ∈ 𝐽𝑖,0

This proves the induction hypothesis for all 𝑗 = 0. Finally, consider the general case 𝑖 < 𝑁 − 1 and 𝑗 > 0. Again, we have

Therefore, 𝑒𝑏0,𝑀 −1 ≤ B +

𝑠𝑏𝑖,𝑗 ≤ max{𝑒𝑏𝑖+1,𝑗 , 𝑒𝑏𝑖,𝑗 −1 } + Δ𝑖,𝑗 ,

𝑀 −1 ∑︁

𝑘 𝐹ˆmax .

𝑘=1

The portion already accounted for on the stage 𝑁 − 1 timeline consists of all last-stage backward work and the augmented last-stage forward-side terms:

where Δ𝑖,𝑗 is the additional delay caused by at most one forward microbatch selected before task (𝑖, 𝑗) under the BF hint. Subtracting

𝑀 −1 ∑︁

𝑠˜𝑏𝑖,𝑗 = max{𝑒˜𝑏𝑖+1,𝑗 , 𝑒˜𝑏𝑖,𝑗 −1 }

𝑗 𝐵 last +

𝑗=0

𝑀 −1 ∑︁

𝑘 𝐹ˆlast .

𝑘=1

gives 𝐷𝑏𝑖,𝑗 ≤ max{𝐷𝑏𝑖+1,𝑗 , 𝐷𝑏𝑖,𝑗 −1 } + Δ𝑖,𝑗 . By the induction hypothesis, ∑︁ 𝑘 𝐷𝑏𝑖+1,𝑗 ≤ 𝐹ˆmax ,

Thus, G≤B+

𝐷𝑏𝑖,𝑗 −1 ≤

𝑘 ∈ 𝐽𝑖+1,𝑗

∑︁

𝑘 𝐹ˆmax .

   ∑︁ 

𝑘 ∈ 𝐽𝑖,𝑗 −1

𝑘 ∈ 𝐽𝑖+1,𝑗 ∑︁  𝑘 ≤ 𝐹ˆmax .

𝑘 𝐹ˆmax ,

𝑘 𝐹ˆmax −

=B+

𝑀 −1 ∑︁

𝑗 𝐵 last −

𝑀 −1 ∑︁

𝑗=0

𝑘=1

Moreover, the forward microbatch contributing Δ𝑖,𝑗 is not contained in either 𝐽𝑖+1,𝑗 or 𝐽𝑖,𝑗 −1 , while 𝐽𝑖+1,𝑗 , 𝐽𝑖,𝑗 −1 , and this block are all contained in 𝐽𝑖,𝑗 . Therefore, 𝐷𝑏𝑖,𝑗 ≤ max 

𝑀 −1 ∑︁

𝑘 𝑘 𝐹ˆmax − 𝐹ˆlast −

𝑘 𝐹ˆlast

𝑘=1 𝑀 −1 ∑︁

𝑗 𝐵 last .

𝑗=0

𝑘=1

Since 𝐹ˆ𝑘 differs from 𝐹 𝑘 only by increasing the last-stage term, 𝑘 𝑘 𝑘 𝑘 𝐹ˆmax − 𝐹ˆlast ≤ 𝐹 max − 𝐹 last .

    𝑘 ˆ 𝐹 max + Δ𝑖,𝑗   𝑘 ∈ 𝐽𝑖,𝑗 −1  ∑︁

Substituting this inequality gives G≤B+

𝑘 ∈ 𝐽𝑖,𝑗

𝑀 −1 ∑︁

𝑀 −1 ∑︁ 𝑗 𝑘 𝑘 𝐹 max − 𝐹 last − 𝐵 last ,

𝑘=1

𝑗=0

This completes the induction and proves the lemma. which proves the lemma.

□

We now restate and prove Theorem 6.1.

Consequently, we arrive at the following lemma.

Theorem 6.1. The iteration makespan C of RRFP under the BF hint arbitration rule satisfies

Lemma B.3. The remaining backward cooldown G is bounded by 𝑀 −1 𝑀 −1 ∑︁ ∑︁ 𝑗 𝑘 𝑘 B+ 𝐹 max − 𝐹 last − 𝐵 last . 𝑘=1

□

C ≤F +B+

𝑗=0 20

𝑀 −1 ∑︁

𝑀 −2 ∑︁ 𝑗 𝑗 𝑗 𝑗 𝐹 max − 𝐹 last + 𝐵 max − 𝐵 last .

𝑗=1

𝑗=0

Proof. The makespan can be decomposed into the time until the last-stage backward cooldown begins and the remaining cooldown: C = 𝐶 last + G. Using the bounds above, C ≤F +B+

=F +B+

𝑀 −1 ∑︁

𝑗 𝑗 𝐹 max − 𝐹 last +

𝑀 −2 ∑︁

𝑗=1

𝑗=0

𝑀 −1 ∑︁

𝑀 −2 ∑︁

𝑗 𝑗 𝐹 max − 𝐹 last +

𝑗=1

𝑗 𝐵 max −

𝑀 −2 ∑︁

Thus, 𝑒˜𝑓𝑁 −1,𝑀 −1 ≤ =

𝑀 −2 ∑︁ 𝑡 =0 𝑀 −1 ∑︁

𝑡 𝑀 −1 𝐹 max + (𝑁 − 1)𝑇max + 𝐹 max

𝑡 𝐹 max + 𝑂 (𝑁𝑇max ).

𝑡 =0

𝑗 𝐵 last

Hence

𝑗=0

F ≤

𝑗 𝑗 𝐵 max − 𝐵 last .

𝑀 −1 ∑︁

𝑗 𝐹 max + 𝑂 (𝑁𝑇max ).

𝑗=0

Applying the same argument to backward gives This proves the theorem. B.3

□ B≤

Proof of Corollary 6.2

𝑀 −1 ∑︁

𝑗 + 𝑂 (𝑁𝑇max ). 𝐵 max

𝑗=0

Define 𝑇max as 𝑇max =

max 0≤ 𝑗 ≤𝑀 −1

which proves the lemma.

𝑗 𝑗 𝐹 max + 𝐵 max ,

□

Let We first record a simple fill/drain bound for the forwardonly and backward-only makespans. 𝑀 −1 ∑︁

𝑗 𝐹 max + 𝑂 (𝑁𝑇max ),

B≤

𝑗=0

𝑀 −1 ∑︁

For any valid offline or online schedule, OPT ≥ 𝐿, because every schedule must execute all forward and backward tasks on the last pipeline stage. Assume that for each microbatch 𝑗, the last stage is the bottleneck with probability at least 1 − 𝑝. Otherwise, assume that the deviation from the last-stage time is bounded by a constant factor 𝜌 ≥ 1:

𝑗 𝐵 max + 𝑂 (𝑁𝑇max ).

𝑗=0

Proof. We prove the forward case. The backward case is analogous. Using the notations 𝑠˜𝑖,𝑗 and 𝑒˜𝑖,𝑗 from above, we 𝑓 𝑓 have −1 𝑠˜𝑖,𝑗 = max{𝑒˜𝑖𝑓−1,𝑗 , 𝑒˜𝑖,𝑗 }, 𝑓 𝑓

𝑗 𝑗 𝐹 max ≤ 𝜌𝐹 last ,

where we ignore non-existing terms at the boundary stages and microbatches. We claim that 𝑗 −1 ∑︁ 𝑖,𝑗 𝑡 𝑠˜𝑓 ≤ 𝐹 max + 𝑖𝑇max . We prove this by induction on 𝑖 + 𝑗. The base case (𝑖, 𝑗) = (0, 0) is immediate. For the induction step, by the induction hypothesis,

where 𝑚𝑙 and 𝑚ℎ are constants. Corollary 6.2. Under the assumptions above, C 𝑁 E ≤ 1 + 2𝑝 (𝜌 − 1) + 𝑂 . OPT 𝑀

−1 −1 𝑒˜𝑖,𝑗 = 𝑠˜𝑖,𝑗 + 𝐹𝑖𝑗 −1 𝑓 𝑓

𝑗 −2 ∑︁ 𝑡 =0 𝑗 −1 ∑︁

𝑗 𝑗 𝐵 max ≤ 𝜌𝐵 last .

and we further assume that the computation time of each microbatch is bounded within [𝑚𝑙 , 𝑚ℎ ]. Hence, 𝐿 𝐿 𝑚ℎ =𝑂 , 𝑇max ≤ 2𝑚ℎ ≤ 𝑀 𝑚𝑙 𝑀

𝑡 =0

≤

𝑗 𝑗 𝐹 last + 𝐵 last .

𝑗=0

Lemma B.4. The single-direction makespans satisfy F ≤

𝑀 −1 ∑︁

𝐿=

𝑗 −1 𝑡 𝐹 max + 𝑖𝑇max + 𝐹 max

Proof. Define the stage-imbalance terms 𝑗 𝑗 Δ 𝑓𝑗 = 𝐹 max − 𝐹 last ,

𝑡 𝐹 max + 𝑖𝑇max,

𝑗 𝑗 Δ𝑏𝑗 = 𝐵 max − 𝐵 last .

By Lemma B.4,

𝑡 =0

and 𝑒˜𝑖𝑓−1,𝑗 = 𝑠˜𝑖𝑓−1,𝑗 + 𝐹𝑖𝑗−1 ≤

𝑗 −1 ∑︁

F +B ≤

𝑗 𝑗 𝐹 max + 𝐵 max + 𝑂 (𝑁𝑇max ).

𝑗=0

𝑗 𝑡 + (𝑖 − 1)𝑇max + 𝐹 max 𝐹 max ≤

𝑡 =0

𝑗 −1 ∑︁

Using 𝑡 + 𝑖𝑇max, 𝐹 max

𝑗 𝑗 𝐹 max = 𝐹 last + Δ 𝑓𝑗 ,

𝑡 =0

𝑗 where the last inequality uses 𝐹 max ≤ 𝑇max . Therefore,

𝑠˜𝑖,𝑗 ≤ 𝑓

𝑀 −1 ∑︁

𝑗 −1 ∑︁

𝑗 𝑗 𝐵 max = 𝐵 last + Δ𝑏𝑗 ,

we obtain F +B ≤𝐿+

𝑡 𝐹 max + 𝑖𝑇max .

𝑡 =0

𝑀 −1 ∑︁ 𝑗=0

(Δ 𝑓𝑗 + Δ𝑏𝑗 ) + 𝑂 (𝑁𝑇max ).

(a) LLM bottleneck distribution

(b) LLM stage latency relative to last stage

1.00

96.8%

1.0

j ) Relative Latency (Fij/Flast

0.98

Bottleneck Ratio

0.8 0.6 0.4 0.2 0.0

Pipeline Stage (c) Multimodal bottleneck distribution

0.6 0.4 0.2

7.2% 4.4% 2.5% 0.0% 0.0% 0.0% 0.0% 1

Pipeline Stage

0.90 0.88

p85 p90 p95

1.15 j ) Relative Latency (Fij/Flast

Bottleneck Ratio

0.8

0.92

0.84

85.9%

0.0

0.94

0.86

2.7% 0.0% 0.1% 0.1% 0.1% 0.1% 0.0% 0

0.96

Pipeline Stage (d) Multimodal stage latency relative to last stage

p85 p90 p95

1.10 1.05 1.00 0.95 0.90 0.85

Pipeline Stage

Figure 6. Detailed bottleneck statistics over 100 iterations. Panels (a) and (c) report the fraction of forward microbatches for which each pipeline stage is the bottleneck. The last stage dominates in both settings, accounting for 96.8% of bottleneck cases in the LLM workload and 85.9% in the multimodal workload. Panels (b) and (d) report p85, p90, and p95 relative forward 𝑗 latency, normalized by the last-stage latency, i.e., 𝐹𝑖𝑗 /𝐹 last . The maximum p95 non-last-stage ratio is 0.84× for LLM and 1.14× for multimodal, supporting the bounded-deviation assumption used in Corollary 6.2. Taking expectation and using OPT ≥ 𝐿 yields C 𝑁𝑇max E ≤ 1 + 2𝑝 (𝜌 − 1) + 𝑂 . OPT 𝐿

Substituting this into Theorem 6.1 gives

C≤𝐿+

𝑀 −1 ∑︁

(Δ 𝑓𝑗 + Δ𝑏𝑗 ) +

𝑗=0

≤𝐿+2

𝑀 −1 ∑︁ 𝑗=1

𝑀 −1 ∑︁

Δ 𝑓𝑗 +

𝑀 −2 ∑︁

Δ𝑏𝑗 + 𝑂 (𝑁𝑇max )

Since 𝑇max = 𝑂 (𝐿/𝑀), the final term is 𝑂 (𝑁 /𝑀). Hence, 𝑁 C ≤ 1 + 2𝑝 (𝜌 − 1) + 𝑂 , E OPT 𝑀

𝑗=0

(Δ 𝑓𝑗 + Δ𝑏𝑗 ) + 𝑂 (𝑁𝑇max ).

𝑗=0

as claimed. Under the last-stage dominance assumption, for each microbatch 𝑗, 𝑗 , E[Δ 𝑓𝑗 ] ≤ 𝑝 (𝜌 − 1)𝐹 last

B.4

𝑗 E[Δ𝑏𝑗 ] ≤ 𝑝 (𝜌 − 1)𝐵 last .

# (Δ 𝑓𝑗 + Δ𝑏𝑗 )

Detailed Bottleneck Statistics

Figure 6 reports the detailed statistics behind the last-stagedominance assumption used in Corollary 6.2. We measure forward computation times over 100 iterations and identify, for each forward microbatch, which pipeline stage has the largest forward computation time. The bottleneck distributions show that the last stage dominates most forward microbatches: 96.8% in the LLM workload and 85.9% in the multimodal workload.

Therefore, "𝑀 −1 ∑︁

□

≤ 𝑝 (𝜌 − 1)𝐿.

𝑗=0 22

The relative-latency panels further show that deviations from last-stage dominance are bounded in scale. For each stage 𝑖, we report the p85, p90, and p95 of the relative latency 𝑗 𝐹𝑖𝑗 /𝐹 last across microbatches. In the LLM workload, the maximum p95 relative latency among non-last stages is 0.84×, indicating that non-last stages are consistently below the laststage latency. In the multimodal workload, some non-last stages can exceed the last-stage latency, but the maximum p95 relative latency is still only 1.14×. These measurements support the bottleneck assumption used in Corollary 6.2: the last stage is usually the bottleneck, and deviations from last-stage dominance remain within a small constant factor.

Detailed Buffer-Size Policy Analysis and Deadlock-Free Guarantee

C.1

Buffer Implementation Details

before each arbitration. If this value is greater than or equal to the configured limit, the stage enters backpressure mode. For non-interleaved schedules, each microbatch passes through each pipeline stage only once in the forward direction and once in the backward direction. Therefore, once D𝑖 reaches the configured limit, the arbitration layer temporarily disables forward dispatch and follows a backward-only drain order. It executes a ready backward task whenever one is available. If no backward task is ready, the stage waits instead of skipping to ready forward tasks. This prevents the stage from producing more forward outputs while allowing backward computations to release the corresponding retained forward inputs. Hence D𝑖 cannot increase in this mode and decreases whenever a backward task executes. The stage remains in this mode until D𝑖 drops below the limit. For interleaved schedules, the situation is more subtle because a microbatch traverses the physical pipeline multiple times, once for each model chunk. For example, with four physical pipeline stages and multiple virtual pipeline stages per stage, the forward path of a microbatch may traverse the stages as 0, 1, 2, 3 for one model chunk, then again as 0, 1, 2, 3 for the next model chunk, and so on. The backward path traverses these chunks in the reverse order. In this case, simply disabling all forward tasks can be unsafe for progress: a microbatch may still need to finish later model chunks in the forward pass before any of its backward tasks can become ready, and waiting only for backward tasks may therefore prevent the computations that would eventually enable buffer release. Thus, under backpressure in interleaved schedules, RRFP switches to a deterministic order that completes microbatches one by one. The stage scans microbatches from index 0 to 𝑀 −1, where 𝑀 is the total number of microbatches. For each unfinished microbatch, the stage follows the microbatch’s fixed local completion order. If a microbatch needs to traverse local model chunks 0, . . . , 𝐶 − 1, where 𝐶 is the number of model chunks, this order is 𝐹 0, 𝐹 1, . . . , 𝐹𝐶 −1, 𝐵𝐶 −1, . . . , 𝐵 1, 𝐵 0 : the forward computations proceed from earlier chunks to later chunks, and the backward computations proceed in the reverse chunk order. The stage checks where the current microbatch is in this order and attempts to execute the next required task. If that task is ready, the stage executes it. If it is not ready, the stage waits rather than skipping to a later task. For example, if microbatch 𝑖 has completed 𝐹 0, 𝐹 1, 𝐹 2 but 𝐹 3 has not yet arrived, the stage waits for 𝐹 3 . After executing 𝐹 3 , it waits for 𝐵 3 , then 𝐵 2 , and so on until the microbatch is fully drained. In effect, the backpressure policy stops opportunistic dispatch and concentrates progress on completing earlier microbatches, so that their backward computations can retire the corresponding activations and reduce buffer occupancy. In this case, each focused microbatch can increase D𝑖 by at most 𝐶 additional forward computations before its backward computations decrease it exactly by 𝐶. Therefore,

At each pipeline-parallel stage, RRFP maintains four buffers (𝑁 denotes PP size): • Forward-ready buffer: stores forward inputs received from the previous pipeline stage, except at PP stage 0 in non-interleaved schedules. • Forward-finished buffer: stores forward outputs waiting to be sent to the next pipeline stage. • Backward-ready buffer: stores backward inputs received from the next pipeline stage. • Backward-finished buffer: stores backward outputs waiting to be sent to the previous pipeline stage, except at PP stage 0 in non-interleaved schedules. RRFP uses the following release policy. First, tensors in the forward-finished and backward-finished buffers are released immediately after the corresponding send completes. Second, each tensor in the backward-ready buffer corresponds to a retained tensor in the forward-ready buffer for the same microbatch. The forward-ready tensor is retained until the corresponding backward computation completes. At that point, both the retained forward input and the backward input are released. Therefore, releasing a tensor from the forward-ready buffer requires the corresponding backward input to have arrived and completed computation. For PP stage 𝑁 − 1, RRFP still sets up the forward-finished and backward-ready buffers, even in non-interleaved schedules. But the runtime moves the forward output directly into the backward-ready buffer locally. C.2

Buffer Backpressure Policy

In RRFP, for PP stage 𝑖, let 𝑛𝑖𝑓 denote the number of forward computations executed by stage 𝑖 so far in the current iteration, and let 𝑛𝑏𝑖 denote the number of backward computations executed by stage 𝑖 so far in the current iteration. The 𝑖th stage computes D𝑖 = 𝑛𝑖𝑓 − 𝑛𝑏𝑖 . 23

D𝑖 can exceed the limit by at most 𝐶 under backpressure. When D𝑖 drops below the limit, the stage exits backpressure mode and returns to the normal readiness-driven arbitration policy. C.3

Even when the buffer limit is 1, backpressure can only force the last stage to execute a backward task, which is exactly the usual 1F1B behavior because stage 𝑁 − 1 executes the backward task immediately after the corresponding forward task anyway. Thus, for stage 𝑁 − 1 to be stuck, we must have

Effectiveness of Backpressure

𝑛 𝑁𝑓 −1 = 𝑛𝑏𝑁 −1 .

We first establish the following theorem.

Otherwise, stage 𝑁 − 1 has backward-ready work. Next, at any time 𝑡 we have

Theorem C.1. Each individual buffer has size at most D0 . Note that for interleaved schedules, the same microbatch may occupy multiple slots, even within the same buffer, corresponding to computation inputs or outputs at different model chunks.

𝑛𝑖𝑓 ≥ 𝑛𝑖+1 𝑓 for every stage 𝑖. Suppose not all forward counters are equal. Then there exists some stage 𝑖 < 𝑁 − 1 such that 𝑛𝑖𝑓 > 𝑛𝑖+1 = 𝑛𝑖+2 = · · · = 𝑛 𝑁𝑓 −1 . 𝑓 𝑓

Proof. For both interleaved and non-interleaved schedules, any buffer entry can appear only after stage 0 has executed the corresponding forward computation (in the same model chunk), and it leaves the system once stage 0 has executed the corresponding backward computation (in the same model chunk). Therefore, every existing buffer entry corresponds to one forward computation at stage 0 whose matching backward computation has not yet been executed, so the total number of such entries is at most D0 . □

This means that stage 𝑖 + 1 has a forward-ready task that has already been output by stage 𝑖 but has not yet been executed at stage 𝑖 + 1. Moreover, from the previous argument and the equality of all backward counters, we have 𝑛𝑖+1 = 𝑛 𝑁𝑓 −1 = 𝑛𝑏𝑁 −1 = 𝑛𝑏𝑖+1 . 𝑓 Therefore, stage 𝑖 + 1 is not in backpressure mode and can execute this forward-ready task, contradicting the assumption of deadlock. It remains to consider the case

Corollary C.2. With a configured limit 𝑀, every buffer has size at most 𝑀 for non-interleaved schedules and at most 𝑀 +𝐶 for interleaved schedules.

𝑛 0𝑓 = 𝑛 1𝑓 = · · · = 𝑛 𝑁𝑓 −1 . Together with 𝑛 𝑁𝑓 −1 = 𝑛𝑏𝑁 −1 and the equality of all backward counters, this implies that the current set of admitted microbatches has fully completed both forward and backward execution. In this case, stage 0 can admit and initiate subsequent microbatches, so the system is not deadlocked. Therefore, no deadlock can occur in the non-interleaved case. For the interleaved case, first observe that

Proof. Under backpressure, D0 cannot increase beyond 𝑀 in non-interleaved schedules. In interleaved schedules, D0 may increase by at most 𝐶 additional forward computations after entering backpressure mode, but the corresponding backward computations then decrease it by exactly 𝐶. Hence D0 is bounded by 𝑀 and 𝑀 + 𝐶, respectively, and the claim follows from the theorem above. □ C.4

Deadlock-Free Guarantee

𝑖+1 𝑛𝑖𝑓 − 𝑛𝑏𝑖 = D𝑖 ≥ D𝑖+1 = 𝑛𝑖+1 𝑓 − 𝑛𝑏 .

We finally prove that training with RRFP under the backpressure policy is deadlock-free.

Therefore, if stage 𝑖 + 1 is in backpressure mode, then stage 𝑖 must also be in backpressure mode.

Theorem C.3. Under reliable computation and communication, training with RRFP under the backpressure policy is deadlock-free if the configured limit is positive.

Case 1: No stage is in backpressure mode. By the same argument as in the non-interleaved case, if the system has no executable work, then we must have

Proof. We first consider non-interleaved schedules. A deadlock can occur only if no stage has executable work. At any time 𝑡, we have 𝑛𝑏𝑖 ≤ 𝑛𝑏𝑖+1 . Moreover, if 𝑛𝑏𝑖 < 𝑛𝑏𝑖+1 , then stage 𝑖 has a backward-ready task and therefore cannot be stuck due to reliable communication. Hence, a deadlock can occur only if

𝑛 0𝑓 = · · · = 𝑛 𝑁𝑓 −1

and

𝑛𝑏0 = · · · = 𝑛𝑏𝑁 −1 .

Otherwise, some stage would have either forward-ready or backward-ready work. Now consider stage 𝑁 − 1. If 𝑛 𝑁𝑓 −1 > 𝑛𝑏𝑁 −1,

𝑛𝑏0 = 𝑛𝑏1 = · · · = 𝑛𝑏𝑁 −1 .

then stage 𝑁 − 1 has at least one forward microbatch whose corresponding backward computation has not yet started. In an interleaved schedule, this means that either the microbatch is eligible for backward, or has not yet finished traversing all local model chunks. In the first case, stage

Now consider the last stage 𝑁 − 1. Under the BF hint, this stage follows an exact 1F1B pattern. Therefore, 𝑛 𝑁𝑓 −1 − 𝑛𝑏𝑁 −1 ∈ {0, 1}. 24

𝑁 − 1 has work to do which is impossible. In the second case, such a microbatch must be forwarded from stage 𝑁 − 1 back to stage 0 for the next model chunk, thereby creating an additional forward-ready task at stage 0. This contradicts the assumption that no executable work exists. Hence, we must have 𝑛 𝑁𝑓 −1 = 𝑛𝑏𝑁 −1 , and together with the equalities above, all admitted work has completed. Stage 0 can therefore admit subsequent microbatches, so the system is not deadlocked.

or returns to stage 𝑘 for last-model-chunk backward, while backward work leaving stage 0 returns to stage 𝑘 for the previous chunk. Hence, the suffix does not introduce an additional blocking point. Therefore, the same argument as in Case 2 applies to the prefix: the target microbatch that the prefix is waiting for cannot be permanently blocked and must eventually return to the corresponding boundary stage, contradicting deadlock. Combining the three cases, no deadlock can occur in the interleaved case. □

Case 2: All stages are in backpressure mode. In this case, a deadlock could only occur if each stage is waiting for its next target microbatch. Suppose stage 0 is waiting for a 𝑗,𝑘 forward microbatch 𝑚 0,𝑓 , where 𝑗 denotes the microbatch index and 𝑘 denotes the model-chunk index. We must have 𝑘 ≥ 1. Otherwise, stage 0 could start computing the first chunk directly. Therefore, stage 0 must have already finished 𝑗,𝑘 −1 computing 𝑚 0,𝑓 and forwarded it to the subsequent stages. Under the backpressure policy, as this microbatch be𝑗,𝑘 −1 comes ready at each stage 𝑖, the corresponding task 𝑚𝑖,𝑓 is the target microbatch and must be computed immediately. Hence, under reliable computation and communication, it can progress through all stages until it reaches stage 0 again 𝑗,𝑘 as the next model chunk 𝑚 0,𝑓 . Consequently, the microbatch that stage 0 is waiting for will eventually become ready, contradicting the assumption of deadlock. The case where stage 0 is waiting for a backward micro𝑗,𝑘 batch is analogous: if it waits for microbatch 𝑚 0,𝑏 , then it

Collective-Order Consistency and Progress

This section gives the detailed argument for RRFP’s tensorparallel coordination protocol. The argument concerns collectiveorder consistency and progress within each tensor-parallel group. Training-loss validation is reported separately in Section E. D.1

Coordination Invariant

Consider one tensor-parallel group. Before any computation step that may invoke tensor-parallel collectives, each rank selects a local candidate from its ready set using the deterministic ready-set arbitration rule. The ranks then exchange the selected microbatch identifiers using a scalar metadata all-gather. If all ranks select the same identifier, the group enters the computation step and therefore invokes collectives for the same tensor in the same order. If the identifiers differ, no rank enters the collective-relevant computation step. The step is deferred, and the local arbitration state is not advanced. The next attempt restarts from the beginning of the same hint order. For local 1F1B hints, this means retrying from backward-forward probing rather than from a later phase. We maintain the following invariant: after every successful collective-relevant computation step, all ranks in the tensor-parallel group have executed the same sequence of collective-relevant microbatches. This invariant holds initially because no collective-relevant task has been executed. Suppose it holds after some successful step. Before the next step, ranks may observe different ready sets because activations or gradients can arrive at slightly different times. The coordination protocol prevents this temporary disagreement from becoming inconsistent collective execution: the group defers computation, avoids entering mismatched collectives, and retries arbitration when later message arrivals change the ready set. If ranks select the same candidate, they all execute the same collective-relevant task, so the executed sequence remains identical across the group. By induction, every successful collective-relevant step preserves the invariant, and tensor-parallel collectives are invoked in a consistent order.

𝑗,𝑘+1 must have finished the previous backward microbatch 𝑚 0,𝑏 , 𝑗,𝑘 or the corresponding forward microbatch 𝑚 0,𝑓 when 𝑘 is the last model chunk. Since this microbatch is the target microbatch for the other stages (all other stages are waiting for it), it is computed immediately. Therefore, the backward microbatch that stage 0 is waiting for will eventually become ready, again contradicting deadlock.

Case 3: A prefix of stages is in backpressure mode. It remains to consider the mixed case where stages 0, . . . , 𝑘 are in backpressure mode while stages 𝑘 + 1, . . . , 𝑁 − 1 are not, for some 0 ≤ 𝑘 < 𝑁 − 1. Since D𝑖 ≥ D𝑖+1, the set of stages in backpressure mode must form such a prefix. Assume, for contradiction, that the system is deadlocked. Then the suffix stages 𝑘 + 1, . . . , 𝑁 − 1 cannot have any ready work. Otherwise, one of them could execute. Therefore, the suffix has already consumed all work currently available from the prefix. In particular, the microbatch that the prefix is waiting for is not stuck inside the suffix, otherwise, the suffix will have executable work, contradicting deadlock. Thus, the only possible waiting cycle lies within the prefix 0, . . . , 𝑘, where all stages are in backpressure mode. We can view stage 𝑘 as the boundary stage of this prefix: forward work leaving stage 𝑘 returns to stage 0 for the next chunk 25

D.2

Progress Under Deferred Computation

preserves the intended training behavior relative to the corresponding 1F1B baseline when only the runtime execution order is changed.

Deferring a computation step does not stop communication progress. RRFP’s send and receive threads run independently of the compute thread, so missing activations or gradients can still arrive while collective-relevant computation is deferred. When such messages arrive, they update the corresponding receive buffers and may add new candidates to the local ready sets. Under reliable message delivery, a temporary disagreement among tensor-parallel ranks can therefore be resolved by subsequent readiness events. Once missing inputs arrive, ranks that previously lacked a candidate can observe it in their ready set. After a failed coordination attempt, ranks do not consume the candidate or move to a later position in the hint order. They retry arbitration from the same point after the ready set changes. Since arbitration is deterministic for a given ready set and hint order, the tensor-parallel group can expose a common candidate and pass the metadata agreement check. The group then resumes computation and enters the next collective-relevant step consistently. Thus, RRFP avoids mismatched collectives while allowing communication to continue until tensor-parallel ranks agree on a common task.

Validation protocol. We evaluate three representative configurations: GPT-Large with TP1/PP8/DP1 and batch size 64, Qwen3-1.7B+ViT-H with TP1/PP8/DP1 and batch size 96, and Qwen3-1.7B+ViT-H with TP2/PP8/DP1 and batch size 96. For each configuration, we run both RRFP and 1F1B with three seeds: 42, 1234, and 2026. Each run uses 500 training iterations, with evaluation every 50 iterations and 10 evaluation iterations per evaluation. We report training and validation loss curves using a logarithmic y-axis, where equal vertical distances correspond to multiplicative changes in loss, to make the rapid early decrease and later convergence behavior visible. Results. Figures 7–9 show that RRFP follows the same overall convergence trend as 1F1B across all three configurations. For GPT-Large, the training and validation curves nearly overlap throughout training. For Qwen, both TP1 and TP2 settings rapidly reduce loss by several orders of magnitude and reach comparable final loss levels. Across seeds, we observe no RRFP-specific divergence or systematic loss instability. These results support that readiness-driven execution changes the runtime ordering of executable tasks while preserving the intended training semantics.

Training Correctness Validation

This section provides the detailed loss-curve validation referenced in the main paper. The goal is to check whether RRFP

GPT-Large PP8 TP1 | Seeds: 42, 1234, 2026 Train Loss

6 × 100

100

200

300

400

7 × 100

500

100

200

300

400

101

rrfp 1f1b

101

500 rrfp 1f1b

9 × 100 LM Loss

Seed 1234 LM Loss

8 × 100

6 × 100

4 × 100

6 × 100

8 × 100 7 × 100 6 × 100

4 × 100 0

100

200

300

400

500

100

200

300

400

101

rrfp 1f1b

101

500 rrfp 1f1b

9 × 100 LM Loss

Seed 2026 LM Loss

rrfp 1f1b

9 × 100 LM Loss

Seed 42 LM Loss

101

Validation Loss

101

rrfp 1f1b

6 × 100

8 × 100 7 × 100 6 × 100

4 × 100 0

100

200

300 Iteration

400

500

100

200

300 Iteration

400

500

Figure 7. Training-correctness validation for GPT-Large with TP1/PP8/DP1 and batch size 64. Each row corresponds to one seed, and the two columns report training and validation loss, respectively. RRFP and 1F1B show nearly overlapping loss curves across all seeds.

Qwen3-1.7B+ViT-H PP8 TP1 | Seeds: 42, 1234, 2026 Train Loss 101

LM Loss

Seed 42 LM Loss

10 7

10 3 10 5

10 8 10 9 10 10

10 7

10 11

10 9

10 12 100

200

300

400

101

500

100

1f1b

200

300

400

500 1f1b

10 5 10 6

10 1

10 7

10 3

LM Loss

Seed 1234 LM Loss

rrfp 1f1b

10 6

10 1

10 5

10 8 10 9 10 10

10 7

10 11

10 9

10 12 100

200

300

400

101

500

100

rrfp 1f1b

200

300

400

500 rrfp 1f1b

10 5

10 1

10 6

10 3

LM Loss

Seed 2026 LM Loss

Validation Loss

10 5

rrfp 1f1b

10 5 10 7

10 7 10 8 10 9

10 9

10 10 100

200

300 Iteration

400

500

100

200

300 Iteration

400

500

Figure 8. Training-correctness validation for Qwen3-1.7B+ViT-H with TP1/PP8/DP1 and batch size 96. Each row corresponds to one seed, and the two columns report training and validation loss, respectively. RRFP and 1F1B show nearly overlapping loss curves across all seeds.

Qwen3-1.7B+ViT-H PP8 TP2 | Seeds: 42, 1234, 2026 Train Loss

Validation Loss

101

rrfp 1f1b

10 6 10 7

10 3

LM Loss

Seed 42 LM Loss

10 1

10 5

10 9 10 11

10 9

10 12 100

200

300

400

101

500

100

rrfp 1f1b

200

300

400

500 rrfp 1f1b

10 5 10 6

10 1

10 7

10 3

LM Loss

Seed 1234 LM Loss

10 8 10 10

10 7

10 5

10 8 10 9 10 10

10 7

10 11

10 9

10 12 100

200

300

400

101

500

100

rrfp 1f1b

200

300

400

500 rrfp 1f1b

10 5 10 6

10 1

10 7

10 3

LM Loss

Seed 2026 LM Loss

rrfp 1f1b

10 5

10 8 10 9 10 10

10 7

10 11

10 9

10 12 100

200

300 Iteration

400

500

100

200

300 Iteration

400

500

Figure 9. Training-correctness validation for Qwen3-1.7B+ViT-H with TP2/PP8/DP1 and batch size 96. Each row corresponds to one seed, and the two columns report training and validation loss, respectively. RRFP and 1F1B show nearly overlapping loss curves across all seeds.

Record · ID 200439 · SHA-256 fc687a0e338aca1a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.