Heimdall: test-time scaling on the generative verification
Authors: name: Wenlei Shi; name: Xing Jin
Published: 2025-04-14 15:46:33

Abstract: An AI system can create and maintain knowledge only to the extent that it can
verify that knowledge itself. Recent work on long Chain-of-Thought reasoning
has demonstrated great potential of LLMs on solving competitive problems, but
their verification ability remains to be weak and not sufficiently
investigated. In this paper, we propose Heimdall, the long CoT verification LLM
that can accurately judge the correctness of solutions. With pure reinforcement
learning, we boost the verification accuracy from 62.5% to 94.5% on competitive
math problems. By scaling with repeated sampling, the accuracy further
increases to 97.5%. Through human evaluation, Heimdall demonstrates impressive
generalization capabilities, successfully detecting most issues in challenging
math proofs, the type of which is not included during training. Furthermore, we
propose Pessimistic Verification to extend the functionality of Heimdall to
scaling up the problem solving. It calls Heimdall to judge the solutions from a
solver model and based on the pessimistic principle, selects the most likely
correct solution with the least uncertainty. Taking
DeepSeek-R1-Distill-Qwen-32B as the solver model, Pessimistic Verification
improves the solution accuracy on AIME2025 from 54.2% to 70.0% with 16x compute
budget and to 83.3% with more compute budget. With the stronger solver Gemini
2.5 Pro, the score reaches 93.0%. Finally, we prototype an automatic knowledge
discovery system, a ternary system where one poses questions, another provides
solutions, and the third verifies the solutions. Using the data synthesis work
NuminaMath for the first two components, Heimdall effectively identifies
problematic records within the dataset and reveals that nearly half of the data
is flawed, which interestingly aligns with the recent ablation studies from
NuminaMath.