Widen the beam where the ranking is right

Every beam measured so far kept the same number of partial contraction orders at every pairing. The search that got worse as it widened ended with a reason to doubt that choice: 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 should cost less and discard less. It left the schedule unmeasured, and asked whether the right one could be read off the network rather than tuned.

A beam ranked on what remains repaired half of that beam’s trouble by changing what it ranks on. This measurement changes where it is wide, with the ranking left as the earlier essays had it — cost so far — so that the two repairs can be told apart.

The intuition turns out to be exactly backwards, and the reason is in the ranking.

Ten shapes of one beam #

A seven-tensor network is contracted in six pairings, so a schedule is six widths. The ones measured:

Every beam pairs by smallest result and each state offers its own best moves before the beam is cut, so the only thing that differs between the rows is how many partial orders survive each cut. Pairings priced are counted the same way for all ten.

Two rows decide the argument. Wide early prices 372 pairings — more than six times width 1’s — and finds the exhaustive order on 27 networks, three fewer than width 1. Wide late prices 78, fewer than width 2, and finds it on 37, seven more than width 1 and seven more than a constant width of 4 at twice the price. On the chart the constant widths form the frontier a tuner would search along, and wide late sits well inside it while wide early sits outside it altogether.

The tail says the same thing #

The share of networks solved exactly is one reading. The ninetieth percentile of cost over the exhaustive order is the reading a code that has to live with its worst networks cares about.

The constant widths give 1.493, 1.277, 1.716, 1.129 and 1.027 at widths 1, 2, 4, 8 and 16 — non-monotone, as the earlier measurement found. Wide late gives 1.191 for 78 pairings, better than every constant width up to 4 at a fraction of their price. Wide early gives 1.443, barely better than width 1 for more than six times the pairings, and its worst network is 4.10 against wide late’s 2.76.

The slow versions sit between their fast siblings and the constants. Wide early, slowly — widths 16 down to 3 — reaches 1.171 and 40 optimal networks by keeping enough width at the end that the early width is not all thrown away; tapering to 1 does slightly worse. Wide late, slowly starts at 3 and prices 177 pairings for 39 optimal networks and a tail of 1.207, which is two networks more than wide late for more than twice the pairings.

Where each beam loses the right order #

The mechanism is visible if the question is asked of each network separately: at which pairing does the beam stop holding any partial order that is consistent with the exhaustive tree, and was the right pairing never offered, or offered and cut?

Width 1 loses the right order only by never offering it. It keeps the exhaustive tree on 30 networks, and on the other 30 the rule’s single best move was simply not the right one — at the first pairing on 10, the second on 11, the third on 6, and later on 3. Nothing is discarded, because a beam of one has nothing to discard.

A constant width of 4 converts most of those into discards. It keeps the tree on 29 networks — one fewer than width 1 — and of the 31 it loses, 26 are pairings that were offered and then cut, 14 of them at the second pairing and 9 at the third. The width did what a width is for: the right pairing was offered on almost every network. Then the ranking on cost so far threw it away.

Wide early is the extreme of the same thing. It keeps the tree on 26. It offers the right pairing nearly everywhere — only 3 networks lose it by never offering it — and discards it on 31, 17 of them at the third pairing, which is exactly where its width falls from 8 to 4 and the beam has to cut everything it was offered down to four. The early width produced candidates, and the narrowing cut them on the one quantity that cannot tell a good prefix from a bad one this early.

Wide late never discards. It keeps the tree on 37. Its first two pairings are width 1, so it loses the right order by never offering it on exactly the networks width 1 does at those pairings — 10 at the first, 11 at the second — and nowhere else except 2 at the third. The losses width 1 suffers at the third to fifth pairings, 9 of them, wide late recovers 7, by being wide at the point where the beam holds few groups, the remaining work is small, and cost so far is most of the total. On these sixty networks its ranking is never asked to discard the right prefix at all.

Where the pairings go #

The prices in the table are not arbitrary, and the breakdown is worth writing out because it says why the two shapes cost so differently for the same largest width.

A state with g groups offers its own best moves out of g(g − 1)/2 possible pairings, and every one of those is priced. A seven-tensor network starts with seven groups, so the six levels price 21, 15, 10, 6, 3 and 1 pairings for each state the beam carries into them. The cost of a schedule is the sum, over levels, of those counts times the number of states that arrive.

Wide early carries one state into the first level, sixteen into the second, eight into the third, four, two and one after that: 21 + 16·15 + 8·10 + 4·6 + 2·3 + 1 = 372. Two hundred and forty of the 372 pairings are priced at the second level, where each of sixteen states has fifteen pairings to consider and the ranking has one pairing’s worth of cost to judge them by.

Wide late carries one state into each of the first three levels and then at most two, four and eight: 21 + 15 + 10 + 2·6 + 4·3 + 8·1 = 78. Its widest level, sixteen, is also its cheapest, because by then each state has two groups and one pairing left. The width costs almost nothing exactly where the ranking can use it, and costs most exactly where it cannot — which is the same fact as the loss figure, counted in pairings instead of in trees.

At nine tensors the arithmetic is starker. The second level has twenty-eight pairings per state, so wide early’s sixteen states there price 448 of its 742. Wide late’s schedule could price at most 184, and measures 142, because partial orders that reach the same grouping by different routes are merged and fewer states arrive than the width allows.

The ranking is what decides where width helps #

That last observation is the whole argument, and it is the ranking half of what the order the products are taken in called a greedy rule: a ranking and a commitment, measured together. A beam’s width produces candidates and its ranking chooses among them, and the value of a candidate depends on whether the ranking can recognise it.

At the first pairings of a seven-tensor network, cost so far is one or two pairings out of six, and says little about the total. Widening there multiplies candidates the ranking cannot tell apart; narrowing afterwards forces it to choose among them anyway, and it chooses on the cheap first pairings that the earlier measurement already identified as the trap. At the last pairings, cost so far is four or five pairings out of six — nearly the whole cost — and the ranking is close to exact. Widening there multiplies candidates the ranking can tell apart, and there are few of them, because a state with three groups has only three possible pairings.

So the intuition that the damaging commitments are early is true and leads to the wrong schedule. The commitments are damaging early because the ranking is uninformed early, and a wide beam does not make the ranking informed. It gives an uninformed ranking more to be wrong about.

At nine tensors the difference is larger #

Forty nine-tensor networks, eight pairings each. Width 1 prices 120 pairings for a median of 1.0615. Wide early — 16, 8, 4, 2 and then 1 — prices 742 for 1.2627, with a ninetieth percentile of 4.126 and a worst network of 13.3 times the exhaustive order, against width 1’s 4.92. Six times the arithmetic has bought an answer a fifth worse in the median and nearly three times worse at the worst. Tapering does better than wide early and worse than width 1: 1.1103 for 1,092 pairings. Wide early, slowly: 1.2117 for 930.

Wide late — width 1 for four pairings, then 2, 4, 8, 16 — prices 142 for 1.0556, the best median of any schedule up to 1,380 pairings, and matches width 1’s 12 optimal networks. Constant width 16 reaches 1.0082 for 1,380. Nothing between those two prices beats wide late in the median.

The losses read the same way at nine tensors. Width 1 keeps the tree on 12 of 40 and loses it on 28 by never offering it. A constant 4 keeps it on 7, a constant 8 on 9, and each discards it on 30 or 31. Wide early keeps it on 4 and discards it on 31. Wide late keeps it on 12 and discards it on 2. The constant and wide-early beams are losing more trees than width 1 does, and they are losing them to the ranking.

With the ranking repaired #

The obvious objection is that all of this is a fact about a bad ranking, and the ranked beam has a better one. So the nine-tensor sweep is repeated with every beam ranked on cost so far plus the largest group still to be paired.

The estimate does exactly what the earlier measurement found. The constant widths become monotone in the median — 1.0615, 1.0615, 1.0220, 1.0101 and 1.0000 at widths 1, 2, 4, 8 and 16 — and the slow schedules improve most: wide early, slowly from 1.2117 to 1.0327, tapering from 1.1103 to 1.0122. Wide late improves from 1.0556 to 1.0400, and is still the cheapest schedule that improves on width 1, at 142 pairings against a constant 4’s 1.0220 for 372.

Wide early is still the worst schedule drawn, 1.2627 improving only to 1.2264, and it finds the exhaustive order on 4 networks of 40 — fewer than any other schedule, ranked or not. An estimate built from group sizes is still weakest at the first pairings, where every group is a single tensor and the bound is the size of the largest input; the fast narrowing still falls on the pairings where the ranking knows least. The repair to the ranking and the repair to the shape are separate repairs, and neither substitutes for the other.

What a schedule should be, then #

The measurement supports a rule that can be stated without tuning anything to a network: keep the beam narrow until the remaining work is a small share of the total, then widen it as fast as the number of groups allows.

The shape follows from two counts a code already has. The number of groups a state holds tells it how many pairings remain, and how many distinct states are possible — three groups have three pairings, four have six, five have ten — so a width equal to that number at the last few levels makes the end of the search exhaustive over the prefixes that reach it, for a cost bounded by those small counts. The width before that point buys candidates the ranking cannot judge, and on this evidence it is better spent later or not at all.

That answers half of the earlier question — whether the schedule can be read off the network. The point at which to widen can be read off the level, which is a property of the network’s size, and nothing here needed the network’s topology. What the measurement does not show is whether a topology-aware schedule — wide exactly at the pairings where the network’s index graph offers several nearly equal choices — would do better still. That would need a reading of the index graph at each state, and it is not measured.

The shape of the finding has been met once before here, on a different combinatorial object. The depth that is worse than both ends found that a hybrid ordering — one bisection, then minimum degree — did worse than either pure strategy, because the mixture put each strategy where the other was the better one. A wide-early beam is the same mistake with a width in it: the exhaustive search’s virtue is spent at the level where the ranking is weakest, and the greedy rule’s cheapness at the level where a wider look would have been nearly free.

And the rule sits beside the ones already measured, not in place of them. The plan that was right at rank four found a stale order losing a factor of eight; a ceiling is not a target found a memory limit priced as a constraint rather than as an objective. A well-shaped beam recovers per cent. Those recover factors.

What this rests on #

The same ensembles as the ranked measurement: sixty seven-tensor networks with eight labels and forty nine-tensor networks with ten, dimensions from 2 to 12, the exhaustive order from the dynamic program over subsets. Each schedule is a function of the pairing level only. The level at which a beam loses the exhaustive order is found by checking, after every cut, whether any surviving state’s groups are all nodes of one exhaustive tree — the one the dynamic program returns. Where several trees tie for the exhaustive cost, a beam can follow a different optimal tree and still be counted as having lost this one, which is why the “kept” counts differ from the “optimum found” counts by a few networks.

The exhaustive order is affordable here only because the networks are small; the least fill there is drew the same line for elimination orderings, and every conclusion about a heuristic in these essays and those is a conclusion at sizes where the answer is still computable.

The schedules are six hand-chosen shapes, not a search over shapes. A different fast-narrowing schedule could do better than the ones drawn, and the claim is not that no early-wide schedule can work but that width spent where the ranking cannot use it is thrown away by the next cut.

The claim that has to fail #

The claim is the one the earlier measurement’s intuition makes: a beam that is wide where commitments are most damaging and narrow where they are forced is at least as good as a beam of one. At nine tensors, over forty networks, the wide-early schedule’s median is 1.263 times the exhaustive order’s against width 1’s 1.062. The refusal is fed the claim that it is no worse and fails there; wide late, measured beside it on the same networks at 142 pairings, is the control that makes the failure a fact about where the width was put rather than about width.

Whose fault is it usually has two candidates in these essays, the problem and the algorithm. In a beam it has three: the rule that offers candidates, the width that keeps them, and the ranking that cuts them. The loss figures assign each lost tree to one of the first and third, and the width’s contribution is only ever to change which of those two is to blame.

Still open: widening where the index graph branches, and the schedule for a stale order #

A schedule read from the index graph. Every schedule here depends on the level alone. The pairings at which a beam most needs width are the ones where several candidate pairings produce results of nearly the same size — where the rule’s ranking is a near-tie. A beam that widens at near-ties and stays at width 1 elsewhere would spend its pairings only where the rule is uncertain; whether that beats wide late, which spends them where the ranking is informed, is the direct comparison between the two readings of where width belongs.

Width across a run. A contraction repeated inside an iteration whose ranks drift is contracted with an order chosen once. A beam run once at compile time can afford a large width, and the question is whether the order a wide-late beam chooses at one set of dimensions goes stale more or less gracefully than the greedy order does, as the ranks move away from the ones it was chosen at.