CoverWeave: Coverage Percolation Governs Compositional Depth Extrapolation under Verifiable Rewards

Reinforcement learning with verifiable rewards (RLVR) is now the standard recipe for training models on checkable reasoning tasks, and the capability it is meant to buy is composition: a policy trained on shallow derivations should solve deeper ones it has never seen. Which property of the training set decides whether this happens is unknown, because existing compositional benchmarks fix combination structure and data volume together and cannot separate them. We introduce CoverWeave, a procedurally generated symbolic environment with an exact checker and a hindsight data engine in which every legal rollout ends in a legal goal, so verified training examples are produced by symbolic execution at zero model cost. In this engine, pair coverage, the fraction of atom pairs that co-occur in training, is an exactly controlled variable at fixed trajectory count and depth profile. A percolation account predicts that depth extrapolation is governed by the giant component $S$ of the atom co-occurrence graph, with success $\approx cS(\rho {)}^d$ at depth $d$. The prediction holds without a free parameter: on a coverage sweep, $S(\rho {)}^d$ matches measured success at three test depths within $2.3$ points on average. Coverage dominates volume: one quarter of the data above threshold reaches $93.5\%$ average solve rate, while four times the data below threshold reaches $21.6\%$, no better than the base amount. Binder cumulant crossings confirm that the realized co-occurrence graph has its structural threshold at the random-graph value $1/(N-1)$ for vocabulary sizes $12$ to $48$, with a finite-size exponent $\nu =3.08$ close to the mean-field value $3$. A threshold of the same shape appears with no weight updates when coverage is varied only in the prompt, and its location agrees across six frozen models to within $0.028$. Training above threshold transfers to building-block-constrained retrosynthesis, raising restricted-catalogue route success from $6.3\%$ to $21.9\%$.