When a language model is trained to be more factual, something has to score its outputs. The most reliable scorers break a response into atomic claims, meaning short self-contained statements such as "she was born in Lyon," and check each claim against evidence. They are too slow to run on every claim during training: VeriFastScore reports that standard pipelines can take more than 100 seconds per response. Any practical training loop therefore checks only some claims, or relies on a cheap approximate checker. That creates a game. The model being trained is an optimizer that will move its errors to wherever the checker does not look. If the audit always targets the rarest entities, the last paragraph, or whatever a cheap checker flags, the model can learn to hide fabrications in the claims that are never examined.
This note proposes treating budgeted factuality checking as an audit-design problem from mechanism design, the study of rules that stay robust when the party being scored optimizes against them. Each atomic claim is sent to an expensive verifier with a known probability. The penalty for an unsupported claim that gets audited is reweighted by the inverse of that probability, and a cheap checker scores every claim as a control. Under this rule the expected penalty for a fabrication is the same wherever in the response the model puts it, so no claim is safe to hallucinate. The audit probabilities can still concentrate the budget where errors are likely. The two-sentence version is this: deterministic budgeted checking gives a model trained against it blind spots to exploit, while randomized checking with reweighted penalties removes them in expectation. The research question is whether that difference shows up in actual training runs, and at what budget.
Core Claim
Randomized mechanisms beat deterministic ones in auctions for a specific reason: a fixed cutoff can be exploited by agents who know it. Regret Minimization and Separation in Multi-Bidder, Multi-Item Auctions shows that sampling the reserve price from a continuous distribution keeps bidders from shading their bids to sit just above a known threshold. Randomized Learning-Augmented Auctions with Revenue Guarantees shows that replacing a hard threshold built on a learned prediction with a smooth randomized allocation curve trades consistency (performance when the prediction is right) against robustness (performance when it is wrong). We borrow the logic of these papers, not their theorems. In factuality training the "agent" is the policy model, the "cutoff" is the rule that decides which claims get verified, and "shading" is error placement.
Let a response decompose into atoms $a_1,\dots,a_n$. Each atom has an unknown hallucination indicator $h_i \in \{0,1\}$, a cheap-checker score $s_i \in [0,1]$, and an expensive-verification cost $c_i$. The auditor draws $D_i \sim \text{Bernoulli}(q_i)$ independently, subject to the budget $\sum_i q_i c_i \le B$, and reports
$$\hat H = \sum_{i=1}^{n} \Big[ s_i + \frac{D_i}{q_i}(h_i - s_i) \Big].$$
This estimator is unbiased for the true hallucination count $\sum_i h_i$ whenever every $q_i>0$, however wrong the cheap checker is. Its variance is $\sum_i \frac{1-q_i}{q_i}(h_i-s_i)^2$, which yields the standard allocation $q_i \propto |h_i - s_i|/\sqrt{c_i}$: audit most where the cheap checker is most likely to be wrong per unit cost.
The estimator itself is classical survey sampling, and we do not claim it as new. What is new is the setting and the analysis around it. First, we characterize how deterministic audit rules, meaning any rule with $q_i=0$ on some atoms, are exploited by a policy trained under reinforcement learning. Second, we set $q_i$ by mixing a learned error predictor with a uniform floor $q_{\min}$. This mirrors the consistency–robustness trade-off: a sharp predictor lowers variance, and the floor bounds variance when the policy learns to shift its errors into atoms the predictor considers safe. Third, we test the prediction empirically, end to end.
A second avenue of manipulation is granularity. A precision-style reward such as the FActScore fraction can be raised by padding a response with trivially true atoms. We therefore score $\hat H$ as an absolute count, paired with a separate reward for informative supported content, and we track padding and hedging as explicit failure modes.
Research Program
The work has three parts.
The first part builds the audit. The expensive verifier is the FActScore Retrieve→LM+NP pipeline against Wikipedia, which Min et al. report agrees with human experts to within a 2% error rate. The cheap checker is a single-pass extractor-verifier in the style of VeriFastScore. The error predictor estimating $|h_i - s_i|$ is a small model that uses the features Min et al. identify as predictive of hallucination: how frequent the entity is and how late in the response the claim appears. Atoms come from the same decomposer for all conditions, so decomposition is held fixed.
The second part is analysis. We will state, and test with synthetic policies, the claim that any audit rule with unaudited atoms admits a policy that achieves a perfect audited score while hallucinating on those atoms. We will then characterize how the variance of $\hat H$, and with it the noise in the reward gradient, scales with $q_{\min}$ and with the quality of the error predictor.
The third part is the training study. A 7–8B open model is trained with reinforcement learning on FActScore-style biography prompts, with every audit rule given the same expensive-verification budget. The rules differ only in how they spend it.
Baselines
The naive reference point is the untrained base model, together with a model trained against the cheap checker alone ($q_i=0$ everywhere). The cheap-only run shows what happens when the policy is free to exploit an approximate scorer. VeriFastScore reports example-level correlation $r=0.80$ and system-level $r=0.94$ with VeriScore, at a 6.6x speedup. That is good enough for ranking systems and loose enough at the example level for a policy to exploit.
The upper bound is exhaustive expensive verification of every atom. We expect it to be the most faithful reward and to cost roughly $1/B$ times more verifier compute. We run it once to locate the ceiling, and beating it is not the goal. Matching it within noise at a fraction of the compute counts as success.
The strongest deterministic competitor is risk-targeted auditing. The same error predictor ranks atoms, and the top atoms are verified until the budget runs out. This is the obvious engineering answer and the most sample-efficient non-random rule, so it is the comparison that matters most.
The key ablation is uniform random auditing: the same estimator with $q_i$ constant. It isolates whether the learned allocation adds anything beyond randomization itself.
The deployment-time comparison is Language Models with Conformal Factuality Guarantees. That method calibrates a threshold on claim confidence and deletes claims below it, and it reports raising biography factuality from about 30% to 80% while keeping about half of the original claims. It is a filter applied after generation, not a training signal, so we apply it to the outputs of every trained model. This tests whether better training reduces how much conformal filtering has to delete.
All runs share prompts, decomposer, verifier, RL algorithm, steps, and a fixed hyperparameter-search budget. The randomized rule is considered to have beaten risk-targeted auditing if it achieves higher exhaustively measured FActScore on held-out prompts with no loss in the number of supported informative atoms, and if its errors do not concentrate in low-audit-probability atoms. Beyond the base-model references in Min et al. (ChatGPT at 58.3% and PerplexityAI at 71.5% FActScore on biographies), we found no reported result on Lacuna for RL training under a budgeted factuality audit. We will therefore report all trained conditions ourselves.
Why not just…?
Why not just verify everything with a fast single-pass checker? This is the most serious practical alternative, and we include it as the cheap-only condition. A fast checker is a fixed, learnable function, and a policy optimized against it is exactly the setting where its blind spots get found. The 0.80 example-level correlation leaves room for that. Our design does not discard the fast checker. It uses it as the control variate $s_i$, and the randomized audit then corrects its bias. If the cheap-only run shows no gap against exhaustive verification when both are scored by the expensive pipeline, then the exploitation premise fails at this scale, and we will report that as the result.
Why not just audit the riskiest claims deterministically? It spends the budget where errors are most likely, and against a fixed model it is probably more accurate than any random rule. The trouble starts when the model is trained against it. Error predictors built on entity rarity and position are features the policy controls, so the policy can learn to state shaky facts about frequent entities early in the response, where the auditor rarely looks. The decisive measurement is the distribution of exhaustively verified errors over audit-probability bins at the end of training. We predict that under deterministic auditing errors pile up in the never-audited bins, and that under randomized auditing they stay flat.
Why not just sample claims uniformly at random? Uniform sampling is already unbiased and already removes blind spots, so it may capture most of the benefit. That is a genuine threat to the allocation component of the proposal. The uniform-audit ablation answers it. If the learned allocation gives no measurable reduction in reward variance or improvement in final FActScore at equal budget, then the contribution reduces to "randomize, and reweight the penalty." That finding would still be useful, and we would report it plainly. We expect allocation to matter most at small budgets, where uniform sampling leaves many responses with zero audited atoms.
Why not just add a KL penalty or early stopping to limit reward hacking? These generic regularizers slow every kind of optimization equally, the useful kind included. We will tune the KL coefficient for every condition within the shared tuning budget. If the deterministic rule's error migration vanishes at a KL strength that does not hurt factuality gains, randomization is unnecessary in this regime, and the experiment will show that directly.
Proposed Experiments
The primary benchmark is FActScore biography generation with Wikipedia as the knowledge source, split by entity-frequency band. That split lets us see whether the rarity penalty and the late-position factuality decay documented by Min et al. move under each audit rule. Budgets are swept from 5% to 50% of exhaustive verifier cost.
Final evaluation always uses exhaustive expensive verification on held-out prompts, plus human checking of a stratified sample of atoms drawn especially from low-audit-probability bins. Reported metrics are FActScore, the absolute count of supported and unsupported atoms, the rate of hedged or vague statements, and the fraction of claims conformal filtering must delete to reach 80% factuality.
To test transfer, we evaluate trained models on long-form answers from A Claim Decomposition Benchmark for Long-form Answer Verification, where we found no reported numbers on Lacuna. We also check verifier calibration on WiCE. WiCE's finding that 54.7% of claims are partially supported is a reminder that the indicators $h_i$ themselves are noisy, so we will measure how that label noise affects the estimator's variance.
Two checks decide the outcome. The first is the exploitation test: under deterministic auditing, do verified errors migrate into unaudited atoms over training, and does randomized auditing prevent this at equal budget? The second is the efficiency test: does the randomized rule at budget $B$ reach the exhaustive-verification FActScore within noise, and does it beat uniform sampling at small $B$?
If the first check fails, the mechanism-design framing is not needed here. If the second fails, the proposal reduces to uniform random auditing. Either outcome is informative about how factuality rewards should be built.
References
- VeriFastScore: Speeding up long-form factuality evaluation
- Regret Minimization and Separation in Multi-Bidder, Multi-Item Auctions
- Randomized Learning-Augmented Auctions with Revenue Guarantees
- FActScore: Fine-grained Atomic Evaluation of Factual Precision in Long Form Text Generation
- Language Models with Conformal Factuality Guarantees
- A Claim Decomposition Benchmark for Long-Form Answer Verification
- WiCE: Real-World Entailment for Claims in Wikipedia