When a language model has to emit a tool call, a SQL query, or a logic formula, a common way to spend extra inference compute is to sample many candidates and let a reward model pick the best one. A reward model here means a learned scorer trained to predict which output a human would prefer. The trouble is that reward models are known to reward surface features such as length. On structured outputs there is a richer supply of surface features: key order, whitespace, quoting, optional arguments spelled out, longer string values, SQL written with extra aliases or parentheses. Larger sample budgets give the scorer more chances to find a candidate that is extreme on one of these features. We therefore expect selection to drift toward them as the budget grows.
This note proposes to measure that drift and to test a simple remedy. Every candidate is parsed and rewritten into a canonical normal form before any scoring. Candidates that mean the same thing are pooled, and the choice combines how many samples landed in each meaning-class with the reward model's score on the canonical rendering. The claim is testable and could fail. If canonicalization removes the drift and the reward model still adds accuracy beyond simple voting over meaning-classes, then reward-model bias on structured tasks is mostly a formatting artifact, and it can be engineered away cheaply. If canonical voting alone does just as well, the reward model contributes nothing useful on these tasks, and that is worth knowing too.
Core Claim
On structured-output tasks where only a syntax check and a learned verifier are available at test time, reward-model Best-of-N shows inference-time over-optimization. As the number of samples $N$ grows, the selected outputs become more extreme on format and verbosity features and accuracy flattens or falls. Syntax-guaranteeing decoding alone does not fix this, because it guarantees that outputs are valid, not which valid output gets chosen. Scoring canonical forms, and aggregating over equivalence classes, should restore monotone scaling at equal or lower verifier cost.
What Prior Work Establishes and Leaves Open
Three papers motivate the concern that the scorer steers search toward its own blind spots, and all three study free-form text.
- Can 1B LLM Surpass 405B LLM? maps compute-optimal test-time search across model sizes. It documents that process reward models (scorers of intermediate reasoning steps) reward length, over-criticize valid unusual steps, and break down on outputs from unfamiliar model families. Its evidence comes entirely from MATH-500 and AIME24.
- Reward Model Generalization for Compute-Aware Test-Time Reasoning bounds the success of search by the verifier's generalization error. It shows that the required sample budget grows exponentially as that error rises. It also assumes unconstrained math generation. - On the Robustness of Reward Models traces verbosity hacking to hidden-state norm growth in Bradley-Terry reward models and fixes it with a sum-to-zero regularizer during training. It evaluates only chat benchmarks.
We take their diagnosis and ask whether it transfers to machine-readable outputs, where "surface" has a precise meaning: anything that changes the string but not the parsed meaning.
Two lines of work supply the machinery we reuse, and neither scores meaning.
- Mitigating Bias in Locally Constrained Decoding via Tractable Proposals shows that masking invalid tokens one step at a time can trap generation in dead ends. It fixes this with automaton lookahead (GCD) at about 1.1x overhead, reaching 100% constraint satisfaction on xLAM, but it uses no semantic verifier.
- CRANE shows that forcing a grammar from the first token hurts reasoning. Its fix is to let the model reason freely and constrain only a delimited answer block, reaching 46.3% on FOLIO with Llama-3.1-8B, versus 39.4% for constrained generation and 32.0% for unconstrained chain-of-thought. It uses no reward model and no search.
We use GCD- and CRANE-style decoding to generate candidates and study what happens when a reward model chooses among them.
T1 is the closest pipeline in structure. It hard-filters candidates with executable checks and then reranks the survivors with a distilled reward model. It does not ask whether the reranker is swayed by formatting, and it treats candidates as strings rather than meaning-classes.
Scaling Test-time Compute for LLM Agents constrains our design. It finds that list-wise judging beats point-wise scoring and that verification is the bottleneck on GAIA, so list-wise judges must appear among our verifiers.
An Empirical Analysis of Compute-Optimal Inference supplies the weighted-majority-voting and REBASE comparisons that our aggregation rule extends.
Research Program
A paired invariance test for verifiers. The first component is a diagnostic built from gold answers in the Berkeley Function Calling Leaderboard (BFCL, code in ShishirPatil/gorilla), xLAM, and Spider. For each gold call or query we write two kinds of rewrite.
- Meaning-preserving rewrites change the string but not the parsed meaning. For JSON they reorder keys, change whitespace and quote style, and spell out default-valued arguments. For SQL they rename aliases, add redundant parentheses, and change keyword case.
- Meaning-changing but format-preserving rewrites keep the formatting but alter the meaning: a wrong argument value, swapped arguments, or a changed literal in a WHERE clause.
A good verifier should give nearly the same score across the first kind and clearly different scores across the second. We report two quantities per verifier. The invariance gap is the mean absolute score change under meaning-preserving rewrites. Sensitivity is the pairwise accuracy at ranking gold above its meaning-changed variant. We also regress verifier score on surface statistics (argument count, total string-field length, nesting depth, token count) within sets of candidates that share a meaning-class.
Measuring drift under real sampling. The second component measures drift. For $N \in \{1, 4, 16, 64, 256\}$ we plot task accuracy against $N$, using BFCL's AST (parsed-structure) matching and execution checks and Spider's execution match. On the same axis we plot the surface statistics of the selected output. Propagation of bias means these statistics move monotonically with $N$ under reward-model selection but not under random selection among valid candidates.
Canonical-class selection. The third component is the remedy. We sample candidates with GCD, or with CRANE-style free reasoning followed by a constrained answer block. Each answer is parsed, and a deterministic normalizer maps it to a canonical form. For JSON, the normalizer sorts keys, fills defaults, and fixes a single rendering. For SQL, it resolves aliases, normalizes casing, and applies a fixed pretty-printer. The canonical forms define equivalence classes $c$ with counts $n_c$. We score one canonical rendering per class with the verifier $r$ and select
$$c^\star = \arg\max_c \left[\log n_c + \beta \, r(\mathrm{canon}(c))\right],$$
where $\beta \ge 0$ is tuned on a held-out split. Setting $\beta = 0$ gives canonical majority voting. A very large $\beta$ gives canonical Best-of-N. Because the verifier sees only one rendering per class, verifier calls fall from $N$ to the number of distinct classes.
Reasoning traces. For CRANE-style candidates we compare scoring the canonical answer alone against scoring the answer together with its free-text reasoning trace. The trace reintroduces exactly the verbosity channel that Hong et al. identified.
Models and verifiers. Policies span small and mid-sized open models (1B–3B Llama-3.2, Qwen2.5-7B). Zhou et al. report that the benefit of verifier guidance depends strongly on model size, so we expect the effects to differ across this range. We use three verifiers:
- a Bradley-Terry reward model trained on Skywork-80K, with and without the sum-to-zero regularizer;
- a generative point-wise judge;
- a list-wise judge.
Baselines
Naive references. The first is greedy decoding under GCD with a canonical grammar. The second is uniform random choice among valid candidates at each $N$. The random choice matters most: any trend in surface statistics under reward-model selection is measured against it.
Strongest existing method. This is reward-model Best-of-N over GCD-valid candidates, in the style of T1 but with the grammar replacing the executable filter. It combines the best syntax guarantee in the file (Dang et al.: 100% constraint satisfaction on xLAM at about 1.1x overhead) with the standard selection rule of Zhou et al.. We run it with the list-wise judge as well, since Scaling Test-time Compute for LLM Agents finds list-wise judges stronger.
No reported result was found on Lacuna for reward-model Best-of-N on BFCL, xLAM, or Spider. The only reference points in the file for these benchmarks are:
- BFCL: above 90% on simple function calls for top models, and roughly 12% on the memory category.
- FOLIO: CRANE's 46.3% with Llama-3.1-8B, which anchors the reasoning-then-answer setting.
We therefore reproduce all baselines ourselves on identical prompts, identical sample pools, and identical tuning splits. Every method selects from the same $N$ samples.
Weighted majority voting and REBASE. We include weighted majority voting over raw strings, following Wu et al., and REBASE-style step pruning where a step structure exists.
Ablations isolating the key ingredient. Canonical-class selection with $\beta = 0$ tests whether voting alone suffices. Canonical Best-of-N with a very large $\beta$ tests whether canonicalization alone removes the bias. Raw-string scoring with class pooling tests whether pooling, rather than canonical rendering, does the work.
Success criterion. The proposal beats the strongest baseline if two things hold. First, its accuracy curve is non-decreasing in $N$ where reward-model Best-of-N flattens or declines. Second, at $N \ge 64$ it exceeds both reward-model Best-of-N and $\beta = 0$ voting by more than seed variance, at equal or lower verifier calls.
Why not just…?
Why not just use JSON mode or grammar-constrained decoding? Constrained decoding guarantees that every candidate parses. It says nothing about which valid candidate the verifier prefers. A loose grammar still permits reordered keys, spelled-out optional arguments, and long string values. There is a real threat, though: a tight grammar that forces a single canonical rendering removes most syntactic surface variance at generation time. We test this directly by running reward-model Best-of-N under a tight canonical grammar.
- If that closes the gap, the finding is simply "use tight grammars."
- If a gap remains, it should come from string-content verbosity and optional arguments. Canonicalization with default-filling removes those, and a grammar cannot.
Why not just execute the candidates? Where a sandbox and a gold outcome exist, execution is the right verifier, and we report it as an upper bound. At deployment, though, execution mostly reveals whether a call runs, not whether it matches user intent. Many calls also have side effects or depend on state; BFCL reports "failed to understand environment state" as the most common failure. T1 further notes that execution filters discard valid candidates whenever the check itself is buggy. Our setting is therefore the common case in which only a syntax check and a learned verifier are available. The execution upper bound tells us how much of the gap the method closes.
Why not just take a majority vote over parsed outputs? This is the most serious threat, and it is built into the method as the $\beta = 0$ case. If canonical voting matches the full rule at every $N$ and model size, we will report that the reward model adds nothing on these tasks. Two considerations complicate this.
- Enyu Zhou argues that correlated errors defeat voting. This applies most strongly to the policy's own systematic mistakes, which are exactly where a verifier could help.
- The size results of Zhou et al. suggest the verifier matters more for small models.
We therefore expect $\beta > 0$ to help mainly for the smaller models, and we will test that prediction.
Why not just retrain the reward model with the sum-to-zero regularizer? Hong et al. report a gain of nearly 8% on RM-Bench Hard accuracy and 40% shorter policy outputs. That fix targets length in chat. It requires retraining, and it is not designed to make scores invariant to key order or alias names. We include the regularized reward model as a verifier. If it passes the invariance test and does not drift, canonicalization is unnecessary for regularized models, and we would say so.
Decisive Checks
Does the bias propagate? The first check is the paired invariance test followed by the drift curves. Under reward-model Best-of-N, surface statistics of the selected output should rise with $N$ relative to random valid choice. The accuracy curve should bend at the same point. If neither happens on BFCL, xLAM, or Spider, the phenomenon does not transfer from free-form math and the remainder of the program is moot.
Where does the remedy sit? The second check places canonical-class selection between two references:
- the tight-grammar baseline, below it;
- the execution upper bound, above it.
We compare at matched samples and report verifier calls.
Does the reward model earn its place? The third check is the $\beta$ sweep, broken down by model size and verifier type. It separates three outcomes: the reward model helps once format is removed; it helps only for small models; or it never beats voting.
Does free-form reasoning reopen the verbosity channel? The last check compares scoring the canonical answer alone against scoring answer plus reasoning trace on FOLIO and GSM-Symbolic, starting from CRANE-style decoding. A drop in accuracy when the trace is included would show that the verbosity channel reopens.
References
- Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling
- Reward Model Generalization for Compute-Aware Test-Time Reasoning
- On the Robustness of Reward Models for Language Model Alignment
- Mitigating Bias in Locally Constrained Decoding via Tractable Proposals
- CRANE: Reasoning with constrained LLM generation
- T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models
- Scaling Test-time Compute for LLM Agents
- An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models
- The Berkeley Function Calling Leaderboard (BFCL): From Tool Use to Agentic Evaluation of Large Language Models