The pruning that loses an occurrence

A pruning rule is a licence to stop looking. Every one of them is an argument of the form “nothing below this state can be an answer”, and if the argument is wrong the search returns fewer answers than there are.

That failure has no signature. There is no exception, no impossible value, no invariant to violate — the search finishes, reports positions, and every position it reports is a genuine occurrence. It has simply not reported all of them.

The two failures #

Both are ways of getting $D$ right and using it wrongly, and both are the kind of mistake that survives a code review.

Applied one character late. The walk consumes the pattern from the right, so a state with $i$ characters left still has to deal with $P[0..i-1]$, and the bound on that is $D[i-1]$. Using $D[i]$ instead includes the character the state is about to match — a character it has not committed to and might match for free.

Since $D$ is non-decreasing, $D[i] \ge D[i-1]$, so the late version prunes at least as much and sometimes more. Measured on a ten-character pattern at a budget of one: the correct bound finds four positions and the late one finds three. All three are real.

Bounded on the wrong end. The walk runs backwards through the pattern, so “the rest of the pattern” reads naturally as what has been consumed. A bound on the pattern’s suffixes is easy to compute — the forward index already extends leftwards, so it needs no second structure at all — and it is a perfectly sound lower bound on a quantity nobody is bounding.

Measured on a twelve-character pattern at a budget of two: the correct bound finds eight positions, the suffix bound finds seven, and all seven are occurrences.

Why the second one is the dangerous one #

Because it is cheaper, and cheaper in the exact place the technique hurts.

A bound that has to be paid for is the essay about the second index: computing a bound on prefixes requires a structure that extends rightwards, which the forward index is not, so the bound doubles the space. A bound on suffixes needs no second index — it falls out of the search structure that is already there.

So the wrong version is the one a reader would reach for after reading the previous essay and deciding the space was too expensive. It computes in the same one pass, produces an array of the same shape with the same monotonicity, prunes a comparable fraction of the tree, and returns a smaller answer.

That is the shape this collection has learned to fear: a cheaper version that is right about everything except which question it answers. A distance that is not a distance is the same shape in the alignment strand — a scoring function that fails the triangle inequality, and therefore a pruning built on it that discards branches holding answers — and the resemblance is not superficial. Both are a pruning whose licence to stop looking came from a property the object does not have.

What the checks in this collection actually do #

Every rejection test in this ladder compares against the correct search’s answer, not against a property of the answers.

The reason is that the properties all hold. Consider what could be asserted about a bounded-error search’s output without a reference:

• every reported position is within the budget of the pattern — true for both failures
• the reported positions are distinct and sorted — true
• the count does not exceed the count at a larger budget — true
• the count is at least the count at a smaller budget — also true, because both bad prunings are consistent across budgets

That last one is worth pausing on. A monotonicity check across budgets is the natural structural test for this search, and it passes: the late bound at $k = 3$ finds at least what it finds at $k = 2$, because it is wrong in the same way at both.

So the only check with teeth is exhaustion. On a text small enough to fill the whole dynamic-programming table, fill it, and require the walk’s answers to be exactly the table’s. That is what the search that spends a budget does at four budgets and what this ladder does again with the pruning switched on.

The same shape, three times in this collection #

It is worth putting them together, because the pattern is more general than any of them.

The occurrences that cross a boundary is the phrase index’s version: a search reporting its primary occurrences and skipping the propagation returns real occurrences and, on a collection of thirty-two copies, one thirty-second of the answer. Every one is correct.

The threshold that reaches zero is the filter’s version in reverse: a counting filter’s threshold raised one above what the lemma allows loses occurrences and reports only real ones.

And the shift somebody published is the matching version: a shift table with an entry one too large steps the window past a place a pattern could have ended, and every match it does report is a match.

Four structures, four different mechanisms, one failure mode: an answer that is a subset of the answer. It is the failure a correctness test cannot see, because correctness tests are written to catch wrong answers and this produces none.

How much of the answer goes, and why the size of the loss is a trap #

One position of four, and one of eight. Those are small losses and they are the reason the failure survives.

A pruning that lost half the answers would be caught by anybody who ran it twice. A pruning that loses one occurrence in four will be caught by a comparison against exhaustion and by nothing else, and the fraction is not a coincidence: the states these rules wrongly abandon are the ones near the budget’s limit, which hold the occurrences that need every unit of the budget. Those are always a minority and they are always the interesting ones.

That is the same distribution-of-damage argument the boundary that hides the burst makes about a window that discards arrivals: the fraction lost is small, the lost fraction is not a random sample, and a summary statistic over the whole answer cannot see either fact.

For a bounded-error search the consequence is specific. The occurrences a broken pruning loses are the most distant matches — the ones at exactly $k$ errors — which is the part of the answer a reader raised the budget in order to get. So the loss is concentrated in the marginal value of the parameter, and a user who raises $k$ from two to three and sees one extra occurrence instead of two has no way to know which of those numbers was right.

Why a plot cannot catch it either #

The pruned tree with the correct bound at a budget of three is 12,051 extensions. With the late bound it is smaller. A plate of tree sizes with the wrong rule in it looks better — a lower curve, a larger share removed, a more impressive result.

That is the second half of the danger and it is specific to prunings. A bug in a pruning does not make the plate look wrong; it makes it look good, and the incentive gradient points the wrong way. The only quantity that moves in the alarming direction is the answer count, and an answer count is a property of the pattern that a reader has no independent expectation about.

The general form: an optimisation whose failure mode is doing less work is an optimisation whose bug improves its own benchmark. Every pruning, every filter, every early exit and every shift rule in this collection has that property, which is why every one of them ships with a rejection test that compares answers rather than costs.

Finding the counterexamples was itself a measurement #

Neither failure showed up on the first parameters tried, and that is part of the finding rather than an aside.

The late bound was applied to the ladder’s default sweep — a sixteen-character pattern, four thousand characters of four-symbol text, four planted occurrences — and lost nothing. So did the suffix bound. Both are wrong at every one of those settings and neither lost an answer, because $D$ was flat where the difference mattered and the walk had budget to spare.

A search over pattern lengths, budgets, alphabets, planted counts and seeds found the settings where each one loses. The late bound loses on ten-character patterns at a budget of one, across several seeds and planted counts; the suffix bound loses across most of the four-symbol settings once the planted count is three or more.

Two things follow. A rejection test needs its own parameters, chosen so the defect fires, and using the essay’s own defaults for it is how a check comes to pass for the wrong reason. And the interval over which a defect is invisible is wide — a whole grid of plausible settings, on the specific pattern the ladder is built around, and a reader who tested there would have concluded both rules were fine.

This site’s ledger already records the general version of that, from a sweep whose pattern sat at a multiple of the sampling rate and therefore agreed with every rate it tried. The rule is the same: a sweep over a parameter has to run on an input that does not agree with the parameter, and a rejection test has to run on an input where the rejection can happen.

The safe direction, stated #

A pruning rule is safe when the quantity it compares against is a lower bound on what the state must still spend.

Both failures above violate that in the same way: they use a bound on something other than what the state must still spend. The late one bounds a longer piece of the pattern, which needs at least as many errors, so the comparison is against a number that may be too large. The suffix one bounds a different piece entirely, so the comparison is against a number with no relation to what remains.

The direction that is always safe is underestimating. A bound of zero everywhere prunes nothing and is correct; a bound that is sometimes too small prunes less than it could and is correct. The whole asymmetry of pruning is there: an error towards zero costs work and an error away from it costs answers, and only one of the two is visible.

This is the same asymmetry the shift rules have, and it is why the published Commentz-Walter rules are described as safe approximations rather than as approximations: they may fall short of the exact shift and may never exceed it. What the approximation gives up measures what falling short costs, and the answer is a few per cent of reads — a price paid for a guarantee that the other direction is impossible.

What a reader should demand of a pruning #

Three things, and they generalise past this ladder.

A statement of what the bound bounds. Not “a lower bound on the errors” but a lower bound on the errors in which piece of the pattern, at which state. Both failures here would be caught by writing that sentence carefully.

A comparison against exhaustion, at a size where exhaustion is possible. Every quantity in this ladder is measured at three or four thousand characters, which is exactly the size where the $n \times m$ table can be filled and compared against. That is not a limitation of the measurement; it is the measurement.

And a demonstration that the check can fail. A rejection test is a claim that a broken version would be caught, and a claim about a test is worth what any untested claim is worth. Both failures above are in this site’s gate, each with a specific pattern and text where they lose a specific number of occurrences, and each fails the build if it ever stops losing them.

Where the correct version’s own risk sits #

The correct pruning is safe by an argument, and it is worth saying what the argument depends on rather than treating safety as established.

$D[i]$ counts disjoint pieces of $P[0..i]$ that occur nowhere in the text. The argument is: an alignment of $P[0..i]$ against any substring must align each piece against something, a piece that occurs nowhere cannot be aligned without at least one edit inside it, and the pieces are disjoint so the edits are distinct.

Two things could break that. The pieces could fail to be disjoint, which the construction prevents by resetting the interval at each break. Or “occurs nowhere” could be wrong — an interval reported empty when it is not — which would be a defect in the reverse index rather than in the bound, and which is checked by the index’s own assertions rather than by this ladder’s.

So the safety rests on the correctness of a structure built for a different purpose, which is the ordinary situation and is worth naming because it is where this collection’s worst reference bug lived: a shift helper indexed by the wrong quantity, correct at both existing call sites by accident, and wrong the first time anything asked about an individual entry. A dependency that has only ever been asked one kind of question has only ever been checked for one kind of answer.

What a correct pruning’s plate looks like #

For contrast, and because the point of the essay is that the two are indistinguishable from the plate alone.

Every number on that plate is a cost. The answer’s size appears nowhere, because the answer’s size is the same on every bar and is therefore not a series — which is exactly the condition under which a plate cannot see the failure this essay is about.

The fix is not a better plate. It is that the sweep producing the plate refuses to return a row where the two policies’ occurrence sets differ, so a plate that draws at all is a plate whose answers agreed. That check is in the measurement rather than in the figure, and it is why the figure can be read.

A check with teeth that does not need the whole table #

The only check with teeth is exhaustion is the conclusion, and it forces every measurement on this ladder down to three thousand characters. There is a weaker check that works at any size, and this essay’s two failures are what make it available.

The two broken prunings are wrong in unrelated ways — one reads the bound array one position late, the other bounds the wrong end of the pattern — so the occurrences they drop are unrelated too. Both return subsets of the truth, and there is no reason for the subsets to coincide.

So running two independently-derived prunings and requiring identical answer sets catches either one. No table, no oracle, no quadratic cost: two walks over the same index, and a disagreement is proof that at least one is unsafe.

It is strictly weaker than exhaustion, and the weakness is worth stating. Two prunings sharing a mistake agree and both pass — which is exactly why independently derived is load-bearing, and why the pair here works: one is a fencepost and the other is a different quantity entirely, so no single error produces both.

This collection already runs that shape at the level above. Four string matchers are required to return identical occurrence lists on every input, precisely because a matcher that quietly misses an occurrence looks better on every counter — the same failure this page is about, caught by agreement rather than by truth.

Which suggests the practical arrangement for a real reference, where the table cannot be filled. Keep exhaustion as the check at the size it is affordable; keep an agreement check between the correct pruning and an unpruned walk at the size it is affordable; and above that, run two prunings and compare. A bound that has to be paid for’s second index makes the second pruning nearly free once the first is built, which is the one place its cost earns something back — and it is the same argument the occurrences that cross a boundary makes for checking a two-stage search against a one-stage one rather than against a property.

What is being claimed #

Two one-character variations on the pruning lose occurrences, and both report nothing but genuine ones: four positions become three, and eight become seven, on the patterns measured.

Every structural property of the output survives both. Sortedness, distinctness, within-budget, and monotonicity across budgets all hold.

The cheaper of the two is the dangerous one. A bound on the pattern’s suffixes needs no second index, which is the expensive part of the correct version, so the wrong construction is the one a cost-conscious reader arrives at.

A pruning’s bug improves its own plate. Less work, a lower curve, a larger share removed, and a smaller answer that nothing on the plate reports.

And the only check with teeth is exhaustion, which is why every measurement on this ladder runs at a size where the whole table can be filled.