When a language model is trained with reinforcement learning against a checker that can confirm a correct answer, most of the sampling budget is wasted. Many sampled solutions have already failed in a way the checker could detect partway through. In a Countdown puzzle, the numbers still unused may be unable to reach the target at all. In an optimization-modeling task, the constraints written so far may already make the model infeasible. Standard training lets those attempts run to the end and then assigns zero reward. We propose to ask the checker at intermediate commit points whether the attempt can still succeed. If the checker returns a proof that it cannot, the attempt is cut on the spot, the step that killed it gets localized blame, and the saved tokens are spent resampling from the last live point.
The key property is that this pruning is sound rather than heuristic. A branch is cut only when success is provably impossible, so pruning never discards a future success. It also leaves the learning signal unbiased, because tokens generated after the point of certain failure carry zero expected gradient. This is the specific lesson we take from dynamic search-space pruning in neural architecture search. There, premature pruning and misleading importance proxies are the main failure modes. We avoid both by allowing hard deletion only on certificates and using heuristics only for ordering, never for deletion.
Core Claim
Reinforcement learning with verifiable rewards (RLVR) optimizes a policy using deterministic pass/fail signals from compilers, solvers or answer checkers instead of a learned judge. In agentic environments whose state only moves in one direction as the model commits actions, the verifier can issue a death certificate for a partial rollout. Examples of such commitments are appending constraints to a model or consuming numbers in a puzzle. Our claim is that certificate-triggered truncation plus budget reallocation improves both sample efficiency and final accuracy over equal-token GRPO (group relative policy optimization, which scores each sample against the mean of its sibling samples). We further claim it beats similarity-based tree pruning. It does this without the sub-rollout cost that stepwise value estimation requires.
The unbiasedness argument is short. Let $t^*$ be the first step at which the verifier certifies that the terminal reward $R$ must equal zero. For every later token $a_t$ with $t > t^*$, the advantage $R - b$ is a constant conditional on the prefix, where $b$ is the group baseline. The score function also has zero conditional mean:
$$\mathbb{E}\left[\nabla_\theta \log \pi_\theta(a_t \mid s_t)\,(R-b) \,\middle|\, s_{t^*}\right] = (0-b)\,\mathbb{E}\left[\nabla_\theta \log \pi_\theta(a_t \mid s_t)\,\middle|\, s_{t^*}\right] = 0 .$$
Dropping those tokens therefore removes only variance and compute. The argument holds exactly when the certificate is sound. It fails the moment a heuristic is substituted for a proof, which is why we keep the two apart.
Where Certificates Exist
Certificates require committed state. In free-form chain-of-thought, a wrong intermediate line can be retracted with "wait, that's wrong," so no prefix is provably dead. We therefore restrict the method to action-based formats and treat free-form math as a stated boundary, not a target.
The first domain is Countdown in a tool-call format. Each call commits one arithmetic operation on two available numbers. Whether the remaining multiset can still reach the target is decidable exactly by memoized search, which is cheap at Countdown sizes.
The second domain is natural-language optimization modeling, using the benchmarks from Solver-Informed RL. That paper couples an LLM to Gurobi, rewards execution, feasibility and objective match, and already parses intermediate .lp files. It uses those files only for staged rewards after generation. We change the output format so that the model first declares the decision variables, closes that block, and then appends the objective and constraints in executable chunks.
Once the variable set is fixed, adding a constraint can only shrink the feasible region. Two sound certificates follow. First, if the partial model is infeasible and the reference optimum is feasible, the branch is dead. Second, for a minimization problem, suppose the partial model's optimum $z_k$ exceeds the reference optimum $z^\star$ by more than the grading tolerance $\epsilon$:
$$z_k > z^\star + \epsilon .$$
Then no completion can match, because later constraints cannot lower $z_k$. Maximization is symmetric. This mirrors bounding in branch-and-bound. Certificates are valid only after the variable block closes, since adding variables can expand the feasible set; before that point nothing is pruned.
Two things are not certifiable and receive no special treatment. A partial model whose objective is still too good, which means constraints are missing, remains live. Mismatches in semantic intent are never pruned.
Research Program
We would build a rollout engine that runs the verifier after each committed chunk and returns one of two results: live, or dead with a certificate. When a branch dies at chunk $k$, three things happen. The branch is truncated. The chunk that produced the death receives a localized negative advantage. The freed token budget is used to resample continuations from the last live state at chunk $k-1$, capped at a fixed number of retries per node.
Resampling changes the sampling distribution, so we separate two groups for advantage computation. The outcome-level group advantage uses only the original independent root samples, which keeps the standard GRPO estimate intact. Retried siblings contribute advantages computed within their own sibling group at the branch node, in the manner of Tree-GRPO from DeepSearch.
The architecture-search literature shapes two design rules as constraints, not as methods we reuse. First, IS-DARTS showed that superficial importance proxies cause collapse: DARTS falls to about 54% on NAS-Bench-201 CIFAR-10, while IS-DARTS reaches 94.36% using a Fisher-information importance measure. Second, SGAS and ASAP showed that greedy irreversible removal buys efficiency at the risk of dropping late-blooming candidates. Our response to both is to permit irreversible deletion only on certificates. Uncertified signals, such as policy entropy at a node, may only decide where retries are spent, and every live node stays eligible.
The analyses would answer three questions. How often do certificates fire as training progresses? Does the dying-chunk penalty act as a free, exact process reward, and does it shorten rollouts the way VSRM does with sub-rollouts? How does verifier call cost scale with problem size? Solver calls on partial MILPs are not free, so wall-clock time is reported alongside token counts.
Baselines
The naive reference is DAPO/GRPO with outcome-only reward on the same action format. It is given the same total generated-token budget per step, the same base model (Qwen2.5-7B-Instruct for both domains), the same data and the same hyperparameter search budget. Dead rollouts simply run to termination and receive zero reward. Beating it means higher final accuracy at equal tokens, or equal accuracy with at least 1.5 times fewer tokens.
The strongest existing rollout-pruning method is Lookahead Tree-Based Rollouts (LATR). LATR branches at high-entropy tokens, runs 20–50-token lookaheads, and prunes children whose normalized edit distance from the parent is too small. It is the closest competitor because it also reallocates rollout budget mid-generation inside GRPO/DAPO, and it reports reaching peak DAPO performance on Countdown in 150 rather than 450 steps. The file gives no absolute Countdown accuracy for it. We would run LATR on our identical tool-call Countdown and optimization formats with its reported window range and annealing schedule, tuned with the same budget as ours. Beating it means reaching the DAPO peak in fewer steps than LATR under equal tokens, with higher final accuracy.
For optimization modeling, the strongest reported system is SIRL. SIRL-32B reports a 68.3% macro average across NL4OPT, MAMO, IndustryOR and OptMATH, and 45.8% on OptMATH, per Solver-Informed RL. The file reports no result for a 7B SIRL model, so we would reimplement SIRL's staged reward and partial KL at 7B on our data as the in-house anchor. The 32B figure is quoted only as an upper reference, not as a matched comparison. A DeepSearch-style MCTS baseline is included for Countdown only, with its fixed frontier weights. The file reports only its math-suite average of 62.95% and no Countdown or optimization-modeling number.
Three ablations isolate the ingredients. The first truncates on certificates but does not reallocate the freed budget, which measures pure compute savings. The second truncates the same fraction of rollouts at random points and reallocates, which measures whether certificate targeting matters. The third penalizes the dying chunk but does not truncate or reallocate, which is certificate-based reward shaping alone.
Why not just…?
Why not just run more GRPO samples with the same tokens? This is the most serious threat. If most dead rollouts die late, truncation frees little budget and equal-token GRPO will match us. DeepSearch reports that extended linear training plateaus near 62% after 1,800+ GPU hours, which suggests that sheer volume stalls. That evidence comes from free-form math, however, not from our domains. The equal-token baseline, together with a measured distribution of death points, settles the question directly. If deaths cluster near the end of rollouts, we would report that the method does not help there.
Why not just use LATR's similarity pruning? Edit distance over a short window cannot see logical state. A sign flip looks like near-duplication, while two paraphrases of the same dead constraint set look divergent. Pruning on it can therefore delete eventual successes and bias the gradient. Our soundness audit makes this concrete. We continue a sample of pruned branches to termination offline and measure how many would have succeeded: it should be zero for certificates and is measurable for LATR.
Why not just add the certificate as a dense penalty, with no pruning? This could plausibly capture most of the credit-assignment benefit. That is why it is an explicit ablation rather than a straw man. If shaping alone matches the full method on accuracy, the remaining contribution is compute, and we would report the claim at that narrower scope.
Why not estimate step values with sub-rollouts, as VSRM does? VSRM cut AIME24 output length from 12,605 to 7,065 tokens at 28.8% versus 29.5% Pass@1 for DS-Distill-1.5B, per VSRM. It pays for this with many sub-rollouts at every boundary. A certificate delivers an exact zero-value verdict for the price of one solver or search call. We compare per-step compute and length reduction on Countdown, where both methods apply.
Decisive Checks
We run on Countdown and on NL4OPT, MAMO, IndustryOR and OptMATH, reporting accuracy, total tokens and wall-clock time. The core result is a steps-to-DAPO-peak and final-accuracy curve at matched tokens against GRPO and LATR on Countdown, and against 7B SIRL on optimization modeling. The soundness audit must show zero pruned-but-winning branches; any nonzero count indicates a format leak that invalidates the unbiasedness argument. Gradient-variance measurements should show lower variance than untruncated GRPO at equal batch size.
The random-truncation ablation is the test that separates a real effect from budget reshuffling. The method matters only if certificate-targeted pruning clearly beats random pruning at the same rate. As a negative control, a free-form-chain-of-thought variant of optimization modeling, where the model may retract constraints, should show certificates breaking soundness. That result would confirm that the committed-state requirement is essential rather than incidental.
References
- Solver-Informed RL: Grounding Large Language Models for Authentic Optimization Modeling
- DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Tree-based Search
- IS-DARTS: Stabilizing DARTS through Precise Measurement on Candidate Importance
- SGAS: Sequential Greedy Architecture Search
- ASAP: Architecture Search, Anneal and Prune
- Promoting Efficient Reasoning with Verifiable Stepwise Reward
- Lookahead Tree-Based Rollouts for Enhanced Trajectory-Level Exploration in Reinforcement Learning with Verifiable Rewards