The threshold that reaches zero

The counting filter’s threshold is $t = m + 1 - q(k+1)$. It falls by $q$ for every error allowed, so for a pattern of twenty-four characters and $q = 5$ it runs 20, 15, 10, 5 and then zero.

A demand of zero shared $q$-grams is not a demand. Every window passes, every window is verified, and the filter has become an expensive way of not filtering: 2,977 windows proposed out of 2,977, and 986,266 table cells computed against the 96,000 that filling the whole table costs.

Ten times worse than doing nothing #

The 986,266 deserves to be read carefully, because “the filter stops helping” understates it by an order of magnitude.

Filling the whole table costs $n \times m$ cells: 96,000. Verifying every window separately costs a banded table of $m \times (m + 2k + 1)$ cells per window, times 2,977 windows — and because the bands overlap, the same work is done again and again. The result is ten times the cost of the thing the filter exists to avoid.

So the collapse is not a return to baseline. A filter that proposes everything is strictly worse than no filter at all, and by a factor that grows with $m$.

The collapse is exact, and that is unusual #

This collection has measured a filter collapse before. The filter that proposes everything is the seed filter’s, and it arrives gradually: as $k$ rises the seeds get shorter, short seeds occur by chance, chance hits accumulate, and the candidate fraction climbs through a half and on towards one.

That collapse has two thresholds and neither is sharp. Chance hits appear when a seed falls below $\log_\sigma n$; the whole text is proposed when the predicted fraction $(k+1)(2k+1)/\sigma^s$ reaches one. Both are approximations and the measured curve crosses them smoothly.

The counting filter’s collapse is a subtraction. At $q(k+1) = m+1$ the threshold is zero, and a threshold of zero admits everything by definition — not nearly everything, everything, and the plate’s assertion demands exactly that.

One of these two filters can be checked for collapse without running it. That is a real difference in kind, and it is the thing to take from the pair.

What the arithmetic says before anything runs #

The whole design space of the counting filter is a subtraction over two integers, and it can be tabulated in advance.

For $m = 24$: at $q = 2$ the threshold stays positive to $k = 6$ and beyond; at $q = 3$ it reaches 4 at $k = 6$; at $q = 4$ it goes negative at $k = 6$; at $q = 5$ at $k = 5$; at $q = 6$ at $k = 4$; at $q = 8$ at $k = 3$.

So for any pattern length and any error budget there is a largest usable $q$, and it is $\lfloor (m+1)/(k+1) \rfloor$ minus nothing. That is the sort of statement this collection likes and rarely gets: a parameter choice with a closed form and no measurement in it.

What the arithmetic does not say is which usable $q$ is best. The threshold being positive is necessary and not sufficient — a filter at $q = 2$ has a healthy threshold and proposes a great deal, because two-character $q$-grams are common. That part needs the sweep.

Why a long $q$ collapses first #

The direction surprises people who have not written the subtraction down, so it is worth stating the mechanism.

A longer $q$-gram is rarer, which is what makes a filter selective. But a longer $q$-gram is also destroyed by more errors: one substitution ruins $q$ of them, so the stock of surviving $q$-grams falls faster.

The threshold captures both: it starts higher for a short $q$ (there are more $q$-grams) and falls slower (each error destroys fewer). So the longest $q$ is the most selective while it works and the first to stop working, and the best choice moves left as the error budget grows.

Measured at $k = 2$: $q = 3$ proposes 92 windows, $q = 4$ proposes 104 and $q = 5$ proposes 121, so the shortest is already the best. At $k = 0$ the order is reversed: 8, 6 and 6. The crossover happens between them, which is a measurement rather than arithmetic.

Two collapses, one shape #

Set the two filters’ failures side by side and the shape underneath is the same one.

Both filters reduce an expensive stage to a cheap one plus a verification, and both are worth having exactly when the number of candidates is small. Both have a parameter that gets weaker as the error budget grows — the seed length, the shared-$q$-gram threshold — and both have a point past which the cheap stage proposes so much that it costs more than the expensive stage would have.

What differs is knowability. The seed filter’s collapse depends on the alphabet, the text length and chance, so it is a measurement; the counting filter’s depends on three integers, so it is a subtraction.

And what also differs is severity. The seed filter at $k = 4$ on the sweep in this phase proposes 649 candidates and computes 160,446 cells against a table of 96,000 — 1.7 times worse than not filtering. The counting filter at its collapse is ten times worse, because it verifies every window rather than a large fraction of them.

What a practitioner needs before choosing #

The two conditions can be stated as a procedure, and it costs one subtraction and one short run.

Subtract. Compute $t = m + 1 - q(k+1)$ for the pattern length and error budget in hand. If it is zero or below at every $q$ worth trying, this filter is not available and the question is which other method to use.

Then measure. For the largest few usable $q$, run the filter on a sample of the corpus and read off the candidate fraction. If it is above about $1/(2k+1)$, the verification will cost more than the table would have; below it, the filter pays roughly the reciprocal.

Neither step needs the whole corpus and neither needs a model. This is the sort of thing fitting a class to measurements argues for in the large: where a quantity can be measured cheaply, measuring it beats reasoning about it, and the reasoning is for the part that cannot be measured — here, the arithmetic that rules configurations out before anything runs.

The right response is not a better filter #

The obvious reaction to a collapse is to tune, and for this filter the tuning runs out.

At $m = 24$ and $k = 5$ the largest usable $q$ is 4, which gives a threshold of 1 — a demand that a window share one four-gram with the pattern, which nearly every window does. At $k = 6$ the largest usable $q$ is 3, with a threshold of 4 out of 22, which is not much better.

So past a certain error rate the filter is arithmetically alive and practically useless, and no choice of $q$ rescues it. The error rate is the thing that killed it: at $k/m$ above about a fifth, a pattern’s $q$-grams are so thoroughly damaged that “shares some $q$-grams” stops separating occurrences from anything else.

That is the honest reading, and it points at the other approaches rather than at a parameter. The search that spends a budget is the method whose cost does not depend on how much of the text looks plausible, and it has its own collapse in a different variable.

The check that the collapse is a collapse #

The plate’s assertion is two-sided and both halves matter.

Where the threshold is positive, the filter must propose fewer than every window. Where it is zero or below, it must propose all of them — not 99.9 per cent, all — and the check is an equality against the window count.

The second half is what catches a filter that has quietly stopped filtering for some other reason. A bug in the incremental count that made the shared total drift upward would produce a filter proposing everything at every $k$, which looks exactly like the collapse and is not; the first half of the check fails on it while the second passes.

The first half is what catches the opposite bug — a threshold applied with the wrong comparison, so that a collapsed configuration still discards windows. That one loses occurrences and every occurrence it does return is real.

A prediction that is right for the wrong reason #

The binomial prediction from the previous essay reports a candidate fraction of exactly one at the collapse, and it deserves no credit for it.

The prediction is the upper tail of a binomial at $t$; at $t \le 0$ the tail is the whole distribution and the answer is one. It is right because a probability of at least zero successes is one, not because it has modelled the filter’s behaviour.

Everywhere else the prediction is an estimate with real error — over by a factor of five at $q = 3$, under by a fifth at $q = 4$, as measured on text with nothing planted in it. A reader seeing the prediction and the measurement agree exactly at the collapse and disagree by fivefold elsewhere should conclude that the agreement is the artefact.

That is the shape a limit is not a prediction warns about, arriving from an unexpected direction: a model that is exactly right in the one regime where it says nothing.

Where the crossing actually is #

“The filter stops paying” and “the threshold reaches zero” are two different events, and the first happens earlier.

At $q = 4$, the thresholds run 21, 17, 13, 9, 5 across $k = 0$ to 4, none of them zero. The savings run 228.6, 18.0, 5.7, 3.5 and 0.9 — so the filter has stopped paying at $k = 4$ while its threshold is still five.

The reason is that the saving depends on the candidate count and the candidate count depends on chance hits, which the threshold does not model. At a threshold of five on a twenty-four-character pattern over four symbols, a fair number of windows share five four-grams with the pattern by accident.

So there are two conditions and a practitioner needs both: the threshold must be positive, which is arithmetic, and the candidate fraction must be under about $1/(2k+1)$, which is a measurement. The first is necessary and the second decides.

The ceiling is a function of the error rate and nothing else #

The subtraction gives a largest usable $q$, and the sweep at a longer pattern is read as showing that the design space depends on $m$ as much as on $q$. Write the ceiling out and it says something narrower and more useful.

The threshold is positive when $q(k+1) < m+1$, so the ceiling is

$$q_{\max} = \left\lceil \frac{m+1}{k+1} \right\rceil - 1$$

which for large $m$ and $k$ is $m/k$ — the reciprocal of the error rate, with the pattern length cancelling out.

Check it against the grids. At $m = 24$ and $k = 4$ the ratio is 25/5, so $q_{\max} = 4$; at $k = 5$ it is 25/6 and $q_{\max}$ is still 4; at $k = 6$ it is 25/7 and $q_{\max}$ falls to 3. The sixteen-character grid, where “most of the plane is shaded”, is the same arithmetic at a smaller numerator: at $k = 3$ the ratio is 17/4 and the ceiling is 4, at $k = 5$ it is 17/6 and the ceiling is 2.

So doubling the pattern length does not buy a larger $q$ at the same error rate. A twenty-four-character pattern with four errors and a forty-eight-character pattern with eight are both at $q_{\max}$ near six, because both have one error in six characters. The ceiling is a property of how damaged the pattern is, not of how long it is.

What the length does buy is the threshold one step below the ceiling, and that is where the longer sweep’s advantage actually comes from. At $q = 4$ and $k = 5$: a twenty-four-character pattern has $t = 25 - 24 = 1$, and a thirty-two-character pattern has $t = 33 - 24 = 9$. Same $q$, same budget, nine times the demand — which is why nothing collapses inside the longer sweep’s range.

The general form is worth writing down because it is the design rule the two conditions add up to. Holding the error rate fixed and backing one step off the ceiling gives $t \approx k+1$: the usable threshold grows with the number of errors, not despite it, because a longer pattern carrying proportionally more errors also carries proportionally more $q$-grams to spare.

That inverts the intuition this filter usually attracts. More errors is not straightforwardly worse — more errors at the same rate is fine, and more errors at a higher rate is what kills it, since the rate is the only thing in the ceiling. A twelve-character pattern with three errors is hopeless and a hundred-and-twenty-character pattern with thirty errors is hopeless in the same way and for the same reason, and the two are the same point on the only axis that matters.

Which sharpens the procedure by one step. Compute the error rate first; it gives the ceiling directly, and if the ceiling is below two the filter is not available at all — $q = 1$ is character counting rather than $q$-gram filtering, so the death condition is $k \ge (m-1)/2$, an error rate of a half. Then take one or two steps below the ceiling, where the threshold is a healthy multiple of $k$, and measure there. The q-grams an error cannot destroy is the safety half of that and the filter that proposes everything is the other filter’s version, whose ceiling has the alphabet in it and therefore cannot be written down at all.

Why this belongs in the wrong-answers field #

The statement this essay is against is not written down anywhere, which is what makes it worth an essay: that a filter’s parameters can be tuned to make it work.

For this filter they cannot, past an error rate the arithmetic names. The design space is a plane, more than half of it is unusable at any interesting error budget, and the usable part shrinks as the pattern shortens. A practitioner who reaches for a $q$-gram filter at $k/m = 0.25$ and finds it slow will try other $q$ values, find them all slow, and conclude something about their implementation.

The collection has this shape elsewhere. The ceiling the shortest pattern sets is a limit on a skipping matcher set by the caller’s pattern set rather than by the algorithm; the block that is not a block is a model parameter that the machine does not supply. In each case the fix is not tuning; it is knowing which regime the problem is in before starting.

What survives the collapse #

Two things, and they are the reason the filter is worth building at all.

At low error rates it is excellent: at $k = 0$ it proposes six windows out of 3,977 and computes 420 cells against 96,000, a saving of 228 times. At $k = 1$ it saves 18 times and at $k = 2$ nearly 6.

And its collapse is safe. A filter proposing everything returns every occurrence; it is slow and it is not wrong. That is worth stating because the failure mode of a filter that were unsafe past a threshold would be far more dangerous, and this collection has one of those in the same phase: the search that spends a budget is exact at every budget, while a pruned version of it that looked similar would silently miss.

The two failures a filter can have #

It is worth separating the two things that can go wrong with a filter, because only one of them is what this essay is about and they are easy to conflate.

A filter can be unsafe: it discards a window holding an occurrence, and the answer set is wrong. That is what raising the threshold above the lemma does, and it is measured in the q-grams an error cannot destroy — one occurrence of twelve lost, with every returned occurrence still correct.

A filter can be useless: it proposes everything, the answer set is right, and the cost exceeds the baseline. That is the collapse.

The second is the one that happens by itself, as a parameter moves, with nothing wrong anywhere. It is also the one no correctness check can see: every gate in this collection that compares a filter’s answers against exhaustion passes at the collapse, because the answers are exactly right.

So the gate for this has to measure a cost rather than an answer, which is unusual here and is why the plate asserts a candidate fraction rather than an occurrence set. The filter that proposes everything reached the same conclusion for the other filter, and the two together are the reason this collection’s filter plates all print the selectivity.

The honest limit #

The four-symbol alphabet is the hardest case for a $q$-gram filter and the sweeps use it throughout. On a twenty-six-symbol alphabet a four-gram is 456,976 possibilities rather than 256, chance hits nearly vanish, and the filter stays useful to a higher error rate — the collapse point does not move, because it is arithmetic, but the practical crossing does.

The occurrences are planted by substituting $k$ characters at random positions, so every planted occurrence has exactly $k$ errors and they are spread. Clustered errors damage fewer $q$-grams, so a corpus whose errors arrive in bursts would give a filter that works past the point measured here.

And the verification cost model charges a banded table per candidate, which is the right charge for a candidate that has to be checked and is generous towards the whole-table baseline, since a single table shares work between overlapping windows. That makes the ten-times figure at the collapse a conservative statement of how bad it is.