The call lineage is a tree without compaction and a forest with it — and RL walks up from one accepted leaf per tree

Explainer for NVIDIA-NeMo/RL #4124 (paired with NVIDIA-NeMo/Gym #3368). RL links pin c617a2c; Gym links pin b27e0db.

Before
Ordinary capture: every call hangs off the call before it, so a rollout's calls form one tree. RL walks up from a single leaf and builds one row.
This PR
With context compaction (CC), each rewrite starts a new root, so the calls form a forest. RL walks up once per tree and builds one row per tree.
Status
Proposed — open PR, not merged. Both pictures below are real runs of the PR's code, with a stand-in model.

Nine pages on this PR, one question each. This one: what the call lineage looks like, and which leaves RL walks up from.

Background. Gym's ledger records each model call's parent: the earlier call whose tokens this call's prompt starts with. Drawn out, that is a tree. A root has no parent and stores its whole prompt. A leaf has no children. When the agent rejects a response and asks again, the retry gets the same parent as the rejected call, so the tree branches. Dotted words have a short explanation: hover or tap them.

The same conversation was run twice through the PR's code: 7 accepted actions, and the agent rejects one response at action 4 and one at action 6. That makes 9 model calls, c1–c9. Without compaction every call extends its parent, so the 9 calls form one tree with 3 leaves. RL walks up from just one of them, the response the agent ended on (Gym _terminal_chain). With compaction every 2 actions, each rewrite starts a new root, giving 4 trees. RL picks the accepted calls from the agent's output, cuts them at each root, and walks up once per tree from that tree's accepted leaf (_plan_selected_calls, then finalize_rollout per tree). Rejected leaves are never walked in either case.

Same 9 calls, as one tree and as a forest

Compaction off · one tree, 3 leaves, 1 walked c1 c2 c3 c4 c5 c6 c7 c8 c9 ✗ rejected leaf✗ rejected leaf accepted leaf = theresponse the agent ended on walk up from c9 only: c9 → c8 → c6 → c5 → c3 → c2 → c1, then reverse pick the leaf: nemo_gym.py L1257-1300 walk: rebuild.py L201-216 1 row · group_g0_s0 · 21 tokens · 7 with gradient · advantage +0.5 [10,11,1001, 20,21,1002, 30,31,1003, 50,51,1005, 60,61,1006, 80,81,1008, 90,91,1009] c1 · c2 · c3 · c5 · c6 · c8 · c9 — c4 and c7 add nothing Compaction on (every 2 actions) · a forest of 4 trees, 6 leaves, 4 walked c1 c2 rewrite c3 c4 c5 rewrite c6 c7 c8 rewrite c9 root + leaf 1. accepted calls = what the agent's output contains: c1 c2 c3 c5 c6 c8 c9 gym_selection.py L91-249 2. cut at every root → 4 chains; each chain's last call is the leaf rollout_reassembler.py L1153-1161 group_g0_s0c1 · c2 6 tok[10,11,1001,20,21,1002] group_g0_s1c3 · c5 6 tok[10,11,1003,50,51,1005] group_g0_s2c6 · c8 6 tok[10,11,1006,80,81,1008] group_g0_s3c9 3 tok[10,11,1009] All 4 rows: reward 1.0, advantage +0.5 — one value for the whole rollout, copied to each row. root continues its parent accepted leaf (walked) rejected leaf (never walked) walk up to the root training row Token values come from the PR test's stand-in for vLLM: a root's prompt is [10, 11]; call i adds two observation tokens and generates 1000+i.The top picture is the PR's code with compaction switched off. True ordinary capture builds the same row in a shorter run (page 3),but cannot run this one: the stand-in gives c4/c5 and c7/c8 identical text, which hits an older Gym limit that predates this PR.

Which leaves get walked, and why not all of them

Compaction offCompaction on
Shape of the lineage1 tree4 trees, one per stretch between rewrites
Leaves3 (c4, c7, c9)6 (c2, c4, c5, c7, c8, c9)
Leaves walked1: the response the agent ended on (c9)4: the last accepted call in each tree (c2, c5, c8, c9)
How RL finds themFrom the harness's declared final response, or the scored response, matched to a ledger rowFrom the agent's whole output: every accepted response is matched to its call, then the list is cut at each root
Rows1 row, 21 tokens4 rows: 6 + 6 + 6 + 3 tokens
Rejected calls (c4, c7)Same in both: never walked and never trained, but still read, checked and cleaned out of storage with the rest (rollout_reassembler.py L680-687)

Walking up from every leaf would train the rejected responses c4 and c7, which the agent threw away. So in both cases RL uses the agent's own record of what it kept to pick the leaves. With compaction that record has to cover the whole conversation, not just the end: a tree whose calls are missing from the agent's output is never walked, so it never trains.

So what. The walk itself did not change: inside each tree, RL still goes from one leaf up to the root and joins the stored tokens. What changed is how many trees there are, and how RL finds the leaf of each: from the agent's full output instead of a single final response. A rollout with 3 rewrites becomes 4 rows that share one reward and one advantage.