A ceiling is not a target

The order the products are taken in ends one of its sections with a sentence that is true and is not a decision procedure: the best order is not a well-formed phrase until the resource has been named. It prices two dynamic programs over the same subsets, one minimising arithmetic and one minimising the largest intermediate held, and finds them disagreeing on three networks in a hundred and twenty — three per cent memory for nine per cent arithmetic on the worst of them.

A code with a fixed amount of memory does not have two objectives. It has one objective and one limit, and the difference between those two sentences turns out to be most of the arithmetic.

That network’s cheapest order holds 9,504 numbers at its widest. The leanest order any evaluation of it can manage holds 2,106 — a reduction of 4.51 times. Reaching 2,106 by asking for the smallest possible peak costs 1.649 times the cheapest order’s arithmetic. Reaching the identical 2,106 by requiring it and minimising arithmetic underneath costs 1.020.

Same memory. Thirty-two times less arithmetic paid for it.

Where the difference comes from #

The two dynamic programs are one line apart, and the line is what they carry forward.

Minimising the peak makes every pairing a decision about the largest object held so far, and carries that number up the tree. Once a subtree has been chosen for the smallest peak it can manage, nothing about the arithmetic it spent getting there enters any later comparison — so an order that pays ten times the necessary work to shave one number off an intermediate is preferred, and the preference compounds at every level.

Requiring the peak instead makes it a filter. A pairing whose result exceeds the ceiling is removed from consideration and the remaining ones are ranked on arithmetic, which is the quantity actually being optimised. Under a ceiling of 2,106 the network above has a great many legal orders, they differ from each other in arithmetic by a factor of 30, and one dynamic program looks at that axis and the other does not.

This is the same distinction a constrained optimisation makes between a penalty and a bound, and the same one a constraint is a weight at infinity measures in the least-squares field: there the constraint is approached by weighting it more and more heavily, and the approximation error is 1/τ². Here there is no approximation — the filter is exact, the ceiling is met exactly, and what is being compared is two different problems that happen to share an answer in one of their two quantities.

Most networks have no memory decision at all #

Before pricing the choice it is worth establishing how often it exists, and the answer is the part of this page most likely to change what somebody does.

Over two hundred and forty networks across four shapes — seven to ten tensors, eight to twelve labels, dimensions up to twenty — the cheapest order’s largest intermediate is an input tensor on 122 of them. Nothing reorders the data: if a network’s biggest object is something it was handed, no evaluation order can make the peak smaller, and the cheapest order is automatically the leanest one.

On the other 118 the peak is an intermediate, so ordering could in principle move it. It does not, on 98 of them: the cheapest order already holds the least any order could. That leaves twenty of two hundred and forty — eight per cent — on which a memory decision exists at all.

So the finding is narrow and it is worth being explicit about that. On ninety-two per cent of these networks a code can ignore memory entirely, take the cheapest order and hold the least any order could. On the remaining eight per cent it matters, and where it matters it is worth up to a factor of five.

The staircase has one step #

The shape of the curve is the second surprise, and it is the one that decides how a code should search.

An exchange rate between two resources is usually a curve: pay a little more arithmetic, hold a little less, and keep going until the trade stops being worth it. That is what fill against growth looks like in the sparse field, where a threshold parameter walks continuously between two failure modes, and it is what a block size against a fast memory looks like in this one.

Here it is a staircase with exactly one step. On the hero’s network the cost is exactly the unconstrained cheapest at every ceiling from 9,504 down to 5,941, rises once to 1.020, and then does not move again all the way to the floor at 2,106. Every one of the twenty networks in the ensemble with a memory decision has precisely two cost levels — a free stretch, one rise, and nothing after it — and the rise sits between 0.62 and 0.95 of the cheapest order’s own peak, at 0.75 in the median.

The reason is that the constraint binds at a pairing rather than at a margin. An order either forms a particular intermediate or it does not, and the sizes of the objects a network can form are a sparse set of numbers rather than a continuum — so lowering the ceiling changes nothing until it crosses one of them, at which point one order becomes illegal and the next-cheapest legal one takes over. Between crossings the answer is constant, which is the same reason the optimal order is a staircase in the dimensions rather than a curve.

The practical consequence is that a code does not need to sweep the ceiling. There is one number that matters — the memory it actually has — and the answer at that number is the answer; measuring the exchange rate around it produces a flat line and a false impression that the trade is smooth.

It also means the first slice of the reduction is free everywhere. Across the twenty, a quarter of the cheapest order’s peak can be given up at no cost at all on the median network, and a third of it on the most generous — so a code with a little less memory than the cheapest order wants has nothing to decide, and one with rather less pays a single fixed price for everything below that point.

The floor, which is the data #

The left edge of the hero figure is shaded: below 2,106 numbers no evaluation order of that network is feasible at all. Two different quantities meet at that edge and they are worth separating, because one of them is an ordering question and the other is not.

The floor is the leanest peak any order achieves, which is what the second dynamic program computes. Underneath it sits the largest input tensor, which nothing reorders — a contraction holds its own data whatever order it is evaluated in. The input is a lower bound on the floor and is usually not equal to it: on eleven of the twenty networks the leanest achievable peak is strictly larger than the largest input, so part of the floor is a fact about the expression and part of it is a fact about the data.

The distinction matters because it decides what to do when nothing fits. A contraction whose largest input does not fit is not a contraction that needs a better path; it is one that needs its inputs split, which is a change to the expression rather than to the order it is evaluated in — the move an index that is a pair makes when it declines to assemble a matrix, and the move a tensor format makes by never forming the object it represents.

And a contraction whose inputs fit while no order fits is a different case with a different repair: the expression is fine and one of its intermediates is too wide, so the answer is to evaluate the contraction in slices over one of its indices, which multiplies the arithmetic rather than changing the expression.

So a code facing a memory limit has four regimes and they want four different responses. Above the cheapest order’s own peak, do nothing. Between that and the leanest peak any order achieves, filter and re-optimise, which costs the same dynamic program with one extra test in it. Between that and the largest input, slice. And below the largest input, stop reordering and restructure.

What the ceiling costs across the twenty #

One network is an anecdote and the hero is the most extreme of the twenty, which is worth saying plainly before the general number.

Minimising the peak costs a median of 1.549 times the cheapest order’s arithmetic, with a worst case of 5.171. Requiring it costs a median of 1.146, worst case 3.065. The gap between the two on one network reaches 5.167 times, and it is never negative — requiring a bound cannot be dearer than minimising under it, which is a fact about the two search spaces rather than a measurement, and is asserted rather than hoped for.

The smaller sample is instructive in the way this field’s samples usually are. The two medians move by a tenth and the widest gap moves by a factor of five, so the median is settled by ten networks and the tail is not — and a reader who took the ten-network figure at face value would conclude that the two questions have the same answer, because on six of those ten they do.

That is the honest summary of the whole page. On most networks there is no memory decision; on most of those that have one, the two ways of asking for it agree; and on the remainder the difference is a factor. A finding that is nothing on ninety-five per cent of cases and a factor of five on the rest is not a rule about contraction, it is a rule about how to ask, and asking correctly costs the same dynamic program either way.

The rules that decide this were chosen on the other resource #

There is a gap between everything above and anything a library does, and it is the same gap the first measurement in this field opened: no library runs a dynamic program. Both of the orders this page compares are exhaustive, and what ships is one of two greedy rules — pair whichever two operands are cheapest to multiply, or pair whichever two leave the smallest result.

Those two rules were separated on arithmetic, where their median excesses are 1.47 and 1.003. Neither description mentions memory, and both decide it.

The smallest-result rule holds more than the cheapest order does on 25 of 240 networks, with a worst case of 4.80. The cheapest-product rule holds more on 120 of 240 — half of them — with a ninetieth percentile of 6.86 and a worst case of 53.2.

So the rule that is forty-seven per cent behind on arithmetic is fifty-three times behind on memory, and the gap between the two rules is an order of magnitude wider on the resource neither of them was chosen for. That is not a coincidence: pairing by cheapest product minimises the cost of the step, which is the size of the union of the two operands’ open labels, and is indifferent to the size of what the step leaves behind. Leaving a large object behind is precisely what a peak is.

The practical reading is a small correction to the previous measurement’s recommendation. It concluded that the smallest-result rule is the better of the two on the evidence of arithmetic, and it is — by a factor of a hundred and forty in the deficit. On memory it is better by a factor of five in the worst case and by a factor of nearly five in how often it is wrong at all, and the two findings point the same way for different reasons. A rule chosen for one resource happening to be right about the other is luck, and it is worth checking rather than assuming: the rule that lost is the one that loses catastrophically here, and if the ranking had come out the other way a library would be shipping a rule that holds fifty times what it needs to.

And on the twenty networks with a memory decision in them, the smallest-result rule already reaches the leanest achievable peak on thirteen, is within 1.6 times on five, and is 4.10 and 3.57 times off on the other two. A code that runs it and then finds it does not fit has one thing worth trying before any of the machinery above — the cheapest order under a filter — and on thirteen of twenty networks the rule was already holding the least there was to hold.

Where the step sits, and why a code should not look for it #

The staircase has one step and it is worth knowing where, because a code with a little room to spare would like to know whether spending it buys anything.

Across the twenty networks the first ceiling that costs any arithmetic at all sits between 0.62 and 0.95 of the cheapest order’s own peak, at 0.75 in the median and above 0.85 on eight of them. Every ceiling above that point is free and every ceiling below it costs the same, which is the two-level staircase again, said from the reader’s end.

So the number a code would want — how much memory can be given up for nothing? — has an answer, it is about a quarter of what the cheapest order holds, and it does not vary much. What varies is what the rest costs: 1.001 to 3.065 at the binding ceiling across the twenty, with a median of 1.15. The first quarter is free on every network drawn and the last is a coin toss between nothing and a factor of three.

Why this is not the two-objective finding again #

It would be easy to read this as a restatement of the disagreement the first measurement in this field found between cost and peak, and it is a different claim about a different pair of objects.

That measurement compares two answers: the cheapest order holds more than the leanest one, so the best order depends on which resource is being counted. This one compares two questions about the same resource, both of which name memory, and finds that one of them buys memory at thirty times the price of the other while delivering the identical amount.

The first is a trade and has no wrong side. The second has a wrong side, and the wrong side is the formulation almost every description of the problem reaches for, because minimise the peak is the sentence that comes to mind when memory is short. It is also the formulation a library exposes when it offers a choice of objective, which is the practical form of the finding: an interface with two objectives in it cannot express a ceiling, and the ceiling is what a machine has.

What the filter costs to add #

A last piece of arithmetic, because the whole recommendation rests on it.

The unconstrained search is a dynamic program over the 2^t subsets of the network’s tensors, with 3^t transitions between them — 2,187 for seven tensors and about sixty thousand for ten. The constrained search is the same program with one extra comparison per state: the result of this subset, against the ceiling. It visits the same states, it makes the same transitions, and it answers a different question.

So the choice this page is about is free. There is no version of this in which a code decides not to impose the ceiling correctly because imposing it correctly is expensive, which is the usual shape of a finding in this field and is not the shape of this one. The two searches cost the same and one of them is wrong.

The filter also answers the feasibility question in the same pass. If no order fits, the full subset’s cost comes back infinite, and it does so having proved it rather than having failed to find anything — which is a stronger statement than a greedy rule can make. A greedy rule that exceeds the ceiling has found one order that does not fit; the dynamic program that comes back infeasible has established that none does, and a code facing that answer knows to restructure rather than to try again with a different rule.

The refusals #

The claim worth breaking is the one that sounds like common sense: a contraction that has to fit in a given amount of memory should be evaluated in the order that holds the smallest intermediate. It is not wrong about feasibility — the leanest order fits whenever anything fits — and it is wrong about everything else. The assertion that the two ways of asking cost the same arithmetic is fed the twenty networks and required to fail, at a median of 1.549 against 1.146 and a worst single gap of 5.167.

The second refusal covers the reading in the other direction, which is that a ceiling is expensive. Fed a network where the leanest order costs no more than the cheapest one, the claim that memory is always paid for in arithmetic has to fail: on nine of the twenty networks with a memory decision, the whole reduction is free.

And the third is a control on the model rather than on the finding. A constrained order that reports a peak above its own ceiling would make every number on this page meaningless, so the search’s answer is checked against the ceiling it was given, on every network, every time it runs.

What is not measured here #

Three limits, each of which would change the numbers rather than the shape.

The peak is counted in numbers, not in what a machine holds. A real evaluation holds its two operands and its result at once, and a cache holds tiles of them; the model here counts the largest single intermediate, which is the quantity a contraction path optimiser exposes and not the quantity a machine runs out of. The three-object version would move every number on this page and none of the orderings, because scaling a peak by a constant does not change which orders are legal at a given ceiling — unless the constant differs between orders, which it does when the operands differ in size, and that is the case this page does not cover.

The ensembles are small networks. Seven to ten tensors is what a dynamic program can price exhaustively, which is the whole reason this field can measure heuristics against answers rather than against each other. The networks where memory is genuinely the binding constraint have hundreds of tensors and are exactly the ones where no optimum is available, so the eight per cent figure above is a statement about small networks and cannot be extrapolated.

And the filter is exact here. A constrained search is only as good as its ability to prove a pairing illegal, which is trivial when every dimension is known before evaluation. It is not trivial when the sizes depend on data — a sparse intermediate whose fill is not known until it is formed — and that is the situation the sparse field’s whole symbolic phase exists to handle, where the prediction is a bound rather than a count.

The same distinction, three fields over #

A limit that is treated as an objective is not particular to contraction, and this collection has the pattern twice more with the same arithmetic behind it.

A threshold between fill and growth is a sparse factorisation choosing pivots under a bound on how far from the best pivot it will go, rather than minimising either quantity — and the whole content of the threshold is that the bound is not an objective. The knob that moved two things is the hierarchical field’s version: decide how many digits are needed, divide by the condition number, compress to that. A requirement, then an optimisation underneath it.

Where the format starts paying is the counter-example worth naming, since it is an honest two-objective comparison: a hierarchical solve against a dense one, both costs real, and a crossover that moves with the accuracy. Nothing there is a ceiling and nothing there should be phrased as one.

The distinction generalises into one sentence, and it is the reason this page exists rather than being a remark. A machine’s memory is a constraint; a code’s arithmetic is an objective; and an interface that offers a choice of objective cannot express the first. Every library that lets a caller minimise either cost or peak is offering two objectives, and a caller who needs a ceiling reaches for the wrong one because it is the only one that mentions memory.

Still open: the ceiling that moves during the run #

Everything above holds the ceiling fixed, which is what a machine’s memory is and not what a running code’s free memory is.

A contraction inside an iteration shares its machine with everything else the iteration holds, so the memory available to it is smaller when the ranks are large — which is exactly when the intermediates are large too. The ceiling and the demand move together and in the same direction, and whether the feasible set stays non-empty along a run is a question neither this page nor the one before it asks. The construction that would answer it is a sweep over the plane of rank against free memory, with the cheapest feasible order at each point, and the interesting quantity is the shape of the region where no order fits at all.

There is also a question about what a code should do when the answer is no order fits. Splitting an input is one response and it changes the expression; evaluating the contraction in slices over one of its output indices is another, and it multiplies the arithmetic by a factor that depends on which index is sliced. Which index to slice is a third ordering problem of the same kind, over the same label sets, and it is not measured anywhere in this field.

One line #

A memory limit is a constraint and not an objective, and a search that minimises the peak instead of bounding it pays up to five times the arithmetic for exactly the same amount of memory.