The need is set further on

The prefix sits further down split a beam search’s tolerance in two. A beam over tensor-contraction orders keeps a few partial orders and extends each by every pairing it could make next, and it cuts twice at every level: among the pairings out of each partial order, ranked by the size of their result, and among the partial orders those pairings produce, ranked by their cost so far. Measuring each cut separately on the exhaustive order’s own path showed which one loses it. The pairing cut barely does — the exhaustive pairing is the size ranking’s first choice on 34 of 60 seven-tensor networks. The order cut does: the exhaustive prefix sits a median factor of 2.33 above the cheapest prefix on offer, and needs more room than its pairing on 49 of the 60.

That essay measured the need by walking the exhaustive tree, which a beam does not have. Its last section asked whether a beam could see the need coming anyway:

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.

It cannot, and the reason is not a defect in the ratio. On the networks where the need is set at the first level, one reading of the ratio gets it exactly. On most networks the need is set further on.

Three readings of the offer #

The networks are the earlier ones: sixty random networks of seven tensors and forty of nine, eight labels, every one solved exhaustively so the optimal order and its cost are known. The beam is the earlier one with its pairing tolerance at one — the setting the earlier essay’s best cell used — and its cap of sixteen candidates at each cut.

“The prefixes it is offered” at the first level can be read three ways, and every one is computable before the beam takes a step, from nothing but the network:

• the kept pairings’ ratio — among the first pairings that survive the pairing cut, the dearest step over the cheapest. These are the prefixes the order cut is literally offered.
• dearest kept over cheapest of all — the dearest surviving step over the cheapest step among every pairing, including the cheap ones the size ranking cut. This is the ratio the walk’s need is defined against at the first level.
• the ratio over all pairings — dearest over cheapest among every first pairing, whether the pairing cut kept it or not.

For each network each reading is set beside the need — the largest factor, over the walk down the exhaustive tree, by which the exhaustive prefix sits above the cheapest prefix one pairing on — and then used as $1 + \tau_{\text{order}}$ for a beam on that network.

The offer and the need #

The figure at the top of the page is the result. The violet points, the ratio the order cut is literally offered, lie along the bottom: on 26 of the 60 networks the pairings that survive the pairing cut all cost exactly the same, the ratio is one, and those networks have a median need of 2.81. The ratio is within 1.5 of the need on 24 networks of 60, and its rank correlation with the need is −0.13. It is not a weak signal; it is no signal.

The blue points are more interesting. Eighteen of them sit exactly on the diagonal, and the rest scatter on both sides of it, from three hundredths of the need to twenty times it. The reading is within 1.5 on 32 of 60 and its rank correlation is 0.13. The third reading, over every first pairing, is not drawn: it runs from 36 to 6,195 on networks whose need is two or three, a median of 132 times the need, and lands within 1.5 on none.

Why the first reading is so often one is a matter of counting. A seven-tensor network offers 21 first pairings. The pairing cut at a tolerance of one keeps a median of two of them, never more than eight, because the size ranking it uses is sharp at the first level: a few pairings produce small results and the rest produce results several times larger. Two pairings with small results are often two pairings of the same shape, and two pairings of the same shape cost the same. So the order cut is usually offered a near-tie at the first level, and a near-tie says nothing about a gap. Meanwhile on 20 of the 60 networks the cheapest first pairing of all is one the size ranking cuts, which is why the second reading — which looks past the cut to that cheapest pairing — does better, and why the walk’s need, which looks past it too, is larger than anything the order cut is literally shown.

At nine tensors every count falls: 11, 18 and none of 40, with rank correlations of 0.16, 0.04 and 0.33 — the last because a ratio of hundreds still orders the extreme networks roughly, while being no use as a tolerance. Four in five was 48 of 60 and 32 of 40. The nearest any reading comes is two-thirds of that.

Exact at the first level, silent after it #

The eighteen exact points say what the reading measures. At the first level the walk’s need is the exhaustive pairing’s step over the cheapest step among every pairing. The second reading is the dearest surviving step over the same cheapest step. The two are equal precisely when the exhaustive order begins with the dearest pairing the size ranking keeps, and the need is then set at that first level — which is the earlier essay’s “dear-first prefix” in its purest form.

Of the 25 seven-tensor networks whose need is set at the first level, the reading is exact on 18 and within 1.5 on 19. Of the 35 whose need is set later — 18 at the second level, 12 at the third, 4 at the fourth and one at the fifth — it is within 1.5 on 13, and those thirteen are coincidences: a first-level ratio that happens to match a gap that opens two or three levels down. At nine tensors the split is the same: 12 exact of the 16 set at the first level, and within 1.5 on 5 of the 24 set later.

Nor are the later gaps the small ones, which would have rescued the prediction in practice if not in letter. At seven tensors the median need is 2.50 among the networks that set it at the first level and 2.50 among those that set it at the second; it falls to 1.87 at the third and 1.45 at the fourth. At nine tensors the second level’s median is the largest of all, 4.76 against 3.50 at the first. A beam that read its first level correctly and trusted it would be blind to the widest gaps on the larger networks.

So the prediction asked the first level for something it can only contain on a minority of networks. The earlier essay found the order cut’s largest need “an early expense”, at the first or second level on two networks in three, and read that as an invitation to look early. The first and second levels are not the same place for a beam. At the first level it holds the empty prefix and every pairing it could make; at the second it holds whatever survived the first cut, and the gap that opens there is between prefixes that did not exist when the first level’s ratio was read.

The network drawn is the extreme case among those whose kept ratio is one. Its exhaustive order begins with a pairing 1.78 times the cheapest; the kept pairings all cost the same; the dearest kept over the cheapest of all is 1.67, within a factor of 1.07 of the first level’s own gap. Then at the second level the exhaustive prefix is 7.36 times the cheapest one pairing on, because the order that will turn out best makes its expensive move second, and no ratio read before that move is offered could have said so.

A tolerance that lands on the line #

The second half of the prediction is about what a beam gains. Set $\tau_{\text{order}}$ from each reading, network by network, and compare with the fixed tolerances the earlier essay’s grid already priced.

The fixed tolerances draw a line: from 21 networks for 62 pairings at $\tau_{\text{order}} = 0$, through 33 for 103 at one and 43 for 117 at two, to 51 for 136 at eight. The line is steep in the middle and flat at the end: from one to two it gains ten networks for fourteen more pairings a network, from three to eight five networks for twelve. A rule that knew each network’s need would sit well above that line, buying the steep part’s networks without paying for the flat part’s width on networks that never needed it. Each reading lands on that line or close to it. The kept ratio solves 32 for 102 pairings, which is the fixed tolerance of one — not surprising, since on 26 networks it is the fixed tolerance of zero and on the rest a small one. The second reading solves 37 for 119, a little below the fixed two’s 43 for 117. The third solves 51 for 140, the fixed eight’s count at a price slightly above the fixed eight’s, because a tolerance of a hundred is no tolerance: it keeps everything the cap allows, and the ring that marks the cap alone sits on the same point.

At nine tensors the kept ratio does slightly better than the line, 15 networks for 315 pairings where the fixed tolerances pass through 14 for 345 — two or three networks above the line at that price, the only gain any reading makes. The prediction’s target was the fixed eight’s 25 networks for the fixed two’s 421 pairings. No reading comes near it at either size — widen the beam where the ranking is right found the same about widths shaped in advance, which cost more than they bought — and the one that matches the fixed eight’s count, at seven tensors and at nine, pays the fixed eight’s price or more to do it.

That is the sense in which a tolerance read off the first level is a fixed tolerance in disguise. A reading that cannot rank the networks by their need cannot spend width where it is needed; it spends it according to something else, and the something else here is how alike the first pairings’ costs are, which is roughly how alike the network’s tensors are. The beam then buys its networks at the going rate.

What a beam can know, and when #

The earlier essays found three things about this beam that this one leaves standing. The pairing cut and the order cut need different tolerances, and the order cut needs the wider one (the prefix sits further down). A near-tie is the wrong model of the ranking’s uncertainty; the uncertainty is a factor of two or more (a near-tie is a factor of four). And ranking on an estimate of what remains helps a beam see the cost an early pairing imposes later (a beam ranked on what remains).

What this one adds is a limit on adapting the tolerance from inside the run. The order cut’s need is a property of where the exhaustive prefix sits in the ranking, and the exhaustive prefix is what the beam is looking for. A ratio read off the offer measures the spread of the offer, and the spread and the position coincide only when the answer happens to sit at the spread’s edge at the very first level. Past that, the information arrives at the level where the gap opens, which is the level at which the beam has already decided what to keep. A tolerance that adapts per level runs into the same wall from the other side. Read at each level as the dearest kept prefix over the cheapest prefix of all, it is by construction at least as wide as everything the pairing cut kept, so it keeps all of it, and the beam is the cap alone; read as the kept prefixes’ own spread, it is the first reading again, one level down. Either way the gap of 7.36 on the network drawn would be crossed only by keeping a prefix 7.36 times the cheapest, and the cap of sixteen, which already decides the fixed eight’s results, would decide that one too.

That points to the cap rather than the tolerance as the thing a beam on these networks is short of. At a fixed tolerance of eight the cap binds: with $\tau_{\text{order}}$ unbounded the beam solves exactly as many networks at seven tensors and one more at nine. The search that got worse as it widened found a beam could lose networks by widening, and the order the products are taken in priced what the exhaustive search costs, and a ceiling is not a target showed what happens when one limit is mistaken for the objective; between them sits the question of how many partial orders a beam must hold, which the cap answers with a number nobody has measured.

What a hundred networks do not show #

The networks are random, with eight labels and tensors of similar order; on structured networks — a chain, a grid, a tree of tensors from a physical model — the first pairings’ costs differ much more, and the kept ratio might carry more information than it does here. The pairing tolerance is held at one; at zero the kept pairings are fewer and the kept ratio is one more often, and at two the second reading’s numerator moves. And the need is defined against the cheapest prefix one pairing on, over every pairing, including ones the pairing cut removes; a need defined against only what the beam is offered would be smaller, and would make the order cut look less hungry than it is.

Still open: a per-level tolerance, the cap, and the estimate at the order cut #

Two cheap runs as a diagnosis. A beam cannot see its need, but it can see whether it matters: run it at $\tau_{\text{order}} = 0$ and at one, and compare their costs. The prediction with a sign is that on the networks where the two disagree the need exceeds 2 on at least four in five, and that a beam which widens to the fixed eight only on those networks solves at least 48 of the sixty seven-tensor networks for fewer pairings than the fixed three’s 124.

The cap as the parameter. The prediction is that with $\tau_{\text{order}}$ unbounded, raising the cap from 16 to 32 solves at least five more seven-tensor networks than the fixed eight does now, and that the excess of the networks left unsolved falls below 1.05 at the median — so that past a tolerance of three, a beam’s results on these networks are set by how many partial orders it may keep and not by which it prefers.

The estimate at the order cut, still. The earlier essay’s first question is unanswered: ranking partial orders by cost so far plus the largest remaining group. The prediction stands as it was made — the order cut’s median need falls below 1.5 at seven tensors with that estimate — and this essay adds a reason to expect it: the gaps that open at the second and third levels are expensive moves deferred, which an estimate of the cost remaining is built to see.