Reinforcement learning with verifiable rewards trains a language model by checking each of its answers with an automatic grader, such as a unit test or an exact-match parser. The approach works well on math and code because the grader is free and never wrong. In most domains that matter, though, the only trustworthy grader is expensive: a frontier model scoring a clinical answer against a rubric, a human expert reading a proof. Paying that grader for every sampled answer makes the verification bill grow linearly with training length. The obvious workaround is to let the model grade itself. That fails in a predictable way: the generator learns to produce answers its own grader accepts but the true grader would reject.
This note proposes a small change borrowed from mechanism design. The model grades its own answers. An expensive external auditor re-checks only a random, shrinking fraction $q_t$ of the answers the model accepted. When an audit catches a false acceptance, the penalty is scaled by $1/q_t$, so the expected punishment for fooling the self-grader stays the same even as audits become rare. This mirrors the logic of K-Implementation: a promised transfer that sits off the equilibrium path costs little once agents stop deviating. The claim is that deterrence, meaning the incentive not to hack, is then independent of the audit rate. The audit rate controls only gradient variance. The total verification cost becomes sublinear in training steps exactly when the self-grader's false-acceptance rate decays, which is an explicit and falsifiable condition.
Core Claim
Consider one training step. The policy produces a response and a self-grade $\hat s \in \{0,1\}$. The true, costly grade is $s$. If $\hat s = 1$, the auditor is called with probability $q_t$. A caught false positive ($\hat s = 1$, $s = 0$) receives reward $-\bar\lambda / q_t$ instead of $+1$, where $\bar\lambda$ is a fixed deterrence constant. A false positive therefore has expected reward
$$ \mathbb{E}[r \mid \hat s=1, s=0] = (1-q_t)\cdot 1 - q_t \cdot \frac{\bar\lambda}{q_t} = 1 - q_t - \bar\lambda , $$
which lies below the honest reward of $0$ whenever $\bar\lambda > 1$, for every $q_t$. So in expectation the generator gains nothing from exploiting its own grader, however rarely audits happen.
The price is variance. The variance of the penalty term is about $f_t \bar\lambda^2 / q_t$, where $f_t$ is the fraction of self-accepted answers that are actually wrong. Keeping this variance bounded requires $q_t \propto f_t$. The cumulative audit cost $C(T) = \sum_t q_t N_t^{+}$, with $N_t^{+}$ the number of self-accepted rollouts at step $t$, is then $o(T)$ if and only if $\sum_t f_t = o(T)$.
This is the language-model analogue of the "historical inertia" in Steering No-Regret Learners to Optimal Equilibria. There, early payments make the target behavior self-sustaining, and payments can then be withdrawn. Here, early dense audits make honest self-grading self-sustaining. The rate $f_t$ can be estimated without bias from the audits themselves, so the schedule adapts online and needs no prior knowledge of learning rates. That prior knowledge is a stated limitation of Game Redesign in No-regret Game Playing.
Relation to Prior Work
Three groups of papers play different roles here.
The steering literature supplies the logic. Game Redesign in No-regret Game Playing makes a target action strictly dominant by penalizing alternatives, so that cost vanishes once the target is played. Zhang et al. show that sublinear, but not constant, budgets are necessary and sufficient to steer learners in extensive-form games (Steering No-Regret Learners to a Desired Equilibrium). Both assume the mediator knows the agents' utilities and that the agents are naive. Our setting reverses the second assumption. The generator is exactly the "strategic agent" the open-problems list flags, because gradient pressure pushes it toward whatever the self-grader rewards. Utilities are also not known in advance, since $f_t$ is learned from audits.
The self-verification literature motivates the approach and constrains it. Trust, But Verify (RISE) trains one policy to both solve and grade, and finds that grading ability improves faster than solving ability. That gap is why we expect $f_t$ to fall. RISE, however, queries the true grader on every rollout. Rubric Curriculum RL exploits the same gap in non-verifiable domains through self-judged pairwise tournaments. It treats judging cost as free and reports that static rubric judges are hacked within about 200 steps. That result is the failure our deterrence term is meant to prevent.
Two further papers constrain the design. Anchored Policy Optimization shows that heavy penalties on non-target outputs can collapse exploration. Large rare penalties are therefore a real risk, not a theoretical nicety, and we must measure entropy. Rollout allocators such as VIP (Adaptive Rollout Allocation) and CBS (Contextual Rollout Bandits) decide how many samples each prompt gets while the grader is free. Our method decides which samples the costly grader sees, so the two are complementary.
Finally, Rubrics as Rewards supplies the non-verifiable testbed and the auditor protocol: instance-specific rubric checklists scored by a strong judge.
Research Program
We would build audited self-reward on top of GRPO-style training, which scores each rollout relative to the other rollouts sampled for the same prompt. Each rollout is followed by a self-grading turn, as in RISE. Only self-accepted rollouts are eligible for audit, because hacking manifests as false acceptances and self-rejected answers get reward 0 anyway. The audit rate is set as $q_t = \max(q_{\min}, c\,\hat f_t)$, where $\hat f_t$ is an exponentially weighted, inverse-probability estimate of the false-acceptance rate.
The inverse-probability penalty enters as a separate loss term outside the per-prompt group normalization. Otherwise one heavy penalty would distort the advantages of the whole group. It is clipped at a ceiling $\Lambda$, and the resulting bias is logged. The grading turns are trained only on audited labels, so the grader receives no direct reward for leniency.
On the theory side we would formalize the sublinearity condition above. We would also characterize what happens when clipping at $\Lambda$ binds: deterrence then weakens to $\min(\bar\lambda, q_t\Lambda)$, which predicts a critical audit rate below which hacking returns.
Baselines
The naive reference is pure self-reward with no audits after a short warm-up. We expect it to hack, and we will measure how fast.
The linear-cost upper reference is RISE with the auditor queried on every rollout. On AIME 2024, RISE-7B reaches 12.5% accuracy, and RISE-1.5B reaches 74.5% self-verification accuracy against 26.8% for standard RL (Trust, But Verify). We rerun it at our scale rather than import these numbers. Beating RISE means coming within two points of its accuracy while using an order of magnitude fewer auditor calls, with a fitted cost exponent clearly below one.
The strongest competitor at equal budget is uniform subsampling of auditor calls on the same decaying schedule, with audited labels used as ordinary rewards and no inverse-probability scaling. This is the key ablation that isolates our ingredient. It sees exactly the same audits, so any gap between it and our method is attributable to the deterrence scaling.
We also run an uncertainty-triggered auditor that queries the grader where the self-grade is least confident. Because VIP is the strongest allocator in the file, we additionally run VIP with the auditor restricted to the same call budget. VIP reports +12.3 Pass@32 and +6.3 Mean@32 on AIME 2024 for Qwen2.5-Math-1.5B with RLOO (Adaptive Rollout Allocation).
In the rubric domain, the reference is RaR with a full judge. RaR-Implicit reports 31.2 on HealthBench (Rubrics as Rewards), and RcRL reports a 14.6% improvement on the full set (Rubric Curriculum RL).
All methods share the base model, prompts, rollout count, optimizer settings, and an equal hyperparameter-search budget. All budget-limited methods are matched on total auditor calls.
Why not just…?
Why not just train a reward model on early judge labels and freeze it? A frozen grader is a fixed target, and the generator's distribution moves away from it. Rubric Curriculum RL reports that static rubric judges are exploited within about 200 steps, with output entropy falling to 73%. We include a frozen-reward-model baseline trained on the same number of auditor labels our method spends by step 500. If it matches our final hidden-hacking rate, the deterrence mechanism is unnecessary, and we would say so.
Why not just audit where the self-grader is uncertain? This is a genuine threat on accuracy per call, since active selection is often efficient. The problem is that a successful hack is precisely an answer the grader confidently accepts, and uncertainty sampling systematically never audits those. Our experiments log true correctness for every rollout for analysis only. If uncertainty sampling nevertheless keeps false acceptances low, we would adopt a hybrid: uncertainty-weighted $q$ with inverse-probability penalties, which keeps the incentive unbiased.
Why not just anneal the audit rate without the $1/q_t$ penalty? This is the uniform-subsampling baseline. Under it the expected penalty for a false acceptance is $q_t\bar\lambda$, which goes to zero, so the analysis predicts that hacking resumes once $q_t$ drops below roughly $1/(1+\bar\lambda)$. If this baseline does not degrade, the core claim is wrong.
Why not just use VIP or CBS? Both assume the grader is free and choose where to spend rollouts, not grader calls. VIP's analysis also requires a zero KL penalty. We test them under a matched auditor budget and also stack VIP with our auditor. The claim is not that they fail, but that without deterrence, restricting their grader budget reintroduces hacking.
Proposed Experiments
The first stage is a controlled verifiable setting. We train Qwen2.5-Math-1.5B and a 7B model on MATH-Hard and evaluate on MATH-500 and AIME 2024/2025. The exact-match checker plays the role of the "expensive" auditor, and every call to it is counted. Because true correctness is also cheap to compute here, we log it for all rollouts purely for measurement. This yields the hidden false-acceptance rate $f_t$ that the method can only estimate. The outputs are accuracy against cumulative auditor calls, the fitted exponent $\alpha$ in $C(T) \approx T^\alpha$, the trajectory of $f_t$, gradient-norm spikes, and output entropy.
The second stage moves to a domain without a cheap checker. We train on RaR-Medicine prompts with their 7–20 item rubrics. A strong judge scoring the rubric is the auditor, and the policy grades itself against the same rubric. Evaluation uses HealthBench plus a held-out, stronger judge and a small blinded human panel to detect hacking that the auditor itself might miss.
Three checks decide the question. First, the deterrence ablation: at identical audit schedules, only the inverse-probability variant should keep $f_t$ decaying. Second, the sublinearity test: $\alpha$ should be clearly below one while accuracy stays near the RISE reference. If instead $f_t$ plateaus, the theory predicts linear cost, and we report that as a negative result on when self-verification can replace an oracle. Third, the variance test: we sweep the clipping ceiling $\Lambda$. The expectation is that $\Lambda$ too low lets hacking back in, $\Lambda$ too high causes entropy collapse, and the working range between them is where the method is usable.
References
- k-Implementation
- Steering No-Regret Learners to a Desired Equilibrium
- Game Redesign in No-regret Game Playing
- Trust, But Verify: A Self-Verification Approach to Reinforcement Learning with Verifiable Rewards
- Rubric Curriculum RL: Exploiting the Generation-Verification Gap in Non-Verifiable Domains
- Anchored Policy Optimization: Mitigating Exploration Collapse via Support-Constrained Rectification
- Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards
- Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards
- Rubrics as Rewards: Reinforcement Learning Beyond Verifiable Domains