Introduction

Hyperparameter search offers a menu of methods with a rough reputation ordering. Random search is the cheap baseline you are told you outgrow [1]; Bayesian and model-based sequential methods — the Tree-structured Parzen Estimator (TPE) [2], CMA-ES [3] — are supposed to beat it by placing each point more carefully; multi-fidelity pruners like Hyperband and ASHA [4, 5] promise to go faster still. The natural question — “which method is best?” — invites an answer about the algorithms.

That framing hides the variable that actually decides the winner. Every method spends a fixed wall-clock budget on two things: deciding where to sample next (the sampler's own compute) and evaluating the sample (running the objective, e.g. a backtest). Call the first the ask/tell tax and the second the eval cost. A method's search power is how many points it can place times how well it places them, and the point count over a budget B is n_{\mathrm{evals}} \approx B/(\mathrm{tax}+\mathrm{eval\ cost}). The tax is a roughly fixed number of seconds per suggestion, but its significance is set entirely by the eval cost it is divided against. When eval cost is tiny, the tax dominates the denominator and anything that inflates it — a surrogate, a kernel-density estimate, a covariance update — directly shrinks the number of points explored. When eval cost is large, the tax is a rounding error and smartness is nearly free.

This paper is a controlled demonstration that the best method is selected by the eval cost, not by the algorithm's reputation. We take a seeded synthetic multimodal objective (a stand-in for a noisy backtest, with a known optimum so regret is well defined) and three samplers spanning the throughput \leftrightarrow sample-efficiency axis: uniform random and scrambled Sobol (dumb, high-throughput) and a model-based sequential sampler (smart, sample-efficient, paying a real per-suggestion tax). We sweep the per-eval cost across four orders of magnitude under a fixed wall-clock budget and measure, from one seeded run: the throughput and eval count each method affords at each cost; the mean regret each achieves; the eval cost at which the smart sampler overtakes the best dumb one; and the monotone regime inversion between the cheap and expensive ends.

Scope and honesty constraints.

One constraint bounds every claim and we state it here in full. The timing is modeled, not measured. For each method we fix a per-suggestion ask/tell tax in seconds and we set a per-eval cost knob in seconds; the number of evaluations a fixed wall-clock budget affords is computed from them by n_{\mathrm{evals}}=\lfloor B/(\mathrm{tax}+\mathrm{eval\ cost})\rfloor. No real clock is read to produce the reported curves, which is precisely why they are seed-stable and machine-independent. A single actually-measured perf_counter timing of each sampler's ask/tell path is recorded in the results as a labelled plausibility check, but it is non-load-bearing: it does not feed the crossover in any way. The modeled tax stands in for the real, in-loop Python KDE/covariance/pruner overhead that a smart sampler pays — overhead the accompanying blog measured directly as an 18–30\times throughput hit. All numbers derive from one seeded run of one public harness (scripts/run_all.py), with the objective in scripts/objective.py and the samplers in scripts/samplers.py.

The objective, the samplers, and the ask/tell tax

The synthetic objective.

We optimize a deterministic, seeded, closed-form function over the unit square [0,1]^2 (dimension 2), designed to reward coverage-plus-placement the way a real search does. It is the sum of a broad quadratic bowl pulling toward the optimum, a narrow global Gaussian peak at a fixed known point x^\star=(0.62,0.41), and a lattice of eight deceptive Gaussian bumps that create genuine local traps strictly below the global peak: \begin{equation} \label{eq:objective} f(x) = -A\,\lVert x-x^\star\rVert^2 + H\,e^{-\lVert x-x^\star\rVert^2/2\tau^2} + \sum_{k=1}^{8} h_k\, e^{-\lVert x-c_k\rVert^2/2\sigma^2}, \end{equation} with A=1.2, H=1.0, \tau=0.05, \sigma=0.08. The peak is deliberately narrow (\tau=0.05): localizing it is a needle-in-haystack task that raw breadth (millions of cheap points) solves but a handful of points can miss, and that narrowness is what makes the eval-cost crossover appear. Because x^\star is known, the regret of the best-found point is a well-defined, honest quantity: \begin{equation} \label{eq:regret} \mathrm{regret}(x_{\mathrm{best}}) = f(x^\star) - f(x_{\mathrm{best}}) \ge 0. \end{equation} Each evaluation is a noisy observation, \mathrm{observe}(x)=f(x)+\varepsilon with \varepsilon\sim\mathcal{N}(0,\,\mathrm{noise\_std}^2) and \mathrm{noise\_std}=0.03, the analogue of a single backtest being a noisy estimate of a strategy's edge. The noise is deterministic in the query point (hashed to a seed), so re-querying a point reproduces its value — keeping the whole experiment seed-stable — while nearby points get independent draws, so a sampler cannot denoise for free. We score the best point found by its true value f, not by the lucky noisy observation that made us select it.

The three samplers.

We compare methods spanning the throughput \leftrightarrow sample-efficiency axis:

• random — independent uniform draws, the Bergstra–Bengio baseline [1]: dumb, maximal throughput.

• sobol — a scrambled Sobol / QMC sequence [6, 7]: dumb, but low-discrepancy, so better space coverage than uniform at the same count.

• sequential — a model-based sampler: a Sobol warm-up for coverage, then contracting-Gaussian exploitation of the best observed basin (a CMA-ES-like contraction with occasional wide explore jumps to escape traps). It is genuinely sample-efficient and stands in for the TPE / CMA-ES / ASHA family [2, 3, 5].

The ask/tell tax.

The dumb samplers emit a point in microseconds; the smart sampler pays milliseconds of per-suggestion bookkeeping (in a real TPE this is fitting kernel-density estimates on every ask, in CMA-ES a covariance update, in ASHA the pruner's rung accounting). We model this as a fixed per-suggestion tax in seconds: \mathrm{tax}=2\times10^{-6} for random, 3\times10^{-6} for Sobol, and 6\times10^{-3} for the sequential sampler — a 3000\times ratio between smart and dumb. This tax is the entire mechanism of the crossover.

The timing model (modeled, machine-independent)

Every method spends a fixed wall-clock budget B; each suggestion costs the tax plus the per-eval cost. The number of evaluations a method affords is therefore exactly \begin{equation} \label{eq:nevals} n_{\mathrm{evals}}(m,\, c) = \left\lfloor \frac{B}{\mathrm{tax}_m + c} \right\rfloor, \qquad \mathrm{throughput}(m,\,c) = \frac{1}{\mathrm{tax}_m + c}, \end{equation} where c is the per-eval cost and B=150 s. Equation (3) is the whole timing model. No wall clock is read: the reported curves are pure arithmetic over the two modeled quantities (tax and eval cost), which is why they reproduce bit-for-bit across machines and seeds. The two readings are the same fact, since \mathrm{throughput}=n_{\mathrm{evals}}/B up to the floor's sub-unit slack.

We stress the honesty boundary. The tax and the eval cost are modeled inputs, not measurements; n_{\mathrm{evals}} is computed, not timed. The harness does record one genuinely measured quantity — a perf_counter timing of each sampler's ask/tell path over a fixed number of points — but it is a labelled plausibility check that plays no part in the crossover. Its only purpose is to confirm the modeled ordering is not absurd (the sequential sampler's per-suggestion path is real Python work, the dumb samplers' is near-free). The load-bearing timing is entirely Eq. (3), and the tax it uses stands in for the KDE/covariance/pruner overhead a real smart sampler pays in the loop.

Results

All numbers below are from one seeded run (seed 0, Python 3.12.3, NumPy 2.5.1), sweeping 25 per-eval costs logarithmically from 10^{-4} to 10^{0} s under a B=150 s budget, averaging 12 seeds per cell.

Throughput and evaluations afforded.

Table 1 reads the timing model at the two ends of the sweep. At the cheap eval cost the tax dominates the denominator: the dumb samplers run at \sim\!9{,}800 evals/s while the sequential sampler is throttled to 164 evals/s, a 59.8\times throughput penalty, and over the same 150 s budget the dumb samplers afford 1.47 million evaluations against the sequential sampler's 24{,}590 — a 59.8\times gap in raw coverage. At the expensive eval cost the tax vanishes into the denominator: all three methods run at \approx\!1 eval/s and afford 149 evaluations each. The tax is fixed; only its significance moved.

Regret: cheap versus expensive.

Table 2 pairs the two ends with the mean regret each method reaches. In the cheap regime, breadth wins: uniform random reaches mean regret 0.0083 and scrambled Sobol 0.0112, both far below the sequential sampler's 0.0535 — the dumb samplers' 1.47 million scattered points localize the narrow peak that the sequential sampler's 24{,}590 carefully-placed points, throttled by the tax, cannot reliably reach. In the expensive regime the ordering inverts: with all methods pinned to 149 evaluations, the sequential sampler's placement reaches mean regret 0.104 while random balloons to 0.284 and Sobol to 0.230. The same three algorithms, the same objective; only the eval cost changed, and the ranking flipped.

The crossover eval-cost.

Sweeping the full 25-point grid, the sign of the regret gap (sequential minus the best dumb sampler) flips exactly once and stays flipped: dumb wins below, smart wins above. Interpolating in \log_{10}(\text{eval cost}) at the sign change locates the crossover at 0.1217 s/eval, bracketed by the grid points 0.10 s/eval (last dumb win) and 0.1468 s/eval (first smart win). Table 3 records it. This is the operational payoff: measure how long one evaluation of your objective takes; below \sim\!0.12 s buy throughput (random / Sobol), above it buy sample-efficiency (the smart sampler).

The monotone regime inversion.

The two endpoints are not a fluke of the extremes; the gap closes monotonically as eval cost rises. Table 4 traces the sequential sampler against the best dumb sampler across a representative slice of the grid. At 10^{-4} s the dumb best is 0.0083 and smart is 0.0535 (dumb ahead by a wide margin); the gap narrows through the 10^{-2} decade; the two curves cross near 0.12 s/eval; and by 10^{0} s smart is 0.104 against a dumb best of 0.230 (smart ahead). The inversion is a single, monotone hand-off, not a noisy tie.

Discussion

Throughput and sample-efficiency are two knobs, and the eval cost sets which one pays.

The dumb samplers maximize the number of points at the expense of their placement; the smart sampler maximizes placement at the expense of the count. Neither is universally better. Equation (3) makes the trade-off explicit: the tax and the eval cost sit in the same denominator, so shrinking the eval cost magnifies the tax and shrinking the tax is worth exactly as much as the eval cost is large. In the cheap regime the sequential sampler spends the overwhelming majority of its budget inside its own ask/tell machinery and only a sliver actually evaluating; a scrambled Sobol stream spends all of it evaluating. When looking is cheap, looking wins.

The reputation ordering is the wrong axis.

“Random is a baseline you outgrow” [1] and “model-based methods place points better” [2, 3] are both true statements about placement quality per point, and both are silent on the variable that decides the outcome under a wall-clock budget. Our sequential sampler is more sample-efficient — at equal evaluation count it reaches lower regret — and it still loses decisively in the cheap regime, because equal evaluation count is exactly what the tax denies it. The right question is never “which sampler places k points best” but “how many points does each afford, and how well-placed, once the tax is charged.”

A decision rule.

The rule needs one number: time a single evaluation of your objective. Below the crossover (\sim\!0.12 s/eval here) the tax on a smart sampler costs you an order of magnitude in point count for placement a near-free eval does not reward — use random or scrambled Sobol and spend the saved effort widening the search. Above it the tax is a rounding error — use the sample-efficient method and let it place its few, expensive points well. The exact crossover is objective-specific (it depends on the tax magnitude and the landscape), but the existence of a finite crossover, and the monotone inversion around it, are the general facts.

Limitations

• Modeled timing, not measured. The per-method ask/tell tax and the per-eval cost are fixed modeled seconds, and n_{\mathrm{evals}} is computed from Eq. (3), not read from a clock. This is what makes the results seed-stable and machine-independent, but it means the reported throughputs and eval counts are consequences of the modeled tax, not observations of a particular implementation. The modeled tax stands in for the real in-loop KDE/covariance/pruner overhead of a smart sampler; the recorded perf_counter sanity check confirms only that the modeled ordering is plausible and is explicitly non-load-bearing. A different implementation, with a different tax, moves the crossover; the mechanism — a finite crossover set by the tax/eval-cost ratio — does not.

• One synthetic objective. The numbers are specific to a single seeded multimodal function on [0,1]^2 with a narrow global peak, deceptive bumps, and observation noise 0.03. The magnitudes (the exact crossover, the regret levels) are tied to that landscape and to the tax values; a smoother objective, a wider peak, or a lower noise level moves them. The qualitative structure — dumb wins cheap, smart wins expensive, a finite crossover between — is what generalizes.

• A stand-in sequential sampler. Our smart sampler is a compact Sobol-warm-up-plus-contracting-Gaussian model, not a full TPE, CMA-ES, or ASHA implementation. It captures the two properties that matter here — genuine sample-efficiency and a real per-suggestion tax — but its exact regret curve is not a benchmark of any named library. The blog this accompanies measures the tax on real TPE/CMA-ES/ASHA implementations directly.

• Regret, not out-of-sample edge. We measure optimization regret against a known optimum, which is the right quantity for “which method searches best.” It is deliberately not a claim that the found optimum survives out-of-sample; on a real backtest the winner of any large search must still be deflated for multiple testing before it is believed. Search quality and tradability are separate instruments.

Conclusion

The best hyperparameter search method is not a property of the algorithm; it is selected by the cost of one evaluation. A smart sequential sampler pays a fixed per-suggestion ask/tell tax that a dumb sampler does not, and under a fixed wall-clock budget that tax is divided against the eval cost: n_{\mathrm{evals}}=\lfloor B/(\mathrm{tax}+\mathrm{eval\ cost})\rfloor. When one evaluation is cheap (10^{-4} s), the tax throttles the smart sampler's throughput 59.8\times (164 vs 9{,}804 evals/s) so it affords only 24{,}590 evaluations against the dumb samplers' 1.47 million, and breadth wins: mean regret 0.0083 (random) and 0.0112 (Sobol) beat the sequential sampler's 0.0535. When one evaluation is expensive (10^{0} s), the tax is a rounding error, all methods afford 149 evaluations, and placement wins: mean regret 0.104 (sequential) beats 0.284 (random) and 0.230 (Sobol). The ranking inverts monotonically, and the finite crossover sits at 0.122 s/eval, bracketed by 0.10 and 0.147 s/eval. The timing is modeled and we say so plainly: the tax and eval cost are fixed seconds, n_{\mathrm{evals}} is arithmetic over them, and the one measured perf_counter check is a non-load-bearing plausibility note. The practical rule is one measurement: time a single evaluation, and if it is cheaper than the crossover buy throughput, otherwise buy sample-efficiency. There is no single best optimizer — there is a regime, and a cost that selects it.

Reproducibility.

All numbers derive from one seeded run. scripts/run_all.py regenerates results/results.json from seed 0 (Python 3.12.3, NumPy 2.5.1) deterministically; the objective is in scripts/objective.py and the three samplers in scripts/samplers.py. The timing model is Eq. (3) (run_all.affordable_evals); the crossover locator is run_all.find_crossover. tests/ contains deterministic invariant tests for the objective (known optimum, seed-stable noise), the samplers (coverage, the tax ordering), the timing arithmetic, and the regime inversion.

References