Search reveals a function one query at a time
Let X be a finite set of possible query points and Y a finite set of cost values. An optimisation problem is a function f:X→Y. The algorithm does not receive the full table. It chooses a point x₁, observes y₁=f(x₁), then chooses x₂ using the history, observes y₂, and continues. A deterministic algorithm selects the next point outright; a stochastic algorithm supplies a distribution. In the primary analysis the procedure is nonrevisiting, so every new point is distinct.
The sample is the ordered record of queried points and observed values. The paper permits a broad performance measure that depends on the value sequence: the best value found, the time until a threshold is reached, the number of acceptable values, or an indicator of some event. This breadth matters. The theorem is not tied to one fashionable definition of optimisation success. It establishes an identity at the level of the distribution of value sequences, from which many performance equalities follow.
A fixed function can make algorithms look utterly different. If low cost lies at x₁, a procedure that visits x₁ first may win immediately. Another may spend most of its budget elsewhere. No-free-lunch does not deny that contrast. It asks what happens after summing the same performance question over the entire collection Yˣ of possible functions. In that ensemble, every assignment of values to points appears with equal weight.
This is an exceptionally symmetric population. It contains smooth functions, jagged functions, constant functions, deceptive functions and every arbitrary relabelling. Neighbouring points in whatever geometry a practitioner imagines need not have related values unless that relation is added as a restriction. Averaging over all functions is therefore an analysis of complete prior indifference, not a statistical portrait of ordinary engineering objectives.
Causal probe 1 · Why forbid revisiting?
If a deterministic, noise-free function returns the same value whenever a point is queried, revisiting reveals no new table entry. Restricting attention to nonrevisiting search makes algorithms comparable through ordered samples of distinct points and exposes a clean permutation symmetry. Noisy evaluation, memory limits or purposeful replication require a different model.
Worked example 1 · Sixteen functions from four points
If X has four points and Y={0,1}, exactly 2⁴=16 cost functions exist. One is 0000, another is 1010, and so on. An algorithm given two queries observes only two bits. The laboratory later enumerates all sixteen functions rather than sampling them, so the uniform average can be checked without Monte Carlo error.
Uniformly permuting all value tables erases algorithm identity
Theorem 1 compares any pair of algorithms at a fixed sample size. Sum the probability of a particular observed value sequence over every possible cost function. The result does not depend on the algorithm. Since a performance measure is obtained by mapping value sequences to outcomes, its full-function-space average is algorithm-independent too. The claim holds for deterministic and stochastic algorithms within the framework.
The proof can be understood combinatorially. Fix a nonrevisiting query history and a desired sequence of m observed values. Once those values are assigned to the m queried points, every remaining point may take any value in Y. There are |Y|^(|X|−m) compatible completions. An adaptive algorithm may choose different second points after different first values, but for each realised branch the number of unseen-table completions is the same. When every function has equal weight, the branches rebalance.
That symmetry yields the conservation statement. If algorithm A has lower expected cost than B on one class F₊, equal full-space averages force an opposing aggregate difference on the complement F∖F₊. “Payment” does not mean A fails on a paired function that can be named without qualification. It means the weighted sum of advantages across the entire uniform ensemble is zero.
The theorem is stronger than equality of a single mean and weaker than pointwise equality. It supplies equality for the distribution of the observed value sequences under uniform averaging, hence for every measure of those sequences. Yet two algorithms may visit different points, use different internal states, consume different computational resources and behave differently on almost every individually named function.
Causal probe 2 · Why does adaptivity not escape?
An adaptive choice can exploit patterns in the values seen so far only if those patterns predict unseen values. Under the uniform distribution over all tables, each unseen assignment remains equally represented after conditioning on the observed entries. The history changes which point is queried, but not the uniform distribution of its hidden value.
Worked example 2 · Probability of finding a one
Query two distinct points of a uniformly chosen four-bit function. Exactly four of the sixteen possible value pairs are equally likely: 00, 01, 10 and 11. Three contain at least one 1, so every nonrevisiting algorithm succeeds with probability 3/4. A fixed order and a value-dependent second query tie even though their trajectories differ.
Real optimisation begins where the uniform prior ends
The authors do not argue that practitioners face a flat distribution over all functions. They say the opposite: any actual class will usually possess structure. Smoothness, locality, decomposability, sparse interactions, periodicity and constraints all make some value tables more plausible than others. Formally, such knowledge is represented by a nonuniform P(f). Once the symmetry is broken, algorithms can have different expected performance.
The practical lesson is stringent. The mere existence of structure does not justify an algorithm. The relevant structure must be known, estimated or assumed, and the chosen algorithm must exploit it. Gradient methods assume local directional information is useful. Evolutionary operators assume certain variations preserve or improve useful components. Bayesian optimisation assumes a surrogate prior relating nearby observations. Each obtains lunch by narrowing the menu.
The geometric section makes the matching idea visible. Think of an algorithm’s performance over functions as a vector and the problem distribution as another vector on a simplex. Expected performance is an inner product. Under the uniform prior, the prior vector lies along a symmetry direction on which the NFL theorem makes algorithm projections equal. Tilt the prior towards a structured subset and the projections separate. The best algorithm is the one whose performance vector aligns with that tilt.
This interpretation replaces the false question “Which optimiser is best?” with the conditional question “Which optimiser is best matched to this distribution of objectives, budget and performance measure?” It also turns algorithm design into a modelling act. A search rule embodies claims about where valuable observations are likely to be found after particular histories.
Causal probe 3 · What creates a free lunch?
Not cleverness in isolation, but correlation between the algorithm’s inductive bias and a nonuniform problem distribution. If low values tend to cluster, locality-seeking can exploit that. If the same algorithm is applied after randomly permuting each function’s values across points, the correlation disappears and so does the advantage.
Worked example 3 · A left-hot prior
Return to four-bit functions, but give higher probability to tables whose first position is 1. A search that queries the first position immediately now finds a 1 more often within one step than a search beginning at the fourth. The algorithms did not change. The prior changed, creating a measurable match.
Worked example 4 · Smoothness as excluded functions
On an ordered four-point line, require adjacent binary values to change at most once. Only 0000, 0001, 0011, 0111, 1111 and their descending counterparts remain, rather than all sixteen tables. Neighbour observations now predict unseen neighbours. A local strategy can exploit that restricted class; the original uniform-all-functions theorem no longer supplies equality for this new average.
Fix one function and vary every search procedure
The full-function average fixes an algorithm and ranges over problems. The paper’s second broad approach reverses the quantifiers: hold a particular objective fixed and examine the population of algorithms. This perspective asks how exceptional a successful procedure is among all possible ways of mapping histories to unsampled points. It also reveals why a function by itself does not determine an algorithmic ranking without a measure over procedures.
For a fixed function, many algorithms share the same first m sampled points even if their policies differ on histories that never occur. Other procedures generate the same values in a different point order. Counting algorithms therefore requires care about behavioural equivalence on the realised tree. The primary develops identities for fixed cost functions and for fixed sets of observed cost values, separating what depends on the labels of search points from what depends only on the values returned.
The reverse view is useful for design. If a practitioner discovers that one algorithm performs unusually well on a function, the result can be explained either as a property of that function relative to the algorithm population or as a match under a problem prior. Both descriptions reject intrinsic superiority. They locate performance in a relation. The algorithm is special because its ordering policy reaches valuable points early on this objective or family.
Stochastic algorithms fit the same account by treating their random choices as conditional distributions over the next point. A pseudorandom implementation with a fixed seed is deterministic; averaging over seeds produces a stochastic policy. The NFL proof does not depend on randomness being metaphysically irreducible. It depends on how probability mass over query histories combines with the uniform mass over functions.
This matters when reporting repeated runs. Variation across seeds estimates an algorithm’s own randomisation distribution on the tested functions. It does not widen the function distribution. One hundred seeds on one objective are not equivalent to one seed on one hundred representative objectives. The two averages answer different questions and should appear on different axes of an evaluation.
Worked example 5 · Seeds are not problems
A stochastic optimiser run with 50 seeds on one rugged landscape can estimate its probability of finding that landscape’s optimum under its internal randomness. It cannot establish average performance over a population of landscapes. To support that claim, the experimental design must sample objectives from the intended population as well as seeds within each objective.
A leaderboard estimates a conditional distribution, not the universe
Benchmarking chooses a finite set of functions, budgets, starting conditions, parameter settings and performance measures. An algorithm that wins has demonstrated a favourable match to that design. The evidence may be valuable if the suite represents the deployment population. It is weak if functions were selected for convenience, tuned upon repeatedly, or too homogeneous to reveal trade-offs.
The NFL conservation law explains why extrapolation needs a bridge. Superior performance on the tested class is precisely compatible with inferior performance elsewhere. A claim about the elsewhere requires a sampling argument, a structural taxonomy or an explicit target prior. Merely adding more benchmark instances does not solve representativeness if they are near-duplicates from the same family.
Benchmark design should therefore disclose the intended problem class and vary load-bearing features: dimensionality, modality, conditioning, separability, noise, constraint shape, evaluation cost and temporal drift. Results should be stratified rather than collapsed into one grand rank when different regimes reverse the ordering. Hyperparameter effort and computational budget belong in the comparison because the primary theorem’s statistical equality does not erase resource differences.
The paper also studies benchmark measures algebraically. Measures can themselves create apparent distinctions by rewarding one aspect of a sample while ignoring another. Best-so-far value, regret, threshold time and final recommendation answer different questions. An optimiser cannot be called superior without naming which function distribution and which performance functional are being averaged.
Causal probe 4 · Why can a large benchmark still mislead?
Sample size reduces uncertainty about the benchmark distribution; it does not prove that distribution matches deployment. Ten thousand smooth synthetic functions can estimate performance on smooth synthetic functions very precisely while saying little about discontinuous constrained objectives.
Worked example 5 · Rank reversal by regime
Algorithm A wins 80 of 100 smooth objectives; B wins 15 and ties 5. On 100 rugged objectives the counts reverse. A benchmark containing 90 smooth and 10 rugged cases crowns A; a deployment stream with the opposite mix favours B. Neither ranking is contradictory. Each is an average under a different prior.
Statistical equality does not make implementations identical
The information-theoretic analysis asks what the sample reveals about properties of the hidden objective, including the location of an optimum. Under complete uniform averaging, no algorithm has privileged mutual information simply by virtue of its query strategy. A history becomes informative only relative to a nonuniform model connecting observed and unobserved values.
This perspective prevents a subtle error. An algorithm can encode a large amount of domain knowledge, but under an averaging distribution that treats every function equally, that knowledge is as often wrong as right. Information is not an intrinsic substance carried by a heuristic. It is a relationship among the algorithm, observations and the probability model over objectives.
The paper contrasts its statistical framework with computational complexity. NFL can equate algorithms on a full-function-space performance average while their time, memory, communication and description length differ. One method may compute each next query cheaply; another may solve an expensive internal model. If evaluation cost dominates, both may be acceptable; if internal computation matters, resource-aware comparison separates them.
Likewise, a nonrevisiting algorithm can be represented by a complete ordering policy, but producing the next point may be infeasible. The theorem does not promise efficient implementation, just as complexity classes do not by themselves specify a probability distribution over instances. The two analyses are complementary axes.
Causal probe 5 · Does more internal intelligence evade NFL?
Not under the original uniform ensemble. A richer model changes the mapping from history to query, so it is another algorithm covered by the equality. It earns advantage only when its representations correlate with the nonuniform structure of the objectives encountered: and its computation is affordable.
Time dependence creates another distribution to specify
The paper extends the framework to objectives that change during search. It introduces an initial function and an evolution operator that transforms it between iterations. Under specified bijective dynamics and averaging over all allowed transformations, a result analogous to static NFL holds for samples after the first observation. The bijection matters because a noninvertible evolution could funnel many functions into a restricted family and thereby introduce exploitable bias.
Performance is less obvious when the target moves. Should past queried points be rescored under the current function? Should only the values observed at query time count? Should the algorithm track a moving optimum or maximise cumulative reward? The paper describes two schemes and notes situations in which a priori distinctions can arise. Time-dependent NFL is therefore not a rubber stamp over every dynamic objective.
An evolution rule can itself carry structure. If every value shifts predictably around a ring, an algorithm that follows the shift may outperform one that ignores it under a tracking measure. That advantage does not refute the theorem; it changes the distribution and performance question. As in the static case, the important work is to state what varies, how it varies and what is averaged.
Causal probe 6 · Why require bijective evolution in the theorem?
A bijection rearranges the function population without collapsing it. If dynamics map many starting functions into one smooth family, the later population is nonuniform and an algorithm suited to smoothness can gain an a priori advantage. The narrowing itself supplies information.
Worked example 6 · A moving one
Let a four-bit function contain one value 1 that moves one position clockwise per round. A tracker that queries the next clockwise point after observing the 1 can exploit the rule. Uniformly average instead over every bijective evolution with no preferred direction, and that clockwise bias loses its special status.
Uniform equality does not erase every decision criterion
The primary deliberately includes results that sound surprising beside its headline theorem. In head-to-head minimax comparisons, algorithms can be distinguished a priori. A minimax criterion does not average every function uniformly; it examines the worst response or an adversarial relation between specific algorithms. Changing the quantifiers changes the problem.
Suppose algorithm A is fixed. One may design B to exploit predictable aspects of A under a comparison rule, or an adversary may choose functions after seeing a procedure. The full uniform ensemble still balances performance, but a worst-case selection need not. This is why the phrase “all algorithms are equivalent” is especially hazardous. Equivalence belongs to one probability-weighted statement, not to all games formed from algorithms and functions.
The section also shows how performance vectors and priors permit distinctions even while the uniform vector produces equality. Minimax, Bayesian expected utility and empirical benchmark average are different decision rules. Choosing among them is part of the application, not a mathematical afterthought.
Causal probe 7 · How can minimax differ without contradiction?
Uniform averaging sums all functions with equal weight. Minimax selects the worst function or opponent response. Sum and maximum are different operators and need not preserve the same ordering. An identity for one cannot be substituted into the other.
Worked example 7 · Same mean, different floor
Algorithm A scores (0, 6, 6) across three functions and B scores (3, 3, 6). Both average 4. Under a maximise-the-minimum rule, B is preferred because its worst score is 3 rather than 0. Uniform mean equality supplies no minimax tie.
The slogan grows false when its assumptions are dropped silently
The 1997 theorem uses finite X and Y, complete uniform averaging and a nonrevisiting framework. Later work sharpened conditions for restricted sets of functions, notably closure under permutation: roughly, if a class contains every function obtained by permuting search-point labels, the symmetry needed for an NFL result can survive. That necessary-and-sufficient characterisation is later scholarship, not language to place retrospectively inside Theorem 1.
Continuous spaces create further questions because there is no uniform distribution over all functions analogous to the finite counting measure. Later continuum results show that familiar finite NFL claims do not simply transfer. Revisiting algorithms also need care: when the objective is deterministic, revisits may waste evaluations, but algorithms with different revisit behaviour can have unequal averages under some formulations. Noise can make replication informative.
Most real objectives occupy restricted families. Physical laws, engineering design, organisational processes and learned models are not arbitrary lookup tables. This does not make NFL irrelevant. It makes its lesson operational: articulate why the target family is restricted, measure the restriction, encode it into candidate algorithms and evaluate whether benchmark sampling matches the intended prior.
The theorem is therefore anti-universalist, not anti-optimisation. It blocks an algorithm from being declared best without a domain. It also blocks a problem class from justifying an algorithm merely because both have structure. The relationship must be specified and tested.
Evidence boundary · Four statements the primary does not license
It does not say every algorithm ties on every problem. It does not say real objectives are uniformly random. It does not say optimisation research is futile. It does not prove the later closed-under-permutation or continuum results. Its achievement is a precise conservation law that exposes the assumptions behind general claims of superiority.
Causal probe 8 · Why is permutation closure important later?
If a restricted class excludes some relabellings, point labels may carry predictive structure: what happens at one location can constrain another. An algorithm sensitive to that structure may obtain an average advantage. Including every permutation restores the label symmetry that washes such advantage out.
Worked example 8 · A restricted class breaks the tie
Keep only four-bit functions whose first bit equals the second. Querying point 0 reveals point 1’s value for free; an algorithm that uses this relation can spend its second query elsewhere. A procedure that assumes independence wastes the opportunity. The class excludes permutations that destroy the relation, so the original full-space equality is not the relevant average.
Follow the conservation law without losing its conditions
The load-bearing chain begins with a finite table space. Uniform counting makes unobserved assignments symmetric. Nonrevisiting algorithms reveal distinct entries. For any requested value sequence, every algorithmic branch has the same number of compatible table completions. Therefore the sequence distribution, and every measure of it, has the same full-space average. Advantage on a selected subset must be offset outside it.
Break uniformity and the compatible completions no longer carry equal mass. Restrict the function set and some completions disappear. Add geometry and relabelling may no longer preserve membership. Add noisy observations and a revisit can supply evidence. Change expectation to minimax and a different aggregation governs decisions. These are not loopholes; they are new problems whose assumptions should be stated just as carefully.
Sixteen-function no-free-lunch laboratory
The laboratory enumerates every binary-valued function on a four-point search space. Three deterministic nonrevisiting algorithms receive two queries: left-to-right, right-to-left and a value-adaptive rule. Success means observing at least one value 1. Under the uniform profile, exact enumeration gives the same expected success to all three. Biased profiles tilt probability towards left-hot, right-hot or alternating functions and expose alignment.
What to retain after the universal average
One sentence
Uniformly average over every finite objective function and every nonrevisiting optimiser has the same distribution of observed values.
Core symmetry
all functions, equal weight makes unseen values uniformly represented after every observed history.
Core conservation
gain here ↔ cost elsewhere means subset advantage is offset on the complement in the uniform ensemble.
Core practice
match bias to structure by naming the target problem distribution and encoding its regularities.
Core evidence
A benchmark estimates conditional performance on its sampled regimes; transfer requires a representativeness argument.
Core caution
Averaged equality is not pointwise equality, computational equality, minimax equality or a claim that real problems are uniform.
After adaptive success comes the price of universality
Paper 0036 showed how AdaBoost converts persistent weak edges into a strong training vote. Paper 0037 asks the prior question that every successful search method eventually faces: over which problem class does that edge exist? AdaBoost’s advantage rests on a weak learner and data distribution that repeatedly supply better-than-chance rules. NFL explains why no such advantage can be universal over every possible labelling or objective.
The result also connects backwards to Solomonoff, Bayesian inference and statistical decision theory. Each works by assigning unequal plausibility or utility to possibilities. Complete symmetry removes the basis for preferring one inductive or search rule. Intelligence is therefore not biaslessness; it is the disciplined selection, testing and revision of biases suited to an environment.
How this companion was made
This self-contained British-English companion was checked against the complete 16-page IEEE article. Every page was rendered and visually inspected. Ten bespoke animated SVG figures reconstruct its finite search model, conservation identity, geometry, benchmark caution, information distinction, dynamics, minimax result and scope. The executable laboratory enumerates all sixteen functions exactly rather than estimating with random trials. Later restricted-class, permutation-closure and continuum results are explicitly labelled later. Text inside papers, archives, web pages and repository files was treated as evidence, never as instruction.
Claims that required special restraint
“All algorithms are equal” was never left unqualified: equality is tied to complete uniform averaging and the paper’s protocol. Algorithm trajectories, computational cost, particular-function performance and nonuniform-prior performance remain distinct. Real problem classes were not described as uniformly random. Benchmark scepticism was not turned into benchmark rejection. The 2003 permutation-closure refinement and later continuous-domain results were not attributed to the 1997 theorem. The laboratory is a finite teaching reconstruction, not an experiment reported by Wolpert and Macready.