Two greedy contraction rules against the exhaustive optimum, over 60 random networks
At its defaults it draws two greedy contraction rules against the exhaustive optimum, over 60 random networks. Each curve is one rule's excess over the exhaustive answer, sorted, so the horizontal axis is the share of networks at or below that excess. Pairing whichever two operands are cheapest to multiply is optimal on 1.7 per cent of them, has a median excess of 1.446 and a worst case of 25.4. Pairing whichever two leave the smallest result — the rule the libraries ship — is optimal on 50.0 per cent with a median of 1.0026. The upper curve is the spread between each network's own best and worst orders, median 607, which is the size of the thing being searched for.
heuristic-excess is one function in lib/figures/contract.js —
contraction order — one expression, one value, and orders that differ by two million. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
Each curve is one rule's excess over the exhaustive answer, sorted, so the horizontal axis is the share of networks at or below that excess. Pairing whichever two operands are cheapest to multiply is optimal on 1.7 per cent of them, has a median excess of 1.446 and a worst case of 25.4. Pairing whichever two leave the smallest result — the rule the libraries ship — is optimal on 50.0 per cent with a median of 1.0026. The upper curve is the spread between each network's own best and worst orders, median 607, which is the size of the thing being searched for.
show: "guided"
The arguments are the ones A beam ranked on what remains passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
60 random 7-tensor networks, each contracted by a beam that pairs by smallest result and keeps the width's best partial orders, ranked three ways: on cost so far, on cost so far plus the largest group still to be paired, and on cost so far plus the cheapest pairing that closes each index still open. Solid lines are medians and dashed lines ninetieth percentiles of the cost over the exhaustive order. At width 8 the medians are 1.0000, 1.0000, 1.0000 and the ninetieth percentiles 1.129, 1.051, 1.107. A wider beam returns a dearer order than a narrower one on 24, 12, 23 networks respectively.
show: "anomaly", by: "size"
The arguments are the ones A beam ranked on what remains passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Each curve is one network, drawn against how many partial orders the search keeps at each pairing, under the rule that pairs by smallest result. Every curve is at or above 1, since no beam beats the exhaustive order, and every one of them rises somewhere: keeping more candidates returned a dearer order than keeping fewer, by up to 3.49 times in a single step of the width. The cause is that the beam is ranked on cost so far, so a state whose prefix is dear and whose completion is cheap is discarded once there are enough cheap prefixes to fill the beam — and the better the rule, the more often the discarded state was the one that would have finished best.
show: "guided-sets"
The arguments are the ones A beam ranked on what remains passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For 60 random 7-tensor networks, the networks on which some wider beam returns a dearer order than a narrower one, for a beam ranked on cost so far and on three estimates of what remains. Each bar splits the anomalous networks into those the unranked beam was also anomalous on and those it was not, and the hollow segment counts the unranked beam's anomalous networks that the ranking repaired. cost so far: 24, of which 24 shared and 0 new, 0 repaired; + largest group: 12, of which 11 shared and 1 new, 13 repaired; + half the groups: 12, of which 11 shared and 1 new, 13 repaired; + closing pairings: 23, of which 10 shared and 13 new, 14 repaired.
show: "guided", t: 9
The arguments are the ones A beam ranked on what remains passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
40 random 9-tensor networks, each contracted by a beam that pairs by smallest result and keeps the width's best partial orders, ranked three ways: on cost so far, on cost so far plus the largest group still to be paired, and on cost so far plus the cheapest pairing that closes each index still open. Solid lines are medians and dashed lines ninetieth percentiles of the cost over the exhaustive order. At width 8 the medians are 1.0656, 1.0101, 1.0030 and the ninetieth percentiles 1.892, 1.328, 1.356. A wider beam returns a dearer order than a narrower one on 27, 22, 21 networks respectively.
show: "guided-cost"
The arguments are the ones A beam ranked on what remains passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For 60 random 7-tensor networks and beams of widths 1 to 8, the ninetieth percentile of the cost over the exhaustive order against the mean number of pairings the search priced, counting the pairings an estimate prices to rank the beam, on a logarithmic horizontal axis. At width 8: cost so far 1.129 for 301 pairings, + largest group 1.051 for 301 pairings, + closing pairings 1.107 for 1505 pairings. The exhaustive dynamic program makes 2187 transitions, drawn as the vertical line.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
144 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
no beam beats the exhaustive order, seed 1 — checked 60 times
the lower envelope of these orders is the optimum at rank 2 — checked 15 times
no carried order beats the order chosen at rank 2 — checked 8 times
no beam of width 1 beats the exhaustive order — checked 6 times
a beam keeps at least one partial order at every level
a cap of at least one on the width
a growth factor the ensemble is drawn at
a median, a ninetieth percentile or a worst case
a median, a ninetieth percentile, or the share of networks whose optimum was missed
a network in this ensemble whose cheapest order is not already its leanest
a number of networks per shape
a number of networks to price
a rank the train network is planned at
a reading of the ordering measurement this generator draws
a tie tolerance of zero or more
a tighter ceiling never costs less arithmetic
a train the network is built for
a wider beam is not a better beam, and it is the better rule that it most often makes worse
a wider beam returns a dearer order somewhere under the cost rule
a wider beam returns a dearer order somewhere under the size rule
and at the widest beam the two rules have become the same rule
and holds more than the optimum far more often
and is not optimal across the whole range
and minimising the peak never costs less than requiring it
and no beam of any width beats the exhaustive order
and no ceiling makes the arithmetic cheaper than having none
and no width makes the beam exhaustive
and pairing by smallest result is the better of the two
and the median network pays a clear premium for asking the wrong question
and the orders are far apart where they differ
and the rise is not a rounding
and the tail is not
and the widest beam drawn is still a fraction of the exhaustive program's transitions
enough networks to say anything
enough networks with a memory decision
every order holds something
no close beam beats the exhaustive order
no heuristic beats the exhaustive order
no max beam beats the exhaustive order
no none beam beats the exhaustive order
nothing beats each network's own best order
one extra candidate removes a third or more of the cheapest-product rule's excess
one of the two greedy rules
ranked on cost so far, or with the largest group added
requiring a ceiling is never dearer than minimising under it
seven tensors, or nine, which is as large as the exhaustive order is priced
several ceilings are feasible
somewhere in the sweep the one-line rule computed now beats the exhaustive order computed then
the admissible ranking lightens the tail at the widest beam
the constrained answer respects the ceiling
the median network's carried order is within five per cent of its own optimum
the optimal order changes several times across the rank axis
the plan is exactly optimal at the rank it was compiled at
the rule that loses on arithmetic loses by far more on memory
the width costs work monotonically
this network has a memory decision to make at all
which is the gap the width is closing
wide-early finds the optimum no more often than width one
wide-late prices fewer pairings than a constant four
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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.
Where the flop count stopped predicting the timeA 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.
Where the flop count stopped predicting the timeA 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.
Where the flop count stopped predicting the timeThe 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.
Where the flop count stopped predicting the timeThe 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.
Where the flop count stopped predicting the timeThe 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.
Where the flop count stopped predicting the timeWiden 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.