Verifiable generation, group-relative updates, and test-time sampling

Fix a finite nonempty set $Q$ of prompts. For each $q\in Q$, fix a finite nonempty ordinary-token alphabet $V$, a positive integer generation budget $L_q$, an end-of-sequence token $e\mathrm{\notin }V$, and a truncation marker $\tau \mathrm{\notin }V\cup \{e\}$. Generate at most $L_q$ tokens from $V\cup \{e\}$. A permitted response is the sampled prefix through its first $e$ if $e$ occurs within the budget; otherwise it is the full $L_q$-token prefix followed by the unsampled marker $\tau$. Fix a nonempty finite ordered list of distinct permitted responses $(y_{q,1},\dots ,y_{q,m_q})$ and let $Y_q$ be its underlying set. The prompt set, tokenizer alphabet, budget, terminal markers, and response list are part of the evaluation protocol; changes to these data may change the response distribution being evaluated. Merely reordering the response list while keeping its underlying set and policy masses fixed leaves that distribution unchanged.

For each $q$, fix a strict total order ${\prec }_q$ on $Y_q$, meaning an irreflexive, transitive relation for which either $y{\prec }_{q}z$ or $z{\prec }_{q}y$ holds for every pair of distinct responses $y,z$. Let $U\subseteq {\mathbb{R}}^d$ be open. For each $q\in Q$, a parameterized sampling policy is a probability mass function ${\pi }_{\theta }(\cdot \mid q)$ on $Y_q$, for $\theta \in U$, with a fixed nonempty support $B_q\subseteq Y_q$: ${\pi }_{\theta }(y\mid q)>0$ for $y\in B_q$, ${\pi }_{\theta }(y\mid q)=0$ for $y\mathrm{\notin }{B}_q$, and ${\sum }_{j=1}^{m_q}{\pi }_{\theta }(y_{q,j}\mid q)=1$. Each mass is totally differentiable in $\theta$. Write the support in the inherited order as $(b_{q,1},\dots ,b_{q,n_q})$. At a fixed prompt this is the finite-action policy of a one-decision finite Markov decision process, with response strings as actions. Its score vector on the support is

$S_{\theta }(q,y):={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(y\mid q),y\in B_q\mathrm{.}$

For finite sums over supported responses, write ${\mathbb{E}}_{\theta }[f(Y)\mid q]:={\sum }_{k=1}^{n_q}{\pi }_{\theta }(b_{q,k}\mid q)f(b_{q,k})\mathrm{.}$

For each prompt, let $C_q:Y_q\to \{0,1\}$ be a supplied correctness predicate and $A_q:Y_q\to \{0,1\}$ a supplied verifier. The finite response set has its power-set sigma-algebra, so both maps are measurable. $C_q(y)=1$ means that response $y$ is correct for the stated task criterion; $A_q(y)=1$ means that the verifier accepts it. A false acceptance is an output with $A_q(y)=1$ and $C_q(y)=0$. The verifier is not assumed to equal the correctness predicate.

Also fix a finite real reward $r_q(y)$ and a finite real selection score $u_q(y)$ on $Y_q$, when a training or best-of-$N$ procedure uses them. The total order ${\prec }_q$ resolves equal selection scores by choosing the ${\prec }_q$-least maximizer. Independent draws from ${\pi }_{\theta }(\cdot \mid q)$ mean that the joint mass of any finite tuple $(y_1,\dots ,y_N)$ is ${\prod }_{i=1}^N{\pi }_{\theta }(y_i\mid q)$.

A differentiable policy has normalized action probabilities, a fixed support, and the score vector given by the gradient of the log probability.

A probability measure is a measure of total mass one on a measurable space.

Finite sums are defined recursively and are independent of the list extension used for the finitely many terms.

For a fixed prompt $q$, take the finite truncated response set $Y_q$, sampling policy ${\pi }_{\theta }(\cdot \mid q)$, verifier $A_q$, and selection score $u_q$ from the generation protocol. Given an integer budget $N\ge 1$, choose exactly one of the following modes. Response draws, verifier and score evaluations, and comparisons of real scores and of the supplied tie order are supplied terminating exact operations with finite per-call costs. Each draw returns a response from the specified policy support with the stipulated independent law; no construction of a random source is asserted.

1. Rejection search. Draw responses one at a time independently from ${\pi }_{\theta }(\cdot \mid q)$. Return the first response $y$ for which $A_q(y)=1$, together with status accepted. If no sampled response is accepted after $N$ draws, return failure and no response. Stop at the first acceptance or after the $N$th draw, whichever occurs first.

2. Best-of-$N$. Draw exactly $N$ responses independently from ${\pi }_{\theta }(\cdot \mid q)$. Return a response with maximal value of $u_q$; if several responses have maximal score, return the ${\prec }_q$-least one. Return status selected. This mode does not use the verifier to select its output and does not declare the selected response correct.

Its output law is the one induced by the specified prompt, finite response set, length budget, truncation marker, policy, verifier or score, and tie order.

Budgeted verifier generation terminates with bounded response and selection calls ↗: proves termination, the output rules, and the finite draw, evaluation and comparison bounds under the supplied-call model.

The finite response set, sampling law, correctness predicate, verifier, selection score, and deterministic tie order.

For every input of budgeted verifier-guided generation, with integer $N\ge 1$ and its supplied terminating exact operations, rejection search terminates with the first verifier-accepted response and status accepted, or with failure and no response exactly when all $N$ responses are rejected. It uses at most $N$ response draws and at most $N$ verifier evaluations. For a complete presampled tuple $(y_1,\dots ,y_N)$, it succeeds exactly when at least one $A_q(y_i)=1$.

Best-of-$N$ terminates after exactly $N$ response draws and can return the stipulated least maximizer using $N$ score evaluations, at most $N-1$ score comparisons and at most $N-1$ tie-order comparisons. It returns status selected and makes no correctness or verifier-acceptance assertion. Both modes therefore use finitely many supplied calls and have finite total cost equal to their finite bookkeeping cost plus the sum of actual finite per-call costs. The draw-count and output conclusions hold for every realized response tuple; independence is needed only for probabilistic calculations that separately assume it.

Budgeted verifier-guided generation and best-of-N sampling: gives the two modes, stopping instructions and supplied-operation model.

Fix a prompt $q$, a budget $N\ge 1$, and the finite response law, correctness predicate, and verifier from the generation protocol. In part 1, $Y_1,\dots ,Y_N$ are independent draws from that law and $p:=\mathrm{Pr}(C_q(Y_1)=1)$ is their common one-draw correctness probability. Parts 2 and 3 state their own sampling hypotheses.

1. If $A_q=C_q$, rejection search returns an accepted response with probability $1-(1-p{)}^N$.

2. For any rule that selects one of these $N$ candidates and reports it as accepted only when its verifier value is $1$, if each draw satisfies $\mathrm{Pr}(A_q(Y_i)=1,C_q(Y_i)=0)\le ϵ$, then the probability of outputting an accepted but incorrect response is at most $Nϵ$. This bound does not require independent draws.

3. For an adaptive sampler, let $p\in [0,1]$. Suppose that for every $i\le N$ and every positive-probability history $h=(Y_1,\dots ,Y_{i-1})$ with no earlier correct response, the conditional probability of correctness at draw $i$ is at least $p$. Then the probability of no correct response in the first $N$ draws is at most $(1-p{)}^N$.

Finite response law, correctness predicate, and verifier.

Rejection search returns the first verifier-accepted sample, or failure after the budget.

DeepSeek-AI, DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning.

Let $Y$ be a finite nonempty response set with a fixed enumeration $(y_1,\dots ,y_m)$, and let $p$ and $q$ be probability mass functions on $Y$ satisfying $p(y)>0\Rightarrow q(y)>0$. Define $\rho (y)=p(y)\mathrm{/}q(y)$ when $q(y)>0$ and $\rho (y)=0$ when $q(y)=0$. Then, for every real-valued function $f$ on $Y$,

${\sum }_{j=1}^{m}q(y_j)\rho (y_j)f(y_j)={\sum }_{j=1}^{m}p(y_j)f(y_j)\mathrm{.}$

In particular, ${\sum }_{j=1}^{m}q(y_j)\rho (y_j)=1$. This is a finite response identity; it asserts no change-of-measure result on an arbitrary trajectory space.

A probability law assigns total mass one and sums its point masses over finite events.

A finite response policy has normalized masses on its fixed support.

Finite sums are defined by recursion on their upper index.

Fix a nonempty finite ordered prompt list $(q_1,\dots ,q_M)$ with no repeated prompt. For each prompt $q_{\mathrm{\ell }}$, take the finite truncated response set $Y_{q_{\mathrm{\ell }}}$, ordered policy support $B_{q_{\mathrm{\ell }}}$, and policy family ${\pi }_{\theta }(\cdot \mid q_{\mathrm{\ell }})$ from the generation protocol, with open parameter domain $U$. Fix a reference probability mass function ${\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(\cdot \mid q_{\mathrm{\ell }})$ that is positive on exactly $B_{q_{\mathrm{\ell }}}$, a finite reward function $r_{q_{\mathrm{\ell }}}:B_{q_{\mathrm{\ell }}}\to \mathbb{R}$, an initial parameter ${\theta }_0\in U$, group size $G\ge 2$, a positive integer number $T$ of outer iterations, a positive integer number $K$ of inner steps per outer iteration, a clipping threshold $ϵ\in (0,1)$, a penalty weight $\beta \ge 0$, and positive step sizes ${\eta }_{t,k}$ for $1\le t\le T$ and $1\le k\le K$. The prompt weights are uniform. Response draws, reward and policy-mass evaluations, scalar arithmetic, square roots, logarithms and comparisons are supplied terminating exact operations with finite per-call costs. Draws return supported responses with the specified independent law. Also supply an exact total domain oracle $M_U:{\mathbb{R}}^d\to \{0,1\}$, returning $1$ exactly on $U$, and an exact objective-gradient oracle: given the frozen outer-iteration data and a parameter in $U$, it returns the Euclidean gradient of $F_t$ when that total derivative exists and returns undefined-gradient otherwise. Both oracles terminate on every call with finite per-call cost. The gradient oracle includes the fixed finite objective data and any policy evaluations needed for its decision. This is a supplied-oracle model; it asserts neither an algorithm for deciding differentiability of arbitrary functions nor a general membership algorithm for arbitrary open sets.

At outer iteration $t$, freeze ${\theta }_{t-1}$ and, for each prompt $q_{\mathrm{\ell }}$, draw $G$ independent responses $Y_{\mathrm{\ell },1},\dots ,Y_{\mathrm{\ell },G}$ from ${\pi }_{{\theta }_{t-1}}(\cdot \mid q_{\mathrm{\ell }})$. Compute the finite rewards $R_{\mathrm{\ell },i}:=r_{q_{\mathrm{\ell }}}(Y_{\mathrm{\ell },i})$, their mean

${\bar{R}}_{\mathrm{\ell }}:=\frac{1}{G}{\sum }_{i=1}^G{R}_{\mathrm{\ell },i},$

and their population standard deviation

$s_{\mathrm{\ell }}:=\sqrt{\frac{1}{G}{\sum }_{i=1}^G(R_{\mathrm{\ell },i}-{\bar{R}}_{\mathrm{\ell }}{)}^2}\mathrm{.}$

Set $A_{\mathrm{\ell },i}:=(R_{\mathrm{\ell },i}-{\bar{R}}_{\mathrm{\ell }})\mathrm{/}{s}_{\mathrm{\ell }}$ when $s_{\mathrm{\ell }}>0$, and set $A_{\mathrm{\ell },i}=0$ for every $i$ when $s_{\mathrm{\ell }}=0$. Hold the responses, rewards, and advantages fixed through the $K$ inner steps. For a candidate parameter $\theta \in U$, use the sequence-level ratio

${\rho }_{\mathrm{\ell },i}(\theta ):=\frac{{\pi }_{\theta }(Y_{\mathrm{\ell },i}\mid q_{\mathrm{\ell }})}{{\pi }_{{\theta }_{t-1}}(Y_{\mathrm{\ell },i}\mid q_{\mathrm{\ell }})}\mathrm{.}$

The denominator is positive. Define $\mathrm{clip}(x,1-ϵ,1+ϵ):=\min (1+ϵ,\max (1-ϵ,x))$, and use the exact finite-distribution forward KL penalty

$D_{\mathrm{K}\mathrm{L}}({\pi }_{\theta }(\cdot \mid q_{\mathrm{\ell }})\mathrm{\parallel }{\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(\cdot \mid q_{\mathrm{\ell }})):={\sum }_{j=1}^{n_{q_{\mathrm{\ell }}}}{\pi }_{\theta }(b_{q_{\mathrm{\ell }},j}\mid q_{\mathrm{\ell }})\log \frac{{\pi }_{\theta }(b_{q_{\mathrm{\ell }},j}\mid q_{\mathrm{\ell }})}{{\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(b_{q_{\mathrm{\ell }},j}\mid q_{\mathrm{\ell }})},$

where $(b_{q,1},\dots ,b_{q,n_q})$ is the ordered support from the generation protocol. The empirical objective is

$F_t(\theta ):=\frac{1}{M}{\sum }_{\mathrm{\ell }=1}^M[\frac{1}{G}{\sum }_{i=1}^G\min \{{\rho }_{\mathrm{\ell },i}(\theta )A_{\mathrm{\ell },i},\mathrm{clip}({\rho }_{\mathrm{\ell },i}(\theta ),1-ϵ,1+ϵ)A_{\mathrm{\ell },i}\}-\beta D_{\mathrm{K}\mathrm{L}}({\pi }_{\theta }(\cdot \mid q_{\mathrm{\ell }})\mathrm{\parallel }{\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(\cdot \mid q_{\mathrm{\ell }}))]\mathrm{.}$

For each outer iteration, set ${\theta }^{(0)}:={\theta }_{t-1}$. For each inner step $k$, call the supplied objective-gradient oracle at ${\theta }^{(k-1)}$. If it returns a gradient, form the proposed update

${\theta }^{(k)}:={\theta }^{(k-1)}+{\eta }_{t,k}\mathrm{\nabla }{F}_t({\theta }^{(k-1)})$

and call $M_U$ at that proposal. If $M_U$ returns $1$, apply it; the stipulated fixed positive support then holds on $U$. If the gradient oracle returns undefined-gradient, stop and return the last valid parameter with status undefined-gradient. If $M_U$ returns $0$, stop and return the last valid parameter with status invalid-update. After $K$ successful inner steps set ${\theta }_t:={\theta }^{(K)}$ and continue to the next outer iteration. After $T$ successful outer iterations return ${\theta }_T$ with status complete. This procedure asserts no monotone improvement, unbiasedness, or convergence guarantee.

Finite group-relative updates preserve admissibility and have bounded oracle calls ↗: proves valid-parameter and finite-objective properties, finite termination, and the response-draw and gradient-attempt bounds in the supplied-oracle model.

The finite truncation, response sets, policy support, and prompt-wise probability masses.

The differentiable policy family and fixed positive support convention.

For positive finite response laws, the sequence-level probability ratio is the exact finite change-of-measure factor before clipping.

The finite sums used for group averages and the exact finite-distribution KL.

The probability laws that govern the finite response draws.

For every input of the finite group-relative policy-update procedure, under its supplied exact terminating operation and oracle model, every formed advantage, sequence ratio and objective value at a parameter in $U$ is a finite real number. Zero group standard deviation uses the stated zero-advantage branch, without division by zero. The last valid parameter always lies in $U$ and retains the stipulated fixed positive support.

The procedure terminates with one of its specified statuses after at most $TMG$ response draws, $TMG$ reward evaluations, $TK$ objective-gradient attempts and $TK$ domain-oracle calls. An undefined gradient returns the previous valid parameter with status undefined-gradient; a rejected candidate returns it with status invalid-update; if all iterations succeed it returns ${\theta }_T\in U$ with status complete. All these bounds hold pathwise and allow early exit. The work consists of finite arithmetic over the prescribed finite lists and the sum of the finite costs of the actual supplied calls. In particular it is finite, but no uniform bound on the internal cost of arbitrary objective-gradient or open-set membership oracles is claimed. No unbiasedness, monotone-improvement or convergence conclusion is asserted.

Finite-budget group-relative policy update: gives the finite loops, full clipped objective and exact gradient/domain oracle model.

Fix a prompt $q$, an open parameter set $U\subseteq {\mathbb{R}}^d$, and the finite response policy with nonempty fixed support $(b_1,\dots ,b_m)$ and score vectors $S_{\theta }(q,b_j)$ from the generation protocol. For any fixed finite reward function $r$ on that support, define

$J(\theta ):={\sum }_{j=1}^m{\pi }_{\theta }(b_j\mid q)r(b_j)\mathrm{.}$

Then, for every $\theta \in U$,

${\mathbb{E}}_{\theta }[S_{\theta }(q,Y)\mid q]=0,{\mathbb{E}}_{\theta }[r(Y)S_{\theta }(q,Y)\mid q]={\mathrm{\nabla }}_{\theta }J(\theta )\mathrm{.}$

The finite truncated response law, fixed support, and policy score.

The fixed-support differentiable policy convention and logarithmic score vector.

This finite proof uses only the normalized mass function and finite sums. It uses no trajectory law, dominated interchange, conditional expectation, or choice principle.

Fix a prompt $q$, a parameter $\theta$ in the open domain of its finite response policy, a finite real reward function $r$ on the policy support, and an integer $G\ge 2$. Let $Y_1,\dots ,Y_G$ be independent responses with common law ${\pi }_{\theta }(\cdot \mid q)$, let $R_i:=r(Y_i)$, let $S_i:={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(Y_i\mid q)$, and set $\bar{R}:=G^{-1}{\sum }_{j=1}^G{R}_j$ and $J(\theta ):={\mathbb{E}}_{\theta }[r(Y)\mid q]$. Then ${\mathbb{E}}_{\theta }[\frac{1}{G}{\sum }_{i=1}^G(R_i-\bar{R})S_i\mid q]=(1-\frac{1}{G}){\mathrm{\nabla }}_{\theta }J(\theta )\mathrm{.}$ If instead ${\bar{R}}_{-i}:=(G-1{)}^{-1}{\sum }_{j\mathrm{\ne }i}{R}_j$, then ${\mathbb{E}}_{\theta }[\frac{1}{G}{\sum }_{i=1}^G(R_i-{\bar{R}}_{-i})S_i\mid q]={\mathrm{\nabla }}_{\theta }J(\theta )\mathrm{.}$

The finite response policy, support, score vector, and expectation convention.

The finite score has zero mean and its reward-weighted mean is the gradient of expected reward.

This identity covers unnormalized same-policy centering and the leave-one-out center. It does not cover division by a random group standard deviation, clipped probability ratios, or samples reused from a frozen old policy; none of those modifications inherits an unbiasedness claim from this calculation alone.

The finite prompt set, response support, token budget, truncation marker, verifier, reward rule, and sampling policy define the distribution to which an evaluation result applies. An empirical pass@1 is the observed fraction of prompts whose single designated sample is correct; oracle pass@N is the fraction with at least one correct response among N candidates; verifier-selected accuracy is the fraction correct among returned responses the verifier accepts. This last fraction is defined only when at least one returned response is accepted; it is undefined when none is accepted. These statistics need not agree, because the verifier can accept an incorrect response, reject a correct one, or select an incorrect candidate even when another candidate in the group is correct.

The proved group-score identity applies only to unnormalized centering under independent draws from the same finite policy. The finite-budget group update additionally divides by a random group standard deviation, clips a sequence-level policy ratio, and reuses samples from a frozen old policy for several inner steps. The identity alone proves no unbiasedness, monotone policy improvement, or convergence claim for that procedure.

For a general finite-horizon offline MDP with fixed stationary target and behavior policies, the cited trajectory-ratio lemma assumes the Axiom of Choice, a shared fixed initial state and transition/reward law, full-horizon absolute continuity, and integrability of the target return or other function being reweighted. Clipping or self-normalization alters the weights, so that exact change-of-measure identity alone does not establish the corresponding clipped or self-normalized equality or a generic offline-policy safety or performance guarantee. A verifier or benchmark score is an evaluation signal and does not certify a mathematical proof.

The budgeted rejection and best-of-N procedures.

The finite independent and adaptive success bounds and false-acceptance union bound.

The finite sequence-ratio, group-normalized, clipped update procedure.

The exact scope of the unnormalized group-center identity.

The general finite-horizon trajectory ratio under AC and full coverage.

AC asserts that every family of nonempty sets has a choice function.

Absolute continuity means every behavior-null measurable set is also target-null.

A real function is integrable when the integral of its absolute value is finite.

The fixed-start finite MDP, common transition/reward law, stationary policies, and full-coverage setup.