Contraction order — where it appears
Named by 9 essays across one field — each of them below, with the objects they name alongside it.
Also named here as tensor network — the same set of essays touches all of them, so they are one junction rather than several.
The order the products are taken in
The sparsity field's first essay says the elimination order decides the memory. This is the same sentence about arithmetic: a contraction of several tensors over shared indices has one value and many evaluation orders, and on the inner product of two trains they differ by a factor of two million.
A ceiling is not a target
Asked to hold the smallest possible intermediate, an evaluation order costs a median of 1.55 times the cheapest order's arithmetic. Asked to hold no more than that same amount, it costs 1.15. The two answers hold exactly the same number of numbers, and on one network they are 5.17 times apart in work.
The plan that was right at rank four
An evaluation order is chosen once and paid for thousands of times, and the dimensions it was chosen at are not the dimensions it runs at. Compiled at rank four and run at rank 256 it costs 8.01 times the order that rank deserves; compiled at 256 and run at 2 it costs 301 times. A one-line rule recomputed on arrival costs 2.92 and 1.11.
The search that got worse as it widened
Keeping two candidate orders instead of one removes a third of the cheapest-product rule's excess, and by eight it has removed all of it — the two greedy rules this field separated become the same rule. On twenty-four of sixty networks a wider search returns a dearer order than a narrower one, and it is the better rule that it more often makes worse.
A beam ranked on what remains
A beam over contraction orders ranked on cost so far returns a dearer order when it is widened on 24 of 60 networks. Rank it on cost so far plus the largest group still to be paired — a lower bound on what remains, and free — and that falls to 12, eleven of them from the original 24. Rank it on a stronger estimate that is not a bound and the count stays at 23, but only 10 are the same networks: the anomaly has moved, not gone. At nine tensors, where the unranked beam's median at width 8 was worse than at width 1, both rankings make widening pay again.
Widen the beam where the ranking is right
A beam that is wide at its first pairings and narrow at its last looks like the right shape, since the early commitments are the damaging ones. Measured, it is worse than no beam: at nine tensors a width of 16, 8, 4, 2 and then 1 prices 742 pairings and has a median of 1.263 against width 1's 1.062 for 120. The reverse shape — width 1 early, doubling to 16 at the end — prices 78 pairings on seven tensors and finds the exhaustive order on 37 of 60 networks, against 30 for a constant width of 4 at 161. A beam should be wide where cost so far is nearly the whole cost.
A near-tie is a factor of four
A beam over contraction orders spends its width by level — wide late was the best schedule, finding the exhaustive order on 37 of 60 seven-tensor networks for 78 pairings priced. The alternative was to widen only where the ranking is a near-tie. Measured, near-ties buy nothing: keeping every candidate within a quarter of the best changes nothing at all, because the pairing the exhaustive order wants is almost never tied with the ranking's first choice. It sits a factor of two to four further down. Widen to keep everything within a factor of three and the beam finds the exhaustive order on 46 networks for 150 pairings, and at nine tensors has a median of 1.007 where every schedule tried before had 1.056 or worse below 1,380 pairings.
The prefix sits further down
A beam over contraction orders cuts twice at every level — once among the pairings out of each partial order, ranked by the size of their result, and once among the partial orders that survive, ranked by their cost so far — and one tolerance had been widening both. Measured separately, the exhaustive order's pairing is the size ranking's first choice on 34 of 60 seven-tensor networks; its prefix sits a median factor of 2.3 above the cheapest prefix on offer, and needs more room than its pairing on 49. So the width belongs at the order cut, as predicted. What was not predicted is the other half: widening the pairing cut alone is worse than not widening at all, because it hands the cost-so-far ranking more chances to choose a cheap-first prefix.
The need is set further on
A beam over contraction orders needs a wide tolerance at its partial-order cut, a median factor of 2.33 at seven tensors, and the beam was predicted to see that need in its own first level — the ratio of the dearest prefix it is offered to the cheapest, within a factor of 1.5 on four networks in five. The best such ratio is within 1.5 on 32 of 60, and none ranks the networks better than chance. A beam that sets its tolerance from its first level lands on the line the fixed tolerances draw. The ratio is exact where the need is set at the first level, and 35 of 60 networks set it later.
Named alongside it
The objects these essays reach for when they reach for this one.
Tensor networkFlop countHeuristicBeam searchArithmetic costSymbolic phaseAdmissible estimateElimination orderGreedy algorithmMemory hierarchyTensor trainAlternating least squares