In a search-box typeahead, how can suggestions tolerate a typo in the typed prefix without breaking the latency budget?

## What typo tolerance means here Users mistype. If the prefix `iphoen` returns nothing, the dropdown fails exactly when it could help most. **Typo tolerance** lets a typed prefix match stored completions whose prefix is within a small **edit distance**: the number of single-character insertions, deletions, substitutions and, in some variants, transpositions of adjacent characters needed to turn one string into the other. The difficulty is cost. Exact prefix lookup follows one path; fuzzy lookup can follow many. ## Why the naive approach explodes An illustrative count for a 6-character prefix over a 26-letter alphabet, one edit: 1. deletions: 6 2. substitutions: 6 x 25 = 150 3. insertions: 7 positions x 26 letters = 182 4. transpositions: 5 That is about **343** candidate strings, some of them duplicates, each requiring its own lookup. Allowing two edits multiplies the count again into the tens of thousands. At per-keystroke rates this breaks the budget. ## Techniques that keep it bounded - **Length-dependent limits.** Allow no edits for one- or two-character prefixes, one edit for medium lengths, and at most two for long prefixes. At very short lengths a single edit matches a large share of all stored prefixes, so fuzziness adds mostly noise and little recall. - **Automaton intersection.** A **Levenshtein automaton** accepts every string within distance d of the typed prefix. Walking it together with the trie or FST means a branch is abandoned as soon as it can no longer stay within d, so only viable paths are explored and no variant list is generated. - **Anchored first characters.** Some systems treat the first character as correct. This is a heuristic, resting on the assumption that first-letter typos are less common, and it sharply narrows the search. - **Fallback only.** Run the exact pass first and the fuzzy pass only when it returns fewer than the desired number of suggestions. - **Work caps.** Stop after visiting a fixed number of nodes or collecting enough candidates, and return what was found. ## Learning corrections from logs Query logs contain **reformulations**: a user types `recieve`, gets poor results, and immediately types `receive`. Aggregating those pairs offline yields a **correction map** from common misspelled prefixes to canonical ones. At request time a map lookup handles the frequent typos cheaply, and the automaton handles the rest. Keyboard-adjacency weights, such as treating a substitution by a neighbouring key as cheaper, refine the ranking further. ## Ranking fuzzy against exact | Match kind | Typical treatment | |---|---| | Exact prefix match | ranked by its normal score | | One edit | score multiplied by a penalty, for example 0.5 | | Two edits | larger penalty, or shown only if space remains | | Correction-map hit | treated close to exact, since users confirmed it | The penalties are illustrative. The principle is that an exact match the user is literally typing should rarely be displaced by a fuzzy guess, while a very popular fuzzy match can still earn a slot when exact matches are weak. ## Interaction with the rest of the design - **Caching.** Fuzzy results for short prefixes are usually disabled anyway, so the short-prefix cache is unaffected; longer fuzzy results are rarely worth caching. - **Precomputation.** Top-k lists stored per node still help: once the automaton reaches a viable node, its stored list supplies candidates without descending further. - **Multiple scripts.** Edit distance over characters behaves differently across writing systems, so per-locale limits are common. ## Summary Typo tolerance is affordable when it is bounded: small, length-aware edit limits, automaton-guided traversal instead of enumeration, exact matches first, fuzzy passes as a fallback, and cheap correction maps for the common mistakes.