Can shared-prefix trees reduce redundancy in agent rollouts?

Agent rollouts are expensive. Multi-turn agentic tasks produce trajectories with thousands of tokens and many tool calls per rollout. Group-based RL methods like GRPO sample multiple independent trajectories per task and use the group statistics for advantage estimation. The standard implementation samples each trajectory independently, from the same starting prompt — meaning every trajectory begins by re-generating the same early-turn context.

The redundancy is substantial. If task setup, initial planning, and the first few tool calls are similar across rollouts (often the case, because they all start from the same prompt), then each independent rollout pays the token cost for the early turns again, even though the model would produce nearly the same early sequence each time. The compute is real; the information added per rollout is small in the early turns.

Tree-GRPO restructures this. Rollouts share common prefixes by design — the tree starts as a single trunk and branches at decision points. Compute spent on the trunk is amortized across all leaf trajectories. The same total token budget that produces N independent chain-based rollouts can produce more than N leaf trajectories under tree sampling, because the branches diverge late while sharing the early context.

The empirical consequence is twofold. First, more distinct trajectories per fixed cost means better statistics for advantage estimation — the noise in group-relative comparisons decreases as the effective N grows. Second, the same budget can train on harder tasks where the trajectory length itself was the bottleneck — long trajectories with shared early planning fit into budgets that independent rollouts cannot accommodate.

The pattern generalizes beyond Tree-GRPO. Anywhere RL training samples multiple trajectories from a shared starting point, shared-prefix sampling saves compute. Speculative decoding has the analog at the inference layer. The unifying principle: when starting state is shared, compute up to the divergence point is amortizable.