acceptodds
Under review as a conference paper at ICLR 2027

CoverWeave: Coverage Percolation Governs Compositional Depth Extrapolation under Verifiable Rewards

Abstract

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 of the atom co-occurrence graph, with success at depth . The prediction holds without a free parameter: on a coverage sweep, matches measured success at three test depths within points on average. Coverage dominates volume: one quarter of the data above threshold reaches average solve rate, while four times the data below threshold reaches , 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 for vocabulary sizes to , with a finite-size exponent close to the mean-field value . 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 . Training above threshold transfers to building-block-constrained retrosynthesis, raising restricted-catalogue route success from to .

Primary area:
reinforcement learning
Keywords:
Compositional Generalization, Reinforcement Learning with Verifiable Rewards, Depth Extrapolation, Percolation and Phase Transitions, Synthetic Reasoning Environments

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_MF7cOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
1
Soundness
3
Read review
Paper summary

After having the LLM explain to me the paper's core concept (e.g. percolation), the main intuitive idea, the claims and results (as can be seen by my prompt above). Here is my attempt to a summary:

The authors are looking in the ability of LLMs to generalize from shallow problems training (e.g. problems with 2 reasonning steps) to deeper problems (e.g. with 8 reasoning steps). Their claim is that this ability depends on data connectivity, and not on the volume of the problem set or the choice of optimizer. To demonstrate this, they created COVERWEAVE, a synthetic data engine that creates a set of shallow problems and control their connectivity (how the different reasoning steps appear together). They show that a trained policy can solve a d-step problem if all the d required reasoning steps (atoms) belong to a single connected graph. Hence they derive a probability of successfully solving a problem based on the connectivity. They show that optimizing this connectivity threshold allow models to perform deep reasoning with 4x less data. Further, they show that their results transfers to real-world multi-step chemical retrosynthesis.

Critical strengths

The result is amazing. It allowed me to rethink what is important for training LLM-based policies.

The link to percolation is amazing. At the time where LLM based agentic tools can prove results, conduct experiments and write papers from a single prompt, these papers are extremely valuables. Linking different areas of science (here bringing percolation to improve the training efficiency of reasoning agents) is crucial. The paper does it very well, the formalization is good, and once understood, the results are striking.

Finally, this results is not only interesting for this specific RL area.

Critical weaknesses

However, the paper clearly lacks accessibility. Without the LLM to pre-digest the paper for me, it would have extremely difficult for me to understand the problem at hand. I asked an RLVR expert colleague if he understood it after 5 mins spent on it: no. I believe that accessibility is key. The authors are facing the risk that a large audience that would be interested in these results simply do not get it, because of the clarity issue. I think the paper is written by/for percolation experts that also have advance knowledge in RLVR reasoning agent training.

I really invite the authors to rethink how they can improve the clarity of their paper (as Hindsight Experience Replay does). Formalization is important, but it can go in the appendix. Their main result on reasoning atom connectivity is crucial to our community, and it would be a shame that most researcher miss it because of accessibility. Take my prompt and my summary, try to bring this intuition in the paper, while keeping your formalization.

Convince me that you do so, and I'll be more than glad to go from weak reject to strong accept.

Questions for authors

None.

Reviewer_sRQDOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes the hypothesis of coverage percolation, claiming that, for computational depth extrapolation in RLVR, atom co-occurrence coverage in the training data is more important and fundamental than the amount of training data. Theoretically, the central hypothesis is Psucc(ρ,d)≈cS(ρ)dP_{\mathrm{succ}}(\rho,d)\approx cS(\rho)^d where ρ\rho denotes pair coverage, S(ρ)S(\rho) is the fraction of atoms in the largest component S of the atom co-occurrence graph, and dd is the computation depth of the task. Then, to support the hypothesis, the authors create a program-verifiable artificial symbolic environment and use hindsight relabeling to generate training data without requiring model generation. The authors control the percolation threshold of Erdos-Renyi random graphs and evaluate it in a very comprehensive way, observing that, high-coverage training with 1/4 data could substantially outperform low-coverage training with 4 times data, and claims to validate their claim. The authors also use retrosynthesis on top of the fictional symbolic environment to show generalizability of the conclusion.

Critical strengths

(1) The paper is very ambitious and targets a high-value real-world problem. A key contribution of the paper is an ambitious attempt on a theoretical framework for how people determine the data recipe for model training. On top of common metrics like data volume and depth, the authors adopt a more graph-theory inspired perspective to revisit the challenge, introducing the metric of common co-occurrence coverage and making an attempt to relate it to training performance. The attempt is interesting and innovative.

(2) Rather than relying solely on empirical correlations, the authors build a theoretical quantitative framework which is very explicit and falsifiable. Reliable and insightful math and theoretical results are really rare in the field today, and the attempt to do it and connect the theory with the frontier is encouraging and should be valued.

Critical weaknesses

(1) Soundness of the results. This is the primary and most serious concern. The statistics on the largest connected-component in Table 2 are severely inconsistent with the random-graph model specified in Algorithm 1 and Section 4. In Algorithm 1, the edge set EρE_\rho is claimed to be sampled uniformly among subsets containing a fixed number of edges from the (N2)\binom{N}{2} possible atom pairs, which is clean and easy to reproduce. Furthermore, the data generation process ensures the realized co-occurrence edge set equals EρE_\rho. In Section 4, the authors explicitly identify the resulting graph with a uniform fixed-edge random graph, which is equivalent at the relevant scale to an Erdős–Rényi random graph with mean degree λ=ρ(N−1)\lambda=\rho(N-1). However, in Table 2 where the core result of the paper is validated on, the paper reports that S(ρ)S(\rho) equals 0.23,0.31,0.860.23, 0.31, 0.86 for ρ=0.05,0.10,0.30\rho=0.05, 0.10, 0.30 respectively, whereas the average S(ρ)S(\rho) for such a graph is 0.620,0.962,0.999980.620, 0.962, 0.99998, which shows great discrepancy that is far beyond a sampling artifact (mathematical proof below). The inconsistency here is highly fundamental to the validity and soundness of the entire paper.

Mathematical proof: For N=32N=32 and ρ=0.30\rho=0.30, the graph has around 149 edges and mean degree 9.3. For a uniform fixed-edge graph G(N,m)G(N,m), we can do a union bound over nonempty vertex cuts, which gives us the following result $\Pr(G\text{ disconnected}) \leq \sum_{k=1}^{16} \binom{32}{k} \frac{\binom{496-k(32-k)}{149}} {\binom{496}{149}} <3.3\times10^{-4}$, showing that the graph should be fully connected (i.e. S(ρ)=1S(\rho)=1 compared to the reported 0.86) with probability exceeding 99.96%. If the setting is consistent throughout the paper, the reported result falls in a highly unlikely event with probability no more than 0.04%, which is not convincing.

(2) Significant overclaim of the results. The results only hold on a highly artificial symbolic setting. Thus, even without the soundness concern in (1), all the results only hold for the highly structured fictional world, which has a giant gap to real-world learning on practical tasks. The evidence can only support the claim that some mathematics hold for a symbolic and structured setting with fixed rules (i.e. a super small model or even a fixed program can easily capture everything without RL, which is not a setting where generally RL is applied to). Although the authors try to show generalizability with retrosynthesis settings (which is still highly structured), the sample size is too small and the results are mixed. Based on the current reported results, I suspect that the claims cannot broadly transfer to general RLVR tasks, which could severely lower down the significance of the work.

Questions for authors

The questions are mainly associated with the critical weaknesses. The two weaknesses above are the main reason that I don't think the paper scientifically holds, and addressing them could materially change my assessment of the paper since the topic is truly interesting, ambitious, and promising.

(1) Could you please provide a justification for the soundness concern in Weakness 1?

(2) Could you please leverage additional experiments or justification to show generalizability of the results and demonstrate that the claim is generally applicable to common RLVR settings?

Reviewer_Ld4JOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper asks which property of a training set for RL with verifiable rewards decides whether a policy trained on shallow derivations solves deeper ones. It introduces CoverWeave, a procedurally generated symbolic environment with an exact checker and a hindsight data engine. The engine rolls out legal action sequences, relabels the final state as the goal and prunes the sequence to the actions that contribute to it, so verified training examples cost no model calls. Rejection sampling then makes pair coverage ρ an exactly controlled variable at a fixed trajectory count and depth profile. Pair coverage is the edge density of the graph of atom pairs that co-occur in training. The authors propose a percolation account. If an atom's role propagates along observed pairs, a depth-d task is solvable only when its d atoms lie in the giant component, so success ≈ c·S(ρ)^d, where S is the fraction of atoms in the giant component.

They train Qwen3 models (4B–32B) with GRPO and compare it with PPO, RLOO, DAPO, SFT, STaR and rejection-sampling fine-tuning, training on derivations of depth at most 2 and testing at depths 3, 4 and 8. They report that S(ρ)^d matches measured success within 2.3 points on average with no fitted parameter. Four times the data below threshold reaches 21.6% average success, against 93.5% for a quarter of the data above it. Binder-cumulant crossings place the threshold of the co-occurrence graph at the random-graph value 1/(N−1) for vocabularies of 12 to 48 atoms, with a finite-size exponent of 3.08. A threshold of the same shape appears in context for six frozen API models, at locations within 0.028 of each other. Training above threshold raises restricted-catalogue retrosynthesis success from 6.3% to 21.9%. The authors also report that atoms held out of training are solved far more often than their account predicts.

Critical strengths
  1. The hindsight engine produces verified data with no model calls, and the coverage-seeking sampler fixes coverage at a given trajectory count and depth profile. Static compositional benchmarks such as SCAN, COGS and CFQ cannot vary combination structure independently of volume. The ablation shows the steering matters: without it, realized coverage falls from 0.50 to 0.28.
  2. A falsifiable account, reporting where it fails. The paper states separate predictions (P1–P3), distinguishes the structural threshold from the behavioral one, and reports up front that held-out atoms are solved 94% of the time, against its own hypothesis. The controls (name permutation, structure permutation, instance memorization) and the 4×-below vs ¼-above comparison are well chosen.
Critical weaknesses
  1. The main prediction doesn't fit the paper's own numbers. The key result is that success at depth d is roughly S^d. Here S is the share of atoms in the largest connected group of the co-occurrence graph. The paper says the edges of this graph are drawn at random, and Table 3 confirms that it behaves like a standard random graph. For such a graph, however, the S values in Table 2 are far too low. At N = 32 and ρ = 0.10, each atom has about three neighbours on average, so almost all atoms (about 95%) should be in the largest group. I checked this with the paper's own formula in Appendix A.4 and with a quick simulation, but Table 2 reports only 31%. The gap is just as large for ρ = 0.05 to 0.20: Table 2 gives 23–64%, where a random graph gives 62–100%. With the expected S values, the formula predicts 60–75% success at depth 8 for ρ = 0.10, while the paper measures 0%. So the close match between prediction and measurement only works with S values that this kind of graph would not produce. The same applies to the paper's explanation of why success takes off so much later than the graph connects.

    Other numbers don't match the tables either. Table 4 says the threshold shifts by only 0.0068 across depths, but in Table 2 the success curves cross 50% at ρ ≈ 0.25, 0.29 and 0.36 for depths 3, 4 and 8. Table 4 reports a correlation of −0.08 between ρ and χ (how much success varies across seeds), but the χ values in Table 2 give +0.88. In Table 7, GLM-5.2's fitted curve would reach about 47% near ρ = 0.16, while Table 6, the same model's sweep, never goes above 25%.

  2. Some numbers look too clean or don't add up. In Table 1, all the GLM-5.2 entries are whole numbers. Its zero-shot row and its low-coverage few-shot row are identical in all six columns. The 4× data row is identical to the GRPO ρ < ρ* row in five of six columns, even though each is averaged over five seeds and five instance families. GRPO reaches 97.5% in distribution, but DAPO, a variant of GRPO, gets 73.8%, the same as PPO, RLOO and SFT. The API costs also disagree. Table 1 says USD 0.03–0.06 per episode, while Section 5 and Table 11 work out to about USD 0.0014 per episode.

  3. The explanation behind the results is not convincing. The paper's story is that a model learns what an atom does from the atoms it appears with in training. If that were true, atoms never seen in training could not be solved, yet above the threshold they are solved 94% of the time. The paper treats this as a small refinement. To me it suggests something simpler: the model learns a general way to read the rules at test time, and more varied training data teaches this better. Two other results point the same way:

    • Removing causal pruning leaves coverage unchanged (0.497 vs 0.500) but costs 26 points of success, so coverage alone does not decide the outcome.
    • With a fixed number of trajectories, low coverage just means less varied data. In the N = 32 sweep at ρ = 0.02, every two-atom example comes from only 10 atom pairs, against 248 at ρ = 0.5. Nothing in the paper separates coverage from plain data diversity.

    I also have doubts about the RL part and the transfer. Only GRPO is run across coverage levels, so it is unclear whether verifiable rewards matter at all; SFT on the same data might do just as well. For retrosynthesis, I could not tell how a Qwen3 model trained on a symbolic game is used inside AiZynthFinder. The main gain is from 4 to 14 solved targets out of 64, with no error bars. Route quality is measured only on solved targets: 24 of 28 for CoverWeave, against 33 of 121 for Retro-fallback. That favours a method that only solves the easy ones.

  4. Hard to read, and parts feel LLM-generated. When I started reading from the introduction, technical terms kept appearing without explanation, which made the paper very hard to get into. I had to jump ahead to Sections 3 and 4 to follow the argument. The abstract already uses "legal goal", "atoms", "depth profile", "giant component", "Binder cumulant crossings" and "finite-size exponent" without explaining any of them. The introduction's main idea is that an atom's "role" "propagates along observed pairs", but the paper never says what a role is. Figure 1 uses depths k+1, 2k and 4k, and the "susceptibility χ", before k or χ is defined. The contributions mention "supercritical pretraining", although the training is RL fine-tuning and "supercritical" is never introduced.

    Many sentences sound impressive but say little, such as "The optimizer is not the lever", "Adding examples is not adding information about how atoms combine" and "coverage wins without ambiguity". I cannot be sure, but together with a few odd details, this made me feel that many parts were written by an LLM and not carefully checked, beyond the language polishing declared in the AI-use statement. Figure 2 has the garbled label "Illual status" and the word "Illustrative" inside a panel titled "Measured rollout". Table 7 names the models only as "GPT-class" and "Claude-class". Yue et al. (2025) is cited as "Chen et al.", leaving out its first author.

  5. Important details are missing from the main paper. There is no section that clearly describes the benchmark, the metrics or the baselines. I could not find any of the following:

    • the number of atoms or trajectories in the default setup (the reproducibility statement points to Appendix A.2, which contains no numbers);
    • the number of test goals, or what an "instance family" is;
    • how the model sends actions to the environment, which Qwen3 size was used for each table, or the training hyperparameters.

    "Exact solve rate" is never defined, and the "Avg." column mixes in-distribution and out-of-distribution results. There is no comparison with earlier methods for compositional generalization or data selection; the baselines are other training methods, simple search heuristics and one frozen model. The three controls promised in Section 3 (name permutation, structure permutation and instance memorization) are never reported. Table 5 also tests "predictors" that the design keeps fixed, such as mean training depth.

  6. Visible errors. Several mistakes suggest the paper was not checked carefully:

    • In Table 1, the blue row highlight covers the group labels in the left column, so "Coverage" and "Ctrl" appear as "overage" and "trl".
    • Figure 2 contradicts itself, even though Appendix A.1 calls it "experimental measurements". Panel (a) says ρ = 0.10 and "disconnected", but it draws 8 of the 10 possible edges, and A1 is connected to A4 through A2. Some of its values are impossible for a five-atom graph, such as S = 0.28 and ρ = 0.74. Panel (b) names the path A1–A2–A3–A4 but highlights A1–A2–A4.
    • In Table 10, DESP's USPTO-190 and Restricted numbers seem swapped: 14.06% equals 9 of 64 targets, and 22.63% equals 43 of 190.
    • The red numbers, orange shading and underlines in the tables are never explained. Table 6's caption mentions columns that are not in the table, and "Eq. equation 1" appears throughout.

Overall, the writing looks polished, but the paper is hard to follow. Terms are used before they are explained, key setup details are missing from the main text, and several tables and figures contain errors the authors don't seem to have noticed. The question is timely, and a data generator that changes which atoms appear together while keeping the amount of data fixed would be a useful tool. However, the S^d formula and the percolation idea are close to Okawa et al. (2023) and Lubana et al. (2025), which the paper mentions only briefly. Also, with a fixed number of trajectories, low coverage simply means the same few pairs are repeated. "Coverage beats volume" is therefore close to the known finding that varied data beats repeated data.

Questions for authors
  1. How were the S values in Table 2 measured? For a random graph with N = 32, about 95% of atoms should be in the largest group at ρ = 0.10, and almost all of them at ρ = 0.15 and above. What does your formula predict with these values?
  2. How were the threshold shift of 0.0068 and the correlation of −0.08 in Table 4 computed? Table 2's curves cross 50% at ρ ≈ 0.25 to 0.36, and its χ values give a correlation of +0.88.
  3. How many episodes stand behind each GLM-5.2 number in Table 1? Why are the zero-shot and low-coverage few-shot rows identical, and how do the per-episode costs in Table 1 match Table 11? Which models are "GPT-class", "Claude-class" and the others in Table 7?
  4. How can GLM-5.2 have a midpoint of 0.158 and a ceiling of 0.94 in Table 7, when Table 6 never goes above 25%?
  5. What are the number of atoms and trajectories in the default setup, the number of test goals per split, and the definition of an instance family? Please also give the definition of exact solve rate, the prompt and action format, the training hyperparameters, and the Qwen3 size used for each table.
  6. What are the results of the name-permutation, structure-permutation and instance-memorization controls described in Section 3?
  7. Does SFT, or another optimizer, also reach about 95% at high coverage? Can you add a control that keeps the number of distinct training goals the same across coverage levels?
  8. Symbol names and rules are resampled for each instance. What counts as the same atom across training instances, and on which instances is the co-occurrence graph built?
  9. Are the values in Figure 2 measured, as Appendix A.1 says, or illustrative, as panel (c) says? How can panel (a) show ρ = 0.10 and disconnected support while drawing 8 of the 10 possible edges?
  10. How is the CoverWeave model used inside AiZynthFinder? What are the correct DESP numbers in Table 10? How many runs stand behind the gain from 4 to 14 of 64 targets?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.