A failure teaches a schedule nothing

What the hindsight was worth priced a borrowed result on a folding search. The search looks for a consistent mountain-valley lettering of the rhombille tessellation patch; it finishes in eighty-four nodes on its best run and not at all inside twenty thousand on two runs in five, and stopping every attempt at a hundred nodes and starting again costs 512 in expectation. That cutoff was read off 120 measured runs afterwards. The universal schedule of Luby, Sinclair and Zuckerman, which knows nothing about the runs, costs 3,222 — 6.3 times as much — and a larger unit brings it close to the hindsight, at the price of knowing what unit to choose.

It ended with the middle course that seems to sit between knowing nothing and knowing everything. Estimate the scale of the running times from the attempts already made, and set the unit from the estimate. Every failed attempt carries information about the distribution — at the least, that runs of that length fail — and a schedule that adjusted as it went might recover most of the factor of six.

It cannot, and the reason is short enough to state before measuring anything.

What a failed attempt reports #

A restart schedule runs an attempt with some cutoff $c$. Either the attempt finishes before $c$, and the whole job is over, or it reaches $c$ and is stopped. In the second case it has cost exactly $c$, and the only thing learnt is that this run needed more than $c$. The number of nodes the run would eventually have taken is not observed; that is what stopping it means.

So consider any rule that chooses the next cutoff from what it has seen. Before the first attempt it has seen nothing, and chooses some $c_1$. If the job is still running at the second attempt, the first attempt failed, and what it has seen is “an attempt at $c_1$ failed” — which it could have predicted with certainty, since otherwise the job would be over. Every history a rule can observe while still running is the history in which every earlier attempt failed, and there is exactly one such history for each attempt number.

A rule that learns from its failures therefore chooses the cutoff for attempt $i$ as a function of $i$ alone. It is a fixed list, written down in advance, and its expected cost is computed exactly as any fixed list’s is:

$$\mathbb{E}[\text{cost}] = \sum_i \Pr(\text{attempts } 1 \ldots i-1 \text{ fail}) \cdot \mathbb{E}[\min(X, c_i)],$$

with $X$ the running time of a fresh attempt. The first figure writes down five rules’ lists. Doubling after every failure is 1, 2, 4, 8, …; growing by half is 1, 2, 3, 4, 6, 8, 12, …; the universal schedule is 1, 1, 2, 1, 1, 2, 4, … . Nothing any attempt does could change a single entry.

And no list beats the hindsight cutoff #

Luby, Sinclair and Zuckerman proved the other half in the same 1993 paper. When the distribution of running times is known, the best strategy of any kind is a fixed cutoff repeated forever — the one minimising one attempt’s expected cost divided by its chance of succeeding. Every list, adaptive-looking or not, is a strategy, so no list can cost less than the best fixed cutoff for that distribution.

Put together, the two halves close the question the earlier essay left. A schedule reading its own failures is a list; no list beats the hindsight cutoff; and which list comes nearest depends on the distribution, which is exactly what the schedule does not know. The gap between knowing nothing and knowing the cutoff cannot be crossed by watching failures, because failures are the one observation that knowing nothing already predicts.

What the lists cost on the measured runs #

The prices are exact expectations over the same 120 runs the hindsight cutoff was read from.

Doubling after every failure costs at least 1,820 nodes, 3.56 times the hindsight. It spends its early attempts far below the eighty-four nodes the fastest run needs, which costs little, and then doubles past the hundred-node sweet spot to 128, 256, 512 and beyond, where each failed attempt is expensive and the chance of failing is still about two in three. Doubling from sixteen costs about the same, at least 1,805: skipping the cheap early attempts saves almost nothing, because they were nearly free.

Growing by half after each failure does better, at least 1,204 — 2.35 times — because it lingers longer near the right scale: its cutoffs run 58, 87, 130, 195, 292, spending several attempts in the range where a run of this search is likeliest to finish.

The universal schedule at a unit of one costs 3,222, the worst of the rules measured here, and that is its design: it spends a fixed share of effort at every scale, including the ones far below where anything finishes, in exchange for a guarantee that holds on every distribution. The geometric rules have no such guarantee and do better here only because this search’s tail happens to suit them.

Three of the four are lower bounds. The measurement stops each run at twenty thousand nodes, and a list whose cutoffs pass that while there is still a real chance of failing cannot be priced beyond it; the true cost is at least what is shown. None of them comes within a factor of two of the hindsight, and none could, since the one list that would is the constant hundred that only hindsight chose.

Why the lists that do well do well here #

It would be a mistake to read the ranking of the four lists as a ranking of the rules. On a different search the order could reverse, and the reason is visible in the fixed-cutoff curve drawn further down.

Stopping is cheaper than finishing found that this search’s expected cost under a fixed cutoff is nearly flat from a hundred nodes to two hundred — 512, 532, 530 — and climbs steeply after. A list does well here if it spends many attempts in that flat stretch and few beyond it, and growing by half does exactly that by accident of its ratio: five of its cutoffs lie between 58 and 292. Doubling puts only two there, and the universal schedule, at a unit of one, reaches a cutoff of 128 only on its 255th attempt.

On a search whose flat stretch sat at ten thousand nodes, growing by half would take about two dozen attempts to get there and doubling fifteen, and the universal schedule would be the only one with a guarantee on how much it wasted on the way. The geometric rules are not learning; they are guessing the scale in a particular shape, and a guess that fits one distribution is a guess that misfits another.

The difficulty was in the coin located the source of this search’s tail in the randomisation of the letter order itself, which is also why a restart helps at all: each attempt draws a new order, so each attempt is a fresh chance at an easy run. That independence is what makes the expected cost a clean sum, and it is also what makes a failure uninformative — a new draw owes nothing to the draw before it.

The units on that figure make the same point from the other direction. Every unit is a guess made before the first attempt, and a guess near the scale of the runs does well while a guess far below does badly; the entire difference between the rows is information about the scale that no row acquired by running. What remains is where such a guess could honestly come from.

Information from outside the run #

The fifth bar in the second figure is the universal schedule with a unit chosen differently. The search has been run on four other patches — the square, elongated, hexagonal and triangular — and on none of them does it ever take more than 53 nodes. Take that as the unit, so the schedule’s cutoffs are 53, 53, 106, 53, 53, 106, 212, …, and its expected cost on the rhombille patch is 872: 1.70 times the hindsight, against 6.30 for a unit of one.

That unit is not hindsight about the rhombille patch; it was fixed before a single rhombille run. It is a statement about how long this search takes on patterns of this kind, and it is information the rhombille runs themselves could never have supplied, because it came from runs that succeeded. A search that fails tells a schedule nothing; a search that succeeds elsewhere tells it the scale of success.

The price is an assumption. Borrowing a unit assumes the new pattern’s easy runs look like the old patterns’ runs, and the rhombille patch is exactly the pattern where that assumption is least safe: its fastest run, 84 nodes, is longer than every run on every other patch. The borrowed unit worked because it undershot by less than a factor of two, and the universal schedule’s structure — every scale tried, each half as often as the one below — absorbs an undershoot at a logarithmic price.

The field found this first #

Results about folding keep turning out to have been found elsewhere first, and this one was.

The restart result is from Luby, Sinclair and Zuckerman, 1993, and the impossibility here is a direct reading of it: their optimal strategy for a known distribution and their universal strategy for an unknown one bracket every schedule that sees only failures. What the study of search did next is the part that matters.

Gomes, Selman and Kautz, 1998, established that randomised restarts are what make heavy-tailed combinatorial search practical, which is the cure that was named first. And in 2002, Kautz, Horvitz, Ruan, Gomes and Selman proposed dynamic restart policies: rather than learning from the bare fact of failure, they watched each run from the inside — features of the search’s state in its first few hundred steps — and used a model trained on many previous runs to predict whether this run was a long one. That is the move the argument here forces. A schedule can learn while searching only if the run reports more than whether it has finished, and a prediction built from features needs a population of earlier runs to be trained on, which is information from outside the run in exactly the sense the borrowed unit is.

So the field’s answer to “can the unit be learnt while searching” was the same as the arithmetic’s: not from failures, and yes from observations of the run’s interior backed by other instances. The tail was named somewhere else found the heavy tail described in that field before it was met on a crease pattern; the limit on learning was described there too, implicitly in 1993 and explicitly in 2002.

What a run of this search could report #

The dynamic-policy idea translates directly, and it is worth saying what the features would be.

The lettering search assigns a letter to a crease, propagates what the vertex conditions force, and backtracks when a vertex has no consistent letter. A run that is going to be long has, early on, made a choice high in its tree that it will spend thousands of nodes failing to recover from. The order that proves nothing exists found the cost of a refutation set by how many free choices sit above the contradiction, which is a quantity visible within a few dozen nodes: the depth of the deepest backtrack so far, the number of creases still free, the number of vertices whose letters were forced rather than chosen.

None of those is measured here, and a policy built on them would need the 120 runs split into ones it learns from and ones it is tested on. What the arithmetic establishes is that such features are necessary for learning within a run, not that these particular ones suffice.

What the pricing assumes #

Attempts are independent. Each restart starts the search with a fresh random order, so its running time is a fresh draw from the same distribution. That independence is bought with the search’s own coin, and restarting what cannot be restarted is the reminder of what that means: taking the coin out gives a deterministic search that finishes the same patch in eighty nodes and has nothing left to reseed, so every schedule priced here is a schedule for a tail the randomisation created in the first place. A restart that kept anything from the previous attempt — a learnt clause, a remembered forced letter — would violate this, and would also be a way of carrying information from failures that the argument above excludes by assumption.

The distribution is the empirical one. The 120 measured runs stand for the search’s running-time distribution, with unfinished runs treated as longer than every cutoff; the geometric rules’ costs are lower bounds for that reason.

Cost is counted in nodes. Restarting has overhead in practice — re-reading the pattern, re-initialising the search — and a schedule with many short attempts pays more of it than the node count shows. The universal schedule’s many unit-length attempts would pay most.

What the argument does not settle #

It does not say borrowing a unit is safe. The borrowed unit came from four patches whose searches never have a tail at all, and it happened to be the right order of magnitude for the one that does. A pattern whose easy runs were a hundred times longer than its neighbours’ would defeat it, and the only protection is the universal schedule’s logarithmic insurance.

It does not measure a dynamic policy. The features named above are candidates; whether any of them separates long rhombille runs from short ones within fifty nodes is untested.

It does not say the coin should be kept at all. The deterministic search on the same patch costs eighty nodes, less than a sixth of the hindsight cutoff’s 512 and less than every schedule here, so the whole comparison is among ways of managing a tail that a different design of the search does not have. The schedules are the right answer to a randomised search and not necessarily the right answer to the patch.

And it does not apply to a search that reports progress. The argument is about a schedule that observes only success or failure. A search that could say how close it was to finishing would give a schedule something to learn from, and most real searches can say something.

Still open: whether a run of fifty nodes can tell it is long #

The borrowed unit recovered most of the gap and a dynamic policy might recover more, and the natural next measurement is the one that would say which.

Record, for each of the 120 runs, the state of the search at fifty nodes — its deepest backtrack, its free creases, its forced letters — and ask whether those numbers separate the runs that finish by a hundred from the runs that do not. If a single feature does it, a policy that restarts runs showing that feature would cost less than the hindsight fixed cutoff, which no list can, because it would be using information no list has. That is the precise sense in which watching the inside of a run is worth more than hindsight about its length.

Sideways from here, the borrowed unit suggests a question about the tessellations rather than the search. The rhombille patch is the one whose tiles are not regular, and the propagation that never had to work found the twist construction doing real work there for the first time. Whether a pattern’s irregularity predicts its search’s tail — so that a unit could be borrowed from patterns of the same irregularity rather than from all patterns — would turn the choice of unit from a guess into a measurement.

The habit worth carrying is about learning from outcomes. Before building something that adapts, list what it can actually observe while it is still running. If the only observation available is one the system’s own continued existence already implies — the job is not done, so every attempt so far has failed — then the adaptation is a fixed plan with a story attached, and the information it needs has to come from somewhere else.