# Heimdall: test-time scaling on the generative verification

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 29 of its 35 references that are in the map.
- First posted on arXiv 14 Apr 2025.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [A Survey on LLM-as-a-Judge](https://mlsanity.com/paper/2411.15594/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [From Generation to Judgment: Opportunities and Challenges of LLM-as-a-judge](https://mlsanity.com/paper/2411.16594/) (2024)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [Justice or Prejudice? Quantifying Biases in LLM-as-a-Judge](https://mlsanity.com/paper/2410.02736/) (2024)
- [Generative Reward Models](https://mlsanity.com/paper/2410.12832/) (2024)
- [LLM Critics Help Catch LLM Bugs](https://mlsanity.com/paper/2407.00215/) (2024)
- [Competitive Programming with Large Reasoning Models](https://mlsanity.com/paper/2502.06807/) (2025)
- [GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoning](https://mlsanity.com/paper/2504.00891/) (2025)
- [CriticBench: Benchmarking LLMs for Critique-Correct Reasoning](https://mlsanity.com/paper/2402.14809/) (2024)
- [Self-Generated Critiques Boost Reward Modeling for Language Models](https://mlsanity.com/paper/2411.16646/) (2024)
- [Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities?](https://mlsanity.com/paper/2502.12215/) (2025)
- [Critique Fine-Tuning: Learning to Critique is More Effective than Learning to Imitate](https://mlsanity.com/paper/2501.17703/) (2025)
- [Trading Inference-Time Compute for Adversarial Robustness](https://mlsanity.com/paper/2501.18841/) (2025)
- [Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification](https://mlsanity.com/paper/2502.01839/) (2025)
- [Teaching Language Models to Critique via Reinforcement Learning](https://mlsanity.com/paper/2502.03492/) (2025)
- [S2R: Teaching LLMs to Self-verify and Self-correct via Reinforcement Learning](https://mlsanity.com/paper/2502.12853/) (2025)
- [MM-Verify: Enhancing Multimodal Reasoning with Chain-of-Thought Verification](https://mlsanity.com/paper/2502.13383/) (2025)
- [Human-Centered Design Recommendations for LLM-as-a-Judge](https://mlsanity.com/paper/2407.03479/) (2024)
- [LLM-as-a-Judge & Reward Model: What They Can and Cannot Do](https://mlsanity.com/paper/2409.11239/) (2024)
- [Critique Ability of Large Language Models](https://mlsanity.com/paper/2310.04815/) (2023)
- [Training Language Models to Critique With Multi-agent Feedback](https://mlsanity.com/paper/2410.15287/) (2024)
- [T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models](https://mlsanity.com/paper/2504.04718/) (2025)
- [Dyve: Thinking Fast and Slow for Dynamic Process Verification](https://mlsanity.com/paper/2502.11157/) (2025)

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

- [CompassVerifier: A Unified and Robust Verifier for LLMs Evaluation and Outcome Reward](https://mlsanity.com/paper/2508.03686/) (2025)
- [Trust, But Verify: A Self-Verification Approach to Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2505.13445/) (2025)
- [RewardAnything: Generalizable Principle-Following Reward Models](https://mlsanity.com/paper/2506.03637/) (2025)
- [PAG: Multi-Turn Reinforced LLM Self-Correction with Policy as Generative Verifier](https://mlsanity.com/paper/2506.10406/) (2025)
- [From Trial-and-Error to Improvement: A Systematic Analysis of LLM Exploration Mechanisms in RLVR](https://mlsanity.com/paper/2508.07534/) (2025)
- [V1: Unifying Generation and Self-Verification for Parallel Reasoners](https://mlsanity.com/paper/2603.04304/) (2026)
- [What If Consensus Lies? Selective-Complementary Reinforcement Learning at Test Time](https://mlsanity.com/paper/2603.19880/) (2026)
- [Scaling over Scaling: Exploring Test-Time Scaling Plateau in Large Reasoning Models](https://mlsanity.com/paper/2505.20522/) (2025)
- [Right Is Not Enough: The Pitfalls of Outcome Supervision in Training LLMs for Math Reasoning](https://mlsanity.com/paper/2506.06877/) (2025)
- [Self-Harmony: Learning to Harmonize Self-Supervision and Self-Play in Test-Time Reinforcement Learning](https://mlsanity.com/paper/2511.01191/) (2025)
- [Faster and Better LLMs via Latency-Aware Test-Time Scaling](https://mlsanity.com/paper/2505.19634/) (2025)
- [Scaling Generative Verifiers For Natural Language Mathematical Proof Verification And Selection](https://mlsanity.com/paper/2511.13027/) (2025)
- [Trust but Verify! A Survey on Verification Design for Test-time Scaling](https://mlsanity.com/paper/2508.16665/) (2025)
- [RefCritic: Training Long Chain-of-Thought Critic Models with Refinement Feedback](https://mlsanity.com/paper/2507.15024/) (2025)
- [From Solving to Verifying: A Unified Objective for Robust Reasoning in LLMs](https://mlsanity.com/paper/2511.15137/) (2025)
- [Population-Evolve: a Parallel Sampling and Evolutionary Method for LLM Math Reasoning](https://mlsanity.com/paper/2512.19081/) (2025)
- [Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling](https://mlsanity.com/paper/2505.11730/) (2025)
- [OPV: Outcome-based Process Verifier for Efficient Long Chain-of-Thought Verification](https://mlsanity.com/paper/2512.10756/) (2025)
- [Pseudo-Formalization for Automatic Proof Verification](https://mlsanity.com/paper/2605.20531/) (2026)
- [Do Code Semantics Help? A Comprehensive Study on Execution Trace-Based Information for Code Large Language Models](https://mlsanity.com/paper/2509.11686/) (2025)
- [From Curiosity to Caution: Mitigating Reward Hacking for Best-of-N with Pessimism](https://mlsanity.com/paper/2604.04648/) (2026)
- [Budget-aware Test-time Scaling via Discriminative Verification](https://mlsanity.com/paper/2510.14913/) (2025)
- [Learning Generative Selection for Best-of-N](https://mlsanity.com/paper/2602.02143/) (2026)
- [Beyond Token-level Supervision: Unlocking the Potential of Decoding-based Regression via Reinforcement Learning](https://mlsanity.com/paper/2512.06533/) (2025)
- [Towards Better RL Training Data Utilization via Second-Order Rollout](https://mlsanity.com/paper/2602.22765/) (2026)
- [Diagnosing Sampled LLM Reasoning in Formal Geometry: Coverage, Realization, and Validity Evidence](https://mlsanity.com/paper/2609.32924/) (2026)

## Abstract (arXiv)

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.