Paper Explained: RayOrch — Batching Children Across Parents on GPUs Without Losing Track of Who Owns What

Split PDFs into pages and videos into clips, batch them across sources on GPUs, and still route every result back to the right parent in the right order. A from-scratch walkthrough of RayOrch: its vocabulary, state machine, commit rule, and measured results.

RayOrch: Programming and Executing Lineage-Controlled Multi-Grain Dataflows for Foundation-Model Data Preparation

What problem does this paper solve?

The paper is "RayOrch: Programming and Executing Lineage-Controlled Multi-Grain Dataflows for Foundation-Model Data Preparation" (arXiv:2609.18703, September 2026, a technical report). It is a systems paper: a programming model and distributed execution engine for the preprocessing pipelines that produce training data. It does not propose a new model architecture.

Here is what the abstract says. Preparing high-quality training data for foundation models needs scalable pipelines that turn heterogeneous documents and videos into structured records. These pipelines expand each parent item, such as a PDF, into an ordered, input-dependent sequence of children, such as pages, and the child counts can be long-tailed. GPUs should batch children across parents while keeping parent relationships, child order, completion status, and result routing intact. Existing systems either hide parallelism inside coarse-grained jobs or expose flat records and leave lineage tracking and regrouping to the application. RayOrch keeps parent-child relations throughout execution. Programs declare ordered, variable-cardinality expansions and matching gathers. The compiler validates each pair, and the runtime records child membership, immediate parents, immutable ordinals, and terminal states. On NVIDIA H20 GPUs, the authors report a 15.14× speedup scaling MinerU from 4 to 64 GPUs and 7.82× scaling a video pipeline from 8 to 64 GPUs. End-to-end time drops 13.1% versus Ray Data and 29.0% versus Daft on MinerU, and 16.0% versus Ray Data on Docling.

An analogy: grading exam papers

Picture a school where every student hands in a different number of answer sheets. Some turn in 2 pages and some turn in 48. Graders get through the work faster if they take a mixed stack from many students than if they finish one student's pile before starting the next. GPUs behave the same way: batching pages from several PDFs keeps the hardware busier than feeding one document's pages at a time.

Mixing the stacks causes problems, though. Every graded sheet has to go back to the right student, in page order. If you wait until everyone is done before returning anything, the student with 2 pages waits on the student with 48. And if page 1 of one student's exam turns out to be disqualified, grading the rest of that student's pages is wasted effort. You still don't want to stop grading everyone else.

That is exactly the question the paper poses (§1): how do you batch fine-grained work across parents while keeping the structure needed for per-parent completion, ordered reconstruction, and failure containment?

Two existing approaches and where they fall short

The paper sorts existing approaches into two camps (§1, Table 1).

The first is coarse-grained. Each document runs as one opaque job. The parent-child relation stays implicit and safe, but the engine can't see the page-level parallelism inside the job, so it can't form batches that span documents.

The second is flat. Children flow as independent rows through Ray Data's flat_map or Daft's explode. You gain parallelism and batching, but "parent ID" and "position" become ordinary application columns. According to the paper, these flat interfaces don't treat those columns as structure. The application has to decide when a parent is complete and how far a failure reaches. In the Ray Data and Daft pipelines the authors evaluated, this also added a shuffle or regrouping barrier after the child stage (§1).

RayOrch's vocabulary: Domain, Entity, Call, Grain

The central idea is to keep structural lineage for the whole execution and treat physical batches as disposable (§1). The paper is explicit that "lineage" here means control state for scheduling and completion. It is not a post-hoc provenance log, and it is not Ray's task-recomputation lineage.

The terms (§3.1, Table 2):

• Domain: one level of the hierarchy, such as "PDF" or "Page"
• Entity: one unit at that level, such as "page 0 of PDF A", with an immutable key
• Expansion: the ordered set of child Entities materialized for one parent
• Call: one configured use of a user function (for example, page OCR) in the program
• Grain: one Call applied to one Entity. This is the unit of scheduling, retry, and commit

A program uses F.expand to declare a parent-to-child expansion and F.reduce to declare the matching ordered child-to-parent gather. There is also F.filter, which drops members within a Domain, and F.broadcast, which makes an ancestor's value available in a descendant Domain. Arbitrary joins and regrouping are deliberately left out (§4.1, Table 3). Before anything runs, the compiler checks acyclicity, Domain compatibility, and expand/reduce pairing, then lowers the program to an immutable graph. So "which child belongs to which parent" comes from the declaration, not from scanning record fields at reduce time.