The prefix sits further down

A near-tie is a factor of four changed how a beam search over tensor-contraction orders spends its width. A beam keeps a few partial orders — some of the tensors already paired, the rest still open — and extends each by every pairing it could make next. It cuts twice at every level: out of each partial order it keeps the pairings whose results are smallest, and out of all the partial orders those pairings produce it keeps the ones whose cost so far is lowest. The earlier beams had a fixed width at each level. The essay gave it a tolerance instead — keep every candidate within a factor $1 + \tau$ of the best — and found that a near-tie is the wrong idea of uncertainty. A tolerance of a quarter changed nothing; the useful $\tau$ was two or three, and with it the beam found the exhaustive order on 46 of 60 seven-tensor networks.

That tolerance was one number applied at both cuts. The essay measured how far down the pairing ranking the exhaustive order’s own pairing sits, level by level, and found a factor of two to four. It did not measure the other cut, and said so with a prediction: the partial-order cut “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’.” Split $\tau$ in two, find each one’s smallest useful value separately, and the measurement “would tell which of the two cuts was losing the exhaustive order”.

It does tell, and the answer is the one predicted. The surprise is in the half of the grid nobody was asked about.

Two rankings, two gaps #

The networks are the earlier essays’: seven or nine tensors on random index graphs, eight distinct index labels, dimensions between two and twelve, sixty networks at seven and forty at nine, each with its exhaustive order computed by dynamic programming over every subset. The beam is the same machine with one change: the pairing cut keeps every pairing whose result is within $1 + \tau_{\text{pair}}$ of the smallest, the order cut keeps every partial order whose cost so far is within $1 + \tau_{\text{order}}$ of the cheapest, and both are capped at sixteen as before.

The first measurement needs no beam at all. Follow the exhaustive tree level by level. At each level, two numbers say how far down each ranking the exhaustive order’s next move sits: its pairing’s result size over the smallest result on offer, and its prefix’s cost so far over the cheapest prefix one pairing on from the same place. The largest of each along the walk is the $1 + \tau$ that cut needs to keep the exhaustive order in reach.

At seven tensors the exhaustive pairing is the size ranking’s first choice at every level on 34 networks of 60, and the median need at the pairing cut is exactly one. The median need at the order cut is 2.33. On 49 networks the order cut needs more room than the pairing cut; on most of the rest they need the same. At nine tensors the pairing cut needs a median of 1.50 and the order cut 3.20, and the order cut needs more on 33 of 40. The cloud sits above the diagonal in both colours, most of it in a column at a pairing need of one.

So the reading the earlier essay took from its pairing walk — the exhaustive pairing is a factor of two to four down the ranking — was a reading of the hard networks at the size ranking’s cut, the ones it walked because the beam failed them. Over the whole ensemble the size ranking is usually right about the next pairing. What it cannot be right about is the order in which the cheap pairings are taken relative to an expensive one, and that decision is made at the other cut.

Why the prefix sits further down #

The reason is the one the prediction gave, and the walk makes it concrete. The exhaustive order on a typical network pays for one expensive pairing early — joining two tensors whose shared indices are small and whose free indices are large — because that pairing removes an index everything later would otherwise carry. At the level it takes that pairing, its prefix is dearer than the alternatives by the whole cost of that pairing, and the alternatives are prefixes that took a cheap pairing instead and will pay more later. Ranked by cost so far, the exhaustive prefix is not near the top; it is a factor of two or three down, at the level where it spent.

The walk locates the expense. The level at which the order cut’s need is largest is the first or second on 43 of the sixty seven-tensor networks and on 28 of the forty nine-tensor ones, and at that level the exhaustive order’s pairing is the size ranking’s own first choice on 41 networks of 60 and 23 of 40. So the typical failure is not that the beam never considers the right pairing. It is offered first, at the second level, by the ranking whose job is to offer it — and the next cut throws it away because it was the dearest thing anyone had done so far. A ceiling is not a target priced orders against a memory limit and found the cheapest order often peaks early; this is the same early peak, seen by a ranking that reads it as waste.

The size ranking at the pairing cut does not have that problem, because it does not look at what was spent. A pairing whose result is small is one that contracts a lot away, and the exhaustive order’s pairings are, level by level, mostly the ones that do that. A beam ranked on what remains attacked the same weakness from the other side by adding an estimate of the remaining cost to the cost so far; this measurement says where its estimate was needed, and it is at exactly the cut where a cost-so-far ranking is blind.

The reach figure turns the walk into the quantity a beam’s designer would choose by. At $\tau = 0$ — only exact ties kept — the pairing cut keeps the exhaustive order in reach on 57 per cent of seven-tensor networks and the order cut on 5 per cent. To keep it in reach on 70 per cent the order cut needs $\tau = 2$; the pairing cut needs a half. At nine tensors the order cut keeps none in reach until $\tau = 1$, and 45 per cent at 2.

Spend the width where it is needed #

The grid is the measurement the earlier essay asked for. Its diagonal is the single tolerance: 31 networks at $\tau = 0$, 46 at $\tau = 2$ for 150 pairings priced, 53 at $\tau = 8$ for 338. Read along a row instead, and the cost of the same success falls. With the pairing cut at 0.5 and the order cut at 8, the beam finds 46 networks for 98 pairings; with the pairing cut at 1 and the order cut at 8, 51 networks for 136. Both beat the single $\tau$ of two at both cuts, one for two thirds of its work and the other for less.

At nine tensors, which the dial shows, the pairing cut is not free: the walk said it needs a median factor of one and a half, and the best cells are at $\tau_{\text{pair}}$ of 0.5 to 1 with the order cut at 3 to 8 — 25 networks of 40 at (1, 5) for 510 pairings, where the single $\tau$ of three found 19 for 743. Holding the pairing cut at zero, the order cut alone reaches only 14.

So the prediction holds in its own terms. The order cut is the one that was losing the exhaustive order, and its smallest useful tolerance is two to three; the pairing cut’s is a half to one.

The half of the grid nobody asked about #

The prediction did not say what happens in the lower-left corner — the pairing cut widened and the order cut not — and on the reasoning that more candidates can only help, it should have been no worse than the top row. It is the worst region of the grid.

With the order cut at zero, widening the pairing cut from nothing to 0.5, 1, 2, 3, 5 and 8 reduces the seven-tensor networks solved from 31 to 26, 21, 14, 13, 7 and 4, and raises the median excess from exactly one to 1.016, 1.042, 1.096, 1.137, 1.235 and 1.446. At nine tensors the networks solved fall from 12 to 1 and the median rises from 1.030 to 1.733. A beam that keeps more pairings and the same number of partial orders does worse than a beam that keeps fewer of both — at the widest, a median of 45 per cent over the exhaustive order at seven tensors and 73 per cent at nine.

The mechanism is in what the order cut does with what it is given. With $\tau_{\text{order}} = 0$ it keeps only the cheapest partial order. When the pairing cut keeps one pairing per state, the cheapest partial order is chosen among the few that the size ranking proposed — pairings that contract a lot away — and cost so far only breaks ties among good proposals. When the pairing cut keeps eight, it proposes cheap pairings that contract little, and the order cut, ranking by cost so far, prefers them: they cost least now. The beam becomes a cost-so-far greedy search with a size-ranked shortlist that has been lengthened until it no longer filters anything. The search that got worse as it widened found a beam whose larger width made results worse, and traced it to a ranking that was being given more rope; this is the same failure, located at one cut.

Held at $\tau_{\text{order}} = 8$, the same widening of the pairing cut does no harm at seven tensors — the median is one at every $\tau_{\text{pair}}$ — and only a little at nine. A wide order cut keeps the dear prefixes alive, and then a wider pairing cut simply proposes more of them.

The frontier puts all four paths on one pair of axes. The two paths that widen the order cut lie above the single-$\tau$ path wherever they overlap in work: at 98 pairings the order-cut path has 46 networks where the single $\tau$ has 33 at 103. The path that widens the pairing cut stays at sixty-odd pairings, because a beam whose order cut keeps one state prices little whatever it is offered, and falls straight down.

What the two rankings are for #

Where the width actually goes says why the split is cheaper. Averaged over the sixty networks, the beam with $\tau_{\text{pair}} = 0.5$ and $\tau_{\text{order}} = 8$ holds 1.5, 2.4, 3.1, 3.0 and 2.4 partial orders at its first five levels; the single $\tau$ of two holds 2.3, 4.2, 5.6, 5.6 and 3.5. The split beam keeps fewer states at every level and solves as many networks, because the states it keeps are the dear prefixes the walk says are needed, and the states the single $\tau$ adds are extra pairings out of each of them, which the walk says are mostly not. With both tolerances at zero the beam holds 1.1 to 1.3 states a level; with only the pairing cut widened to eight, 1.1 to 1.4 — almost the same width, because the order cut at zero keeps one state whatever it is offered, and a worse choice of that one state.

Widen the beam where the ranking is right widened by level and found that the beam should be wide late, not early. That result is consistent with this one without being explained by it: if the order cut’s mistakes are made at the first two levels, a beam that is narrow there has already discarded the dear prefix, and widening later can only keep the best of what survived. Widening the order cut from the first level keeps the dear prefix alive at the level it is made, which is why a narrower beam does better.

The single tolerance treated the two cuts as two places to be generous. They are two rankings with different jobs and different failures. The size ranking at the pairing cut is a forward-looking heuristic — a small result means less work later — and it is usually right about the next move; it needs only enough room to break the occasional near-tie, which at seven tensors is none and at nine is a factor of one and a half. The cost-so-far ranking at the order cut is a backward-looking record, and it is wrong about exactly the move the exhaustive order is built around, an early expensive pairing that pays for itself later. It needs room for that pairing’s whole cost.

Widening the forward-looking cut while starving the backward-looking one is the worst combination, because it feeds the blind ranking options it cannot evaluate. The order the products are taken in began the subject with a greedy rule that was almost never optimal and almost never far from it; a beam built from these two rankings can be made far better than greedy or, with the tolerances the wrong way round, far worse.

Pairings priced is the right currency for comparing beams, and the wrong one for deciding whether to run one. Each pairing priced is a product of a few integer dimensions, a handful of operations; the contraction it helps choose costs the order’s whole count of multiply-adds, which on these networks runs from a few hundred to two hundred thousand, with a median of 2,610 at seven tensors and 5,436 at nine — and on networks of realistic dimensions, many orders more. The difference between 98 pairings and 150 is small next to the difference between an order 1.4 times dearer than necessary and the exhaustive one, even here, and negligible at realistic sizes. What the split buys is not the saving in search; it is that the search’s success no longer depends on choosing one number well for two jobs, which is the kind of saving a block size is a property of the machine found in a different setting — a parameter that looked like one knob turning out to be two quantities that had been tied together.

What a hundred networks do not show #

The ensembles are random graphs of small dimension, and the measured gaps are properties of them: a network family whose optimal orders never pay early — chains, for which the plan that was right at rank four priced a closed form — would show no order gap at all. The cap of sixteen bounds both cuts and is not varied; at the widest tolerances it binds, and some of the flattening at $\tau = 5$ and 8 is the cap’s. And the walk measures the need along the exhaustive tree only, which is a sufficient tolerance for keeping that tree in reach, not a necessary one: a beam can find an equally cheap order that is not the exhaustive tree, and the solved counts here would include it.

Still open: the estimate at the order cut, and a tolerance read off the walk #

The repaired ranking at the order cut. The cost-so-far ranking is blind to an expensive early pairing, and the beam ranked on cost so far plus the largest remaining group was built to see it. The prediction with a sign is that with that estimate at the order cut, the order cut’s median need falls from 2.33 to below 1.5 at seven tensors, and a beam with both tolerances at one finds the exhaustive order on at least as many networks as the best cell here, (1, 8), for fewer than 120 pairings — which would make the width the estimate’s error and not the ranking’s.

A tolerance per network. The walk measures each network’s need only with its exhaustive tree in hand. But the first level’s gap at the order cut is visible to the beam itself: the ratio of the dearest to the cheapest prefix it is offered. The prediction is that the order cut’s need is within a factor of 1.5 of the largest first-level ratio on four networks in five, so that a beam can set $\tau_{\text{order}}$ from its own first level and find as many networks as the fixed 8 for the pairings of a fixed 2.