Stopping is cheaper than finishing

There is one pattern in this collection whose search for a consistent lettering does not have a cost so much as a distribution. On the rhombille tessellation patch, a hundred and twenty runs of the same search — same pattern, same code, differing only in the order the letters are tried — produce results from eighty-four nodes to more than twenty thousand, with forty-eight of the hundred and twenty never finishing at all.

The obvious response to a run that is taking a long time is to let it continue, on the reasoning that it must be getting somewhere. That reasoning is wrong here, and the measurement says how wrong.

What a restart strategy costs #

Suppose every attempt is abandoned after C nodes and started again with a fresh order of guesses. Attempts are independent, so the number needed is geometric: if a fraction p of attempts finish within C, the expected number of attempts is one over p.

Each attempt costs either its own running time, if it finishes, or C if it does not. Average that over the measured runs and the expected total is

E[min(X, C)] divided by P(X ≤ C) — what one attempt costs, over the chance that attempt is the last one needed.

Both quantities are read off the hundred and twenty runs directly. Nothing is fitted and no distribution is assumed; the runs that never finished are counted as being above every cutoff, which reads the tail conservatively rather than flatteringly.

The numbers #

At a cutoff of a hundred nodes, nineteen per cent of attempts finish. That sounds like a poor success rate, and the arithmetic says it is a very good one: an attempt costs at most a hundred, about five attempts are needed, and the expected total is five hundred and twelve.

At two hundred, a third of attempts finish and the total is five hundred and thirty — no better.

At a thousand: two in five finish, and the total is one thousand six hundred and twenty-four. At five thousand: five thousand six hundred and ninety-seven. At twenty thousand, where three attempts in five finish, the total is sixteen thousand two hundred and ninety-one.

The curve rises the whole way. There is no interior optimum to be found by careful tuning; the cheapest strategy measured here is the most impatient one tried, and the only reason the table stops at a hundred is that below it no attempt finishes at all and the expected cost becomes infinite.

Reading the curve as a whole #

The eight rows are worth taking together rather than one at a time, because their shape says more than any of them.

Between a hundred and two hundred the curve is almost flat — five hundred and twelve against five hundred and thirty — which means the region where the strategy is nearly optimal is broad. That matters practically: a cutoff does not have to be tuned, it has to be small, and anything in the low hundreds is within a few per cent of the best available.

From five hundred upward the curve tracks the cutoff itself almost exactly. At five thousand the expected total is five thousand seven hundred, at ten thousand it is ten thousand six hundred, at twenty thousand it is sixteen thousand three hundred. That is the signature of a cutoff so large that the strategy has stopped being a strategy: nearly every attempt runs to the cutoff, so the expected total is the cutoff divided by a success probability that is barely moving.

And the success probability really is barely moving. It goes from nineteen per cent at a hundred to thirty-three at two hundred — which is where most of the mass is — and then crawls: forty-two at a thousand, forty-nine at five thousand, fifty at ten thousand, sixty at twenty thousand. Between a thousand nodes and ten thousand, a factor of ten more patience buys eight percentage points. That is the tail, stated as a purchase.

Why patience does not pay #

The intuition that a long-running search is nearly done comes from problems where the work is a fixed quantity being ground through. This is not one.

A backtracking search commits to its early decisions and cannot tell whether they were good, and the vertex conditions are far too weak to warn it. If the first two or three guesses put it in a region of the lettering space where the circuits cannot all be avoided, the cost of discovering that is the size of the region — and on a patch with a hundred and twenty-six independent chains of panels, a region can be enormous. The search is not making progress toward an answer; it is proving, expensively, that a corner it entered by accident contains none.

A run that has already spent five thousand nodes is therefore not five thousand nodes closer to finishing. It is evidence that this run’s early guesses were bad, and the appropriate inference is that they will go on being bad. A fresh run draws new early guesses, and a fifth of the time those guesses are good enough to finish inside a hundred nodes.

The condition for this to work #

A restart strategy is not always a good idea, and it is worth being explicit about what makes it one here, because the same arithmetic applied to the wrong problem gives the wrong advice.

Two things have to hold.

The attempts have to be independent. They are, because the only thing changed between runs is the seeded stream that decides which letter to try first at each branch — the same device the sampler uses to make two draws two draws rather than one walk twice. Nothing is carried over: no learnt clause, no memory of which regions were bad, no ordering heuristic that improves. A restart here really is a fresh draw, which is what makes the geometric arithmetic apply.

The distribution has to have a heavy tail. It does: a fifth of runs finish inside a hundred nodes and two fifths do not finish inside twenty thousand, which is a spread of more than two hundred to one among the finishers alone. On a distribution with a short tail, restarting throws away real progress and the curve slopes the other way.

The four easy patches are the control that shows this. Their runs finish between twenty-five and fifty-three nodes, every time; a cutoff below twenty-five would never finish and a cutoff above fifty-three would never fire. There is no restart strategy for them, because there is nothing to restart away from.

The same arithmetic on the other four #

Running the numbers on a patch with no tail is the check that the method is not producing a foregone conclusion, and it is worth doing because the answer is qualitatively different rather than merely smaller.

Take the square patch, whose hundred and twenty runs all finish between twenty-five and thirty-six nodes. A cutoff of twenty finishes nothing: the expected cost is infinite, and no amount of restarting helps — the same degenerate case as a patch whose letters cannot agree at all would present, for a completely different reason. A cutoff of thirty finishes most runs and costs about thirty-two in expectation. A cutoff of forty finishes all of them and costs twenty-seven — which is the median run, because with every attempt succeeding the strategy is just the search.

So on a patch with no tail the curve is U-shaped with its minimum at no cutoff at all, and the advice inverts: run it out. That is what one would expect and it is why the check is worth doing. A method that recommended restarts on every problem would be recommending nothing.

The difference between the two shapes is entirely the tail. It is not the size of the pattern — the rhombille is under twice the triangular patch’s panel count — and it is not the rarity of a good lettering, since the hexagonal patch’s letterings agree twice in two hundred and its search never needs a restart.

What this is not a result about #

Three careful distinctions, because this sits next to a hardness result and could easily be read as bearing on it.

It is not about flat-foldability. Deciding whether a general crease pattern folds flat is NP-hard, and nothing here touches that. The search in question decides whether an admissible lettering exists whose arcs close no circle, which is a constraint problem over a fixed graph and is not known to be hard at all.

It is not a worst-case statement. The expected costs above are averages over a measured sample on one pattern. A different pattern with a hundred and twenty-six chains might behave completely differently, and nothing here is a bound.

It is not a claim that this search is good, and what it backtracks on says how little it knows. The restart curve describes the algorithm as built: propagate the vertex conditions, branch at the vertex with the fewest labellings left, decide the letter at random. A better branching rule — one that preferred creases on many circuits, say — might have no tail and need no restarts. That the impatient strategy wins is a statement about how much the current algorithm’s early guesses matter, which is close to being a statement about how little it knows.

The measurement discipline #

There is one methodological point worth pinning down, because it is what makes the numbers honest and it would have been easy to get wrong.

Forty-eight of the hundred and twenty runs did not finish. Their true costs are unknown and larger than twenty thousand. Any average that assigns them a value — twenty thousand, or the mean of the finishers, or anything else — is an average partly of invented numbers.

The restart arithmetic never needs their values. E[min(X, C)] is bounded above by C for any run that exceeds it, whether it would have finished at twenty-one thousand or at ten million; and P(X ≤ C) counts them as failures, which they are. So the curve is computed entirely from what was observed, and the unfinished runs enter it as the thing they are — attempts that did not succeed — rather than as a number somebody chose.

The consequence is that the curve is conservative in the right direction. If some of the unfinished runs would have finished at twenty-one thousand, the twenty-thousand cutoff’s cost is understated, and the case for stopping early is stronger than it looks.

What is being searched for, and why it is worth searching for #

It is worth restating the object, because the arithmetic above is indifferent to it and the result is not.

The search is looking for a mountain-valley lettering of the rhombille patch that satisfies every condition at every one of its hundred and twenty-six interior vertices and whose arcs — the statements this panel lies above that one that each crease forces — close no circle. A circle in those statements is a proof that no arrangement of the layers exists, so a lettering with one is a lettering that cannot fold whatever else is true of it.

Two thousand letterings drawn at random from this patch produce not one that qualifies, which is why the question needed a search rather than a sample. The search finds one, and the restart arithmetic is about how cheaply.

That matters for reading the curve, because a restart strategy on a problem with no answer never terminates at any cutoff, and the expected costs above would all be infinite. The strategy is only meaningful once existence is settled, and existence was settled first — by a single run that happened to guess well.

The cost in seconds, for scale #

Node counts are the right unit for comparing strategies and the wrong one for deciding whether any of this matters, so it is worth converting once.

A node on this patch costs about eighty microseconds: a propagation pass over a hundred and twenty-six vertex tables, and a sweep over a hundred and fifty-seven panels and two hundred and eighty-two arcs looking for a circle. Five hundred and twelve nodes is therefore about forty milliseconds, and sixteen thousand is about one and a third seconds.

Neither is a number anybody would organise a working day around, and saying so is part of reporting the result honestly. The factor of thirty-two is real; the quantity it multiplies is small. What makes the measurement worth making is not the second and a third saved — it is that the same shape of distribution appears in searches where the units are hours, and the arithmetic that says stop and restart does not care which.

The third option, which is cheaper than both #

The curve compares patience against impatience and takes for granted the thing that produces the distribution in the first place. There is a third strategy, it was found later, and it beats every row of the table.

The randomness is not in the choice of which crease to decide — that is the standard fewest-labellings rule — but in which letter to write on it first. That was a coin, put there so that different seeds would return different letterings.

Replace it with a constant and the rhombille patch settles in eighty nodes, on every run, with no spread and nothing to restart away from.

Eighty against five hundred and twelve for the best restart strategy, and against sixteen thousand two hundred and ninety-one for patience. The impatient strategy is six times worse than simply not randomising, and the patient one is two hundred times worse.

Which puts the patch back on the line #

Eighty nodes on a hundred and fifty-seven panels is 0.51 per panel, and the four patches with no tail run 0.54 to 0.56.

So the rhombille is not the outlier the table makes it. Searched without a coin it sits exactly where the other four sit, on the same law, and the entire distribution the restart arithmetic operates on was manufactured by the line of code that made the runs differ.

That does not make the arithmetic wrong. Every number in the table is a correct expectation over the measured runs, and the conditions the method requires — independent attempts, a heavy tail — hold exactly. It makes the arithmetic a correct answer about a distribution that did not have to exist.

What each strategy is actually for #

The three now sort themselves by purpose rather than by cost, which is the useful arrangement.

To settle whether a lettering exists, use the constant order: eighty nodes, deterministic, and no possibility of a tail. Existence is what the search was built to answer, and it answers it without any of this apparatus.

To collect many different letterings, the coin is required — forty seeds under it return forty distinct witnesses, and forty seeds under a constant return one witness forty times. There the restart curve is exactly the right instrument, and five hundred and twelve nodes per witness is what diversity costs.

Patience is for nothing. Sixteen thousand nodes buys neither existence, which eighty settles, nor diversity, which a restart collects six times cheaper.

So the rung’s conclusion survives and its scope narrows. Stopping is cheaper than finishing, and not randomising is cheaper than either — unless the randomness is what is wanted, in which case stopping is how to pay for it.

What a folder should take from this #

Very little directly, and one thing indirectly, which is worth separating.

Directly: nothing. A folder does not run backtracking searches, and the lettering of a printed pattern was settled long before the sheet was drawn.

Indirectly: the shape of the result says something about how these patterns behave that the folder’s experience already contains. A tessellation that will not come together does not usually come together with more effort. It comes together, or does not, according to decisions made near the beginning — which pleat was set first, which polygon was collapsed before which — and the remedy when it fights is to open it out and begin again with a different order rather than to press harder.

That is not an argument from the mathematics; the search is not a model of a pair of hands. It is a coincidence of structure between a problem whose difficulty lives in its early choices and a craft whose difficulty lives there too, and it is worth noticing without being leaned on.

There is one place the two really do meet, and it is elsewhere in this collection rather than here. The order a twist is collapsed in changes whether it collapses: set every pleat as a shallow valley first, let the ring rotate, and only then press home — and reversing that order produces a stubborn starred object that will not flatten. That is a statement about hands, established by folding rather than by measuring, and it is the folding counterpart of a search whose early decisions decide its cost. Neither is evidence for the other. Both are true of the same patterns.

Where the ladder goes next #

The idea of abandoning a search and restarting it is not this collection’s, and not this subject’s. It comes from the study of satisfiability solvers in the nineteen-nineties, where exactly this distribution was measured and exactly this arithmetic was applied — and the transfer to a question about paper is the kind of borrowing worth recording rather than reinventing.

What is genuinely open here is the branching rule. Every measurement in this rung describes a search that guesses at random among the creases the propagation has not settled. The obvious alternative is to branch on a crease that lies on many independent circuits, since those are what the search backtracks on — and the machinery to compute which creases those are already exists in this collection, pointed at a different question. Whether it removes the tail or merely moves it is not known, and it is the first thing to try.