% Choose the Search Method by the Cost of One Evaluation.
% Controlled, seeded study of the throughput-vs-sample-efficiency crossover in
% hyperparameter search. Every number in this manuscript comes from
% results/results.json (seed 0), produced by scripts/run_all.py.
% TIMING IS MODELED, not measured (see the timing-model section and limitations).
% Primary arXiv category: cs.LG (Machine Learning).
% Cross-list: math.OC (Optimization and Control), stat.ML (Machine Learning).
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}
\usepackage[numbers,round]{natbib}
\usepackage{microtype}
\usepackage[hidelinks]{hyperref}
\setlength{\emergencystretch}{2em}

\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\evals}{n_{\mathrm{evals}}}

\title{Choose the Search Method by the Cost of One Evaluation:\\
A Reproducible Throughput-versus-Sample-Efficiency Crossover\\
in Hyperparameter Search}
\author{Eugen Soloviov}
\date{July 2026}

\begin{document}
\maketitle

\begin{abstract}
Which hyperparameter search method is best --- dumb high-throughput sampling
(random, scrambled Sobol) or a smart sample-efficient sequential sampler (the
TPE / CMA-ES / ASHA family) --- is usually argued as a property of the
algorithm. We show, on a seeded synthetic multimodal objective, that it is
instead a property of one external number: the cost of a single evaluation. A
smart sequential sampler pays a fixed per-suggestion \emph{ask/tell tax} for its
modeling; a dumb sampler emits a point for almost nothing. Under a fixed
wall-clock budget, the number of evaluations a method affords is exactly
$\evals=\lfloor B/(\mathrm{tax}+\mathrm{eval\ cost})\rfloor$, so the tax is
divided against the eval cost. When one evaluation is cheap ($10^{-4}$ s), the
smart sampler's tax throttles its throughput $59.8\times$ ($164$ vs
$9{,}804$ evals/s), letting it afford only $24{,}590$ evaluations against the
dumb samplers' $1.47$ million; breadth wins and mean regret is $0.0083$ for
random and $0.0112$ for Sobol versus $0.0535$ for the sequential sampler. When
one evaluation is expensive ($10^{0}$ s), the tax is a rounding error, all
methods afford the same $149$ evaluations, and sample-efficiency wins: mean
regret is $0.104$ for the sequential sampler versus $0.284$ (random) and
$0.230$ (Sobol). The ranking inverts monotonically, and we locate the finite
crossover eval-cost at $0.122$ s/eval (bracketed by the grid points $0.10$ and
$0.147$ s/eval). We state plainly that the timing is \emph{modeled}: the tax and
eval cost are fixed seconds and $\evals$ is computed from them, so every curve
is seed-stable and machine-independent; a real \code{perf\_counter} measurement
is recorded as a labelled, non-load-bearing plausibility check only. The modeled
tax stands in for the real KDE/covariance/pruner overhead an in-loop smart
sampler pays. This study accompanies a \href{https://marketmaker.cc}{marketmaker.cc}
blog post.
\end{abstract}

\section{Introduction}
\label{sec:intro}

Hyperparameter search offers a menu of methods with a rough reputation ordering.
Random search is the cheap baseline you are told you outgrow
\citep{bergstra2012random}; Bayesian and model-based sequential methods --- the
Tree-structured Parzen Estimator (TPE)~\citep{bergstra2011tpe}, CMA-ES~\citep{hansen2016cmaes}
--- are supposed to beat it by placing each point more carefully; multi-fidelity
pruners like Hyperband and ASHA~\citep{li2018hyperband,li2020asha} 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: \emph{deciding where to sample
next} (the sampler's own compute) and \emph{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
$\evals \approx B/(\mathrm{tax}+\mathrm{eval\ cost})$. The tax is a roughly fixed
number of seconds per suggestion, but its \emph{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 \emph{method} is selected
by the eval \emph{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.

\paragraph{Scope and honesty constraints.} One constraint bounds every claim and
we state it here in full. \emph{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
$\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 \code{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
(\code{scripts/run\_all.py}), with the objective in \code{scripts/objective.py}
and the samplers in \code{scripts/samplers.py}.

\section{The objective, the samplers, and the ask/tell tax}
\label{sec:setup}

\paragraph{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 \emph{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 \emph{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
\emph{true} value $f$, not by the lucky noisy observation that made us select it.

\paragraph{The three samplers.} We compare methods spanning the throughput
$\leftrightarrow$ sample-efficiency axis:
\begin{itemize}
\item \textbf{random} --- independent uniform draws, the Bergstra--Bengio
  baseline \citep{bergstra2012random}: dumb, maximal throughput.
\item \textbf{sobol} --- a scrambled Sobol / QMC sequence
  \citep{sobol1967distribution,owen1998scrambling}: dumb, but low-discrepancy, so
  better space coverage than uniform at the same count.
\item \textbf{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
  \citep{bergstra2011tpe,hansen2016cmaes,li2020asha}.
\end{itemize}

\paragraph{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 \code{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.

\section{The timing model (modeled, machine-independent)}
\label{sec:timing}

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}
\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~\eqref{eq:nevals} 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}=\evals/B$ up to the floor's sub-unit slack.

We stress the honesty boundary. The tax and the eval cost are \emph{modeled}
inputs, not measurements; $\evals$ is \emph{computed}, not timed. The harness does
record one genuinely measured quantity --- a \code{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 \emph{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.~\eqref{eq:nevals}, and the tax it uses stands
in for the KDE/covariance/pruner overhead a real smart sampler pays in the loop.

\section{Results}
\label{sec: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.

\paragraph{Throughput and evaluations afforded.} Table~\ref{tab:throughput} 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.

\begin{table}[t]
\centering
\caption{The timing model at the two ends of the sweep (seed $0$, budget
$B=150$ s). At the cheap eval ($10^{-4}$ s) the sequential sampler's ask/tell tax
throttles its throughput $59.8\times$ and it affords $59.8\times$ fewer
evaluations; at the expensive eval ($10^{0}$ s) the tax is negligible and all
methods afford the same $149$ evaluations.}
\label{tab:throughput}
\begin{tabular}{lrrrrr}
\toprule
& & \multicolumn{2}{c}{cheap eval ($10^{-4}$ s)} & \multicolumn{2}{c}{expensive eval ($10^{0}$ s)}\\
\cmidrule(lr){3-4}\cmidrule(lr){5-6}
Method & tax (s) & throughput (ev/s) & evals & throughput (ev/s) & evals \\
\midrule
random     & $2\times10^{-6}$ & $9{,}804$ & $1{,}470{,}588$ & $1.000$   & $149$ \\
sobol      & $3\times10^{-6}$ & $9{,}709$ & $1{,}456{,}310$ & $1.000$   & $149$ \\
sequential & $6\times10^{-3}$ & $164$     & $24{,}590$      & $0.994$   & $149$ \\
\bottomrule
\end{tabular}
\end{table}

\paragraph{Regret: cheap versus expensive.} Table~\ref{tab:regret} 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.

\begin{table}[t]
\centering
\caption{Regret at the two ends of the sweep (mean over $12$ seeds, seed $0$).
Cheap eval: the dumb high-throughput samplers win (lower regret) on breadth.
Expensive eval: the smart sequential sampler wins on sample-efficiency. The best
method in each regime is in the leftmost winning column.}
\label{tab:regret}
\begin{tabular}{lrrr}
\toprule
& \multicolumn{3}{c}{mean regret ($\downarrow$ better)}\\
\cmidrule(lr){2-4}
Eval cost & random & sobol & sequential \\
\midrule
cheap ($10^{-4}$ s)     & $\mathbf{0.0083}$ & $0.0112$ & $0.0535$ \\
expensive ($10^{0}$ s)  & $0.2837$          & $0.2303$ & $\mathbf{0.1040}$ \\
\bottomrule
\end{tabular}
\end{table}

\paragraph{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~\ref{tab:crossover} 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).

\begin{table}[t]
\centering
\caption{The crossover eval-cost (seed $0$): the per-eval cost at which the smart
sampler's mean regret overtakes the best dumb sampler's and stays ahead,
interpolated in $\log_{10}(\text{eval cost})$ at the regret-gap sign change.}
\label{tab:crossover}
\begin{tabular}{lr}
\toprule
Quantity & Value \\
\midrule
crossover eval-cost (interpolated)      & $0.1217$ s/eval \\
bracket, last dumb-win grid point       & $0.1000$ s/eval \\
bracket, first smart-win grid point     & $0.1468$ s/eval \\
\bottomrule
\end{tabular}
\end{table}

\paragraph{The monotone regime inversion.} The two endpoints are not a fluke of
the extremes; the gap closes monotonically as eval cost rises.
Table~\ref{tab:inversion} 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.

\begin{table}[t]
\centering
\caption{The regime inversion across eval cost (mean regret over $12$ seeds, seed
$0$). ``dumb best'' is the smaller of random and Sobol at that cost. The sign of
(sequential $-$ dumb best) is positive (dumb wins) at low cost and negative (smart
wins) at high cost, flipping once near the crossover at $0.122$ s/eval.}
\label{tab:inversion}
\begin{tabular}{rrrrl}
\toprule
Eval cost (s) & dumb best & sequential & sequential $-$ dumb best & winner \\
\midrule
$1\times10^{-4}$ & $0.0083$ & $0.0535$ & $+0.0452$ & dumb \\
$1\times10^{-3}$ & $0.0092$ & $0.0538$ & $+0.0446$ & dumb \\
$1\times10^{-2}$ & $0.0101$ & $0.0530$ & $+0.0428$ & dumb \\
$1\times10^{-1}$ & $0.0413$ & $0.0507$ & $+0.0095$ & dumb \\
$1\times10^{0}$  & $0.2303$ & $0.1040$ & $-0.1263$ & smart \\
\bottomrule
\end{tabular}
\end{table}

\section{Discussion}
\label{sec:discussion}

\paragraph{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~\eqref{eq:nevals} 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.

\paragraph{The reputation ordering is the wrong axis.} ``Random is a baseline you
outgrow'' \citep{bergstra2012random} and ``model-based methods place points
better'' \citep{bergstra2011tpe,hansen2016cmaes} 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 \emph{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.''

\paragraph{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 \emph{existence} of a finite crossover, and the monotone
inversion around it, are the general facts.

\section{Limitations}
\label{sec:limitations}

\begin{itemize}
\item \textbf{Modeled timing, not measured.} The per-method ask/tell tax and the
  per-eval cost are fixed modeled seconds, and $\evals$ is computed from
  Eq.~\eqref{eq:nevals}, 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
  \code{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.
\item \textbf{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.
\item \textbf{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.
\item \textbf{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 \emph{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.
\end{itemize}

\section{Conclusion}
\label{sec: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:
$\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, $\evals$ is arithmetic over them, and the one
measured \code{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.

\paragraph{Reproducibility.} All numbers derive from one seeded run.
\code{scripts/run\_all.py} regenerates \code{results/results.json} from seed $0$
(Python 3.12.3, NumPy 2.5.1) deterministically; the objective is in
\code{scripts/objective.py} and the three samplers in \code{scripts/samplers.py}.
The timing model is Eq.~\eqref{eq:nevals} (\code{run\_all.affordable\_evals});
the crossover locator is \code{run\_all.find\_crossover}. \code{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.

\bibliographystyle{plainnat}
\bibliography{refs}

\end{document}
