The filter that proposes everything

The same pattern, the same text, the same filter. Only the number of errors allowed changes.

At four errors the filter proposes 2,679 of the 20,000 positions and the machinery of filtering costs 38% more than filling the rectangle it was avoiding. At seven it costs twelve times as much.

Nothing in the filter has gone wrong. Every candidate is correct, every occurrence is found, the pigeonhole holds at every row. What has happened is arithmetic, and it has two thresholds in it.

The three stages, and both of them grow #

It helps to see where the work goes, because the collapse is usually described as though the verification stage were the only casualty.

Both sides rise by nearly three orders of magnitude, and the index side rises for a reason this field has already measured: finding a seed is cheap and locating its occurrences is not. Counting the occurrences of a seed is about two ranks per character and is independent of how many there are; turning each occurrence into a text position is a walk to a sampled row, and that walk costs 860 times what the count does.

So a filter over a self-index pays the locate cost per seed occurrence, and seed occurrences are exactly the quantity that explodes. The filter stage is not immune to its own selectivity; it is charged by it twice, once by the walk and once by the verification downstream.

What never fails is the search itself. Backward search finds every exact occurrence of every seed in time proportional to the seed length, on a structure that has not changed and does not care. Everything that goes wrong goes wrong in what is done with the answer.

The seed length is the only variable #

The pattern is 24 characters and the pieces are $\lfloor 24/(k+1)\rfloor$ characters each. So the error budget does not act on the filter directly; it acts by shortening the seeds.

$$s = \left\lfloor \frac{m}{k+1} \right\rfloor$$

And a seed of length $s$ drawn from a text of $n$ characters over $\sigma$ symbols is expected to occur

$$\frac{n}{\sigma^{s}}$$

times by chance. That is exponential in $s$ and $s$ falls like $1/k$, so the chance hits rise doubly-exponentially in the error budget. Between $k=3$ and $k=4$ the seed goes from six characters to four, which multiplies the expected chance hits by $\sigma^2 = 16$, and the candidate count goes from 154 to 2,679.

The first threshold: where chance hits appear at all #

The chance term crosses one when $\sigma^s \approx n$, that is

$$s \approx \log_\sigma n = \log_4 20{,}000 = 7.14$$

Above it a seed is expected to occur less than once by accident, so essentially every candidate comes from a real occurrence and the selectivity is near 100%. The measurement agrees: at $s = 8$ the filter proposes 20 candidates of which 15 are answers; at $s = 12$ and $s = 24$ every candidate is an answer.

This is the threshold that is usually quoted, and quoting it alone is what makes people think the filter degrades gracefully. It does not describe the collapse; it describes where the collapse begins.

The second threshold: where it proposes the whole text #

The candidate count is the seed hits times the widening. With $k+1$ seeds and $2k+1$ candidate starts per hit:

$$\text{candidates} \approx (k+1)(2k+1)\,\frac{n}{\sigma^{s}}$$

Divide by $n$ to get the fraction of the text proposed:

$$\frac{\text{candidates}}{n} \approx \frac{(k+1)(2k+1)}{\sigma^{s}}$$

The $n$ cancels. The fraction of the text a filter proposes is a property of the pattern, the error budget and the alphabet, and a longer text does not dilute it. A filter that proposes 13% of twenty thousand characters proposes 13% of twenty million.

That fraction reaches one at

$$s \approx \log_\sigma\!\big((k+1)(2k+1)\big)$$

which for $k=6$ over four symbols is $\log_4 91 = 3.25$, and the seed at $k=6$ is 3. Measured: the filter proposes 67% of the text.

The prediction tracks the measurement until it exceeds one, at which point it must stop: a prediction of 142% is a count of proposals, and the measurement is a set of distinct positions. The proposals collide, so the set saturates. The two quantities agree exactly as long as they are the same quantity, which is a check on the arithmetic rather than a defect in it.

The prediction has a second term and it is the one that is dropped #

The formula above is the chance term. There is another, and leaving it out makes the filter look several times worse than it is exactly where it is working.

At a real occurrence, all $k+1$ seeds fire and they all point at the same start. So a genuine occurrence contributes $2k+1$ candidates, not $(k+1)(2k+1)$. The full prediction is

$$\text{candidates} \approx \underbrace{o\,(2k+1)}_{\text{the occurrences}} \;+\; \underbrace{(k+1)(2k+1)\frac{n}{\sigma^{s}}}_{\text{chance}}$$

for $o$ occurrences. On this text with three planted occurrences:

At $k=2$ the planted term is three quarters of the prediction. Dropping it would predict 4.6 candidates against 20 measured — a factor of four out — and the natural conclusion from that would be that the model is wrong. The model is fine; the term nobody writes down is the one that dominates when the filter is doing its job.

And a check built only on the chance term would be passed by a filter with no occurrences in its text. That is why the sweep here plants occurrences and requires the answer to be non-empty at every row: a selectivity whose numerator is zero by construction is not a measurement of anything.

The alphabet moves both thresholds #

Everything above is over four symbols, and both thresholds are logarithms base $\sigma$. So the alphabet does not shift the collapse, it scales it.

Over two symbols the collapse is nearly immediate. A twelve-character seed at one error is already under $\log_2 20{,}000 = 14.3$, so chance hits appear straight away; by two errors the filter proposes 5.5% of the text and the saving is 2.7×; by three it has lost.

The last row of that table is worth a second look, because it is a different failure from the ones above it. At six errors over two symbols there are 9,809 genuine occurrences in twenty thousand positions. Half the text matches. A filter proposing everything is not being defeated by chance hits; it is correctly reporting that nearly everything is an answer, and the thing to fix is the query rather than the algorithm.

Which means “the filter proposed everything” has two causes and they need telling apart. One is that the seeds got short and the proposals are noise; the other is that the answer got large and the proposals are right. The selectivity is the same in both cases and the remedy is not: the first is fixed by a longer pattern, the second by asking a different question. The two are distinguished by the numerator — 41 answers in the four-symbol case against 9,809 in the two-symbol one — which is why every plate in this family prints the answer count beside the candidate count.

And the answer to “does seed-and-extend work” is not a property of seed-and-extend. It is a property of $m$, $k$, $\sigma$ and $n$, and all four are known before a single index query is made.

Where this leaves the practical matcher #

Three things follow, and none of them is that the filter is a bad idea.

The pattern length is the dial, not the error budget. The filter’s health depends on $m/(k+1)$ against $\log_\sigma n$, so a caller who wants more errors and keeps the filter can ask for a longer pattern. That is exactly what read aligners do: they will not align a short read at high error rates, and the refusal is arithmetic rather than policy.

A filter that has stopped filtering should be turned off, and the condition is computable. The crossing where filter-plus-verify costs more than the rectangle is at roughly $n/(2k+1)$ candidates — verifying a candidate is $m(2k+3)$ cells against the table’s $nm$ — and the candidate count itself is predicted by the formula above. Nothing prevents an implementation from computing both and choosing, and this collection is aware of none that does.

A refusal is a legitimate answer and it is what the arithmetic supports. A short read at a high error rate is a query whose filter cannot work and whose whole-table alternative costs $nm$ cells over a genome; refusing it is not a limitation of the aligner, it is the only honest response to a question with no cheap answer and, at high enough $k$, no small answer either.

And “the filter is exact” is not a defence. Everything here is a correct algorithm returning correct answers. The pigeonhole holds, the verification is real, no occurrence is missed at any row of any table. The failure is entirely one of cost, it is invisible to every correctness test, and it degrades smoothly enough that nobody sees where it started — which is the shape of defect this field exists for.

The shape this is an instance of #

Three of the last four fields on this site have produced a structure whose advertised behaviour is a conditional, and each time the condition was left off the advertisement.

A Bloom filter’s false-positive rate is the formula everybody sizes with, and it is right about the wrong quantity. A sketch’s guarantee is one query wide and is quoted as though it covered a table of them. A summary’s rank error is a fraction of something and the something is usually the whole stream when the question was about a tail.

This one has the same shape and a different mechanism. There is no probability in it, no guarantee to misread, and nothing about it is approximate — the filter is exact and its correctness is unconditional. What is conditional is whether it is worth running, and that condition is a piece of arithmetic in four known parameters that no statement of the algorithm includes.

The generalisation worth carrying is the question rather than the threshold. For any filter: what fraction of the input does it propose, at what parameters does that fraction reach one, and is the fraction computable before the filter runs? For seed-and-extend all three have closed-form answers. For most filters the third is the interesting one, because a filter whose selectivity can only be discovered by running it is a filter that cannot be turned off when it stops paying.

The disaster is bounded, and the bound is computable too #

The collapse looks unbounded on the plates and it is not. The same four parameters that predict where the filter stops paying also cap how badly it can fail, and the cap is worth having because it changes what kind of risk this is.

The candidate count saturates at $n$ — there are only $n$ positions to propose, and the collisions noted above are what make the measurement fall below a prediction that has gone past one. Each candidate costs a banded verification of $m(2k+3)$ cells. So the filter’s total work, at its very worst, is

$$n\,m\,(2k+3)$$

against the whole table’s $nm$. The filter cannot cost more than $2k+3$ times the thing it was avoiding, whatever the alphabet, the text or the pattern.

The measurements sit under that ceiling and near it once the seeds are short. At seven errors the bound is 17 and the measured cost is 12.5 times the table; at six the bound is 15 and the measurement is 9.3. The gap between them is the saturation — 80.7% of positions proposed rather than 100% — plus the positions near the ends of the text where a band is clipped.

That is a different kind of risk from the one the falling curves suggest. A filter whose worst case were unbounded would be a hazard: a query with the wrong parameters could run for arbitrarily long. This one degrades to a bounded multiple of the exhaustive method, the multiple is linear in the error budget rather than exponential, and it is known before the query starts. A cost ceiling that can be computed from the query is the difference between a system that must refuse and one that may simply be slow, and it is the strongest argument for keeping the filter switched on even past the crossing — provided the caller is told which side of it they are on.

Making the cells cheaper does not move the crossing #

The natural response to the crossing is to make verification faster, and the natural way to do that on this site is a column computed in machine words, which evaluates a whole column of the table in a handful of word operations instead of one operation per cell.

It does not move the crossing at all, and the reason is worth stating because it applies to every optimisation of this shape.

The crossing is a ratio of two cell counts. Bit-parallel evaluation is a discount on the price of a cell, and both sides of the ratio are made of the same cells — the filter’s bands and the whole table alike. Applying it to the verification and not to the baseline would be comparing an optimised implementation against an unoptimised one, which is the commonest way a benchmark flatters a filter. Applying it to both leaves the ratio exactly where it was. The absolute numbers fall by a large factor, every curve on every plate shifts down together, and the point where they cross does not move a millimetre.

So only two things can move it, and they are both changes to the structure of the comparison rather than to the speed of the arithmetic.

Fewer candidates. Longer patterns, a larger alphabet, a filter with a better selectivity at the same seed length — everything the sections above are about. This is the lever that works and it works on the term that is exploding.

A discount the baseline cannot have. Verification of one candidate may stop the moment the band’s best surviving cell exceeds $k$, because that candidate is then known not to be an answer. The full table has no such exit: it must report every position within $k$, so it cannot abandon a column on the grounds that one alignment has failed. That asymmetry is real, it is not measured here, and it is the only per-cell change that genuinely favours the filter — which makes early abandonment worth more to a seed-and-extend matcher than any amount of vectorisation.

The general form is the one to carry away. An optimisation that applies to both arms of a comparison changes the numbers and not the decision, and a great many reported improvements to filtering are of exactly that kind. The question to ask of any such change is not how much faster it made the filter, but whether it could have been applied to what the filter was avoiding.

What is not measured here #

Other filters, which have different thresholds. A $q$-gram counting filter, a filter that walks the index with an error budget, a filter over overlapping seeds rather than a partition — each has its own arithmetic and each of them fails somewhere. What generalises is not the threshold but the question: what fraction of the input does this filter propose, and at what parameters does that fraction reach one?

The distribution of the text. Every text here is drawn uniformly, so $n/\sigma^s$ is exactly right. Real text is not uniform, and a seed drawn from a common region occurs far more often than the formula says while a seed from a rare region occurs less — so the variance of the candidate count on real data is larger than anything here shows, and the mean is not where the trouble is.

The other end. At $k=0$ the filter is the index answering the question and the table is not used at all. The 2,286× saving in the first row is therefore not a filter’s saving; it is the saving of not needing a filter, and it belongs to the index rather than to this algorithm.