ROC-n-reroll: How verifier imperfection affects test-time scaling

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "ROC-n-reroll: How verifier imperfection affects test-time scaling".

Jane: The paper was written by Florian E. Dorner, Yatong Chen, André F. Cruz and Fanny Yang from ETH Zurich and Max Planck ETH Center for Learning Systems and Max Planck Institute for Intelligent Systems and Tübingen AI Center.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we’re digging into a paper that’s been making the rounds in the AI world, and the title alone caught my eye: “ROC-n-reroll: How verifier imperfection affects test-time scaling.” Jane, what’s your first reaction to that name?

Jane: Oh, I love it. It’s playful, but it’s also dead-on. You’ve got the “reroll” part, which is exactly what these methods do—they keep rolling the dice on new answers until they find a good one. And “ROC” is that classic curve from machine learning that measures how well a classifier separates the good from the bad. So the title is basically telling us: the quality of your rerolling depends entirely on how good your verifier is at telling right from wrong.

Tom: And that’s the crux of it. A lot of people in the field have been acting like test-time scaling is this magic trick—just generate more answers, pick the best one, and boom, your model gets smarter. But this paper says, hold on, that only works if your verifier is perfect. And in the real world, verifiers are far from perfect.

Jane: Right. Think of it like a game show where you get to spin a wheel to win a prize. If the host tells you which envelope has the cash, you’ll always win. But if the host is guessing half the time, you’re just as likely to walk away with a consolation prize. That’s the whole problem this paper tackles.

Tom: And the authors—Florian Dorner, Yatong Chen, André Cruz, and Fanny Yang—they’re from ETH Zürich and the Max Planck Institute. These are serious folks in the theory side of machine learning. They’re not just running experiments; they’re proving things mathematically.

Jane: Which is refreshing. We get so many empirical papers that say “this works” without explaining why. This one gives us a framework. They show that the performance of these rerolling methods—Rejection Sampling and Best-of-N—is completely determined by the shape of the verifier’s ROC curve. Not by the details of the model, not by the prompt, just that curve.

Tom: And that’s a huge simplification. It means we can predict how much better a model will get with more compute, just by looking at that one curve. But it also means we have to be careful—if that curve is flat near the origin, you’re not going to get much better no matter how many times you reroll.

Jane: Exactly. And that’s the hook for our next segment. We’re going to break down what they actually found about Rejection Sampling versus Best-of-N, and why one of them is secretly more efficient than the other. Stick around.

Summary: Tom: So we’re back, and we’re still talking about “ROC-n-reroll.” Jane, you teased that Rejection Sampling is more efficient than Best-of-N. Can you walk us through that?

Jane: Sure. So there are two main ways to use a verifier. Best-of-N is the obvious one—you generate N answers, score them all, and pick the highest-scoring one. Rejection Sampling is different: you generate one answer, score it, and if it doesn’t meet a threshold, you throw it away and try again. You keep going until you get one that passes.

Tom: And the paper proves that, for the same average amount of compute, Rejection Sampling gives you a higher accuracy. That’s Proposition six in the paper. It’s a mathematical guarantee, assuming the verifier’s ROC curve is concave.

Jane: And the intuition is pretty simple. Best-of-N always uses exactly N samples, even if the first one is perfect. Rejection Sampling stops as soon as it finds a good one. So it’s not wasting compute on answers that are already fine.

Tom: But here’s the twist—they also show that as you crank up the compute, both methods converge to the same accuracy. So the gap closes. If you have unlimited time and money, it doesn’t matter which one you use. But if you’re on a budget, Rejection Sampling is the smarter play.

Jane: And that’s not just theory. They ran experiments on GSM8K and MATH500, using Qwen and Llama models as verifiers. And the predictions match the empirical results almost perfectly. The curves they derive from the ROC geometry line up with the actual measured accuracy.

Tom: I was really impressed by Figure one in the paper. They show two different verifiers that have the same performance at low compute—say, three or four samples—but then they diverge wildly at higher compute. One plateaus, the other keeps climbing. And the paper explains exactly why: it’s all about the slope of the ROC curve near the origin.

Jane: Which brings us to a scary implication. You can’t extrapolate. If you see a model improving with more samples, you can’t assume it’ll keep improving. The early scaling is determined by the top-right corner of the ROC curve, but the high-compute limit is determined by the bottom-left corner. Those two regions are independent.

Tom: So you could have a verifier that looks great in small tests but is secretly terrible at high compute, or vice versa. That’s Proposition three and Proposition seven in the paper. They prove it’s impossible to predict the high-compute performance from low-compute observations.

Jane: And that’s a warning for anyone doing cost-benefit analysis on test-time scaling. You can’t just run a small pilot and extrapolate the curve. You need to actually measure the ROC curve near the origin, which requires a lot of data.

Tom: But we’re not done yet. In the next segment, we’re going to talk about what this means for reinforcement learning and how you might actually train better verifiers. Stay with us.

Improvements: Tom: Welcome back. We’ve been talking about “ROC-n-reroll” and how verifier imperfection limits test-time scaling. But the paper doesn’t just stop at pointing out the problem. It also suggests some ways forward. Jane, what’s the big one?

Jane: The big one is the connection to reinforcement learning. The authors show that if you train a model with KL-regularized RL, using the verifier as a reward, the optimal policy converges to Rejection Sampling as you reduce the regularization. That’s Proposition four.

Tom: Which is a huge deal. It means that a lot of the recent work on RL fine-tuning for reasoning models—like DeepSeek-R1—might just be a fancy way of doing Rejection Sampling. The model is learning to mimic the distribution of answers that the verifier would accept.

Jane: And that’s not a bad thing. It gives us a theoretical justification for why RL works so well in math and coding. The verifier is nearly perfect in those domains, so the RL policy is learning to produce near-perfect answers. But it also means that if your verifier is biased or flawed, your RL model will inherit those flaws.

Tom: So the improvement isn’t just about making better verifiers. It’s about understanding that the verifier is the bottleneck. The paper suggests that training verifiers with a focus on the low-FPR region—the bottom-left of the ROC curve—is more important than overall accuracy.

Jane: Exactly. Because that’s the region that determines high-compute performance. If you’re planning to use a lot of test-time compute, you want a verifier that has a steep slope near the origin. That means it can confidently reject wrong answers without accidentally rejecting correct ones.

Tom: And the paper even hints at a practical way to do that. They mention partial AUC metrics, which focus on specific regions of the ROC curve. So instead of training a verifier to maximize overall AUROC, you could train it to maximize the lower-left partial AUC.

Jane: Which is a concrete, actionable suggestion. It’s not just theory for theory’s sake. It’s saying, if you know your compute budget, you can tailor your verifier training to match.

Tom: And there’s another angle. The paper shows that Rejection Sampling is more compute-efficient than Best-of-N. So maybe we should be building systems that use RS as the default, rather than BoN. The practical disadvantages—like not being able to parallelize as easily—might be worth overcoming for the efficiency gain.

Jane: Right. And they also open the door to hybrid methods. Could you combine the parallelizability of BoN with the efficiency of RS? That’s a question they leave for future work, but it’s a tantalizing one.

Tom: Before we wrap up, let’s bring in Lu and Meng for their takes. Lu, you’ve been quiet.

Lu: I think the most exciting implication is for self-improvement. If RL converges to RS, then we have a clear path to making models better without human labels. We just need a decent verifier, and the model will learn to produce answers that pass it. The question is whether that creates a ceiling or a ladder.

Meng: And from an engineering side, I’m wondering about the cost of estimating these ROC curves. The paper uses one thousand samples per question to get the curve. That’s expensive. But if we can predict the curve from a smaller sample, we could save a lot of compute. That’s a practical challenge the paper doesn’t fully address.

Tom: Great points. Let’s move to the conclusion and tie this all together.

Conclusion: Tom: We’re wrapping up our discussion of “ROC-n-reroll: How verifier imperfection affects test-time scaling.” Jane, give us the one-minute version.

Jane: The paper gives us a precise, mathematical framework for understanding how imperfect verifiers limit test-time scaling. It shows that Rejection Sampling is more compute-efficient than Best-of-N, but they converge at high compute. And it warns us that we can’t extrapolate performance from small-scale experiments.

Tom: And the big takeaway for the field is that the verifier is the real bottleneck. If we want better test-time scaling, we need better verifiers, especially in the low-FPR region. The paper even connects this to reinforcement learning, showing that RL policies essentially learn to do rejection sampling.

Jane: It’s a sobering but empowering result. Sobering because it means we can’t just throw more compute at a problem and expect linear gains. Empowering because it gives us a clear target for improvement.

Tom: And with that, we’re going to say goodbye to this paper. It’s been a pleasure, “ROC-n-reroll.” You’ve given us a lot to think about. Next up, we’ve got a paper on diffusion models that I’m really excited about. Thanks for listening, everyone. See you next time.

Jane: Take care, and keep rerolling—but check your verifier first.