A long run shows itself early

What the hindsight was worth priced a borrowed idea on a folding search. The search looks for a consistent mountain-and-valley lettering of a patch of the rhombille tessellation, it has a heavy tail — it finishes in eighty-odd nodes on its best runs and not at all inside twenty thousand on two runs in five — and stopping every attempt at a cutoff and starting again with a fresh seed is far cheaper than letting each run finish. The best cutoff was read off 120 measured runs afterwards. A failure teaches a schedule nothing then proved that no schedule which learns from its own failures can do better: a failed attempt reports only that it failed, which is what knowing nothing already predicted, so every such schedule is a fixed list, and no list beats the cutoff hindsight chooses.

It ended where the search literature had gone in 2002, when Henry Kautz, Eric Horvitz and their colleagues proposed restart policies that watch a run from the inside, read features of its early behaviour, and restart the runs that look long. A schedule can beat hindsight about a run’s length only by using information about the run’s interior, and the essay named the features a lettering search could report — the deepest backtrack so far, the creases still free, the vertices whose letters were forced — and said that testing any of them would need the runs split into ones a policy learns from and ones it is tested on.

This is that test, on the same 120 runs, and it needs one feature, which the search was already counting.

What a run already reports #

The lettering search assigns a letter to a crease, propagates whatever the vertex conditions force, and asks one more question at every node: whether the letters so far close a loop of panels each lying above the next, which no folded state can contain. When they do, the branch is abandoned; that is a loop refusal, and the search keeps a running count of them. Nothing about the count was designed as a predictor. It is bookkeeping.

The search keeps a second count beside it, of the times a vertex had no lettering left consistent with the letters already chosen. On this patch that count never moves early. In the first fifty nodes of all 120 runs the vertex conditions refuse nothing at all: propagation forces every letter a vertex can force, so no vertex is ever left with nothing to choose, and every dead end the search meets that early is a loop. That is why one count is enough. A run cannot be in trouble at node fifty in any way the search would notice except by closing loops, so a run in trouble is a run with many loop refusals.

The search is deterministic once its seed is fixed, so the count a run had reached by node fifty can be read without changing anything: run the same seed with a budget of fifty nodes, and it stops at exactly the point the full run passed, with its count in hand. Doing that for each of the 120 seeds gives every run two numbers, its refusals by node fifty and the nodes it took to finish.

The picture separates without being asked. Runs that finish quickly — the ones a cutoff near a hundred and fifty nodes keeps — sit almost entirely at three to seven refusals. Runs that never finish sit in two places: a few at the same low counts, and a large group at sixteen or seventeen. Of the fifty runs refused eight times or more by node fifty, one finishes within a hundred nodes, and twenty-eight never finish at all. Of the seventy refused fewer times, twenty-two finish within a hundred.

The cluster at sixteen is the shape the earlier essay predicted in words. The order that proves nothing exists found that a refutation’s cost is set by how many free choices sit above the contradiction. A run that is refused sixteen times in its first fifty nodes has made an early choice that dooms everything below it and is discovering that one branch at a time; each new attempt beneath the bad choice closes a loop almost at once. The count rises fast exactly because the run is trapped, and it rises fast early, which is when a restart is cheap.

How many refusals should end a run #

The policy that uses the count is the plainest possible. At node fifty, look at the count. If it is at least some threshold, abandon the run and start again with a fresh seed. Otherwise let it continue to a cutoff, and if it has not finished by then, abandon it too.

Its expected cost is computed as a fixed cutoff’s is: what one attempt costs on average, divided by its chance of being the attempt that finishes. A run that finishes before node fifty costs its own length; a run abandoned at node fifty costs fifty; any other costs the lesser of its length and the cutoff.

The best fixed cutoff, searched over every whole number of nodes, is 166, at 483 nodes in expectation — a little under the 512 the earlier essays read off a list of round cutoffs, because a handful of runs finish between 150 and 166 and a cutoff fitted to the node catches them. The refusal policy at its best restarts at eight refusals and otherwise cuts at 151, and costs 387 nodes: four fifths of the best fixed cutoff.

The curve has the shape it should. A threshold of two or three refusals throws away runs that would have finished, because most good runs have been refused three or four times by node fifty, and the policy pays for restarting them. A threshold of sixteen or twenty catches only the most obviously trapped runs and leaves the ones at eight to fifteen, which are almost as hopeless, to run on to the cutoff. Between them, at eight, the count does the most work.

Cheaper failures, not more successes #

The policy’s advantage is not where it might be expected. It does not finish more often. An attempt under the refusal policy succeeds a quarter of the time, against 31 per cent for the best fixed cutoff; restarting at eight refusals throws away the one quick run in that group and several that a cutoff of 166 would have caught. What it changes is what a failure costs. An attempt under the fixed cutoff costs 149 nodes on average, because every doomed run is carried all the way to 166; an attempt under the policy costs 97, because more than half of the runs it fails on are dropped at fifty rather than carried to the cutoff. Expected cost is the ratio of the two, attempt cost over success rate, and the policy improves the numerator by a third while giving up a fifth of the denominator: 97 over a quarter is 387, and 149 over 0.31 is 483.

That is the general shape of a good restart rule, and it is worth having in that form. A restart policy is paid for in the cost of its failures, because on a heavy-tailed search most attempts fail whatever the policy does. Any information that lets a failure be recognised earlier is worth having even if it also condemns some runs that would have succeeded, and the threshold is set exactly where condemning one more good run costs more than the doomed runs it releases.

When to read the count #

Fifty nodes was the number the earlier essay picked. It is not obviously the right one, and the dial on the first figure moves it.

Read at node twenty-five, the count has had little time to separate the runs, and the best policy costs 458, only five per cent under the fixed cutoff. Read at fifty it costs 387; at seventy-five, 355, a quarter under, with a threshold of sixteen — by then the trapped runs have reached the cluster at sixteen and nearly nothing else has. Read at a hundred, the count is useless: the best policy never restarts on it, because the useful cutoff is itself around a hundred and fifty and a run that is going to finish quickly has mostly done so. The count is worth reading at the point where a trapped run has had time to show it and a good run has not yet had time to finish, and on this patch that is between fifty and seventy-five nodes.

Chosen on one half, paid on the other #

Everything above was chosen and priced on the same runs. The fixed cutoff of 166 is hindsight, and so are the threshold of eight and the cutoff of 151; a policy with two numbers to tune has more room to fit the accidents of 120 runs than a policy with one. The earlier essay said what the honest version needs: the runs split, the choices made on one half, the prices paid on the other.

Chosen on runs 1 to 60, the fixed cutoff is 101 and costs 541 on runs 61 to 120; the refusal policy chosen on the same runs is seven refusals and a cutoff of 101, and costs 437. Chosen on runs 61 to 120, the fixed cutoff is 161 and costs 579 on runs 1 to 60; the policy is eight refusals and 161, and costs 435. On both halves the policy keeps four fifths of the fixed cutoff’s cost or less on runs it never saw.

And on the second half it does better than hindsight. Runs 1 to 60, priced by the best fixed cutoff that could have been chosen knowing those runs, cost 456 — and the refusal policy, chosen without them, costs 435. That is the precise sense in which watching a run is worth more than hindsight about runs: the best list for those sixty runs, written down after seeing them, is beaten by a rule written down before, because the rule uses something no list has — what each run is doing while it runs. On the first half the policy comes within five per cent of that half’s hindsight, 437 against 417.

The literature’s answer, reduced to one number #

The policies Kautz, Horvitz and their colleagues built were statistical models: dozens of features of a solver’s early behaviour, a decision tree or a Bayesian classifier trained on many previous runs, and a prediction of whether this run would be long. The cure was named first and the tail was named somewhere else recorded how much of this subject’s search behaviour arrived already described by that literature, and the dynamic policy is the last piece of it.

What the crease pattern adds is how little it takes. A single count, kept for another reason, at a single node, with a single threshold, recovers a fifth of the cost and holds up on runs it was not fitted to. The reason it is enough here is particular to this search. A loop refusal is the search discovering, again, that the letters it holds cannot be stacked — and on this patch a doomed early choice produces refusals in bulk, sixteen in fifty nodes, while a sound one produces a few. The feature is good because the failure it signals is loud. On a search whose doomed runs failed quietly — by exhausting vertex options rather than by closing loops, say — the same count would say nothing, and the policy would need the richer features the literature used.

The fourth thing this search met second #

These essays have been a record of one search meeting, one by one, results the study of combinatorial search had already written down. The heavy tail was there first; the restart that cures it was there first; the universal schedule was there first, in 1993, with the impossibility of beating hindsight from failures implicit in it; and the policy that watches a run from the inside was there in 2002. Found by people not folding paper counted the same pattern in geometry — a shortest Möbius strip with a literature in differential geometry and none in origami — and found before it was designed in buckling, where a crushed cylinder published a crease pattern twenty years before anyone designed with it.

What is different this time is direction. Each earlier rediscovery found the folding version to be a case of the general result. Here the folding version is a simplification of it: the general policy needs a trained model over many features because general solvers fail in many ways, and this solver, on this patch, fails in one way so loudly that a single counter carries the whole signal. A rediscovery can return something to the field it came from, and what a crease pattern returns here is a worked case of how little a dynamic restart policy can need.

What the measurements assume #

One patch. Every number is about the rhombille patch that gave the earlier essays their heavy tail. The other four patches of the same construction finish without a tail worth restarting, so nothing here could be tested on them, and whether a loud refusal count is a property of this search or of this patch is open.

One hundred and twenty runs, split once. The held-out test uses one split, first half against second, both ways. A different split would give different numbers, and with sixty runs a side the costs carry an uncertainty of tens of nodes. The direction — the policy cheaper than the fixed cutoff on unseen runs, by a fifth or more — holds on both halves, which is what was asked of it.

A budget that truncates. Runs that had not finished by twenty thousand nodes are counted as unfinished, which both the fixed cutoff and the policy treat the same way, since neither ever lets a run go that far.

Why sixteen, and whether a better count exists #

Why sixteen. The trapped runs pile up at sixteen and seventeen refusals rather than spreading out, which suggests a particular early choice that every one of them makes and then spends its fifty nodes trying to repair. Which crease that is, and whether it is the same crease on every trapped run, would say what the count is actually counting.

Whether a better feature exists. The count was the first thing tried, because it was already there, and it worked. The depth of the deepest backtrack, the free creases, the forced letters — the features the earlier essay listed — were not measured, and any of them might separate the runs more cleanly.

The probe is the run, stopped early #

The count at node fifty is the full run’s count at node fifty. The search is deterministic given its seed, and the probe is the same search with the same seed stopped at a budget of fifty; the runs’ lengths are the ones the earlier essays’ figures use, from the same seeds.

Every price is an exact expectation over the measured runs, an attempt’s average cost over its chance of success, with thresholds from two to twenty and cutoffs searched over every whole number from the reading node to six hundred; every useful cutoff on this patch is under two hundred, and the best fixed cutoff is the same searched to twenty thousand. The figures require the refusal policy to beat the best fixed cutoff by more than a tenth on all 120 runs, to beat a fixed cutoff chosen the same way by more than fifteen per cent on each held-out half, and to beat a half’s own hindsight cutoff on at least one of them.

The last figure is the yardstick the earlier essays used — stopping is cheaper than finishing drew it first — drawn again at the two cutoffs this one settled on. It is the ceiling every schedule built from failures lives under, and the refusal policy is the first thing here to get beneath it.

Still open: which crease traps a run #

The cluster at sixteen refusals is the lead. If the trapped runs share an early choice, the policy could be replaced by a rule about the choice itself — never take that letter on that crease first — which would cost nothing at all to apply and would turn a restart strategy into a better search. Recording, for each trapped run, the letters it held when its count passed eight, and looking for the crease they agree on, is a short measurement with a definite answer.

The other direction is the one the earlier essay raised and this one makes testable. The propagation that never had to work found the rhombille patch to be the one where the construction did real work, and the difficulty was in the coin located its tail in the randomised letter order. Whether a loud refusal count belongs to the rhombille’s irregular tiles or to the search — whether a degree-six or a crumpled pattern, searched the same way, traps its runs as loudly — would say whether a policy written on one patch could be carried to another.

The habit worth carrying is about the data a process already keeps. Before designing a measurement of a process from outside, read the counters it keeps for its own reasons. The search had been counting its refusals since it was written, to report how much the loop test pruned; the number that tells a long run from a short one was sitting in that report the whole time.