How Do Large Language Monkeys Get Their Power (Laws)?

How Do Large Language Monkeys Get Their Power (Laws)?

Speakers: Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, Sanmi Koyejo

Conference: ICML 2025

YouTube: https://slideslive.com/39044104

Overview

This talk, presented by Rylan Schaeffer and Joshua Kazdan at ICML 2025, delves into the fascinating and seemingly paradoxical scaling laws observed when using Large Language Models (LLMs), affectionately termed "large language monkeys," with multiple independent attempts to solve problems. While it has been empirically established that the overall success rate across a dataset, known as pass@k, scales polynomially (a power law) with the number of attempts k, the success rate for individual problems pass_i@k scales exponentially. The core of their work is to resolve this discrepancy by identifying the underlying statistical properties of problem difficulty that give rise to these aggregate power laws.

The research highlights a critical aspect of understanding and predicting the capabilities and vulnerabilities of LLMs. Just as pre-training compute scaling has become a predictable science, the ability to predict inference scaling is crucial for the efficient development and deployment of advanced AI systems. By uncovering the necessary and sufficient conditions for power law scaling in pass@k, the authors offer a fundamental theoretical framework that unifies empirical observations and provides a more robust method for forecasting LLM performance under repeated sampling.

Background

▶ Watch: Introduction: Scaling pre-training vs. inference compute. (0:00)

The field of machine learning has long recognized the importance of scaling laws, which describe how model performance changes predictably with increases in compute, data, or model size. A well-established example is the scaling of pre-training compute, where increasing computational resources during pre-training leads to predictable improvements in downstream task accuracy. This relationship is often observed as a roughly linear trend when plotting logarithmic pre-training compute against accuracy.

More recently, attention has shifted to inference-time compute scaling. Pioneering work, such as that by O1 (as referenced in the talk), demonstrated that allocating more compute during inference can also significantly improve downstream task accuracy. One prominent method for scaling inference compute, especially for complex or open-ended tasks, is through multiple independent attempts, often referred to as best-of-n sampling or self-consistency. In this approach, an LLM is prompted to generate hundreds or thousands of potential solutions to a given problem. While most attempts might be incorrect, the sheer volume of attempts increases the probability of finding at least one correct solution. The talk humorously refers to LLMs in this context as "large language monkeys," emphasizing the high volume of potentially random attempts.

To quantify the efficiency and practicality of this scaling strategy, researchers typically use the metric pass@k. This metric comes in two forms: pass_i@k, which is the probability of solving a single problem i at least once in k independent attempts, and pass_d@k, which is pass_i@k averaged over an entire dataset d. Empirical studies have consistently shown that pass_d@k typically follows a power law, meaning it scales polynomially with k. This is evident when plotting the logarithm of the number of attempts (log k) against the logarithm of pass_d@k (log pass_d@k), which reveals a linear relationship. This phenomenon has been observed across various domains, including capabilities datasets (e.g., mathematical problem-solving) and jailbreaking datasets (e.g., best-of-n jailbreak on AdvBench).

However, a significant paradox emerges when examining pass_i@k. For an individual problem, pass_i@k is calculated as 1 - (1 - pass_i@1)^k, where pass_i@1 is the probability of solving problem i in a single attempt. Since (1 - pass_i@1) is a constant for a given problem, pass_i@k inherently scales exponentially or geometrically with k. This creates a stark contradiction: individual problems exhibit exponential scaling, while the average across a dataset exhibits polynomial (power law) scaling. Resolving this paradox and understanding the conditions under which these aggregate power laws emerge is the central objective of this research.

Key Findings

▶ Watch: The paradox: Individual exponential, aggregate power law. (3:00)

The central finding of this research is the resolution of the paradox between individual problem exponential scaling and aggregate dataset polynomial scaling in LLM inference performance. The key insight lies in the distribution of single-attempt success rates (pass_i@1) across the entire dataset of problems. The authors demonstrate that for pass_d@k to exhibit power law scaling, the distribution of pass_i@1 must possess a specific structural property: a power law left tail.

Specifically, this means that there must be a sufficient number of very difficult problems (those with low pass_i@1 values) that persist in the distribution, even if their absolute frequency diminishes. These "hard problems" are crucial because they "stretch out" the aggregate behavior, preventing the overall success rate from quickly saturating as it would if all problems were relatively easy.

The paper formalizes this intuition with two theorems:

1. Sufficiency: If the distribution of pass_i@1 has a power law left tail, and individual problems scale exponentially, then the aggregate pass_d@k will exhibit power law scaling.
2. Necessity: If pass_d@k scales polynomially and individual problems scale exponentially (under certain regularity assumptions), then the distribution of pass_i@1 must have a power law left tail.

Empirical evidence strongly supports these theoretical findings. The researchers fitted beta distributions to the empirically observed pass_i@1 rates for various LLM capabilities datasets (like coding and mathematical problem-solving) and jailbreaking datasets. In nearly all cases, these fitted distributions exhibited the predicted heavy left tails, confirming the presence of a power law left tail.

Furthermore, this theoretical framework successfully explains deviations from power law scaling. For instance, the talk highlights the case of Llama 3 on a jailbreaking dataset, which did not follow the power law trend and showed faster-than-expected improvement. The analysis revealed that Llama 3's distribution of pass_i@1 lacked a heavy left tail. This meant that after a relatively small number of attempts (around 10^4), the model was able to jailbreak on virtually every prompt, leading to a saturation of success and a departure from power law behavior.

Finally, the theoretical understanding enabled the development of a new distributional predictor for pass@k scaling. Instead of relying on traditional linear regression fitted to log k vs log pass_d@k after many samples, this new approach focuses on accurately fitting the left tail of the pass_i@1 distribution. This distributional estimator was shown to be more sample-efficient, yielding a lower relative error, particularly when data is limited (either fewer problems in the dataset or fewer samples per problem). This has significant practical implications for early prediction of LLM performance.

Technical Deep Dive

▶ Watch: Resolving paradox: Key difference is problem distribution. (5:30)

The core of the technical argument revolves around the distinct mathematical forms of pass_i@k and pass_d@k and how their interaction necessitates a specific structure in the underlying problem difficulty distribution.

Let's first define the metrics more formally:

• pass_i@1: The probability that a Large Language Model (LLM) solves problem i in a single attempt.
• pass_i@k: The probability that problem i is solved at least once in k independent attempts. This is given by the formula:

pass_i@k = 1 - (1 - pass_i@1)^k

As noted, (1 - pass_i@1) is a constant for a given problem i. If pass_i@1 > 0, then (1 - pass_i@1) < 1, and (1 - pass_i@1)^k decreases exponentially with k. Therefore, pass_i@k approaches 1 exponentially fast. Taking the negative logarithm, -log(1 - pass_i@k) would show exponential growth.

• pass_d@k: The average pass_i@k over an entire dataset d. This is typically expressed as an expectation over the distribution of problems:

pass_d@k = E_i[pass_i@k] = E_i[1 - (1 - pass_i@1)^k]

pass_d@k = 1 - E_i[(1 - pass_i@1)^k]

Empirical observations consistently show that pass_d@k adheres to a power law relationship, meaning pass_d@k ≈ C k^(-\alpha) for some constants C and \alpha > 0. On a log-log plot, this appears as a linear relationship: log(pass_d@k) ≈ log(C) - \alpha log(k). This is the "polynomial scaling" observed.

The paradox arises because a simple average of exponentially decaying functions would typically also decay exponentially, not polynomially. The resolution lies in the nature of the distribution of pass_i@1 across problems. Let P(p) be the probability density function of pass_i@1 values, where p represents a possible value for pass_i@1.

Then, pass_d@k = ∫_0^1 (1 - (1-p)^k) P(p) dp.

The crucial insight is that for pass_d@k to exhibit power law scaling, the distribution P(p) must have a power law left tail. This means that as p approaches 0 (indicating very difficult problems with low single-attempt success rates), P(p) must behave like p^{\beta-1} for some \beta > 0. In other words, there must be a sufficient density of extremely hard problems.

Let's consider the intuition: when k is small, pass_d@k is largely influenced by all problems. However, as k increases, (1-p)^k quickly goes to zero for problems where p is large (easy problems). The only problems that continue to contribute significantly to 1 - pass_d@k (the failure rate) are those where p is very small (hard problems), because (1-p)^k decays slowly for small p. If there are enough of these hard problems, and their density follows a power law as p -> 0, then the integral ∫_0^1 (1 - (1-p)^k) P(p) dp will also exhibit power law behavior with respect to k. The exponent \alpha of the aggregate power law in pass_d@k is directly related to the exponent \beta of the power law left tail in P(p).

The paper provides two key theorems:

1. Sufficiency: If P(p) has a power law left tail (i.e., P(p) ~ p^{\beta-1} as p \to 0), then pass_d@k scales polynomially with k. The intuition here is that the hard problems, though individually rare, persist in a way that their collective contribution prevents pass_d@k from decaying too quickly.
2. Necessity: Conversely, if pass_d@k scales polynomially and pass_i@k scales exponentially, then P(p) must have a power law left tail. This means that if we observe aggregate power law scaling, it implicitly tells us something fundamental about the distribution of problem difficulty that the model faces. Without a sufficient density of hard problems, the aggregate would inevitably fall faster.

The authors use beta distributions to model P(p) empirically. A beta distribution Beta(\alpha, \beta) is defined on the interval [0, 1] and can model a wide range of shapes. Crucially, a beta distribution with \alpha < 1 (or \beta > 0 and \alpha being its first parameter, depending on parameterization) can exhibit a heavy left tail, which means P(p) rises sharply as p approaches 0. Fitting such distributions to empirical pass_i@1 data allows for verification of the theoretical prediction.

The new distributional predictor leverages this understanding. Instead of fitting a linear regression to log(pass_d@k) vs log(k) after observing many attempts, it directly estimates the parameters of the P(p) distribution (e.g., of a beta distribution) from limited pass_i@1 samples. Once P(p) is estimated, the pass_d@k for any k can be simulated or calculated, providing a more robust and sample-efficient prediction, especially for extrapolation.

Experimental Setup & Results

▶ Watch: Core finding: Single-attempt success rates need power law left tail. (7:00)

The empirical validation of the theory relied on analyzing the scaling behavior of Large Language Models (LLMs) across diverse tasks, specifically focusing on capabilities datasets and jailbreaking datasets.

Datasets:

• Capabilities Datasets: These included problems requiring coding and mathematical problem-solving. While specific dataset names beyond "math" and "coding" were not explicitly stated in the transcript, these categories represent common benchmarks for LLM reasoning abilities.
• Jailbreaking Datasets: The talk specifically mentioned AdvBench and the "best of n jailbreak" scenario. These datasets are designed to test the robustness and safety of LLMs by attempting to elicit undesirable or harmful responses.

Models:

• The experiments involved various "large language monkeys" or "frontier AI models/systems." The transcript specifically called out Llama 3 as a model that exhibited different scaling behavior.

Methodology:

1. Empirical pass_i@1 collection: For each problem in the datasets, researchers would run the LLM for a single attempt to estimate pass_i@1. This process would be repeated across many problems to build an empirical distribution of pass_i@1 values.
2. Distribution Fitting: The empirical distributions of pass_i@1 were then fitted with beta distributions. The beta distribution, defined on [0, 1], is a flexible choice for modeling probabilities. The key was to observe the shape of the fitted beta distribution, particularly its behavior as p approaches 0.
3. pass_d@k Observation: For aggregate pass_d@k, the models were run with varying numbers of attempts k, and the overall success rates were calculated and plotted on a log-log scale to observe the power law relationship.
4. Predictor Comparison: The new distributional estimator was compared against the classic least squares regressor. The classic method involves empirically calculating pass_d@k for several k values, taking their logarithms, and then fitting a linear regression to log(pass_d@k) vs log(k) to predict future pass_d@k values. The distributional estimator, on the other hand, fits P(p) and then uses that to predict pass_d@k.

Headline Results:

• Confirmation of Power Law Left Tails: For most capabilities datasets (coding, math) and jailbreaking scenarios, fitting beta distributions to the empirical pass_i@1 data consistently revealed heavy left tails. This provided strong empirical evidence supporting the theoretical prediction that such a distribution is necessary for aggregate power law scaling. The visual plots showed a reasonably good fit between the beta distribution and the observed data.
• Explaining Llama 3's Deviation: The research successfully explained why Llama 3 deviated from the power law trend in jailbreaking. Unlike other models, Llama 3's pass_i@1 distribution did not exhibit a heavy left tail. This meant that the model was able to resolve even the hardest jailbreaking prompts after a relatively modest number of attempts (around 10^4). As a result, the pass_d@k quickly saturated, leading to a faster decline in the failure rate than predicted by a power law, thus appearing to "fall faster" than other models on a log-log plot. This absence of persistent hard problems prevented the aggregate pass_d@k from maintaining a power law trajectory.
• Superiority of Distributional Predictor: When comparing the new distributional estimator against the classic least squares regressor, the distributional method demonstrated superior performance. While both methods showed closely correlated fit power law exponents when all available data was used, the distributional predictor proved much more sample-efficient. This was particularly evident in scenarios with limited data, whether due to having fewer problems in the dataset or fewer samples (k) per problem. The distributional estimator consistently achieved a lower relative error in predicting the scaling exponent.

These results collectively validate the theoretical framework and highlight the practical utility of understanding the underlying distribution of problem difficulty for predicting and analyzing LLM inference behavior.

Practical Implications

▶ Watch: Formal proofs: Sufficiency and necessity for power laws. (8:00)

The findings from this research have profound practical implications for anyone involved in building, evaluating, and deploying Large Language Models (LLMs). Understanding the scaling laws of inference, particularly through repeated attempts, offers a more scientific and predictable approach to managing LLM performance.

1. Predicting Capabilities and Vulnerabilities: The ability to predict pass@k scaling with high confidence is crucial for forecasting both the positive capabilities and potential vulnerabilities of LLMs. For instance, knowing how quickly an LLM can solve complex math problems or how resistant it is to jailbreaking attempts after k tries allows developers to set realistic performance expectations and allocate resources effectively. If a model's pass_i@1 distribution indicates a lack of a heavy left tail (like Llama 3 in jailbreaking), it suggests that scaling k beyond a certain point will yield diminishing returns, as all problems will eventually be solved.
2. Informed Resource Allocation: Infrastructure teams and model deployers can use this framework to make data-driven decisions about the number of attempts (k) to use for a given task. Instead of relying on ad-hoc experimentation, they can estimate the pass_i@1 distribution from a small sample and then predict the k required to achieve a target success rate. This optimizes compute resource usage, balancing desired performance with cost.
3. Model Evaluation and Benchmarking: Current evaluation metrics often focus on pass@1 or pass@k for a fixed k. This research suggests that a more comprehensive evaluation should involve analyzing the entire distribution of pass_i@1. Understanding the shape of this distribution, particularly the presence and exponent of its left tail, provides deeper insights into a model's inherent difficulty profile and its potential for improvement with increased attempts. Benchmarks could incorporate metrics related to the pass_i@1 distribution characteristics.
4. Guiding Model Development: For model builders, these insights can inform architectural choices and training methodologies. If the goal is to develop models that maintain power law scaling for pass_d@k (implying continuous improvement with more attempts), then the training process should ideally ensure that the model continues to find some problems genuinely hard, leading to a pass_i@1 distribution with a heavy left tail. Conversely, if the goal is to quickly "solve" all problems, even the hardest ones, then a distribution without a heavy left tail (like Llama 3's jailbreaking performance) might be desired, indicating efficient resolution of difficult cases.
5. Improved Forecasting with Limited Data: The new distributional predictor is a significant practical advancement. In real-world scenarios, collecting vast amounts of data for many k values can be expensive and time-consuming. This predictor allows for more accurate extrapolation of pass@k scaling from fewer problems or fewer samples per problem, accelerating the evaluation cycle and enabling quicker decision-making.
6. Trade-offs and Limitations: While powerful, this framework specifically applies to inference scaling via repeated attempts. Other inference scaling strategies (e.g., larger models, more complex prompting techniques) might follow different scaling laws. Furthermore, the talk highlighted that understanding what makes certain questions hard (as per the Q&A) is still an open research question. While the theory identifies the statistical necessity of hard problems, it doesn't intrinsically explain their qualitative nature, which could be a limitation for targeted model improvements.

In essence, this work elevates the understanding of LLM inference from empirical observation to a principled, theoretically grounded science, enabling more predictable and efficient development and deployment.

Key Takeaways

• Inference Scaling Predictability: Scaling inference via multiple independent attempts (best-of-n sampling) in Large Language Models exhibits predictable power law scaling for aggregate pass@k across datasets.
• The Paradox Resolved: While individual problem success rates (pass_i@k) scale exponentially, the aggregate pass_d@k scales polynomially due to a specific characteristic of the problem difficulty distribution.
• Power Law Left Tail is Key: The distribution of single-attempt success rates (pass_i@1) must possess a power law left tail (many hard problems that persist) for aggregate pass_d@k to follow a power law. This property is both theoretically sufficient and necessary.
• Empirical Validation: Data from coding, math, and jailbreaking benchmarks confirms the presence of these heavy left tails in pass_i@1 distributions, explaining observed power law scaling. Deviations, like Llama 3's jailbreaking performance, are explained by the absence of such a tail.
• New Distributional Predictor: A novel distributional estimator, which models the pass_i@1 distribution, offers a more sample-efficient and accurate way to predict pass@k scaling compared to traditional regression methods, especially with limited data.
• Crucial for AI Science: This research contributes to building a "science of predictable inference scaling," vital for understanding and forecasting both the capabilities and vulnerabilities of advanced AI systems.

About the Speaker(s)

The talk was primarily presented by Rylan Schaeffer and Joshua Kazdan. They led the audience through the intricate details of their research, from the initial paradox to its theoretical resolution and empirical validation. The work was a collaborative effort, and they extended their gratitude to a team of many wonderful collaborators: John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, and Sanmi Koyejo. Their collective expertise contributed to this significant advancement in understanding LLM scaling laws. The speakers also acknowledged independent but related work on inference scaling laws by Noam Levy, further contextualizing their research within the broader field.