The search that got worse as it widened

The order the products are taken in separates two greedy rules that sound like the same idea. Pair whichever two operands are cheapest to multiply: median excess 1.47 over the exhaustive answer. Pair whichever two leave the smallest result: 1.003. Nothing about the two descriptions would have chosen between them, and the measurement is what says the second is the one to ship.

Both rules keep one thing. At every step they choose a pairing and commit to it, and everything that pairing made impossible is gone. The obvious repair is to keep more than one — carry the best few partial orders forward, extend each of them, keep the best few of what results — which is a beam, and its width is a single knob running from the rule a library ships to the search it cannot afford.

The knob does two things, and neither of them is what the description suggests.

It repairs the bad rule and does not improve the good one #

The cheapest-product rule starts at a median excess of 1.471 and one extra candidate takes it to 1.145 — a third of the excess removed by keeping two things instead of one. At width 3 it is 1.085, at 4 it is 1.026, and at 6 it is 1.0000.

The smallest-result rule starts at 1.0026 and the width buys it nothing: 1.0026, 1.0103, 1.0069, 1.0000, 1.0000 across widths 1 to 8. The middle of that sequence goes the wrong way, which is the subject of the second half of this page.

By width 6 the two rules agree to five figures, and by width 8 they are identical. The distinction the previous measurement is built on has stopped existing — the choice of rule, which was worth a factor of a hundred and forty in the deficit at width 1, is worth nothing at all once the search keeps six candidates.

That is worth stating as a fact about heuristics rather than about contraction. A greedy rule is two things at once: a ranking of the available moves, and a commitment to the top one — the same pair the order decides the memory compares four rules on without ever separating them. The measurement that separated the two rules was measuring the ranking through the commitment, and could not tell which of the two it was reading. Widening the beam weakens the commitment, and what is left is the ranking — which turns out to be nearly the same for both rules, because both are ranking the same pairings and differ only in where the ties fall.

What it costs, and it is not the search #

The width is worth having only if it is cheaper than the thing it approximates, which needs both counted in the same unit.

The greedy rule prices 56 pairings on a seven-tensor network. The beam at width 8 prices 301. The dynamic program that answers exactly makes 2,187 transitions over 128 subsets — so the widest beam here is about a seventh of the exhaustive cost, and it reaches the exhaustive answer on the median network.

It does not reach it on the worst. The width-8 beam’s worst case over sixty networks is 2.85 times the optimum, against the greedy rule’s 4.61 and the cheapest-product rule’s 25.4. A beam of any fixed width can discard the branch that wins, at any level, and never look at it again — so the tail is narrowed and not closed, and no width short of the full subset lattice closes it.

Which places the knob precisely. Between a rule that is optimal on half the networks and a search that is optimal on all of them, the width buys the median quickly, the ninetieth percentile slowly, and the worst case not at all.

The smaller sample is this field’s usual warning and it carries here in a particular way. The medians are settled by twenty networks — 1.296 against 1.471 at width 1, and 1.0000 at width 6 either way — and the worst case is not settled by any sample, so a reader who took the twenty-network figure for the measurement would conclude that a wide beam is exhaustive. It is not; those twenty networks simply did not contain the case that shows it.

And a wider beam is not a better beam #

The sequence 1.0026, 1.0026, 1.0103, 1.0069, 1.0000, 1.0000 has a rise in it, and a rise in a quantile is usually a sampling artefact. This one is not.

Twenty-four of sixty networks. On each of those the search was widened, more candidates were considered, and the order that came out cost more than the one a narrower search found — by up to 3.49 times in a single step of the width.

The cause is in the beam’s ranking, and it is worth following because it is not a bug in the implementation. A beam ranks its surviving states by cost so far, because that is the only quantity available at a partial order. A state whose first pairing is dear and whose remaining pairings are cheap is exactly the state an exhaustive search would choose, and it is the state a cost-so-far ranking discards as soon as there are enough cheap-looking prefixes to fill the beam. At width 1 there is no filtering at all — the rule takes its own top move and follows it wherever it goes — and at width 3 there are three prefixes competing on a quantity that does not predict the finish.

So widening the beam changes what is discarded, not merely how much, and the change is not monotone.

And it is the better rule the width more often damages. Twenty-four of sixty under the rule with a median excess of 1.003, three of sixty under the rule with a median excess of 1.47.

That looks backwards and is not. A rule that is already nearly optimal has almost nothing to gain from extra candidates and exactly as much to lose from discarding the right one, so the width is close to a pure downside for it. A rule that is far from optimal has a great deal to gain, and gains it. The asymmetry is the same one this collection keeps finding about repairs in general: a correction applied to something that was already right is not free, and whether it is worth applying depends on where the thing being corrected started.

One network, followed through #

The aggregate says twenty-four of sixty. One of them is worth following, because the sequence is not the shape anybody would predict from the description of the search.

On the fifty-first network of the ensemble the excess reads 1.000, 3.491, 3.926, 3.491, 1.166, 1.000 across widths 1, 2, 3, 4, 6 and 8. The greedy rule finds the optimum outright. Keeping two candidates loses a factor of three and a half. Keeping three loses slightly more. Keeping six recovers most of it, and keeping eight finds the optimum again.

Nothing about that sequence is noise: every entry is an exact count of multiply-adds for a deterministic search over a fixed network, and running it again returns the same six numbers. What it shows is a single wrong prefix dominating the beam. At width 1 the rule’s top move happens to be the optimum’s first pairing and nothing else is ever considered. At width 2 the beam admits a second prefix whose immediate result is smaller, that prefix is cheaper so far at every subsequent level, and it crowds out the first — so the search that considered strictly more orders returned the worse of the two it was choosing between. At width 6 there is room for both, and the right one wins on total cost at the end.

So the anomaly is not a slow degradation as candidates accumulate; it is a narrow band of widths in which the wrong prefix fits and the right one does not. That is why the aggregate curves are not smooth, and it is why tuning a width on a handful of networks produces a number that means nothing — the band’s position depends on the network, and a width that is safe on one is inside the band on another.

The named networks, where the width buys nothing #

The three networks this field opens with are worth checking against, since they are what a reader would picture.

Under the smallest-result rule the beam returns the optimum at every width on all three: the matrix chain, the inner product of two trains, and one alternating-least-squares step. Width 1 is already exact and there is nothing for the width to do. Under the cheapest-product rule the three read 3.35, 4.52 and 1.08 at width 1, and 1.00, 1.03 and 1.00 at width 2 — so one extra candidate is very nearly the whole of the repair on the networks that have names.

That is the counterweight this ladder keeps producing and it points the same way as the others: the structured networks are easy, and the ensemble of random ones is where the measurement lives. A reader whose contractions are chains, ladders and stars has no use for any of this, because the rule a library already ships is optimal on all three.

And the width stops paying as the network grows #

The last measurement is the one that decides whether any of this matters, because a beam exists for networks too large to search — and everything above is measured at seven tensors, where the search is affordable.

Forty networks at each of five sizes, with one more label than tensors, under the smallest-result rule:

The anomaly grows with the network: five of forty at five tensors and twenty-seven of forty at nine. And at nine tensors the median network is worse at width 8 than at width 1 — 1.0656 against 1.0615 — so the beam has stopped being an improvement in the median as well as in the tail.

The reason is combinatorial and it is worth stating because it says the trend continues. A beam of fixed width covers a share of the search space that falls as the space grows: at five tensors there are fifteen distinct pairings at the first level and at nine there are thirty-six, and a beam of eight is a much smaller fraction of the second. The commitment the width was supposed to weaken is weakened less at every size, and the crowding-out that causes the anomaly has more prefixes to crowd with.

So the honest conclusion about the knob is narrower than the first three sections suggest. The width repairs a bad rule cheaply, at every size drawn. It improves a good rule at small sizes and stops improving it at nine tensors, which is still far below the sizes a beam is written for. A code choosing between the greedy rule and a beam on a large network should expect the beam to cost more and buy nothing, and the measurement that would say otherwise cannot be taken, because the optimum it would be measured against is what nobody can compute.

Which of the three to ship #

The measurements support a short rule, and the surprise is how little of the width is worth having.

Width 1 with the smallest-result rule remains the default. Median 1.003, optimal on half the networks, 56 pairings, no anomaly to reason about — a symbolic decision as cheap as the ones an ordering that does not wait for the numbers is built on.

Width 2 is where the cheapest-product rule should be if it must be used at all — 1.145 from 1.471 for 91 pairings against 56 — and it should not be used at all, which the previous measurement established and this one does not revisit.

Width 6 to 8 is worth having on a small network repeated thousands of times, because the median reaches the optimum and the ninetieth percentile falls from 1.49 to 1.13 — and is not worth having on a large one, where the table above says it buys nothing in the median at nine tensors and less at every size past that. The anomaly does not argue against it: the twenty-four networks are cases where a wider beam is worse than a narrower one, and the widest beam is still better than width 1 on the aggregate. What the anomaly argues against is the reasoning — wider is better, so use the widest width affordable — because that sentence is false at every width drawn, and a code that tuned its width by trying a few and keeping the best would be fitting the sample rather than the rule.

And nothing here is worth doing if the order is stale. A beam at width 8 recovers a factor of 1.5 in the median against width 1; an order compiled at the wrong dimensions loses a factor of 8 at the top of a rank sweep and 301 at the bottom. The two are not in competition — one is a better search and the other is searching at the right moment — but a code that has only one improvement to make should make the second.

Where this shape has been met before #

The width is a knob between a heuristic and an exhaustive answer, and this collection has one other place where both ends are computable, which is worth putting beside it.

The least fill there is prices sparse elimination orderings against an exhaustive minimum on grids small enough to have one, and finds minimum degree — the cheap, greedy, universally shipped rule — within a small factor of an answer that costs exponentially more to compute. The two problems are the same problem: an optimal contraction order is a tree decomposition of the network’s index graph, an optimal elimination order is a tree decomposition of the matrix’s graph, and both are NP-hard at the sizes where nobody can search.

What is different is the knob. A sparse ordering’s heuristics are a family of different rules — minimum degree, nested dissection, reverse Cuthill–McKee — and the choice between them is what the field measures. Here there is a single parameter that turns one rule into the other and then into the optimum, so the rules and the search are points on one axis rather than alternatives. That the two rules meet at width 6 is only visible because the axis exists.

The refusals #

The claim worth breaking is the one the word beam carries with it: that keeping more candidates can only help. It is what every description of a beam search implies, it is what makes the width look like a dial between two known points, and it is false on nearly half the networks here. The assertion that a network’s excess falls monotonically as the width grows is fed all sixty and required to reject, at twenty-four of them under the rule a library ships.

The second refusal covers the flattering reading in the other direction — that the width is therefore useless. Fed the cheapest-product rule at widths 1 and 2, the claim that the width buys nothing has to fail: a third of that rule’s excess goes at the first extra candidate, and all of it by the sixth.

And the third is a control on the search itself rather than on the finding. Every beam at every width is checked against the exhaustive answer and required not to beat it, on every network, every time the measurement runs. A beam that returned an order cheaper than the optimum would mean the dynamic program was wrong, and it is the dynamic program that every number in this field is measured against.

What is not measured here #

A beam is not the only way to keep more than one candidate. Ranking the survivors by cost so far is the cheapest choice and it is the cause of the anomaly; ranking them by cost so far plus a lower bound on what remains would be an A* search, the bound is available — the largest single pairing still to be made is a lower bound on the rest — and nothing here measures whether it removes the non-monotonicity or merely moves it.

The networks are seven tensors, because the exhaustive answer has to exist for any of this to be measurable — the position what the symbolic phase can only bound does not enjoy, and has to argue around. A beam’s whole reason for existing is networks of hundreds of tensors, where the anomaly would still be present and undetectable, and where the width’s cost grows linearly while the exhaustive program’s does not.

And the work is counted in pairings priced, which is the search’s own unit and not a machine’s. Both searches are so far below the cost of one evaluation of the network they order that the comparison above decides nothing practical; it is included because a knob between two algorithms is only interesting if the cheap end is genuinely cheap, and 56 against 2,187 is what says so.

Where a heuristic is priced against an answer at all #

Two of this collection’s fields can price a heuristic against the optimum, and they are the two where the optimum is computable on small instances. Putting them beside each other says what is general here.

The least fill there is prices sparse orderings against an exhaustive minimum on grids small enough to have one. The order decides the memory is the same field’s opening measurement, where four orderings of one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries and the one with the better asymptotics loses at every size drawn. An ordering that does not wait for the numbers is where the same decision is made from the graph alone.

Every one of those is a comparison between named rules, and this page is a comparison along a parameter. The difference is worth having because a parameter makes two questions answerable that a list of rules does not: how much of the gap between a rule and the optimum is the rule’s ranking and how much is its commitment, and whether two rules that look different are different once the commitment is weakened. The answers here are: almost all of it is the commitment, and they are not.

Whether the same is true of sparse orderings — whether minimum degree and nested dissection converge to the same answer under a beam over elimination orders — is not measured anywhere in this collection, and it is the obvious thing to take from this page to that field.

Still open: whether the ranking can be fixed #

The anomaly is caused by one line — the beam is ordered on the cost incurred so far — and the obvious repair is to order it on cost so far plus an admissible estimate of what remains.

Two estimates are available without evaluating anything. The largest single pairing still to be made is one, and it is very weak. The sum, over every index still open inside more than one group, of the cheapest pairing that closes it is another, and it is not obviously admissible. Whether either removes the twenty-four networks or simply produces a different twenty-four is the measurement this page does not make, and it is the one that decides whether a beam over contraction orders is a search or a sampling.

The second open question is about the width itself. Every measurement here fixes the width across a whole network, and there is no reason to: the early pairings are where the commitment is most damaging and the late ones are nearly forced, so a beam that is wide at the top and narrow at the bottom would cost less and discard less. What the right schedule is, and whether it can be read off the network’s topology rather than tuned, is unmeasured.

One line #

Widening a greedy contraction search erases the difference between the two rules a library might ship, buys the median optimum for a seventh of an exhaustive search’s work, and on twenty-four of sixty networks returns a dearer order than the narrower search it replaced.