One number, many attempts

A paper from Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc Le, Christopher Re and Azalia Mirhoseini went up on arXiv today and asks a question most evaluations never bother with. If you sample from a model many times on the same problem, how often does at least one sample get it right? They call that fraction coverage, and they measure it for sample counts spanning four orders of magnitude, up to 10,000 samples per problem.

The headline result is that coverage keeps growing as you add samples, and it grows in a regular way. On a log scale the relationship is close to linear across the whole range, and the authors fit it with an exponentiated power law, coverage approximately equal to exp of a times k to the b, where k is the number of samples. That is an inference time scaling law, and it holds across models and tasks that otherwise look nothing alike.

The SWE-bench Lite result

The example that will get quoted is on SWE-bench Lite. DeepSeek-Coder-V2-Instruct solves 15.9 percent of problems with a single sample. With 250 samples per problem and the test suite as a verifier, that becomes 56 percent, above the prior single sample state of the art of 43 percent. Along the way the authors found that 11.3 percent of SWE-bench Lite problems have flaky test suites, which they removed to get a clean 266 problem set. Repeated sampling is a good way to find flaky tests, because a flaky test eventually passes by accident.

The cost comparison in the paper is the part that makes this a product decision rather than a curiosity. Five samples from DeepSeek cost 10.80 dollars in total and solved 29.62 percent of problems. A single sample from GPT-4o cost 39 dollars and solved 24 percent. A single sample from Claude 3.5 Sonnet cost 51 dollars and solved 26.70 percent. A weaker, cheaper model sampled a few times beat the stronger models on both axes, provided you can tell which sample is right.

Weak models, wide coverage

The results on small models are the ones that changed our picture. Gemma-2B on CodeContests goes from 0.02 percent coverage with one sample to 7.1 percent with many, an increase of over 300 times. Pythia-160M, a model nobody would use for anything, has a pass at 1 of 0.27 percent on MATH and reaches 57 percent coverage at 10,000 samples. The Pythia sweep from 70 million to 12 billion parameters and the Llama 3 8B and 70B models all show the same log-linear shape.

The way we read this is that a model's single sample accuracy measures how often the right answer is its mode, and coverage measures whether the right answer is in its support at all. Those are different properties. A tiny model can have the correct proof somewhere in its distribution and almost never pick it. Scaling the model moves the mode. Scaling the samples explores the support. Both are ways to spend compute, and the paper's contribution is to show that the second has a smooth curve too.

The catch is verification

Coverage is an oracle number. It tells you that a correct sample exists, and says nothing about whether you can find it. For code with tests and for formal proofs with a checker, finding it is free, and coverage is the real success rate. For GSM8K and MATH there is no checker, and the paper tests the two common substitutes. Majority voting and reward model selection both plateau around 100 samples, while oracle coverage keeps climbing past 95 percent. Everything above the plateau is capability you cannot cash in.

That gap is the whole reframing. Once you know that a correct answer is usually somewhere in a few hundred samples, the question stops being whether the model can solve the problem and starts being whether you can build a verifier that scales with the sample budget. On tasks with a verifier, the paper shows that the answer is yes and the economics follow. On tasks without one, the coverage curve is a measure of how much a better verifier would be worth.

What this connects to

There is a growing body of work on spending compute at inference rather than in training, through search, self consistency and longer reasoning chains. This paper gives that agenda a clean baseline. Repeated independent sampling is the dumbest possible way to spend inference compute, and it already follows a scaling law. Any smarter method now has to beat exp of a times k to the b at the same cost, and we expect many that have been reported as improvements will turn out not to.

The experiment we would run next is on the verifier side. Take the MATH problems where coverage at 10,000 samples is high and majority vote fails, and characterise what the wrong majority looks like. If the failures cluster into a few recognisable patterns, a trained verifier has something to learn. If they are diffuse, the honest conclusion is that on tasks without a checker the sample budget is worth far less than the coverage curve suggests, and that would be worth knowing before anyone builds a product on it.

Sources

  1. Brown et al., Large Language Monkeys: Scaling Inference Compute with Repeated Sampling (arXiv 2407.21787)