A distance that is not a distance

The Levenshtein distance is a metric. That is not a figure of speech: it satisfies all four requirements, the proof is short, and this collection’s own machinery asserts it on every build by taking random triples of strings and checking that $d(x,z) \le d(x,y) + d(y,z)$.

Give the substitutions a stated matrix and the assertion stops being true.

Not “becomes hard to prove”. Stops being true, with a witness two characters long: under a cost model derived from a walk on a keyboard, $d(\texttt{aa}, \texttt{dd}) = 8$ and going by way of $\texttt{ww}$ costs $2 + 2 = 4$. The detour is half the price of the direct route.

Which properties survive #

A metric needs four things, and it is worth going through them because three of them do survive and only the interesting one does not.

Non-negativity. Every substitution cost in the matrix is at least 1 and every gap cost is positive, so no alignment can have a negative total. Holds by construction, and it is a construction choice: a log-odds score is naturally negative on its diagonal, and the shift that makes identity zero is what keeps this true here.

Identity. $d(x, x) = 0$, because $s(a, a) = 0$ for every symbol and the alignment that pairs every character with itself costs nothing. Also by construction. And its converse holds: any alignment of two different strings must either substitute or gap somewhere, and both cost at least 1.

Symmetry. $d(x, y) = d(y, x)$ requires $s(a, b) = s(b, a)$, which is not automatic — the walk that generates the matrix normalises each row by the number of neighbours that row has, so the two directions could in principle differ. Measured over all 650 ordered pairs of distinct letters: zero asymmetric pairs. The construction happens to be symmetric because the walk’s stationary distribution is uniform on this graph, and it is worth checking rather than assuming, since a matrix built from unequal background frequencies would not be.

The triangle inequality. This is the one that fails, and it fails at the symbol level first.

The mechanism is not subtle. A log-odds score is $-\log_2$ of a probability ratio, and probabilities compose by multiplication while costs compose by addition — so a two-step drift $q \to w \to e$ has a probability that is the product of two one-step drifts, which the logarithm turns into a sum, while $q \to e$ in one step is a single unlikely event with its own cost. There is no reason for the one-step cost of the endpoint to be below the sum of the two-step path, and on a graph where $q$ and $e$ are two keys apart it is not.

Why unit cost is safe, in one paragraph #

The proof is short enough to be worth having, because seeing why it works is what makes it obvious what breaks it.

Take optimal alignments of $x$ with $y$ and of $y$ with $z$. Line them up on their shared string $y$ and read off, for each character of $y$, what happened to it on the left and what happened to it on the right. Each combination gives a column of an alignment of $x$ with $z$: matched-then-matched gives a match or a substitution, matched-then-deleted gives a deletion, and so on. Every one of the nine combinations produces a column costing at most the sum of the two columns it came from — a substitution followed by a substitution costs 1 and the two cost 2; an insertion followed by a deletion cancels and costs 0. So the concatenation is an alignment of $x$ with $z$ costing no more than $d(x,y) + d(y,z)$, and the true distance is a minimum over all alignments, so it is no larger.

The step that fails under a matrix is the first one. A substitution of $a$ for $b$ followed by a substitution of $b$ for $c$ costs $s(a,b) + s(b,c)$ on the two sides and $s(a,c)$ on the combined one, and under unit cost $1 \le 1 + 1$ holds always. Under a matrix it holds exactly when the symbol-level inequality does — which is the sentence the audit above turns into a number.

And a model where it does not fail #

Here is where the honest version of this essay diverges from the sloganeering one.

So “a substitution matrix breaks the triangle inequality” is not a law. It is a property that some models have and some do not, and the difference here is structural: the nucleotide alphabet has two classes of two, so there is no third symbol to route through that is nearer to both endpoints than they are to each other. The keyboard graph is a path-like lattice with diameter nine, and detours are everywhere.

Which means the only responsible thing to do is to check. It is an enumeration over $\sigma^3$ triples, it takes no time at all on any alphabet a person would use, and the answer is a fact about the model rather than a matter of opinion.

The symbol level is not the string level #

A substitution matrix that breaks the inequality does not automatically make the string distance break it, and this is worth separating carefully because the two are different claims.

A string distance is a minimum over alignments. Concatenating an optimal alignment of $x$ with $y$ and an optimal alignment of $y$ with $z$ gives an alignment of $x$ with $z$, and if every column of the concatenation cost at most the sum of the two columns it came from, the string inequality would follow from the symbol one. Where the symbol inequality fails, the concatenated alignment can cost less than the direct optimum — but the direct optimum is a minimum over all alignments, and it may find a cheaper route that has nothing to do with either.

So it has to be measured, and it was:

The rate at the string level (6.61%) is higher than at the symbol level (1.94%), which is the opposite of the intuition that the minimum smooths things out. Two-character strings give the minimum very little room to route around the offending pair, and doubling a letter doubles the violation: $d(\texttt{aa}, \texttt{dd})$ is twice $d(\texttt{a}, \texttt{d})$ and so is the detour, so the gap of 4 is twice the symbol-level gap of 2.

The rate falls as the alphabet widens — 12.70% over three letters, 2.72% over eight — for a reason that has nothing to do with the model getting better: a wider alphabet has more triples, most of them involving letters far apart on the keyboard where the costs are flat, and a flat region of a matrix satisfies the inequality trivially. The denominator grew faster than the numerator. A rate quoted without its alphabet is not a quantity.

What actually breaks #

The dynamic program does not break. It is a shortest path through a lattice and it computes the shortest path correctly whatever the edge weights are, provided they are non-negative. Every number in the previous two essays is right.

What breaks is everything built on top of the distance that assumed the inequality — and that is a large and mostly invisible category, because the assumption is usually a line in a proof rather than a line in the code.

The clearest case is pivot pruning, which is the mechanism under metric trees, ball trees, vantage-point trees and the pivot tables used for nearest-neighbour search over strings. All of them rest on one inequality:

$$\lvert d(q, p) - d(x, p) \rvert \le d(q, x)$$

Read it as a filter. If a query $q$ is at distance 9 from a pivot $p$ and a candidate $x$ is at distance 2 from the same pivot, then $q$ and $x$ are at least 7 apart, so a search with radius 5 can discard $x$ without computing $d(q,x)$ at all. That is the entire saving: the structure exists to avoid computing distances.

Under a non-metric score the bound is false, so the discarded candidate may well have been within the radius.

That is the shape of the failure worth internalising. The index does not crash, does not report an error, and does not return a wrong distance for anything it looks at. It returns fewer answers than there are, at a rate that depends on the data and the pivots, and there is nothing in its output to distinguish that from a query that genuinely had few answers.

It is the same shape as a bound quoted in the wrong model and a summary whose guarantee is about the rank: the machinery is working, the arithmetic is right, and the claim being relied on is about something else.

Two more places the word does damage #

Comparing scores across pairs. A score accumulates per column, so a long alignment scores worse than a short one for the same quality of match. Under a distance that is a count of edits this is at least an honest statement about how many edits there are; under a matrix it is a sum of surprisals, and comparing the totals of a twenty-character alignment and a two-hundred-character one is comparing two quantities with different expected values. Normalising by length is the usual repair and it is itself a model choice — dividing by the alignment length, by the shorter string, or by the longer one give three different orderings.

Clustering. Methods that pick a representative of a group — a medoid, a centre — are usually justified by an argument that the representative is close to everything the group contains, and the argument runs through the inequality. Without it a medoid can be further from a member than two members are from each other, and the group is no longer a description of anything.

What this site was quietly asserting #

This collection has always run a check that takes triples of random strings and requires $d(x,z) \le d(x,y) + d(y,z)$. It passes, it has always passed, and it was written before there was any such thing here as a cost model.

So what it has been asserting, precisely, is that the unit-cost distance is a metric — a true and worthwhile statement, made without the qualification that turns out to carry all the weight. The assertion is not wrong. It is a statement about one model, presented as a property of an operation.

That is the same shape as the plates that measured a dozen summaries under four unstated assumptions, and it is worth naming as a recurring failure rather than as two coincidences: a piece of machinery that is right under a fixed setting acquires the setting as a silent premise, and the premise becomes visible only when somebody makes the setting a parameter. The check now runs under a named model and there is a second check beside it requiring a stated matrix to fail — because an audit that only ever confirms is an audit that has stopped being one.

A fourth option, which repairs the matrix instead #

There is a repair that keeps the graded costs and restores the inequality, it costs one shortest-path computation over an alphabet-sized graph, and it is worth setting out because it turns the defect into a modelling error rather than an inherent limitation.

Take the matrix as the edge weights of a graph on the alphabet, and replace every entry by the cheapest path between its two symbols:

$$s'(a,c) \;=\; \min_{\text{paths } a \to c} \ \sum \text{steps}$$

The result satisfies the triangle inequality by construction — that is what a shortest-path metric is — and it can only lower entries, never raise them. On the keyboard model it takes $s(q,e)$ from 3 to 2, which is exactly the detour that broke the audit, and leaves every entry that was already consistent untouched.

What has changed is the model, and the change is defensible rather than a fudge. The original matrix prices a substitution as a one-step drift: the walk is run for a single step and the log-odds of that step is the cost. But a symbol that drifted from $q$ to $e$ over the life of the two sequences need not have done it in one step, and a model that charges it as though it had is charging for the wrong event. The shortest path is the cheapest explanation available in the same process, and pricing a substitution by its cheapest explanation is what a mutation model with an unbounded number of steps would have done in the first place.

So the failure is a consequence of truncating the walk, and the repair is to untruncate it. That also explains why the two nucleotide models pass the audit unrepaired: with four symbols in two classes there is no third symbol that is nearer to both endpoints than they are to each other, so every path of two steps already costs at least the direct one and the closure changes nothing.

Two caveats, both small and both worth stating. The closure is not free of consequences for the alignments: lowering a substitution cost makes substitutions more attractive relative to gaps, so the ratio the earlier essay is about has moved and the alignments can change. And the closure is a fact about the alphabet rather than about the strings, so it is computed once at model-construction time and never again — which makes it, of the three options above, the only one that costs nothing per query.

What survives without the inequality #

If none of the repairs is taken, it is worth knowing precisely what still works, because the answer is not “nothing”.

Exhaustive comparison is unaffected. A scan that computes the score against every candidate and keeps the best returns the right answer whatever the score is, because it prunes nothing. Everything in this essay is about structures that avoid computing scores, and a structure that computes all of them has nothing to be wrong about.

Symmetry and non-negativity are enough for a great deal. Sorting candidates by score, thresholding, reporting the nearest — all of those need only that the number is well defined and comparable, and all three hold here.

Indexes exist for non-metric spaces — permutation-based, learned, or built on a weaker property such as a bounded violation of the inequality — and they are the honest answer when a graded model is genuinely required and the alphabet does not admit a metric one. None of them is built in this collection, so nothing here says what they cost; what can be said is that the choice is between a structure designed for the space in hand and a structure that assumes a property the space does not have, and only one of those has a failure mode that is silent.

What to do about it #

Three options, and the first two are the honest ones.

Check, then use it. The audit is an enumeration over triples of symbols and a second over triples of short strings. If both come back clean — as they do for the nucleotide models here — every distance-based structure is safe and there is nothing to think about.

Use a metric where a metric is needed. Unit cost is one. So is any model whose substitution costs are themselves a metric on the alphabet, because the concatenation argument then goes through. Where a graded matrix is wanted for accuracy and an index is wanted for speed, that is a real trade-off with a real decision in it, and it should be made rather than discovered.

Or stop calling it a distance. The tools that use these models seriously do not: they report scores, they maximise rather than minimise, and they organise their indexes by seeds and exact matches rather than by distance. That is not an accident of vocabulary. A field that never says “distance” never invites the substitution that this essay is about.

The word is where the mistake lives. Every one of the failures above comes from taking a number that behaves like a distance in three respects out of four, and handing it to a structure that needs all four.