A beam ranked on what remains

The search that got worse as it widened kept the best few partial contraction orders instead of one and found the knob behaving badly. On 24 of 60 random seven-tensor networks, some wider beam returned a dearer order than a narrower one — by 3.49 times in a single step of the width on one of them — and by nine tensors the median network was worse at width 8 than at width 1.

It traced the cause to one line. A beam has to rank partial orders against each other to decide which to keep, and it ranks them on the only number a partial order has, the arithmetic it has cost so far. A prefix whose first pairing is dear and whose remaining pairings are cheap is the prefix an exhaustive search would choose and the first one that ranking discards. It named the repair and did not make it: rank on cost so far plus an estimate of what remains. Two estimates were suggested, one weak and admissible, one stronger and not obviously so, and the measurement asked for was whether either removes the twenty-four networks or simply produces a different twenty-four.

That question has an answer, and both halves of it happen — one estimate each.

Two estimates that cost nothing, and one that costs pairings #

A state of the beam is a set of groups — subsets of the network’s tensors that have already been contracted into one — and the work still to do is to pair those groups until one remains. What can be said about that work without doing it?

Every group takes part in at least one more pairing, and a pairing costs the product of the dimensions of every index either operand still carries, which is at least the size of each operand. So the remaining cost is at least the size of the largest group. That is admissible — it never exceeds the true remainder — and it is free, since the beam already knows every group’s open indices.

The remaining pairings form a binary tree over the groups. Each pairing costs at least the mean size of its two operands, and every current group is an operand exactly once, so the remaining cost is at least half the sum of the groups’ sizes. Also admissible and also free, and neither of the two is uniformly the stronger: half the sum wins when the groups are of similar size, and the largest group wins when one of them dwarfs the rest.

Every index still open in two or more groups must be summed over at some pairing, and the cheapest pairing of two current groups that both carry the index is a natural guess at what that pairing costs. Summing it over the open indices is the estimate the earlier measurement called stronger. It is not admissible, for two reasons: one pairing can close several indices at once and is then counted once for each, and the pairing that closes an index may be between groups formed later, which need not cost as much as any pairing available now. And it is not free. Finding each index’s cheapest closing pairing prices pairings, and those are counted below in the same unit as the search’s own.

The admissible estimate halves the anomaly #

Ranked on cost so far plus the largest group, the beam is anomalous on 12 of the 60 networks, against 24. Ranked on half the groups’ sum, also 12. And the medians and tails move as one would hope from the description of a beam rather than as the earlier measurement found them moving.

At width 8 the ninetieth percentile of the cost over the exhaustive order is 1.051 with the largest-group ranking and 1.027 with the half-sum, against 1.129 on cost so far. The number of networks on which the beam finds the exhaustive order outright rises steadily with the width — 30, 34, 37, 41, 47 and 50 across widths 1 to 8 — where on cost so far it was 30, 30, 28, 30, 35 and 42, dipping at width 3. The median reaches the exhaustive order at width 2 and stays there.

The pairings priced are unchanged: 56 at width 1 up to 301 at width 8, exactly the unranked beam’s, because the estimate is computed from numbers the beam already holds. So on seven tensors this is close to a free repair of half the problem.

And leaves the same networks behind #

The more interesting question is which twelve.

Eleven of the largest-group ranking’s twelve are networks the unranked beam was already anomalous on; one is new; thirteen of the original twenty-four are repaired. The half-sum’s twelve are the same split — eleven shared, one new, thirteen repaired. So the admissible estimates do what a better ranking should: they remove a subset of the failures and introduce almost none. The failures they leave are the ones where a lower bound on the remainder is too weak to separate the prefix that would have won from the prefixes crowding it out, and on those a cheap first pairing still looks better than it is.

The stronger estimate behaves quite differently. Ranked on the closing pairings, the beam is anomalous on 23 of the 60 — one fewer than cost so far — and only 10 of those 23 are from the original set. Thirteen networks the unranked beam widened without trouble are now widened into a dearer order, and fourteen of the original twenty-four are repaired. The earlier measurement’s suspicion was exact: this estimate does not remove the twenty-four networks, it produces a different twenty-three.

That is not the same as saying it is worse. It is worse at one thing — monotonicity in the width — and better at another.

The network followed through before, followed through again #

The earlier measurement traced one network in detail — the fifty-first of the ensemble — whose excess over the exhaustive order read 1.000, 3.491, 3.926, 3.491, 1.166 and 1.000 across widths 1, 2, 3, 4, 6 and 8. Width 1 found the optimum, one extra candidate lost a factor of three and a half, and it took six candidates to recover. A single wrong prefix, cheap in its first pairing and dear afterwards, had crowded the right one out of every beam narrow enough to hold only a few.

The same network under the three rankings reads:

The free estimates move the recovery two widths earlier, to width 4 and width 3, and neither rescues width 2 — which is why the network is still counted among the twelve. At width 2 the beam holds two states, and a bound built only from the sizes of the groups does not separate the prefix that finishes cheaply from the one that does not. The closing-pairing estimate, which reads which indices each prefix has left open and in which groups, does separate them, and keeps the right prefix at every width, including two.

That is the mechanism of the whole comparison in one network. The admissible estimates are functions of how large the groups are, and the damage a wrong prefix does is a function of which indices it has left open. The order decides the memory made the same distinction for elimination orders: the size of what an order has already produced says little about what it has committed the rest of the computation to.

An estimate that is not a bound buys the worst case #

The worst network under each ranking, at widths 1 to 8, reads 4.61, 3.49, 3.93, 4.10, 2.85, 2.85 on cost so far; 4.61, 3.49, 3.49, 2.85, 2.85, 2.85 with the largest group; and 4.61, 2.80, 2.47, 2.21, 2.21, 1.74 with the closing pairings. The admissible ranking never moves the worst case below the unranked beam’s floor of 2.85, and the inadmissible one takes it to 1.74 at width 8 and is below 2.85 from width 2 on.

The two facts fit together once the difference between a bound and an estimate is taken seriously. An admissible estimate is never above the truth, so it never makes a prefix look worse than it is — but it can make a bad prefix look as good as a good one, and it does so most often on exactly the networks whose remaining work is large, which are the networks with bad worst cases. An estimate that overcounts can make a prefix look worse than it is, which reorders the beam on networks that were fine, and it separates good and bad prefixes more sharply on networks whose remainder is dominated by a few dear indices. So the admissible ranking is conservative about change and the inadmissible one is aggressive about it, and each is paid for in the currency of the other.

At nine tensors, where widening had stopped paying #

The measurement that matters most is the one where the unranked beam had failed outright.

On forty nine-tensor networks the unranked beam’s medians across widths 1 to 8 are 1.0615, 1.1559, 1.0814, 1.1822, 1.1149 and 1.0656: every wider beam is worse than width 1 in the median, and width 8 is where width 1 was. Ranked on the largest group they are 1.0615, 1.0615, 1.0149, 1.0220, 1.0122 and 1.0101. Ranked on the closing pairings, 1.0615, 1.0289, 1.0124, 1.0113, 1.0068 and 1.0030.

The tails move further. The ninetieth percentile at width 8 is 1.892 unranked, 1.328 with the largest group and 1.356 with the closing pairings, and the worst network at width 8 is 4.91, 2.13 and 2.63. The number of networks solved exactly at width 8 is 10, 16 and 20 of 40.

The anomaly does not go away at nine tensors under either ranking — 27 networks unranked, 22 with the largest group, 19 with the half-sum, 21 with the closing pairings — and the largest-group ranking’s 22 include 21 of the unranked 27. What changes is that widening, which had become worthless in the median, is worth something again: the beam is still not monotone on half the networks, and it is now better for being wider on the median one.

What the stronger estimate costs #

The closing-pairing estimate prices pairings, and a comparison that did not count them would flatter it.

At seven tensors the unranked and largest-group beams price 56 to 301 pairings across widths 1 to 8. The closing-pairing beam prices 92 to 1,505 — five times as many at width 8 — and the exhaustive dynamic program makes 2,187 transitions over the same networks. So the stronger estimate’s best worst case, 1.74, is bought at seven-tenths of the cost of the exact answer. Against pairings priced, the largest-group ranking’s tail sits below the closing pairings’ at every width drawn — 1.051 at 301 pairings against 1.107 at 1,505 — so at seven tensors the dearer estimate buys the worst case and nothing else.

At nine tensors the proportions change in the stronger estimate’s favour. The exhaustive program makes 19,683 transitions; the unranked and largest-group beams price 120 to 708 pairings; the closing-pairing beam prices 193 to 3,630. Its ninetieth percentile at width 2 — 1.472, for 426 pairings — is better than the largest-group ranking’s at width 4, 1.591 for 372, and within a tenth of its width 8, 1.328 for 708. As the network grows the exhaustive search grows like 3ᵗ and the estimate’s cost grows with the number of open indices and groups, so an estimate that is too dear at seven tensors becomes the cheaper route to a light tail at nine.

What to ship, and what this does to the earlier rule #

The earlier measurement’s recommendation was width 1 with the smallest-result rule as the default, and a wide beam only for a small network contracted thousands of times. The rankings change the second half and not the first.

Width 1 is still width 1. At width 1 there is nothing to rank; every estimate gives the same answer, 1.0026 in the median at seven tensors and 1.0615 at nine.

A beam should never be ranked on cost so far. The largest-group estimate is free, never hurts the median, halves the networks on which widening hurts, and lightens the tail at every width. There is no measurement here in which the unranked beam is better.

The closing-pairing estimate is for large networks and bad worst cases. It is the only ranking that moves the worst case at seven tensors and the one with the best median at nine, and it prices several times the pairings of the free estimates. A code contracting the same network many times, where the order is chosen once, can afford it; a code choosing an order per call cannot.

And the part of the earlier rule this measurement does not touch: a stale order still costs more than any of this buys. The plan that was right at rank four found an order compiled at the wrong dimensions losing a factor of eight; a ranked beam recovers a few per cent in the median.

Where the same repair has been made before #

The ordering field priced the same trade on a different combinatorial object. The least fill there is searched sparse elimination orders exhaustively on grids small enough to allow it, and two minima that are one minimum found that minimum degree, the greedy rule, attains the least fill and the least work together on most graphs. Neither needed a beam, because minimum degree’s ranking is already a statement about the future — the degree of a vertex is the fill its elimination creates — while a contraction rule’s ranking is a statement about one pairing.

That is the difference the estimate repairs. A greedy rule is a ranking and a commitment, the order the products are taken in is where the ranking was first priced, and the beam’s width weakens the commitment. What the width cannot do is improve a ranking that only looks one step ahead, and the estimate is the smallest change that makes it look further. A ceiling is not a target found the same shape one level up: the quantity an order was chosen on is not the quantity it will be judged on, and the gap between the two is where the damage is done.

What this rests on #

Sixty seven-tensor networks with eight index labels and forty nine-tensor networks with ten, each drawn with dimensions from 2 to 12 and each pair of tensors sharing labels at random; the exhaustive order from the dynamic program over subsets. The beam pairs by smallest result and each state offers its own best width moves before the global cut, as in the earlier measurement; with no estimate and a constant width it reproduces that measurement to the digit on every network checked.

Nine tensors is the largest size at which the exhaustive order is priced here, and it is far below the sizes a beam is written for. The trend from seven to nine — the unranked beam losing the value of width, the ranked beams keeping it — is what can be said about larger networks, and it is a trend in two points.

The claim that has to fail #

The claim is the natural reading of the repair: rank a beam on an admissible estimate of what remains, and a wider beam can no longer return a worse answer. It is false, and it is false in an instructive number. With the largest-group estimate, over sixty networks, some wider beam still returns a dearer order than a narrower one on twelve. The refusal is fed the claim that none does and fails there — and the unranked beam’s twenty-four, measured beside it, is what makes the twelve a repair of half rather than a repair of nothing.

Still open: the width schedule, and an estimate from the index graph #

The width across the levels. Every beam here keeps the same number of partial orders at every pairing. The early pairings are where a 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 looks as though it should cost less and discard less. Whether it does, and whether the right schedule can be read off the network rather than tuned, is measured in widen the beam where the ranking is right.

A bound from the index graph. Both admissible estimates look only at group sizes. The remaining contraction is a tree decomposition of the index graph restricted to the open indices, and the treewidth of that graph gives a lower bound on the largest pairing still to come that is often far stronger than the largest group. Computing it exactly is as hard as the problem; a cheap lower bound on treewidth — the minimum degree of the graph, say — is admissible and free, and whether it closes the gap between the free estimates and the closing pairings is unmeasured.