Finite truncated response spaces, correctness predicates, and verifiers

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.