The plan that was right at rank four

The order the products are taken in prices an expression two ways and finds a factor of two million between them. It ends with a recommendation that sounds like the end of the subject: search exhaustively when the network is small and the contraction is repeated, because a dynamic program over ten tensors is sixty thousand transitions and one evaluation of the network costs more than that.

The recommendation has a hole in it, and the hole is the word repeated. A contraction is worth searching for precisely when it will be evaluated thousands of times, and a contraction that is evaluated thousands of times is inside an iteration — which means its dimensions are moving while it runs.

At the rank it was compiled at, the plan is exactly optimal — it must be, that is what the search returned. At rank 16 it costs 1.23 times the right answer, at 64 it costs 2.19, and at 256 it costs 8.01. Nothing has gone wrong with it. It is the same tree of pairings, doing the same multiplications in the same sequence, and returning the same numbers it always did.

The dimensions that move are the whole point of the format #

It is worth being precise about what grows, because a reader who has met contraction ordering only in a matrix chain will reasonably ask why any dimension would change between one evaluation and the next.

In a tensor train the mode sizes are fixed by the problem — a grid, an alphabet, a number of states — and the ranks are not. They are the widths of the cuts between the indices, they are chosen by truncating singular values against a tolerance, and every algorithm in the format changes them as it runs. A sweep that adds a correction raises them; a rounding step lowers them. Starting from a rank-two guess and refining to a tolerance of 10⁻¹⁰ is an ordinary run, and it is a run whose ranks cross two orders of magnitude between the first sweep and the last.

So the network whose order was compiled is not the network being evaluated. The labels are the same, the topology is the same, the output is the same, and the sizes behind four of the ten labels have multiplied by sixty. That is the situation this page is about, and it has nothing to do with approximation error: every count on every figure here is exact, and every order returns the same numbers.

Five orders, each of them optimal over a band #

The first question is what the optimum is doing as the rank moves, because the answer decides whether a stale plan is a little wrong everywhere or exactly right somewhere.

Five orders are optimal somewhere on that axis and each of them is optimal over an interval: the first from rank 2 to 7, the next from 8 to 11, then 12 to 95, then 96 to 127, then 128 upwards. The optimum is a staircase, not a curve.

That is a more useful shape than a drift would have been, and it is worth saying why. If the best order moved continuously with the rank, every compiled plan would be slightly wrong all the time and the only question would be how slightly. Because it is piecewise constant, a plan compiled anywhere inside a band is exactly optimal across the whole band — which is what makes compiling one worth doing at all — and the only thing that matters is whether the run stays inside the band it was compiled in.

The bands are wide. The third of them covers ranks 12 to 95, nearly a factor of eight, and a run that starts at rank 16 and finishes at 80 never leaves it. The bands are also not equally wide, and their edges are not at round numbers, and nothing about the network announces where they are: the crossing at 95 to 96 is where forming one particular intermediate stops being worth what it saves later, and the only way to know it is there is to price both orders.

The plan is wrong in both directions, and one of them is far worse #

A stale plan is usually imagined as one that has been outgrown. Half of the measurement here is the other direction, and it is the larger half.

Compiled at rank 256 and run at rank 2, the plan costs 301 times the order rank 2 deserves. That is larger than any heuristic’s excess measured anywhere in this field, larger than the spread between the best and worst orders of the median random network, and it comes from a plan that was produced by an exhaustive search and was, at the moment it was produced, provably the best thing available.

The asymmetry has a cause. An order compiled at a high rank is one that goes to some trouble to avoid holding an object whose size is driven by the rank, and that trouble is arithmetic: extra pairings, extra intermediates, work that only pays when the thing being avoided is enormous. Run at a low rank the thing being avoided is not enormous, and the trouble is pure waste. An order compiled at a low rank makes the opposite bet — it does the obvious thing, which is cheap when the ranks are small and builds a large object when they are not — and a large object built once is a fixed penalty, not a multiplying one.

So the two mistakes are not the same size, and the practical form of that is a rule about which end to compile at if a plan must be compiled at only one. Compile low. A plan compiled at the bottom of the range costs 8.01 times at the top of it; a plan compiled at the top costs 301 times at the bottom, and 84.5 times even a fifth of the way up.

A rule computed now, against a search computed then #

Which raises the question this page exists for. A library evaluating a contraction has two things it could do: carry the plan it compiled, or run a one-line greedy rule at the dimensions in front of it. The first is an exhaustive answer to the wrong question and the second is an approximate answer to the right one.

The two curves are on the hero figure. At rank 256 the carried plan costs 8.01 times the optimum and the greedy rule — pair whichever two operands leave the smallest result, the rule the previous measurement in this field found to be the better of the two available — costs 2.92. At rank 2 the carried plan compiled at 256 costs 301 times and the same rule costs 1.11.

That is the reversal, and it is worth stating plainly because it inverts the advice the field gives everywhere else. An exhaustive search is better than a heuristic, on a fixed problem, by definition. Across a moving problem it is not, and the crossing is not at the extreme: the carried plan is behind the recomputed rule from rank 64 upwards, which is one step of the staircase past where it was compiled.

And the reverse holds inside the band, which is the honest other half. A plan compiled at rank 16 is exactly optimal at ranks 16, 32 and 64, while the greedy rule at those same ranks costs 1.23, 1.73 and 1.00. Inside its own band the compiled plan is not merely better than the rule, it is the best there is; the rule pays its median excess whether the dimensions moved or not. Neither strategy dominates, and what separates them is a quantity a library can measure — how far the dimensions have travelled since the plan was made — rather than a quantity it cannot, which is what the plan would have cost.

One network is not a measurement #

The train’s inner product is a particular network with a particular shape, and its staircase is the sharpest instance rather than the typical one. The ensemble is what says how much of this transfers.

Sixty random seven-tensor networks, each planned exhaustively at its own dimensions, then evaluated with half of its labels scaled up by a factor g — which is the crudest possible model of a run whose ranks have grown and is deliberately crude, because the point is the size of the movement rather than its shape.

The medians say nothing at any growth factor. The carried plan’s median excess is 1.0000, 1.0084, 1.0104 and 1.0064 at growth factors of 2, 4, 10 and 40 — it does not rise, and it stays inside one per cent of optimal throughout. On the median network the dimensions can move by a factor of forty and the plan compiled before they moved is still the right plan, which is the staircase again: most networks have one band covering the whole sweep.

The tails say everything, and they cross. At a doubling the carried plan’s ninetieth percentile is 1.037 and the recomputed rule’s is 1.732 — carrying wins by a wide margin, because at that distance almost nothing has left its band and the rule is paying its usual excess for no reason. At forty times the carried plan’s ninetieth percentile is 8.98 and the rule’s is 3.32. The worst cases move the same way: 1.43 against 4.48 at a doubling, and 22.2 against 7.16 at forty times.

The share of networks on which recomputing is the better choice runs 12, 21, 28 and 28 of sixty across the four growth factors — so it is not that recomputation becomes right, it is that the penalty for being wrong changes hands. Below the crossing a stale plan is wrong by a per cent and a fresh rule is wrong by a factor; above it, the other way round.

The network whose order cannot go stale #

The counterweight belongs here for the same reason it belonged to the first measurement in this field, and it is the same network.

One step of alternating least squares is a four-index tensor contracted against three factor matrices — a star, with the tensor at the centre. Planned at every combination of mode size 6, 12 and 24 with rank 2, 5, 20 and 60, and run at every combination of mode size 6, 12, 24 and 48 with rank 2, 5, 20, 60 and 120, the carried plan’s excess over the fresh optimum is 1.000000 at all two hundred and forty pairs. There is only one optimal tree, and it is optimal at every set of dimensions the star can be given.

That is a stronger statement than the one this network earned in the first measurement, where its best and worst orders were within eight per cent of each other. Being nearly indifferent to the order and having an order that never changes are different properties, and the second does not follow from the first: a network whose orders are all within a per cent could still change its argmin at every rank, and then a compiled plan would be right in a way nobody could rely on. Here the argmin does not move at all.

The reason is topology, and it is the reason the previous measurement gave for the network’s other good behaviour. A star with four arms has very few groupings, and the ranking between them is decided by which indices each grouping closes rather than by how large they are — so scaling a label scales every candidate’s cost by the same factor and leaves the ordering alone. A chain does not have that property, and the matrix chain this field opens with changes its optimal tree once across a hundredfold scaling of alternate dimensions. A ladder — which is what two trains contracted against each other are — changes it four times.

So the three networks rank the same way on this question as they did on the first one, and the ranking is not a coincidence about sizes. The shape of the network decides both how much the order is worth and how long it stays worth it, and a code that knows its expression is a star can compile once and stop thinking about it, while one that knows its expression is a ladder cannot.

What a plan is, in this field’s own vocabulary #

There is a word for an object that is computed once from the structure of a problem and reused while the numbers change, and this collection has a whole field built on it: a contraction path is a symbolic phase.

The sparse field’s version computes an elimination ordering from the graph of a matrix before any value is looked at, and reuses it across every matrix with that pattern. The order that was right last time is what happens when the reuse is pushed too far there: a pivot order computed for one member of a sequence, applied to another whose values have moved, and a backward error of 4.8·10⁻⁹ where there should have been 10⁻¹⁶.

The two are the same move and they fail differently, and the difference is worth having. A stale pivot order costs accuracy, because the numbers it was chosen against decide whether its pivots are large. A stale contraction order costs arithmetic, and nothing else — the answer is bit-for-bit what it would have been, the residual is unchanged, and no quantity computed from the output differs by anything at all. That makes it the more insidious of the two: the sparse field’s failure is visible in a backward error that every solver already computes, and this one is visible only in a clock.

It also means the repair is available at a different price. A sparse code that suspects its pivot order must refactorise to find out; a contraction code that suspects its path can price both orders from the label sets alone, in microseconds, without evaluating anything.

The measurement a library does not take, and could #

Which is the practical finding, and it is a small one that follows from everything above.

The cost model here reads only the labels and their sizes. Pricing a stored plan at the current dimensions is a walk over the tree — a handful of multiplications per node, no arrays touched — and pricing the greedy rule’s answer beside it is a few hundred more. Against an evaluation that is about to do 10⁸ multiply-adds, both are free.

So a code holding a compiled path can, at every call, compute what that path costs at today’s dimensions and what a one-line rule would cost instead, and take the smaller. It never does worse than the better of the two strategies this page compares, it needs no estimate of how far the dimensions have drifted, and it does not need the exhaustive search it cannot afford to repeat. The whole of the decision is two numbers that the code is already able to produce and does not.

What it cannot cheaply do is re-run the search: that is exponential in the number of tensors, and it is what the plan was compiled to avoid. The asymmetry is the reason the rule above is worth stating — checking a plan is cheap and making one is not, so a code should check constantly and compile rarely, which is the reverse of what a compiled path suggests.

What this does not say #

Three readings to rule out, since each of them is a plausible over-reach from the numbers above.

Not that compiled paths are a mistake. Inside its band a compiled plan is optimal, and the bands are wide — a factor of eight in rank on the widest of the five. The measurement at 301 times is a plan used five bands away from where it was made, which is a run that has changed character rather than drifted.

Not that the greedy rule is safe. Its median excess on this ensemble is what the previous measurement found it to be, its worst case on sixty networks is 4.48 at a doubling, and its worst case is not bounded by anything. It wins here by being current, not by being good.

And not that the rank is the only thing that moves. A mode size can change between calls — a grid refined, a batch resized — and the same arithmetic applies, with the same staircase and different edges. The rank is used here because it is the dimension a tensor format changes on purpose, and because it moves furthest.

What the count would be if the plan were checked #

One number is worth extracting from the ensemble because it is the one a code’s author would ask for.

Taking the smaller of the carried plan and the recomputed rule at every network and every growth factor gives a median excess of 1.000 and a ninetieth percentile of 1.04, 1.47, 2.57 and 3.32 across growth factors 2, 4, 10 and 40 — which is the better of the two curves at every point, by construction, and is strictly better than either strategy alone at every growth factor drawn. The worst case is 7.16, belonging to the recomputed rule at the largest growth, and the check cannot remove it: when both strategies are bad the smaller of the two is still bad.

That is the honest ceiling on the repair. Checking turns two strategies with different failure modes into one with the better of the two, and it does not turn either into a search.

Where else a decision outlives its inputs #

The shape is not particular to contraction, and three other places in this collection have it with different consequences.

The order that was right last time reuses a pivot order across a sequence and pays in accuracy. A factorisation kept past its date reuses a Cholesky factor across a drifting sequence and finds an optimum four members before a cliff. Where the drift lands finds that two drifts of the same relative size cost 19 iterations and 5, because what matters is not how much the matrix moved but where in the spectrum it moved to.

All three are the same sentence — an object computed from one problem, used on another — and they differ in what the staleness is measured in. There it is a norm of a difference between matrices; here it is a distance in the dimensions, and the difference matters because a dimension is a small integer a code already has. A contraction code always knows exactly how stale its plan is, which none of the three above can say, and it is the one that does nothing about it.

The fourth relative is what a rebuild is worth, which prices the other half: how expensive the recomputation is decides the schedule, and there the search costs exponentially more than the evaluation while here the check costs nothing. That asymmetry is why the recommendation above is to check constantly rather than to rebuild on a period.

Still open: what a code should do when the drift is known in advance #

An iteration that raises its ranks according to a tolerance knows, approximately, where they are going. Nothing above uses that.

The obvious construction is to compile not one plan but the staircase — every order that is optimal over some band of the range the run will cross, with the band edges stored beside them — and switch at the crossings. On this network that is five trees and four numbers, found by pricing the orders at a geometric ladder of ranks and detecting where the argmin changes, which costs five dynamic programs rather than one. Whether the edges can be found without pricing every rank between them is the interesting question, and it is a question about how the argmin of a piecewise-linear family in several variables behaves rather than about contraction at all.

What is not yet measured here is the width of a band in a direction other than the rank, and whether the bands of a network with two moving dimensions are intervals or something less convenient. A run that raises its ranks while a grid is refined moves on a plane, and the staircase is then a subdivision of that plane into regions — which may be a small number of them or may not, and the count is what decides whether a compiled staircase is a table or a search.

One line #

An evaluation order is a decision about dimensions, the dimensions move while the expression is evaluated, and past the edge of the band a plan was compiled in, a one-line rule computed now beats an exhaustive search computed then.