title: A Simple and Provable Scaling Law for the Test-Time Compute of Large
    Language Models
summary: 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.
paper_authors._id: 674d483a1c5984922be0ef47
paper_authors.name: Yanxi Chen
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-12-03T11:16:09.629Z
paper_authors._id: 6576f9f4654561a1b345610b
paper_authors.avatarUrl: /avatars/f801f551640caa70368fcc26a0f51d27.svg
paper_authors.fullname: Yanxi Chen
paper_authors.type: user
paper_authors.user: yanxi-chen
paper_authors._id: 674d483a1c5984922be0ef48
paper_authors.name: Xuchen Pan
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-12-03T15:25:01.972Z
paper_authors._id: 64101b4ca92fedb0e8559b91
paper_authors.avatarUrl: /avatars/c7453a5641a94d04a75de9b7d4272bc2.svg
paper_authors.fullname: Xuchen Pan
paper_authors.type: user
paper_authors.user: panxuchen
paper_authors._id: 674d483a1c5984922be0ef49
paper_authors.name: Yaliang Li
paper_authors._id: 674d483a1c5984922be0ef4a
paper_authors.name: Bolin Ding
paper_authors._id: 674d483a1c5984922be0ef4b
paper_authors.name: Jingren Zhou
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-12-03T15:24:55.377Z
paper_authors._id: 602f88f5e8149a962412a667
paper_authors.avatarUrl: /avatars/b78f0e583df8e5d5e3365934fe5f4900.svg
paper_authors.fullname: Zhou
paper_authors.type: user
paper_authors.user: Jingren
paper_title: A Simple and Provable Scaling Law for the Test-Time Compute of Large
    Language Models
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: large language models candidate solutions knockout tournament black-box LLM failure probability MMLU-Pro benchmark