How Big Is the Prompt Search Space?

A 100-token prompt drawn from a 128,000-token vocabulary has about 10^511 possible values, so exhaustive search is out. The more useful result is that even a small, realistic sweep of 32,768 template variants fails — not because it is too expensive, but because with a 200-example evaluation the winning configuration scores about twelve points above the truth purely by chance.

The size of the space, counted

Free-text prompt of L tokens from a vocabulary of V:

  possibilities = V^L

V = 128,000, L = 100:

  log10(128,000) = 5.10721
  100 * 5.10721  = 510.721

  ~ 10^511 possible prompts

For scale, the observable universe holds
roughly 10^80 atoms.

The number is so large that it stops being informative, so narrow it to something a person might actually consider. Ten fixed instructions, and the only question is what order to put them in:

10! = 3,628,800 orderings

At 200 evaluation examples each, one call per example:
  3,628,800 * 200 = 725,760,000 calls

At $0.002 per call: $1,451,520

Just for the ordering of ten sentences you already wrote.

Ordering alone is out of reach. Every additional axis multiplies, and that multiplication is what makes this a combinatorics problem rather than a budgeting one.

A realistic sweep, priced

Take a prompt template with five slots — a role sentence, a format instruction, an example count, a reasoning instruction, an output constraint — and eight candidate wordings for each.

configurations = 8^5 = 32,768

Assumptions, all of which you should substitute:
  evaluation set     200 examples
  cost per call      $0.002
  latency per call   1.0 s
  concurrency        20 requests in flight

  calls  = 32,768 * 200 = 6,553,600
  cost   = 6,553,600 * 0.002 = $13,107
  time   = 6,553,600 / 20 = 327,680 s = 91.0 hours

Ninety-one hours and thirteen thousand dollars, for five slots. Now reduce each slot from eight candidates to three:

configurations = 3^5 = 243

  calls = 243 * 200 = 48,600
  cost  = $97
  time  = 48,600 / 20 = 2,430 s = 40.5 minutes

135x cheaper, from cutting each slot from 8 options to 3.

The lever is the branching factor, not the number of slots, because it is raised to a power. Removing one candidate from every slot — eight to seven — already cuts the space by 49%: 7^5 = 16,807 against 8^5 = 32,768. Being ruthless about which variants are worth including is worth far more than any efficiency in how they are run.

The second problem: the winner is the luckiest

Suppose you could afford all 32,768. There is a worse problem waiting, and it is the reason this page exists rather than the arithmetic above.

Assume, pessimistically but instructively, that all 32,768 configurations are genuinely equally good, with a true accuracy of 72%. Each is measured on 200 examples, so each observed score is the truth plus noise with a standard error of 3.17 percentage points.

Expected maximum of n independent standard normals:

  E[max] ~= sqrt(2 * ln n)  -  (ln ln n + ln 4pi) / (2 * sqrt(2 * ln n))

n = 32,768:
  ln n          = 10.3972
  sqrt(2 ln n)  =  4.5601
  ln ln n       =  2.3415
  ln(4 pi)      =  2.5310
  correction    = (2.3415 + 2.5310) / (2 * 4.5601) = 0.5343

  E[max] ~= 4.5601 - 0.5343 = 4.026 standard errors

In points:
  4.026 * 3.17 = 12.8 points

Expected best observed score: 72.0 + 12.8 = 84.8%

Every configuration is truly 72%. The winner reads 84.8%.

Search hard enough over a noisy measurement and you will find a configuration that looks twelve points better than everything else and is not better at all. The larger the search, the larger the inflation — it grows as sqrt(2 ln n), slowly but without bound. And the inflated score is what gets reported, because it is the one you chose.

The fix is a held-out set. Choose the winner on a development set, then measure it once on a test set it never touched. The development score is inflated; the test score is not. If the two differ by ten points, the sweep found noise, and knowing that is worth more than the sweep.

What an honest exhaustive search would cost

Combine the two results. To distinguish configurations that genuinely differ by one point you need around 32,000 examples per configuration, not 200.

32,768 configurations x 32,000 examples
  = 1,048,576,000 calls

At $0.002 per call:  $2,097,152
At 20 concurrent, 1 s each: 52,428,800 s = 1.66 years

And that is for five slots with eight options each.

Two million dollars and nineteen months to properly evaluate a five-slot template. That is what “the search space is too large” actually means once the statistics are included: the space is not merely large, the cost of a trustworthy comparison between two of its points is high, and the product is what makes exhaustive search hopeless.

What to do instead

1. Cut the branching factor first. Three plausible wordings per slot, not eight. Most candidate variants exist because somebody could not decide, and the arithmetic above says indecision is the expensive part.
2. Search one slot at a time. Coordinate ascent: fix four slots, try all eight options for the fifth, keep the best, move on. Two full passes over five slots is 2 * 5 * 8 = 80 configurations rather than 32,768 — 410 times cheaper. It finds a local optimum and misses interactions between slots, and that is a trade worth making explicitly rather than by accident.
3. Spend the budget on examples, not configurations. Eighty configurations on 2,000 examples costs less than 32,768 on 200, and every comparison it makes is meaningful. This is the single highest-value change available.
4. Use a paired test between candidates. Run both variants on the same examples and compare item by item, which roughly halves the interval for the same number of calls.
5. Hold out a test set and use it once. Once per project, not once per iteration. A test set consulted repeatedly has become a development set and stops protecting you from exactly the effect this page derives.
6. Stop when the interval says stop. If the best two candidates are within their confidence interval of each other, pick the cheaper or the shorter one and move on. More search will not separate them and production traffic will.