When Exponentials Meet Power Laws: How Heavy-Tailed Difficulty Distributions Shape LLM Scaling Laws

Forum topic · 二一 · 2026-05-12

Summary

This post explains the puzzle behind repeated-sampling scaling laws in large language models. Individual problems show exponential decay in failure rate with more attempts, yet aggregate pass rates follow a power law: -log(success) proportional to attempts^c. The resolution is that single-attempt success probabilities are heavy-tailed across problems. A small cluster of extremely hard problems, with near-zero per-attempt success probability, decays so slowly that it dominates the average, converting exponential single-problem behavior into an aggregate power law. If the success probability distribution satisfies P(p <= x) ~ x^alpha, the expected failure rate scales as k^-alpha. Validated on math problems, Lean proofs, and multimodal jailbreaks, this insight lets researchers predict scaling exponents from one attempt per problem, cutting required inference compute by 2-4 orders of magnitude, and guides benchmark design toward heavy-tailed difficulty distributions. Source paper: 'How Do Large Language Monkeys Get Their Power (Laws)?' (ICML 2025 Oral).

> Feynman once said: "If you can't explain your research to a stranger at a bar, you don't really understand it." Today's story is about a pattern that confuses everyone — and the answer hides in the tails of probability distributions.

---

Introduction: A Pattern That Puzzled Researchers

Researchers recently noticed a curious statistical regularity. When you let a large language model tackle a batch of problems — math, coding, jailbreak attacks — and count success as at least one success across multiple attempts, the overall success rate follows a power law:

-\log(\text{success rate}) \propto (\text{number of attempts})^c

In plain terms: gains from additional attempts diminish. The first attempt helps a lot, the second helps, but by the 100th or 1000th attempt, each extra attempt adds almost nothing.

These are the famous scaling laws. Seems normal, right?

But there's a problem. A simple mathematical argument predicts that for *each individual problem*, the failure rate should fall exponentially with attempts.

Exponential decay means: if the first-attempt success rate is 10%, the second might be 19%, the fourth near 35%, and the 32nd near 97%. It converges to 100% fast.

Exponential per problem, power law in aggregate. What's going on?

---

Chapter 1: A Feynman-Style Thought Experiment

Let's understand this with a simple thought experiment.

Imagine 1000 monkeys, each with a typewriter, randomly typing complete English sentences. Some target sentences are easy ("Hi"), some medium ("To be or not to be"), and some nearly impossible (a Shakespearean sonnet).

For any single monkey, the probability of eventually producing its target sentence rises exponentially with attempts. Why? Each attempt is independent: if the single-attempt success probability is $$p$$ , the probability of at least one success in $$k$$ attempts is $$1 - (1-p)^k$$ , and $$(1-p)^k$$ decays exponentially to zero.

But when we aggregate results across all monkeys, things change.

Some monkeys face nearly impossible tasks — $$p$$ is almost zero. Even after medium-difficulty monkeys have all succeeded, these extreme cases keep failing. In the aggregate statistics, they dominate the trend.

That's the answer to the core paradox: exponential decay per unit, power law in aggregate.

---

Chapter 2: The Math, Precisely

Suppose there are $$N$$ problems, and problem $$i$$ has single-attempt success probability $$p_i$$ . After $$k$$ attempts, its success probability is:

1 - (1-p_i)^k \approx 1 - e^{-p_i k}

For any fixed $$p_i$$ (no matter how small), $e^{-p_i k}$ decays exponentially as $$k$$ grows.

Now look at the aggregate. The average failure rate over all problems is:

\text{average failure rate} = \frac{1}{N} \sum_{i=1}^{N} e^{-p_i k}

Here's the key: the sum depends on the distribution of $$p_i$$ .

If all $$p_i$$ are similar — say between 0.01 and 0.1 — the sum decays exponentially. But if the distribution of $$p_i$$ is heavy-tailed — most problems have moderate $$p_i$$ , but a small cluster has vanishingly small $$p_i$$ — then a few "holdout" terms decay extremely slowly.

When these slowly-decaying terms dominate the sum, the aggregate behavior shifts from exponential to power law. Mathematically, if $P(p \leq x) \sim x^\alpha$ (a power-law tail), then:

\mathbb{E}[e^{-pk}] \sim k^{-\alpha}

There it is: an aggregate power law!

---

Chapter 3: What the Data Says

The researchers validated the theory empirically in three domains: math problem solving, Lean proof assistant programming, and multimodal jailbreak attacks.

3.1 Per-Problem Behavior Is Exponential

Isolating each problem, the failure rate over attempts shows clean exponential decay for the vast majority of problems, with high goodness-of-fit.

3.2 Aggregate Behavior Is a Power Law

Pooling all problems, log success rate vs. attempts forms a nearly perfect straight line — the signature of a power law — in stark contrast to the per-problem exponentials.

3.3 The Distribution Is Indeed Heavy-Tailed

The distribution of single-attempt success probabilities: most problems sit between 10% and 50%, but a long tail extends below 0.0001%. These extremely hard problems control the aggregate statistics at large attempt counts.

3.4 Explaining Previously Puzzling Exceptions

This distributional view also explains earlier counterexamples:

Why do some benchmarks not follow a power law? Their difficulty distributions aren't heavy-tailed enough — no cluster of extremely hard problems.
Why does the power-law slope differ across tasks? Different tasks have tails of different thickness.

---

Chapter 4: Why It Matters

4.1 Predict Scaling Behavior with Far Less Compute

The most practical contribution. Previously, predicting a model's performance after $$k$$ attempts required actually running $$k$$ attempts — very expensive.

Now you only need one attempt per problem, then examine the distribution of single-attempt success rates — especially its tail. From the tail's thickness you can directly estimate the power-law exponent. No need to burn millions of inference tokens to forecast scaling.

The paper shows this method predicts the exponent with an order of magnitude lower relative error than prior baselines, or equivalently, requires 2–4 orders of magnitude less inference compute.

4.2 Implications for Benchmark Design

For reliable evaluation → make the difficulty distribution heavy-tailed: include a small set of extremely hard problems.
To compare two models → look at the hardest problems: that's where capability truly diverges.

Most benchmarks fail to distinguish frontier models precisely because they lack sufficiently hard problems — every model easily exceeds 90% success, the tail is too short, the distribution too concentrated.

---

A Feynman-Style Reflection

If Feynman read this paper, he'd probably say:

"This is the kind of paper I like. It starts from an observation — the aggregate is a power law — then asks: 'But isn't that odd? Each problem should be exponential.'

So they check. Per problem, it is exponential. Then where does the aggregate power law come from?

The answer is surprisingly simple: a few problems are just too hard. So hard their single-attempt success rate is nearly zero. These holdout problems sit in the aggregate statistics and drag the exponential into a power law.

This is a story about distributions. Two seemingly contradictory macroscopic phenomena — exponential and power law — become fully harmonious once you understand the heavy-tailed structure underneath.

The lesson: when you see an aggregate statistical law, go look at the shape of the distribution. The truth is often not in the mean, but in the tail."

---

*Paper info*

Title: How Do Large Language Monkeys Get Their Power (Laws)?
Authors: Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, Azalia Mirhoseini, Sanmi Koyejo
Venue: ICML 2025 (Oral)
Link: OpenReview
Code: GitHub