Flat in the budget, and not

Two savings on the same operation, swept over the same dial, with different shapes.

The compound walk is 11.0 at zero errors, 11.0 at one, and 11.0 at two.

The interval enumeration is 98.1, 78.2, and 104.6.

One flat, one not, and the shapes are the mechanisms.

Why one is flat #

The compound walk’s saving is σ ranks becoming one descent. That is a property of the alphabet: at σ = 20 with a balanced tree of depth five, the loop’s smaller-count costs about a hundred and ten ranks and the walk’s costs ten.

The error budget does not change the alphabet, so it does not change the ratio. A search at two errors performs many more extensions and each one is cheaper by the same factor.

Eleven at every budget is therefore not a measurement that could have come out differently — it is arithmetic showing up in a sweep, and the sweep’s value is that it confirms nothing else is happening.

That confirmation is worth having. A factor that ought to be flat and is not would mean the saving depends on something the account does not mention.

Why the other is not #

The enumeration’s saving is the removal of extensions that find nothing, so its factor follows the share of those.

The dead share rises with the budget — 31% at zero errors, 55% at one, 75% at two — because a larger budget reaches narrower intervals and a narrower interval holds fewer of the alphabet’s symbols. A looser budget wastes a larger share is that measurement.

So the factor should rise with the budget, and it does not rise monotonically: 98.1, 78.2, 104.6.

The absolute costs behind those ratios are worth having, because a ratio that stays constant while its arguments multiply by twenty-seven is easy to under-read.

At zero errors: 110,880 ranks for the loop, 10,080 for the walk, 1,130 for the descent. At one error: 1,478,400, 134,400, 18,916. At two errors: 17,724,630, 1,611,330, 169,450.

The loop’s cost multiplies by 13.3 and then by 12.0; the walk’s by exactly the same; the descent’s by 16.7 and then by 9.0.

So the walk’s flatness is the two columns growing at identical rates, which is a stronger statement than a constant ratio: it says the walk is applied to exactly the same set of extensions the loop performs, one for one, with no change in which ones happen.

The descent’s columns grow at different rates because it performs a different set of extensions — the live ones only — and how many of those there are is what the budget changes.

The non-monotone point #

The dip at one error is worth explaining rather than smoothing, because a non-monotone measurement is usually a signal.

Two quantities move with the budget and they push the factor in opposite directions.

The dead share rises, which raises the factor.

The intervals the search reaches change shape. At zero errors the search follows one path, so its intervals are the pattern’s own prefixes — narrowing steadily. At one error it branches once, and the branches lead into intervals that are wider than the exact path’s at the same depth, because a mismatching character at a shallow position leaves a wide interval.

Wider intervals hold more symbols, so the descent costs more per node, which lowers the factor.

At two errors the second effect saturates — the search is deep enough that almost everything is narrow again — and the first effect dominates.

So the dip is the two effects crossing, and the honest summary of the enumeration’s factor over this range is between seventy-eight and a hundred and five, without a monotone trend to quote.

The alphabet moves both lines and it moves them differently, which is worth a sentence because it says which of the two shapes is more robust.

The walk’s flat value is σ⌈log σ⌉ over 2⌈log σ⌉ — that is σ/2, halved again by the two-ranks-a-node identity, giving about σ/2 divided by nothing. At twenty symbols it is 11.0 and at twenty-six it is 13.5. Flat in the budget at every alphabet, at a value the alphabet sets.

The enumeration’s range widens with the alphabet, because the dead share’s own range widens: on four symbols it is 9.5% to 28.9% and on twenty it is 31% to 75%.

So the flat line is flat everywhere and the moving line moves more as the alphabet grows. Two shapes, both stable in kind across the alphabets, which is what makes the classification worth stating as a property of the two savings rather than of one measurement.

The two lines never cross #

On a branching search the enumeration is ahead at every budget by between seven and nine times.

That is worth stating because the natural expectation from two savings with different shapes is a crossing, and there is none. The flat line is at eleven and the moving one is between seventy-eight and a hundred and five, so they are separated by an order of magnitude throughout.

The crossing between these two operations is on a different axis entirely: whether the search branches. The saving that is a loss is where that boundary is measured, and it is a switch rather than a dial.

So a plate sweeping the budget cannot show the decision, and drawing it anyway is useful for a different reason: it establishes that the decision does not depend on the budget.

The absence of a crossing has one further consequence that is easy to misread. Two savings, neither crossing the other, with one an order of magnitude ahead, looks like a case where the smaller one should be dropped.

It should not, and two factors that do not multiply is only half the reason. The other half is that the two lines are drawn on a branching search, and the walk’s line on an exact search is the only line there is — the enumeration’s is 1.90 times worse.

So a plate showing one saving comprehensively beating another over a whole dial is a plate about one regime, and the regime is not on the plate. That is the same limitation as any sweep: it holds everything but its axis fixed, and what it holds fixed here is the thing that decides.

What a flat line is evidence of #

There is a general point about sweeps here and it is the reason both lines are drawn rather than only the interesting one.

A quantity that ought to depend on a parameter and does is a confirmation. A quantity that ought not to and does not is also a confirmation, and it is the one people skip.

The compound walk’s factor being exactly flat across three budgets says that its saving is entirely in the alphabet, which is what its account claims. Had it drifted — say 11.0, 10.4, 9.6 — the account would be incomplete: something about the budget would be affecting it, and the essay describing it as “a factor of σ over the tree’s depth” would have a term missing.

This collection has had that go the other way. The half that is never asked where drew a saving expected to depend on a dial by a factor of three and found it depending by 2.19, and the shortfall was a constant term nobody had noticed — which turned into a whole strand.

So a flat line is a claim being confirmed, and a nearly-flat line where flatness was expected is a claim with something in it.

What the budget is, as a parameter #

It is worth being precise about what is being swept, because “error budget” carries two meanings that behave differently.

The sweep here is over k, the number of edits permitted, at a fixed pattern length of eight. So the ratio k/m goes 0, 1/8, 1/4.

The other reading is the relative budget — errors per character — which is what a workload actually specifies. A read aligner allowing five errors in a hundred characters is at 1/20, tighter than every point measured here.

Those are different sweeps and they would produce different curves. Holding m and moving k makes the search progressively looser; holding k/m and moving m makes it progressively deeper at constant looseness, which narrows the intervals for a different reason.

This strand sweeps the first because it is the parameter a search’s cost is usually quoted against, and the honest limitation is that the numbers apply to short patterns with generous budgets rather than to long patterns with tight ones.

Which direction that biases the enumeration’s factor is answerable from the mechanism: a longer pattern reaches narrower intervals, so the dead share is higher, so the factor is larger. The numbers here are therefore a lower bound on what a long-pattern workload would see, which is the convenient direction and is not a measurement.

The dead share as a predictor #

Since the enumeration’s factor follows the dead share, it is worth asking how well.

At 31% dead the factor is 98.1. At 55% it is 78.2. At 75% it is 104.6.

The relationship is not proportional and it should not be: removing 75% of the work is a factor of four, not a factor of a hundred. The enumeration’s factor is large because it removes the dead branches and shares the walks of the live ones — the branches that find nothing decomposes the factor of seven at one error into two roughly equal halves.

So the dead share explains the direction of the movement and about half the magnitude, and quoting one as a predictor of the other would over-predict by about a factor of two.

That is a small instance of a habit worth having: a mechanism that explains a direction is not a mechanism that predicts a magnitude, and reporting both quantities is what lets a reader tell.

What the search is doing at each budget #

A last piece of context for the three points, because the factors are more legible with the search’s own shape beside them.

At zero errors the search follows one path: eight nodes, one live extension each, and σ − 1 dead ones per node. The dead share is 31% rather than the (σ−1)/σ = 95% that description suggests, because the root node has every symbol present and contributes many live extensions to the total.

At one error the search branches once at each of eight positions, so it explores roughly m·σ paths of which most die quickly. Dead share 55%.

At two errors it branches twice, so the tree is roughly m²σ²/2 paths and almost all of them die at once. Dead share 75%.

The pattern is that the search’s shape changes from a path to a bush, and the enumeration’s value is a property of the bush’s density rather than of its size. That is why the factor does not simply track the work.

The branches an error opens is where this collection first drew that branching, on DNA, and its numbers are the reason a two-error search on a large alphabet is not something anybody runs without a filtering scheme in front of it.

The budget’s other effect #

The budget moves one more thing that neither saving touches and it dominates everything above at large budgets.

The occurrences reported multiply with the budget: a two-error search over a twenty-symbol alphabet reports far more matches than a one-error search, and each of them costs LF steps to locate.

So a query’s total cost is search plus locate, the savings here apply to the first, and the second grows faster with the budget than the first does. At some budget the locating dominates and a factor of a hundred on the search stops mattering.

Where that happens depends on the sampling rate, which is what the locating apparatus becomes’s dial, and the composition of the two is arithmetic this strand does not do.

What can be said is that the savings are on the phase that grows slower, which is the less useful of the two places to save. A budget that doubles the search’s cost and quadruples the locating’s is a budget where the search is becoming the smaller problem.

Two shapes a saving can have #

The classification this sweep produces is worth stating generally, because it is a question worth asking of any improvement before measuring it.

A saving whose factor is a property of the structure. The compound walk: σ ranks becoming one descent, so the factor is σ over the tree’s depth and nothing about the query moves it. Flat in every query parameter, and set by the data’s alphabet.

A saving whose factor is a property of the query. The enumeration: dead extensions removed, so the factor follows how many of them there are, which follows the intervals the query reaches.

The first kind can be quoted once per corpus. The second has to be quoted with a query profile, and a single number for it is a number about one workload.

That distinction is more useful than it sounds, because it says what a benchmark has to vary. A structural saving needs one measurement per alphabet; a query-dependent one needs a distribution of queries, and a benchmark using one query shape will report a number that does not transfer.

This collection has both kinds throughout and has not previously named the distinction. A filter has a selectivity is the query-dependent kind at its most extreme — a filter’s whole value is a property of the data and the threshold. The index that is smaller than the text is the structural kind: a size that is what it is.

Why three points #

Three budgets is a thin sweep and it is worth defending, because this collection usually draws six or eight.

The cost triples the search at each step and then some: 110,880 ranks at zero, 1,478,400 at one, 17,724,630 at two. A fourth point would be about two hundred million and a fifth about two billion, on a text of eight thousand characters.

So the sweep is bounded by the thing being measured rather than by patience. A search allowing three errors in eight characters is not a search anybody runs — three eighths of a short pattern free is close to matching everything — and the measurement would be of a degenerate regime.

At the other end, a fractional budget is not available: k is an integer and there is nothing between zero and one.

Three points spanning the whole usable range of a parameter is a complete sweep, and it is worth saying so rather than apologising for the point count. What it cannot support is a fitted trend, which is why this essay reports a range rather than a slope.

A limit is not a prediction is the habit that applies: three points bound a quantity and do not establish its shape, and a curve drawn through them would be a claim the data does not carry.

What the sweep is for #

Three things, in decreasing order of how obvious they are.

The factors at each budget, which is what a reader wants to quote and which spans seventy-eight to a hundred and five.

The shapes, which say what each saving depends on: one on the alphabet and one on the query.

And the absence of a crossing, which says the decision between them is not on this axis — so a system does not have to measure its budget to choose, and the choice made at write time by the saving that is a loss’s argument stands at every budget.

The third is the one a sweep is uniquely able to say. A pair of measurements at one budget cannot rule out a crossing elsewhere, and three points across the range a real search uses can.

That is a modest thing for a plate to establish and it is the kind of modest thing that keeps a decision from being re-litigated. Without it, a reader adopting the enumeration for branching searches has an open question — whether the walk overtakes it at some budget — and the answer is available only by measuring. With it, the question is closed over the range anybody runs, and the remaining condition is the one this strand states everywhere: it has to be a search that branches.