A near-tie is a factor of four

Widen the beam where the ranking is right measured ten ways of spending a beam’s width across the levels of a contraction order. A contraction of several tensors over shared indices can be evaluated by pairing them in many orders, and the orders differ in arithmetic by factors of thousands and more; the exhaustive order is findable for up to nine tensors, and every heuristic can be scored against it. The beam keeps several partial orders at once and ranks them on the cost so far. Wide early — sixteen partial orders at the first pairings, one at the last — was worse than keeping one throughout. Wide late — one at the first pairings, sixteen at the last — found the exhaustive order on 37 of 60 seven-tensor networks for 78 pairings priced, against width one’s 30 for 56, and at nine tensors had the best median of any schedule up to 1,380 pairings.

Both schedules spend width by level, the same width on every network. The essay closed by proposing the other way to spend it: by uncertainty. The pairings where a beam most needs width, it argued, are the ones where several candidates produce results of nearly the same size — where the ranking is a near-tie. A beam that widens at near-ties and stays at width one elsewhere would put its width exactly where the ranking cannot choose, and whether that beats wide late was the comparison left open.

One knob instead of a schedule #

The construction is a single change to the plain beam. At each partial order, the plain beam offers its best width pairings, ranked by the size of each pairing’s result; the tie-widened beam offers every pairing whose result is within a factor $1 + \tau$ of the smallest, and at least one. After merging, the plain beam keeps its width cheapest partial orders; the tie-widened beam keeps every partial order whose cost so far is within $1 + \tau$ of the cheapest. Both are capped at sixteen, the widest any schedule used. With τ = 0 the beam widens only at exact ties, which are not rare here: sizes are products of integer dimensions and different pairings often produce results of exactly the same size.

The ranking itself is unchanged — the same two keys the plain beam uses — so any difference is where the width went and nothing else. The first key, the smallest result next, is the greedy rule a ceiling is not a target found costing a median of 1.55 times the cheapest order’s arithmetic when used alone; everything a beam does is an attempt to recover what that rule throws away. And τ is a single number with a meaning: how much worse, by the ranking’s own measure, a candidate may look and still be kept.

Near-ties buy nothing #

On the sixty seven-tensor networks, the tie-widened beam at τ = 0 prices 60 pairings and finds the exhaustive order on 31. At τ = 0.25 — every candidate within a quarter of the best — it prices 66 and finds 31. At τ = 0.5, 76 and 32; at τ = 1, 103 and 33. The widths it actually uses at those tolerances average 1.1 to 2.9 across the levels: the beam is widening, a little, and the widening is buying almost nothing. Width one finds 30.

Then it turns. At τ = 2 the beam prices 150 pairings and finds the exhaustive order on 46 networks; at τ = 3, 198 and 48; at τ = 5, 270 and 52; at τ = 8, 338 and 53. Constant widths of 2, 4 and 8 price 91, 161 and 301 and find 30, 30 and 42. For the same pairings, the tie-widened beam from τ = 2 on finds the exhaustive order on more networks than any constant width does, by eleven to sixteen networks. Wide late sits where it did, 78 pairings for 37 — still the cheapest way to beat width one, and now no longer the best at any price above it.

So the proposal is half right. Width spent by uncertainty does beat width spent by level, when there is enough of it. But the uncertainty that matters is not a near-tie. A beam that keeps candidates within a few per cent of the best is a beam of one with extra steps.

How far down the right pairing sits #

Why near-ties are not the place can be read directly off the exhaustive trees, without any beam.

For each network, walk the exhaustive contraction tree from the leaves, and at each level ask where the tree’s own pairing sits in the ranking the beam uses. There is usually more than one pairing consistent with the tree at a level — independent subtrees can be contracted in either order — so take the one the ranking likes best, and record the ratio of its key to the smallest key on offer. A ratio of one means the ranking’s first choice was the tree’s. The largest ratio along the walk is the factor a tie-widened beam would have to tolerate to keep the exhaustive order in reach at every level.

At seven tensors the ranking’s first choice is the tree’s own pairing on 315 of 360 levels. On 34 of the 60 networks it is the first choice at every level — and width one, which follows the first choice, finds the exhaustive order on 30 networks in all. On the other 26 networks the tree’s pairing is somewhere down the ranking, and it is not close: within a quarter of the best on 6 more networks, within a factor of two on 16 more, within four on 21 more, within nine on 25. The median of those 26 needs a factor of about two.

At nine tensors the picture is the same, shifted. The first choice is the tree’s on 252 of 320 levels and on every level of only 13 of 40 networks; within two, four and nine the counts are 21, 29 and 38, and the median network needs 1.96.

That is the answer to where width belongs. The levels where the ranking goes wrong are not levels where two candidates look alike. They are levels where the right pairing produces a result two or three times larger than the pairing the ranking prefers — larger now, and cheaper over the rest of the contraction, which is the whole reason the exhaustive search can prefer it. A near-tie criterion looks for uncertainty in the wrong place: the ranking is confident, and wrong by a factor of two to four.

Reach is necessary, and the second cut decides #

The walk down the exhaustive trees gives a necessary condition for the tie-widened beam: a network whose tree needs a factor above $1 + \tau$ somewhere cannot be solved at that τ, because the tree’s pairing is never offered. It is not sufficient, because the beam makes a second cut — among partial orders, on cost so far — and the right partial order can be offered and then dropped there.

Both halves show up cleanly. At seven tensors, every network the beam solves at τ = 0, 1 and 3 is one whose tree is in reach at that τ; not one is solved from outside. At τ = 0 the tree is in reach on 34 networks and the beam solves 31. At τ = 1 it is in reach on 50 and the beam solves only 33: seventeen networks are offered the right pairing at every level and lose it anyway, to the partial-order cut. At τ = 3 the reach is 55 and the beam solves 48, so the second cut now costs seven. At nine tensors the pattern is sharper still: in reach on 13, 21 and 29 networks at τ = 0, 1 and 3, solved on 12, 9 and 18. At τ = 1 the beam solves fewer networks than width one does, having widened exactly enough to offer more right pairings and then discard them.

That is the jump between τ = 1 and τ = 2 in the frontier figure. The pairing tolerance was already reaching most trees at τ = 1; the partial-order tolerance was not yet keeping them. A partial order whose first pairing was the expensive, correct one is more than twice as dear so far as the cheap, wrong one on many of these networks, and a factor of three admits it where a factor of two does not. The two cuts need about the same tolerance, and it is the second that the earlier essays kept finding at fault. The least fill there is searched every elimination order of a twenty-vertex graph to find the optimum a greedy ordering was missing; the walk down each exhaustive tree here is the same instrument turned on a beam, and it locates the misses rather than only counting them.

Nine tensors #

On forty nine-tensor networks the frontier has the same shape at larger prices: the tie-widened beam gains nothing up to τ = 1 — it finds the exhaustive order on 12, 10, 8 and 9 networks at τ = 0, 0.25, 0.5 and 1, never more than width one’s 12 — and then 17 at τ = 2 and 18 at τ = 3, where constant widths of 2, 4 and 8 find 9, 7 and 10 and wide late 12.

At nine tensors the widening matters more, because the ranking is wrong more often. Width one prices 120 pairings for a median of 1.0615 and a ninetieth percentile of 2.675. Wide late prices 142 for 1.0556 and 2.498. The earlier essay recorded that nothing between those prices and constant width sixteen’s 1,380 beat wide late’s median. The tie-widened beam does: at τ = 2 it prices 426 pairings for a median of 1.0074 and a ninetieth percentile of 1.458; at τ = 3, 615 for 1.0071 and 1.242. Constant width eight, for 708 pairings, has 1.0656 and 1.892 and finds the exhaustive order on 10 networks, against 17 and 18 for the tie-widened beam.

The small tolerances are worse than useless here, which repeats a finding made twice already about widening a contraction beam — and which has a cousin in elimination orderings, where the depth that is worse than both ends found a little of a second method worse than none of it or all of it. At τ = 0.25 the median rises from 1.0615 to 1.1559, and at τ = 0.5 the ninetieth percentile from 2.81 to 3.35. The search that got worse as it widened found wider beams returning dearer orders on two networks in five, and traced it to the ranking on cost so far: a prefix whose first pairing is dear and whose later ones are cheap is the prefix the exhaustive search keeps and the ranking drops first. A slightly wider beam admits a few more cheap-looking prefixes, which then crowd the right one out at the next level. The tie-widened beam at τ ≥ 2 escapes that, because it no longer cuts to a fixed count at all: a partial order within a factor of three of the cheapest is kept however many others are too, and the dear-first prefix is usually within that factor.

Where the width ends up #

A beam that spends width by uncertainty ends up with a schedule of its own, and it is neither of the two the earlier essay compared.

At nine tensors and τ = 2, the beam keeps on average 2.5 partial orders after the first pairing, 4.2 after the second, then 6.0, 7.0, 7.5, 6.9 and 4.0. It is widest at the fourth and fifth pairings, in the middle of the contraction, and narrows at both ends. Wide late prescribes 1, 1, 1, 1, 2, 4 and 8 over the same levels.

Both ends narrow for reasons that are visible in the counts. At the first pairing there is one partial order and the ranking of pairings by result size is at its most informative — width one loses the exhaustive order at the first pairing on only ten of sixty seven-tensor networks — so few candidates are within a factor of three. At the last pairings few groups remain, few pairings are possible, and different routes merge into the same grouping, so the beam cannot be wide even if it wanted to be. In the middle the number of possible groupings is largest and the ranking by result size is least reliable, because the result that looks large now is the one that makes the rest cheap. That is where the exhaustive order hides, and where the tie-widened beam finds it.

This refines rather than overturns the earlier essay’s conclusion that a beam should be wide where its ranking is right. Wide late was right that the early levels do not need width. It was wrong to put the width at the very end, where the beam has little to choose between; the pairings that decide the order are in the middle, and a beam told to keep everything plausible puts its width there without being told where the middle is.

What it costs, in pairings #

The price of the τ = 2 beam at nine tensors is 426 pairings against wide late’s 142 — three times the arithmetic spent on choosing an order. Whether that is worth paying depends on how many times the order will be used, which the plan that was right at rank four found to be the question that decides every contraction plan: an order chosen once and run thousands of times can afford a search a thousand times dearer than one chosen per run. At nine tensors a median of 1.007 against 1.056 is a five per cent saving on every execution, and the ninetieth percentile’s 1.46 against 2.50 is a saving of forty per cent on one execution in ten. And a pairing priced is a size computed from a handful of dimensions, a few operations, where a contraction at these sizes is thousands to millions; the extra 284 pairings are repaid on the first execution.

It is also cheaper than the alternative that reaches the same quality by brute force. Constant width sixteen reaches a median of 1.0082 at nine tensors for 1,380 pairings; the tie-widened beam reaches 1.0074 for 426.

Against the ranking that was repaired #

A beam ranked on what remains attacked the same failure from the other side: rank each partial order on its cost so far plus an estimate of what remains, so that the dear-first prefix is not dropped for being dear first. The largest remaining group, a free and admissible lower bound, halved the number of networks on which widening made the beam worse. That repair and this one are complementary. The estimate changes which partial orders look cheap; the tolerance changes how many are kept once they have been ranked. The tie-widened beam here uses the unrepaired ranking, cost so far alone, and the whole of its improvement is the tolerance. Combining the two is the obvious next measurement and is not made here.

What this does not settle #

Random networks of seven and nine tensors with eight and ten labels, the same family every measurement of contraction beams here has used. Networks with structure — a train, a grid, a tree of tensors — have exhaustive orders of a recognisable shape, and the ranking’s gap to them may be systematically larger or smaller. The cap of sixteen binds at τ = 5 and 8, where the mean width in the middle levels at nine tensors reaches 14 to 15.6; a higher cap would price more and might find a few more exhaustive orders.

The tolerance is applied identically to the pairings and to the partial orders. They are different quantities — a result size and a cumulative cost — and there is no reason the right tolerance for one is the right one for the other.

Still open: the tolerance and the estimate together, and a tolerance per quantity #

Tie-widening on the repaired ranking. Ranked on cost so far plus the largest remaining group, the beam’s anomaly halved; tie-widened on cost so far, its tail fell by a factor of two at nine tensors. Whether the two combine — whether a beam ranked on the estimate needs a smaller τ to reach the same networks, and so fewer pairings — is one sweep over the same ensembles, and it is the measurement that would say whether the remaining gap is the ranking’s or the tolerance’s.

Two tolerances. The walk down each exhaustive tree measured the gap in the pairing ranking, by result size, and found it at a factor of two to four. The gap in the partial-order ranking, by cost so far, was not measured, and it may be the one that needs the wider tolerance: the dear-first prefix is dear by the cost of its first pairing, which can be many times the others’. Splitting τ into one for pairings and one for partial orders, and finding each one’s smallest useful value separately, would tell which of the two cuts was losing the exhaustive order.