Restarting what cannot be restarted

A backtracking search that has taken a bad early decision can spend an enormous time before it takes the decision back. The standard response is not patience. It is to stop, reseed and start again, and the arithmetic for choosing when to stop is short: the expected total for a cutoff C is what one attempt costs, divided by the chance that attempt is the last one needed.

Applied to the search for a consistent lettering of one tessellation patch, that arithmetic said what it usually says. A cutoff of a hundred steps costs five hundred and twelve in expectation; allowing twenty thousand costs sixteen thousand two hundred and ninety-one; the curve rises the whole way and there is no interior optimum, so the shortest cutoff on offer is the best one available.

Every number in that paragraph is correct. The distribution they are correct about was manufactured by the search, in the one line nobody had thought of as a choice.

Where the distribution came from #

A run-time distribution requires runs that differ. This search’s runs differed because, having chosen which crease to decide next, it tossed a coin to decide which letter to try first.

Replacing that coin with a constant — try one letter first, always, on every pattern — makes the search deterministic. It then costs eighty steps on this patch. Not eighty on average: eighty, on every seed, because nothing in the search reads a seed any more.

Eighty against five hundred and twelve is a factor of six against the best restart strategy and a factor of two hundred against patience. But the ratio is the less interesting half. The interesting half is that the strategy has nothing to act on. A restart reseeds a search that has gone wrong, in the way a wrong first letter goes wrong; a search with no seed in it produces the identical run when reseeded, so cutting it off at a hundred steps and starting again produces the same first hundred steps, forever.

The strategy is not merely unnecessary. On a deterministic search it is undefined, and applying it produces an infinite loop rather than a slower answer.

What the curve was measuring #

It is worth being exact about what remains true, because the answer is most of it.

The curve is a correct summary of forty measured runs. Given a search that behaves like those forty, the cutoff arithmetic is the right arithmetic and the numbers it produces are the right numbers. Nothing in the reasoning was sloppy and no step of it would be done differently.

What the curve is a summary of is the question. It is a property of a pair — a pattern and a search — and the collection had read it as a property of the pattern. The sentence “this patch has a heavy-tailed search cost” is the reading that does not survive: what has a heavy-tailed cost is this patch under a randomised value order, and under any other arrangement the same patch has no distribution at all.

There is a sharper way to put the same point, and it is the one worth carrying away. A run-time distribution is a property of an algorithm on an input, never of an input alone. Everybody knows that and everybody writes the shorter sentence, because in most settings the algorithm is fixed and the input is what varies, so the shorthand costs nothing.

It costs something exactly when the algorithm has an unexamined choice in it. Then two people can measure “the same search” and get different distributions, both correctly, and the difference will look like a difference between their instances. Here there was only one person and one instance, and the two distributions were separated by a single unexamined line.

An instrument that produces what it measures #

This shape is worth naming because it is not rare and it is very hard to see from inside.

A restart strategy is a response to variance. Variance in a search comes from randomisation. Randomisation is put into a search deliberately, for reasons that are usually good — here, so that twenty seeds would return twenty different letterings rather than one lettering twenty times. So the chain runs: a good reason produces randomness, randomness produces variance, variance produces a distribution, the distribution invites a strategy, and the strategy is measured and found to work.

Every link holds. The strategy really does beat patience on that distribution, by a factor of thirty. And the entire chain is downstream of a decision that was never examined as a decision, so nothing anywhere in it asks whether the variance should exist.

The tell, in retrospect, is that the strategy’s benefit was very large. A thirtyfold win from stopping early says the distribution has a great deal of mass a long way from its median, and a search that behaves that differently from one run to the next is a search whose randomisation is doing something substantial — which is either a fact about the problem or a fact about where the randomness was put, and those look identical from the curve — the same indistinguishability a nought of two hundred draws has.

It is also a shape with a name outside this subject, and the name is unflattering in a useful way. A measurement whose apparatus contributes the signal is a measurement of the apparatus, and the standard defence is a control: run the instrument with the thing being measured removed, and see what it reports.

The control here costs one run. Take the coin out, run the search once, and look at what is left of the distribution — and the answer is that there is no distribution, which would have ended the matter before the curve was ever computed. Nobody ran it, because a control implies a suspicion, and there was nothing to suspect: the coin was not a knob anybody thought they had turned.

What is left to restart #

Restarts have not become useless here. They have become useless for the question they were being applied to, and they remain exactly as useful for a different one.

The existence question — does this pattern have a consistent lettering at all? — is now answered deterministically in eighty steps and needs no strategy. The variety question — how many different ones does it have, and how far apart are they? — still requires a randomised search, still has a heavy tail, and is still best served by cutting off and reseeding.

The difference is that the second question does not care about a run that fails to finish. It wants distinct witnesses; a run that hits its cutoff produces none and is discarded, and nothing is lost by discarding it because existence has already been settled. So the restart curve moves from being a strategy for answering a question to being a strategy for collecting samples cheaply, which is what it is genuinely good at and where its arithmetic is unambiguous.

There is a real cost to that split and it should be admitted. Answering two questions with two arrangements of a search is more machinery than answering one question with one, and the two arrangements have to be kept honest with respect to each other — the witnesses the randomised run collects have to be witnesses for the same pattern, under the same conditions, as the deterministic run established the existence of. That is bookkeeping, and bookkeeping is where quiet errors live.

The alternative is worse, though, and it is what was in place: one arrangement answering both questions badly, at three orders of magnitude of worst-case cost, with a strategy layered on top to manage a distribution that only existed because the arrangement was trying to do two things at once.

Why a deterministic search cannot be rescued this way #

There is an obvious repair to the undefined-ness above: randomise something else. If the value order must be constant for cost, put the coin in the variable order instead, and restarts become meaningful again.

It does not help, and the reason is the subject of a separate measurement. The variable order buys nothing at all on a pattern that has a lettering — branching on the pattern’s own circuit structure is never cheaper than the standard rule on any of eighty-seven patches and is worse on fifty-two of them. Randomising a choice that does not matter produces a distribution with no spread, which is a distribution no restart strategy can improve.

So the two choices are not interchangeable as places to put randomness. One of them is where the cost lives and therefore where the variety lives; the other is neither. Which of the two choices the cost lives in takes that apart, and its conclusion here is that a restartable search on this problem is necessarily an expensive one.

What a hard instance would have looked like #

It is worth describing the case this is not, because the difference is what makes the correction a correction rather than a rejection of restarts.

A genuinely hard instance has a spread under every arrangement. Fix the value order and the cost still varies with the variable order; fix both and the deterministic cost is enormous; and no cheap rearrangement removes the variance because the variance is the search meeting a real obstruction from many directions. On such an instance a restart strategy is exactly right, its arithmetic is the arithmetic above, and the collection would have nothing to correct.

The way to tell them apart is one run of the control. Take the randomness out and look: if the deterministic cost lands near the old median, the distribution was about the problem and the strategy stands. If it lands at the old minimum or below it, as it does here — eighty against a best-of-forty of eighty-six — the randomisation was the source, because a coin cannot make a search cheaper than its own best case and a removal that beats every randomised run has removed an obstacle rather than found a lucky path.

That test is cheap, general and was not run, and it is the practical residue of the whole episode.

The control has a p-value, and it is one in forty #

The test the essay proposes — take the randomness out and see where the deterministic cost lands — is not merely suggestive. It is a significance test, and the significance is computable from runs already in hand.

Suppose the null hypothesis: the coin merely reshuffles an intrinsically hard search, so a constant order is one more draw from the same distribution. Then it should land at a random percentile among the forty randomised runs, and the chance of it landing below all forty is one in forty-one.

It lands at eighty against a best-of-forty of eighty-six.

So the control refutes the null at about 2.4 per cent, from a single additional run, using a sample that had already been collected for a different purpose.

Which makes it the cheapest test in the collection #

That is worth stating as an arithmetic fact rather than as advice, because it changes what the omission cost.

The forty randomised runs took whatever they took. The control takes one more, and its power comes entirely from the forty already done: with $n$ runs in hand, a deterministic run below all of them is significant at $1/(n+1)$, with no extra sampling and no model fitted to the tail.

The test is free and it was available before the curve was computed. Every ingredient — the forty runs, the search, the one line to change — existed at the moment somebody first noticed the spread, and running it would have taken less time than plotting a single point of the restart curve.

And it says what to do next time #

The general form is short enough to be a habit rather than a procedure.

Whenever a randomised search shows a spread worth building a strategy on, run it once with the randomness removed and compare against the sample’s minimum. Below the minimum: the randomness is the source, and the strategy is managing a distribution somebody manufactured. Near the median: the distribution belongs to the problem, and the strategy is the right response.

There is no third outcome that needs interpretation, and the test cannot be run too late — it works equally well after the curve has been computed, which is when it was eventually run here.

One run, one comparison, and a significance level that improves with every randomised run already taken. A test that gets cheaper the more evidence has been collected for the thing it might refute is an unusually favourable arrangement, and it is the reason the omission is worth recording rather than shrugging at.

The correction, stated plainly #

Three sentences in the collection’s record need reading differently.

The search’s cost on this patch is heavy-tailed — true of the search as it was arranged, and not a property of the patch.

Stopping is cheaper than finishing — true, on that distribution, and the comparison it invites is with patience rather than with not randomising.

The curve rises monotonically and there is no interior optimum — true, and the reason it has no interior optimum is worth revisiting: a distribution whose best cutoff is the smallest one offered is a distribution where the tail is nearly everything, which is what a coin at the wrong branch point produces.

What survives untouched is the arithmetic, the measurement discipline behind it, and the observation that runs which hit the budget must count as above every cutoff rather than being averaged in at their budget. That last point is the one worth keeping: it is what makes the curve a conservative reading rather than a flattering one, and it would matter identically on any distribution.

Which theorem was checked, and how #

Nothing here changes any verdict. Every arrangement of the search returns a lettering that passes the four conditions at every interior vertex and forces no circle in a folded sheet rebuilt from scratch, and every arrangement that exhausts a tree without finding one agrees with every other arrangement that exhausts.

The claim specific to this essay is asserted rather than asserted-and-hoped: on this patch the coin’s cost really does spread — its worst run many times its median, or not finishing at all — and a constant order really does finish every run at the same cost and return exactly one lettering. Both halves, because a cheap search that returned many witnesses would be a strictly better search and the whole trade would evaporate.

What the picture cannot show #

The curve is computed from forty runs, so its tail is estimated from fifteen numbers, and estimates of a heavy tail from small samples are notoriously poor. Nothing here depends on the tail’s exact shape — the argument only needs that a spread exists and that a constant order has none — but the specific figures of five hundred and twelve and sixteen thousand two hundred and ninety-one are worth reading as one sample’s summary rather than as constants.

And there is a version of this essay that would be wrong. A search whose randomisation genuinely reflects a hard instance — where every arrangement has a spread, and no constant removes it — is exactly the case restarts were invented for, and nothing here argues against them there. What is argued is that a distribution has to be shown to belong to the problem before a strategy is built on it, and that showing it requires trying an arrangement with no coin in it, which costs one run.

What it costs a reader #

Less than it costs the collection, and the difference is the useful part.

A reader who had taken away this patch is a hard instance now has to take away something more careful: the patch is unusual within its family, in a way that shows up as search cost under a randomised value order and vanishes under a fixed one, and the unusualness is real and belongs to its tiling. That is a longer sentence and it is not a weaker one — it names which tiling and why, where the old sentence named neither.

A reader who had taken away restarts are how one handles a heavy-tailed search keeps that entirely. It is true, it is the literature’s, and nothing here disputes it. What is added is a prior step: check whether the tail belongs to the search before building a strategy for it, because the check costs one run and the strategy costs a great deal more.

Where the ladder goes next #

The strategy and its arithmetic came from somewhere, and so did the phenomenon they answer. The cure was named before the disease was caught here records the borrowing, which is the honest thing to do with a technique that arrived complete: the heavy-tailed runtime, the restart curve and the reasoning behind both are the search literature’s, and what a crease pattern contributes is an instance in which the tail turned out to be the instrument’s own.