Wizhut Research · Evaluation
Ordering an autocomplete list with nothing but the strings
Every autocomplete box does two jobs. It filters the catalogue down to what begins with the typed text, and then it orders what is left — the job people notice, because the right suggestion either comes first or it does not. Kyori, our open-source JavaScript string library, carries a ranking cost built for that second job: four ordered rules and a tie-break, with no popularity data, no model and no index. This page is where Kyori 0.5.0 stands: how well it orders real searches, measured against the libraries applications already use.
On 11,607 AmazonQAC prefixes the design never saw. Level with Fuse.js, fuzzysort and sorting by length: no gap between them survives a significance test.
Among equal costs, the shorter completion first. It cuts tied cases from 85% to 47%, and the gain holds on the split it was not chosen from.
Ordering by how often people search for a completion beats every string method. It is the one signal that separates candidates of equal length.
Among the slower keys measured. Three quarters of it goes on normalising the same strings again, not on the rules.
Kyori 0.5.0
The cost compares what was typed with one candidate: 0 is a perfect match, lower is better, and the first rule that applies decides. There are no weights, nothing learned and no frequency data, so the same pair costs the same everywhere. Each rule has a precedent in error-tolerant search; what is Kyori’s own is the arrangement, the constants and the last rule’s formula.
Equal as typed, or equal once both strings are folded: accents stripped, lowercase, dashes read as spaces.
The same words as a bag, reordered: "hotel bel-air" against "bel-air hotel".
The fewest edits between what was typed and any start of the candidate, first letter fixed; the unread rest is free. No typo below three typed characters, one for 3–5, two for 6–8.
The length difference, plus how far each typed word lands from where it was typed, its length again if it only matches mid-word, and its typo distance to the nearest word when it is missing.
rank() sorts by the cost, then by the candidate's length, then alphabetically; rankKey() is that order as one number.
The library’s similarity() is a different function on purpose: the share of words two strings have in common. It never looks at characters, and it is not meant as a ranking key — the results below say why.
The evaluation · 11,607 held-out prefixes
The data is AmazonQAC, the query-autocomplete dataset Amazon published at EMNLP 2024: real prefixes people typed into a search box, each with the search it ended in. Each candidate list is exactly what a typo-tolerant prefix filter returns from the catalogue, and ties are reported rather than broken by the alphabet. Kyori was designed on the test split, so the figures that count come from a sample of the train split drawn afterwards and never consulted — and every comparison is tested case by case, corrected across all 19.
Mean reciprocal rank is 1 when the answer comes first, ½ when it comes second, and so on, averaged over every case. The band is how far a tie policy alone could move each score: a narrow band means the method decided the order itself. Every figure was measured on the code released as Kyori 0.5.0.
| Method | Test split | Held out | Band | Tied | In top 10 |
|---|---|---|---|---|---|
Most popular completion Prefix matches, most searched first | — | 0.422 | 0.413–0.448 | 18% | 0.638 |
Kyori 0.5.0 The cost, then shorter first | 0.409 | 0.404 | 0.393–0.416 | 47% | 0.616 |
ORDER BY length The zero-library rule | 0.408 | 0.403 | 0.385–0.441 | 50% | 0.615 |
fuzzysort 4 Subsequence match | 0.409 | 0.403 | 0.390–0.421 | 47% | 0.617 |
Fuse.js 7 Bitap match, weighted by length | 0.408 | 0.402 | 0.355–0.499 | 66% | 0.612 |
match-sorter 8 Match tiers | 0.389 | 0.376 | 0.276–0.942 | 82% | 0.582 |
Kyori, cost alone No tie-break | 0.381 | 0.368 | 0.257–0.988 | 85% | 0.577 |
Character trigrams Trigram cosine | 0.369 | 0.365 | 0.364–0.411 | 15% | 0.591 |
Jaro–Winkler Name-matching similarity | 0.357 | 0.353 | 0.343–0.365 | 48% | 0.594 |
Kyori similarity as a key Word overlap | 0.279 | 0.271 | 0.210–0.706 | 82% | 0.460 |
Damerau–Levenshtein Edit distance | 0.267 | 0.257 | 0.245–0.272 | 64% | 0.459 |
Expected values under a random order inside ties. Most-popular-completion needs Amazon’s search counts, which only the train split carries, so it has no test-split score. “In top 10” is the share of cases where the answer is among the first ten suggestions.
Kyori over sorting by length, the same on both splits and significant on neither once corrected (p = 0.21 and 0.24). Level, not ahead.
Kyori over match-sorter, whose tiers leave 82% of cases tied. A real gap: p < 0.01 after correction.
The cost over the library’s own similarity used as a key — the case for keeping ranking and resemblance as separate functions.
By list size
The same held-out cases, split by how many candidates the filter returned. Ordering nine completions of a long prefix and ordering a thousand completions of one letter are different jobs, and the three rankers below tell them apart.
| Candidates | Cases | Kyori, cost alone | Kyori 0.5.0 | Most popular completion |
|---|---|---|---|---|
| 2–9 | 3,172 | 0.759 | 0.787 | 0.787 |
| 10–49 | 2,259 | 0.454 | 0.499 | 0.519 |
| 50–199 | 2,428 | 0.202 | 0.248 | 0.273 |
| 200–999 | 2,869 | 0.115 | 0.151 | 0.185 |
| 1000+ | 879 | 0.014 | 0.032 | 0.036 |
Where Kyori stands
The question was whether a cost assembled from known parts could order a filtered list better than what applications already use. It orders it as well, not better — and the evaluation shows where the order of such a list actually comes from.
The four string methods at the top share one idea. Sorting by length has nothing else, Fuse.js weighs field length, fuzzysort subtracts the candidate's length from its score, and Kyori breaks its ties that way. Once a list already starts with what was typed, "shorter first" is most of what a string can say.
Most-popular-completion leads by 0.018 (interval 0.013–0.022) and is the only method that separates candidates of equal length. It is level with Kyori on lists of 2–9 and ahead from ten candidates up — and still below 0.04 past a thousand.
As a measure of resemblance, Kyori's word-overlap similarity trails the methods that weigh rare words up: character trigrams lead it by 0.172 on Abt–Buy's product titles. On 400 real misspellings the cost trails Jaro–Winkler by 0.058 and is level with Damerau–Levenshtein. Its strength is the typed prefix and the reordered phrase, not spelling correction.
Every method is interactive on autocomplete lists, and 95% of Kyori's queries finish within 2 ms. A profile puts 76% of the ranking key's time into normalising strings — both are folded again on every comparison — while the rules themselves are cheap.
One catalogue: US product searches on Amazon from September and October 2023. The catalogue is built from the evaluated searches themselves, so every answer is in it; a real catalogue is larger and sometimes lacks the answer. Amazon’s counts bound that from below — 1.8% of held-out answers were searched only once that month, and scoring them as misses costs every method about 0.008. The filter admits a typo in only 8% of cases, so typo handling is lightly exercised. There is no session or user signal, the timings come from one machine, and the misspellings are set against random words rather than near ones. Read the direction of the results and the tested gaps, not the third decimal.
Open source
Kyori is MIT-licensed: five string metrics behind one API, the ranking cost measured on this page and a ready-made autocomplete index, in plain JavaScript with no heavyweight dependencies. Version 0.5.0 is the code every figure here was measured on.