# Surprisal-Guided Selection: Compute-Optimal Test-Time Strategies for Execution-Grounded Code Generation

arXiv: https://arxiv.org/abs/2602.07670 · HTML: https://mlsanity.com/paper/2602.07670/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 23 references that are in the map.
- First posted on arXiv 7 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Reinforcement Learning via Self-Distillation](https://mlsanity.com/paper/2601.20802/) (2026)
- [KernelBench: Can LLMs Write Efficient GPU Kernels?](https://mlsanity.com/paper/2502.10517/) (2025)
- [Learning to Discover at Test Time](https://mlsanity.com/paper/2601.16175/) (2026)
- [The Art of Scaling Reinforcement Learning Compute for LLMs](https://mlsanity.com/paper/2510.13786/) (2025)
- [S*: Test Time Scaling for Code Generation](https://mlsanity.com/paper/2502.14382/) (2025)
- [Kevin: Multi-Turn RL for Generating CUDA Kernels](https://mlsanity.com/paper/2507.11948/) (2025)
- [Agent RL Scaling Law: Agent RL with Spontaneous Code Execution for Mathematical Problem Solving](https://mlsanity.com/paper/2505.07773/) (2025)
- [CUDA-L1: Improving CUDA Optimization via Contrastive Reinforcement Learning](https://mlsanity.com/paper/2507.14111/) (2025)
- [From Word to World: Can Large Language Models be Implicit Text-based World Models?](https://mlsanity.com/paper/2512.18832/) (2025)
- [Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening](https://mlsanity.com/paper/2601.21590/) (2026)
- [Towards Execution-Grounded Automated AI Research](https://mlsanity.com/paper/2601.14525/) (2026)
- [AccelOpt: A Self-Improving LLM Agentic System for AI Accelerator Kernel Optimization](https://mlsanity.com/paper/2511.15915/) (2025)
- [Dr. Kernel: Reinforcement Learning Done Right for Triton Kernel Generations](https://mlsanity.com/paper/2602.05885/) (2026)
- [QiMeng-Kernel: Macro-Thinking Micro-Coding Paradigm for LLM-Based High-Performance GPU Kernel Generation](https://mlsanity.com/paper/2511.20100/) (2025)
- [SSRL: Self-Search Reinforcement Learning](https://mlsanity.com/paper/2508.10874/) (2025)
- [CUDA-L2: Surpassing cuBLAS Performance for Matrix Multiplication through Reinforcement Learning](https://mlsanity.com/paper/2512.02551/) (2025)
- [SuperCoder: Assembly Program Superoptimization with Large Language Models](https://mlsanity.com/paper/2505.11480/) (2025)
- [Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve](https://mlsanity.com/paper/2601.21096/) (2026)

## Built on by (most cited first, 1 of 1)

- [Counterfactual Rollout Replay: Forkable Environments as Free Process Rewards for Software Engineering Agents](https://mlsanity.com/paper/2609.33875/) (2026)

## Abstract (arXiv)

Test-time training (TTT) adapts language models through gradient-based updates at inference. But is adaptation the right strategy? We study compute-optimal test-time strategies for verifiable execution-grounded (VEG) tasks, domains like GPU kernel optimization where a deterministic evaluator provides dense, continuous reward signals. Using KernelBench as our testbed and a 120B-parameter model (GPT-OSS-120B with LoRA adaptation), we find that search outperforms minimal adaptation (1-5 gradient steps): Best-of-N sampling achieves 90% task success (18/20 tasks) at K=64 across the full KernelBench L1 eval set while TTT's best checkpoint reaches only 30.6% (3-seed mean), with TTT's "equivalent K" falling below 1, worse than single-sample inference. The failure mode is over-sharpening: gradient updates collapse diversity toward mediocre solutions rather than discovering optimal ones. Our main contribution is surprisal-guided selection: selecting the highest-surprisal (lowest-confidence) correct sample yields 80% success vs. 50% for most-confident selection, a 30% improvement. Extending to surprisal-guided-top3 matches oracle performance at 100%. This zero-cost strategy, validated through length-controlled analysis, recovers oracle performance. For dense-reward VEG tasks, compute should be allocated to sample diversity and intelligent selection rather than gradient adaptation. The surprisal-guided selection principle may generalize to other execution-grounded domains where optimal solutions occupy the distribution tail.