Verification
Where should test-time compute go? Surprisal-guided selection in verifiable environments
- Where should test-time compute go?
- GPU kernel optimization as testbed
- What I ran
- Selecting by surprisal
- Why not just train more?
- When this works and when it doesn’t
- Can you skip evaluation with surprisal?
- What to do with this
- What this doesn’t cover
- Try it yourself
- Resources
- Citation
Where should test-time compute go?
Test-time adaptation shows strong results on reasoning and discovery tasks. TTT-Discover uses ~50 gradient steps to push past what base models can achieve. The practical question: does this generalize when the reward signal is dense and continuous, as in GPU kernel optimization?
Given a capable code-generation model, extra compute can go to more training (gradient adaptation), more samples (search), or smarter selection.
I tested all three on KernelBench using GPT-OSS-120B with LoRA adaptation. The full Best-of-N evaluation covered 20 L1 tasks. The primary selector comparison used five tasks across two seeds (L1 problems 4, 5, 12, 14, and 15, the first five IDs in the seed-42 eval split), and the adaptation comparison used small task subsets. In those small comparisons, sampling beat short adaptation, and selecting low-probability correct kernels beat selecting the model’s most confident ones.
GPU kernel optimization as testbed
KernelBench has 250 GPU kernel optimization tasks. Given a PyTorch operation, the model generates an efficient CUDA kernel. The compiler and hardware provide ground-truth feedback, functional correctness and continuous speedup (0x to 10x+), with no human judgment.
Dual-loop architecture. The outer loop trains a base policy via reinforcement learning with verifiable rewards (RLVR) on 80 tasks. The inner loop compares test-time strategies (TTT, Best-of-N, and selection mechanisms) against the same execution-grounded evaluator. Rollout matching does not account for the extra cost of gradient updates.
What I ran
I train a base policy using Group Relative Policy Optimization (GRPO) on 80 KernelBench L1 tasks with LoRA.LoRA (Low-Rank Adaptation): a parameter-efficient fine-tuning method that trains small rank-decomposed matrices instead of full model weights. Cuts trainable parameters by ~100x. The checkpoint achieves 98.4% correctness and 0.87x mean speedup. The subset comparisons start from the same checkpoint at temperature 0.25. The comparisons match rollout counts where stated, with training compute paid separately.
Best-of-N (K=64) samples 64 candidates per task and selects the fastest correct one. A five-task subset therefore uses 320 candidates; the full 20-task sweep uses 1,280.
Batch TTT (test-time training) takes 1–5 gradient steps with 32 rollouts per task per step, then selects a checkpoint with Best-of-Adaptation (BoA). The compute includes training as well as rollout generation and evaluation.
Selection strategies: Given K=64 samples per task, compare oracle, random, confidence-guided (highest log-probability), and surprisal-guided (lowest log-probability) selection.
Selecting by surprisal
I measure fast_1: the fraction of selected samples that are both correct and achieve speedup > 1x over the reference implementation. Surprisal is the negative sum of token log-probabilities.
| Strategy | fast_1 | std | Mean Speedup |
|---|---|---|---|
| Oracle (best correct) | 100% | 0% | 226.9x |
| Surprisal-guided-top3 | 100% | 0% | 139.0x |
| Surprisal-guided | 80% | 0% | 41.2x |
| Random correct | 59.2% | 2.7% | 30.0x |
| Confidence-guided | 50% | 14.1% | 11.6x |
Selection comparison on five tasks across two seeds (10 task-seed pairs). All selectors act on correctness-filtered candidates. fast_1 is the fraction of selected outputs faster than the reference. Matching the oracle on fast_1 does not match its mean speedup, 139.0x versus 226.9x.
Surprisal-guided beats confidence-guided by 30 percentage points (80% vs 50%, Cohen’s h = 0.64).Cohen’s h: an effect size for comparing two proportions. 0.2 = small, 0.5 = medium, 0.8 = large. Timing the 3 highest-surprisal correct samples and picking the fastest matches the oracle’s 100% fast_1. When log-probabilities are recorded during generation, ranking adds no model calls, though correctness checks and timing still cost compute.
Surprisal-guided (blue) vs confidence-guided (red). The gap is consistent across seeds. Confidence-guided std = 14.1%; surprisal-guided std = 0%.
The selector picks the most surprising correct sample, not the most surprising overall. Before filtering, high surprisal also selects malformed code. The execution-grounded setting supplies that filter through compilation and execution.
One possible explanation is that the model assigns high probability to common code patterns rather than to the fastest implementation on this hardware. The selector result is consistent with that explanation, but this experiment does not measure how often the kernel strategies appeared in pretraining.
I call the useful low-probability candidates the Expert Tail: correct kernels that the model can generate but ranks below more likely alternatives. Unlike S*, the ranking uses already recorded log-probabilities, not additional model calls. Its usefulness still depends on task-specific variation and the correctness filter.
I also checked sequence length, since longer outputs accumulate more negative log-probability. Across 550 correct samples, the raw Spearman correlation between log-probability and speedup was weak (rho = -0.047, p = 0.27), and it fell to about zero after controlling for code length (partial rho = 0.003, p = 0.95). That global correlation cannot say whether the selector would work as well per task with length-matched candidates or normalized scores.
A quartile breakdown bounds the claim. Q2 (second-highest surprisal) shows the highest fast_1 at 81.0% and Q4 (lowest surprisal) the lowest at 43.9%, so the strongest quartile is in the high-surprisal half rather than at its extreme.
Why not just train more?
I started this project expecting TTT to help. The short adaptation runs underperformed the sampling baseline.
Best-of-N at K=64 achieves 90% task success (18/20 L1 eval tasks). The two failures were Task 82, which reaches 100% correctness but only 1.00x speedup against a cuDNN reference, and Task 95, which reaches 0% correctness. On the five-task comparison below, TTT’s best checkpoint reaches 30.6% fast_1 (three-seed mean), below the matched three-seed Best-of-N sample rate of 39.8%.
| Method | fast_1 | Equivalent K |
|---|---|---|
| Best-of-N K=64 | 100% | 64 |
| Best-of-N K=1 (two seeds) | 53.3% | 1 |
| TTT BoA (3-seed mean) | 30.6% | < 1 |
Subset 1 (5 tasks). Best-of-N achieves 90% (18/20) on the full L1 eval set.
Performance often peaked after one or two adaptation steps and then regressed. In the paper, over-sharpening means gradient updates concentrate probability on solutions that succeeded early in adaptation, reducing the sample diversity needed to find the fastest kernels. I use it as a candidate explanation for this pattern, not an established probability-level mechanism.
Correction, September 8. I removed the earlier NLL-speedup interpretation and figure. The reported negative correlation has the opposite direction under the stated NLL definition, so it cannot support the claim that adaptation increased confidence in worse solutions.
Cross-subset transfer also deteriorated. Checkpoints adapted on Subset 1 and evaluated on Subset 2 achieved 7.5% fast_1, down from the unadapted baseline of 17.5%. Both transfer directions degraded.
Performance peaks at 1-2 steps then regresses. Stars mark BoA-selected checkpoints. The early-peak pattern appears across learning rates spanning three orders of magnitude.
When this works and when it doesn’t
Surprisal-guided selection requires two things: correct samples to select from, and enough log-probability variance within each task.
Of 20 L1 eval tasks, 9 have high log-probability variance (std > 1.0), tasks with diverse solution strategies that give selection something to rank. The remaining 11 produce near-identical log-probabilities across samples, primarily convolution and normalization operations where the model converges to a narrow template. On those tasks, the score offers little separation between candidates.
Measured as the share of sampled kernels that were correct and faster, TTT’s best checkpoint trailed the Best-of-N samples by 9.2 points on Subset 1 (30.6% vs 39.8%, three seeds) and by 20.6 points on Subset 2 (16.3% vs 36.9%, seed 42). Coverage varied by task, so a single aggregate result should not be read as a universal threshold for choosing training over search.
Self-Distilled Policy Optimization (SDPO) in prompt-only mode roughly matched TTT’s best checkpoint (30.4% vs 30.6%) under matched rollout budgets, consistently across three seeds. Adding teacher-interpreted execution feedback lowered SDPO to 26.3%, a 4.1 percentage point deficit.
Reward density is one possible explanation for the short adaptation horizon. It is not isolated here from the task distribution, starting policy, objective, or optimizer. TTT-Discover reports useful longer adaptation in a different setting. Comparing those outcomes does not establish an inverse law between reward density and the number of useful gradient steps.
Can you skip evaluation with surprisal?
I tested whether ranking by surprisal before correctness evaluation, then evaluating only the top m candidates, could cut evaluation cost. Across 30 task-seed pairs, it does not work at small budgets. At m=5 (8% of candidates), surprisal achieves 43% task success versus 59% for random. The extreme high-surprisal tail mixes expert solutions with malformed code the model correctly considers unlikely. Without the correctness filter, you cannot tell them apart.
The crossover is at m=16 (25% of K), where surprisal pulls ahead by 7.5 percentage points. Confidence is worst at every budget level.
What to do with this
The tested setting is GPU kernel optimization with execution-based correctness checks and timing. Assembly optimization and formal theorem proving also offer verifiers, but transferring this selector to them remains an experiment.
For these tasks, I would sample 16 to 64 candidates, filter for correctness, then rank by surprisal using the recorded log-probabilities. On the five-task subset, fastest-correct selection reached 99.9% at K=16 and 100% at K=32 and K=64, but I tested the surprisal selectors only at K=64. Generation and correctness evaluation remain part of the inference budget.
I showed in a previous post that a supervised fine-tuned checkpoint matched GRPO at Pass@4 on multi-turn tool-use. Both experiments make sampling and selection useful baselines before adding training. Neither establishes that selection generally beats RL.
My OpenSec work raised a related question about acting on a strong prior when the evidence points elsewhere. The security agents took incorrect containment actions in 45–97.5% of simulated episodes. I see an analogy with premature commitment, but the two experiments would need separate causal tests before I could give them the same explanation.
For evaluation, I would keep both high-coverage and low-coverage tasks in the set. The two failures here differ: on one task every kernel is correct but none is faster, and on the other the model never produces a correct candidate. A selector has different room to help in each case.
What this doesn’t cover
Selection strategy analysis covers 10 task-seed pairs (5 tasks x 2 seeds). The primary comparison (80% vs 50%) shows a medium-to-large effect (Cohen’s h = 0.64). The sign test at n = 10 gives p = 0.125, so I treat the selector comparison as a small exploratory result. Best-of-N covers all 20 L1 tasks. I tested a single 120B model; transfer to other scales is open. Evaluation uses a fast-proxy protocol (5 timing trials per kernel).
The advantage of low-confidence selection may be domain-specific. In these kernel tasks, some rare correct solutions gave high speedups. In domains where the distribution mode represents optimal behavior, surprisal-guided selection could underperform. The surprisal signal also vanishes on 11/20 tasks where the model produces near-identical solutions.
Try it yourself
# Clone the repo
git clone --recursive https://github.com/jbarnes850/test-time-training.git
cd test-time-training
# Install dependencies
uv sync --extra dev
# Run Best-of-N with selection analysis
uv run python -m scripts.best_of_n \
--split splits/l1_seed42.json \
--subset eval \
--k 64 \
--max_tasks 20
Resources
Citation
@article{barnes2026surprisal,
title={Surprisal-Guided Selection: Compute-Optimal Test-Time Strategies for Execution-Grounded Code Generation},
author={Barnes, Jarrod},
journal={arXiv preprint arXiv:2602.07670},
year={2026},
url={http://arxiv.org/abs/2602.07670}
}
The question I started with was where to spend additional compute. On these KernelBench comparisons, sampling preserved useful alternatives that the short adaptation runs did not reliably improve. The cause of that adaptation failure remains less certain than the performance result.
My practical starting point is to sample, evaluate correctness, and compare selectors at the same budget. Surprisal was useful on the diverse five-task subset, but its signal weakened when candidates were nearly identical. The result depends on that variation, on the verifier, and on the cost already paid to evaluate the candidate pool.