ML//inference//test-time compute//best-of-N

Best-of-N is an inference strategy that samples \(N\) candidate answers to one request and returns the one a scorer ranks highest, and it is used wherever a candidate can be checked or graded: generated code against unit tests, a plan against its constraints, a reply against a reward model. The model is unchanged; the gain comes entirely from generating more and choosing well.

Best-of-N is an inference strategy that samples NNN candidate answers to one request and returns the one a scorer ranks highest, and it is used wherever a candidate can be checked or graded: generated code against unit tests, a plan against its constraints, a reply against a reward model. The model is unchanged; the gain comes entirely from generating more and choosing well.

With a perfect verifier the arithmetic is simple. If one sample is correct with probability ppp, at least one of NNN independent samples is correct with probability 1−(1−p)N1-(1-p)^N1−(1−p)N: a coder right 30% of the time on a task finds a passing program among ten samples 97% of the time. That figure is the ceiling (benchmarks call it pass@N); what is actually delivered depends on whether the scorer picks the correct candidate out of the pool.

Best-of-N is exactly as good as its scorer.

Executable tests and constraint checks select reliably, within what they cover. A learned scorer can be fooled, and a larger pool holds more answers that exploit its blind spots, so with a reward model the true quality of the pick can stop rising, and even fall, as NNN grows (reward hacking).

It differs from self-consistency in where the judgment comes from. Self-consistency needs no scorer and votes among final answers, so it only works when answers can be compared; best-of-N needs a scorer and works on any output it can grade, including code and free text. When a reliable verifier exists, best-of-N is the stronger of the two; without one, the vote is often the safer choice.

The cost grows linearly with NNN: NNN full generations plus NNN scorings, with latency held down by generating the candidates as one batch. A step scorer (PRM) can prune bad candidates partway through instead of paying for every one to the end, which turns sampling into search (test-time compute).

It is not beam search, which keeps the most probable partial sequences by the model's own likelihood; best-of-N compares finished answers by an outside judgment. AlphaCode is the case at scale: huge numbers of sampled programs filtered by the example tests.