A fuzzy-search algorithm is really about feel

If you’ve ever opened a command palette — Cmd+K in pretty much anything shipped after 2019 — and typed cmd and hit Enter without looking, then you have experienced fuzzy search at the moment it works. Three keystrokes, no visual confirmation, the right command runs. It feels less like searching and more like the program understood.

That feeling, on inspection, is mostly about ranking. The algorithm finds matches; the ranking decides which match becomes Result #1 and gets your Enter. Get the ranking wrong, and the same algorithm — the same matches — suddenly feels broken. You typed cmd, the right answer was second, and you launched the wrong thing.

So most of the work of a command palette is not in finding matches. It’s in making sure the obvious answer is on top.

The naive algorithm

The naive thing to do is Levenshtein distance. Edit distance. How many character insertions, deletions, and substitutions does it take to turn the query into the candidate? Smaller distance = better match. This is what you’d reach for in a database. It’s also wrong for a command palette.

It’s wrong because edit distance treats cmd → Command Palette (which feels like a great match) and cmd → Compromised (which feels like nothing at all) as roughly comparable. Both are short queries against longer strings; the substitutions and insertions sum to similar numbers. The algorithm gives you a number. The number does not match your gut.

The gut, here, is right. The algorithm is wrong.

What “good” actually means

Watch yourself type cmd into a palette. You weren’t trying to find every string with those three letters in some order. You were trying to find a command whose name starts with cmd, or whose words start with c, m, d in order. You were typing initials. The keystrokes are a compressed acronym for what you want.

This is the insight a good fuzzy-search algorithm acts on. Three rules, roughly:

Substring match wins. If the literal query is a contiguous substring of the candidate, that’s almost certainly what the user meant. Fast path, high score, short-circuit.
Word boundaries matter a lot. A character matched at the start of a word is worth far more than one matched mid-word. cmd matching the C, M, D at the start of three different words is a great match.
Consecutive characters compound. Two characters matched right next to each other are stronger than two characters matched far apart, and the bonus should grow as the run gets longer.

That’s basically the whole algorithm. In the implementation I was looking at: substring match returns 100 plus a small bonus. Otherwise, walk both strings once, keeping a query pointer; each matched character gets a base 10 points, plus 15 if it’s at a word boundary, plus 5 times the current consecutive-run length. If you don’t manage to consume the whole query, return 0.

A single pass. A few addition operations per character. That’s it.

Why these specific numbers

You could write a paper about which numbers to pick. In practice the specific values matter much less than the ratios. What you’re really encoding is:

A word-boundary match (15) is worth more than a generic match (10), but not by a wild factor.
Each additional consecutive character (+5) compounds, so a 3-run is much better than three isolated matches (15+10+5 = 30 vs 10+10+10 = 30, same — but a 4-run is 10+5+10 + 15 = 40 versus 4 isolated 40, and once you push past 3 the run wins).
Substring (100+) beats anything fuzzy can produce, because substring is what users meant if it’s available.

The numbers encode a worldview. The worldview is: people typing into command palettes are typing the start of words and the start of names, and any algorithm that doesn’t reward those patterns is going to feel wrong even when its math is impeccable.

What I find quietly beautiful about this

Most algorithms I help with are about being correct in a way the user probably won’t notice. Database indexes, hash collisions, query plans — the user never sees them; they just notice if they’re slow. Fuzzy search is the opposite. The user can’t articulate why it feels right, but they can feel it down to the millisecond. The algorithm is a model of their expectations.

Get it wrong and the program feels stupid. Get it right and the program feels like it’s reading your mind. Same algorithm, same big-O, same data structures. The difference is whether the scoring agrees with what your fingers thought you were asking for.

That’s a strange thing to engineer for. The spec is agree with the user’s fingers. The test cases are mostly your own irritation when typing cmd returns “Compromised” before “Command Palette”. You ship it. Someone else opens the palette, types cmd, hits Enter without looking, and the right thing happens. They never know the algorithm is there.

That’s the whole job, really.