A Simple and Provable Scaling Law for the Test-Time Compute of Large
  Language Models
We propose a general two-stage algorithm that enjoys a provable scaling law
for the test-time compute of large language models (LLMs). Given an input
problem, the proposed algorithm first generates N candidate solutions, and
then chooses the best one via a multiple-round knockout tournament where each
pair of candidates are compared for K times and only the winners move on to
the next round. In a minimalistic implementation, both stages can be executed
with a black-box LLM alone and nothing else (e.g., no external verifier or
reward model), and a total of N times (K + 1) highly parallelizable LLM
calls are needed for solving an input problem. Assuming that a generated
candidate solution is correct with probability p_{gen} > 0 and a
comparison between a pair of correct and incorrect solutions identifies the
right winner with probability p_{comp} > 0.5 (i.e., better than a
random guess), we prove theoretically that the failure probability of the
proposed algorithm decays to zero exponentially with respect to N and K:
$P(final output is incorrect) le (1 - p_{gen})^N +
lceil log_2 N rceil e^{-2 K (p_{comp} - 0.5)^2}.$ Our empirical
results with the challenging MMLU-Pro benchmark validate the technical
assumptions, as well as the efficacy of the proposed algorithm and the gains
from scaling up its test-time compute.
674d483a1c5984922be0ef47
Yanxi Chen
claimed_verified
2024-12-03T11:16:09.629Z
6576f9f4654561a1b345610b
/avatars/f801f551640caa70368fcc26a0f51d27.svg
Yanxi Chen
user
yanxi-chen
674d483a1c5984922be0ef48
Xuchen Pan
admin_assigned
2024-12-03T15:25:01.972Z
64101b4ca92fedb0e8559b91
/avatars/c7453a5641a94d04a75de9b7d4272bc2.svg
Xuchen Pan
user
panxuchen
674d483a1c5984922be0ef49
Yaliang Li
674d483a1c5984922be0ef4a
Bolin Ding
674d483a1c5984922be0ef4b
Jingren Zhou
admin_assigned
2024-12-03T15:24:55.377Z
602f88f5e8149a962412a667
/avatars/b78f0e583df8e5d5e3365934fe5f4900.svg
Zhou
user
Jingren
A Simple and Provable Scaling Law for the Test-Time Compute of Large
  Language Models
We propose a general two-stage algorithm that enjoys a provable scaling law
for the test-time compute of large language models (LLMs). Given an input
problem, the proposed algorithm first generates N candidate solutions, and
then chooses the best one via a multiple-round knockout tournament where each
pair of candidates are compared for K times and only the winners move on to
the next round. In a minimalistic implementation, both stages can be executed
with a black-box LLM alone and nothing else (e.g., no external verifier or
reward model), and a total of N times (K + 1) highly parallelizable LLM
calls are needed for solving an input problem. Assuming that a generated
candidate solution is correct with probability p_{gen} > 0 and a
comparison between a pair of correct and incorrect solutions identifies the
right winner with probability p_{comp} > 0.5 (i.e., better than a
random guess), we prove theoretically that the failure probability of the
proposed algorithm decays to zero exponentially with respect to N and K:
$P(final output is incorrect) le (1 - p_{gen})^N +
lceil log_2 N rceil e^{-2 K (p_{comp} - 0.5)^2}.$ Our empirical
results with the challenging MMLU-Pro benchmark validate the technical
assumptions, as well as the efficacy of the proposed algorithm and the gains
from scaling up its test-time compute.
A two-stage algorithm using multiple candidate solutions and a knockout tournament improves the test-time performance of large language models through parallelizable LLM calls.
large language models candidate solutions knockout tournament black-box LLM failure probability MMLU-Pro benchmark