What is the triangle inequality?

The triangle inequality states that traveling directly between two points is never longer than traveling through some third point along the way, a property that sounds obvious for physical distance but has to be checked explicitly for any distance function used in vector search, since not every measure of dissimilarity actually satisfies it.

What does the triangle inequality actually guarantee?

For any three points, the direct distance between the first and the third can never be greater than the distance from the first to the second plus the distance from the second to the third. Picture three cities on a map: the straight-line trip between two of them is never longer than a trip that stops at the third city along the way, even if that third city happens to sit roughly along the route. This holds for straight-line distance in physical space almost by definition, but it’s a property that has to be proven or checked for any other distance function, since plenty of functions that measure how dissimilar two things are don’t actually behave this way.

Why does this property matter specifically for graph-based search algorithms?

HNSW’s search process relies on repeatedly moving toward whichever neighboring vector looks closest to the query, gradually narrowing in on a good answer without ever comparing the query against every single vector in the index, covered in more depth in this site’s coverage of how proximity graphs support search. The triangle inequality is part of what justifies this shortcut-taking behavior: if a vector is already known to be far from the query, and a candidate neighbor is close to that far vector, the triangle inequality gives a way to reason about how far that neighbor might plausibly be from the query without measuring it directly. Distance functions that satisfy the triangle inequality, forming a proper metric space as covered elsewhere in this glossary, support this kind of reasoning cleanly; distance functions that don’t satisfy it can still be searched with HNSW in practice, just without the same theoretical backing for why the search behaves reliably.

Do all the common distance functions used in vector search actually satisfy the triangle inequality?

Euclidean distance and Manhattan distance, both covered elsewhere in this glossary, are textbook examples of distance functions that satisfy the triangle inequality without exception, which is part of why they remain such common defaults. Cosine distance satisfies it too, though only for certain formulations, which is a detail worth being aware of if a system’s correctness depends on the property holding in every case. Plenty of other dissimilarity measures used in practice, covered in this site’s page on non-metric dissimilarity functions, don’t satisfy the triangle inequality at all, and systems using them lean more heavily on empirical tuning and testing than on formal guarantees to confirm the search still performs well.

The triangle inequality is one of the core properties that separates a true metric from a more general dissimilarity measure, and it’s worth keeping in mind whenever evaluating whether a distance function’s theoretical guarantees can be relied on. From here, the pages on metric space and on non-metric dissimilarity functions cover the two sides of this same distinction in more detail.