Wizhut Research · Progress report
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 is where the study stands after seven versions.
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. Tied cases fell from 85% to 47%, and the gain held 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, which is the next thing to fix.
Progress
Kyori began as a single score for everything and was reshaped for autocomplete over the summer. Most of what this page reports happened in one week of September, once the benchmark was rebuilt to measure ordering the way autocomplete research does — and the numbers it produced started to disagree with the design.
The length difference between two strings, plus how far each typed word lands from where it was typed, and a missing word's full length. It survives, much changed, as the last of today's four rules.
Accents, case and dashes stop counting; a typed word found at the start of a word beats one found mid-word; a word that is missing is charged its typo distance to the nearest one.
What has not been typed yet stops costing anything, a typo inside what was typed costs its edits, and the same words in another order cost a flat 1. One misnamed score becomes three contracts: distance, similarity and rank.
Candidate lists become exactly what a prefix filter returns, ties are reported instead of broken alphabetically, and a held-out split is drawn. Measured that way, v4 scored 0.382 with the answer tied in 85% of cases: the order had been the alphabet's.
Among equal costs, the shorter completion wins. 0.409 on the test split, confirmed the same day on the held-out split: 0.404, against 0.368 without it.
A typed prefix is charged the fewest edits to any start of the candidate, so a missed or doubled letter costs 1 instead of 2. Ranking unchanged; misspellings 0.846 → 0.861.
The threshold Lucene's and Elasticsearch's fuzzy suggesters use. Identical on the benchmark, whose lists are already filtered that way; it matters wherever a list is ranked without a filter in front.
Paired significance tests for each comparison the results rest on, and per-query timings for every contestant on two workloads.
Versions 5 to 7 ship to npm as 0.5.0 — the code every figure on this page was measured on.
The method
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 name matching or error-tolerant search, named beside it — 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.
Worked examples
These are outputs of Kyori 0.5.0 as published on npm, not illustrations. The cost is deterministic, so every number below comes back identical on every run and on every machine. Where the previous release answered differently, its answer is shown beside the new one.
| Typed → candidate | Rule | Cost |
|---|---|---|
foo → food A typed prefix. What has not been typed yet costs nothing. | R3 | 0 |
fod → food One edit from the start of the candidate. | R3 | 1 |
dishwaher → dishwasher pods One missed letter. The previous rule compared the first nine letters as they stood, where the gap shifts every letter after it, and charged 2. | R3 | 21 |
ab → ax pens Two typed letters allow no typo, so this is not a prefix match. It used to cost 1, the same as every other candidate starting with "a". | R4 | 16 |
hotel bel-air → bel-air hotel The same words, reordered. | R2 | 1 |
pizza → margherita pizza A later-word match pays its position and the length gap, which is why typed prefixes are routed around this rule. | R4 | 22 |
A struck-through number is what the previous release, 0.4.1, returned for the same pair.
Typed: circle. All three are AmazonQAC final searches that begin with it, so all three cost 0 — and until 0.5.0 the alphabet decided their order.
“stickets” is how the searcher typed it. On a list that already starts with what was typed, the shorter completion is the better bet: that preference is where the +0.036 above comes from.
npm install @wizhut_tech/kyori@0.5.0, then:
const { kyori } = require( '@wizhut_tech/kyori/methods/kyori') kyori.distance('dishwaher', 'dishwasher pods') // → 1 kyori.distance('ab', 'ax pens') // → 6 kyori.rank('circle', [ 'circle time pointer', 'circle placemats', 'circle stickets', ]) // → stickets, placemats, time pointer
The protocol
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. Its test split gives 20,000 prefixes, of which 11,440 have a list worth ordering; a held-out sample of its train split gives another 20,000, of which 11,607 do.
A ranking test is only as honest as its candidate list. Each list here is what a typo-tolerant prefix filter returns from the catalogue: entries that start with what was typed, or come within one typo of it once three characters are typed. Nothing is planted and nothing is sampled, and a case counts only when the filter kept the answer and left at least two candidates to order.
Many rankers give whole groups of candidates the same score and let the alphabet settle the rest. Every figure here is the expected result under a random order inside each tie, shown with the band a tie policy alone could move it across. An alphabetical fallback earns nothing.
Four of Kyori's versions were designed while looking at the test split. So 20,000 rows of the train split were drawn afterwards with a fixed seed, and never consulted. Every comparison is tested case by case — a paired bootstrap interval and a randomisation test, corrected across all 19 comparisons.
Ranking · 11,607 held-out prefixes
Mean reciprocal rank is 1 when the answer comes first, ½ when it comes second, and so on, averaged over every case. The contestants are the typeahead libraries a JavaScript application would otherwise reach for, the zero-library rule of sorting matches by length, and the most-popular-completion baseline of the autocomplete literature. The band is how far a tie policy alone could move each score: a narrow band means the method decided the order itself.
| 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, as in 0.4 | 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 |
Similarity and distance
The library keeps three contracts apart, so each was measured on its own ground: resemblance on the product and paper titles of four entity-matching benchmarks, where the true match has to rise to the top of the whole other table, and edit cost on 400 real misspellings.
| Method | Abt–Buy | Amazon–Google | DBLP–ACM | Fodors–Zagats | Misspellings |
|---|---|---|---|---|---|
| Character trigrams | 0.900 | 0.849 | 0.995 | 0.978 | 0.846 |
| Soft TF–IDF | 0.844 | 0.849 | 0.993 | 0.985 | — |
| TF–IDF | 0.777 | 0.840 | 0.994 | 0.985 | — |
| Kyori | 0.728 | 0.785 | 0.993 | 0.981 | 0.863 |
| Jaro–Winkler | 0.638 | 0.456 | 0.985 | 0.960 | 0.921 |
| Monge–Elkan | 0.628 | 0.709 | 0.986 | 0.949 | — |
| Damerau–Levenshtein | 0.582 | 0.582 | 0.990 | 0.902 | 0.874 |
Mean reciprocal rank. Kyori’s row is its similarity on the four title benchmarks (1,081, 1,098, 2,200 and 112 cases) and its cost on the misspellings (400). DBLP–ACM and Fodors–Zagats are saturated for every method and do not separate them.
Kyori’s similarity counts shared words and weighs them all alike, so it sits behind the methods that weigh rare words up — character trigrams lead it by 0.172 on Abt–Buy and 0.064 on Amazon–Google — and ahead of the edit metrics. A model number or a brand carries the signal in a product title; plain overlap treats it like “the”.
On a misspelling against its word and 49 others, the cost trails Jaro–Winkler by 0.058 and is level with Damerau–Levenshtein (p = 0.26). Version 6 closed most of the gap to Damerau: a missed or doubled letter had been charged twice. Kyori’s strength is the typed prefix and the reordered phrase, not spelling correction.
Efficiency
Timed the way an application pays for it: build whatever the method needs for the list, score every candidate, sort. Two workloads — the held-out autocomplete lists, four typed characters at the median, and 1,081 product names of about fifty characters each ranked against a fixed list of 1,079 — on one core of an Apple M4 Max under Node 26.
| Method | Autocomplete, median | Slowest 5% | Long names, median |
|---|---|---|---|
| Soft TF–IDF | 220 µs | 3.9 ms | 16 ms |
| Kyori 0.5.0 | 120 µs | 2.0 ms | 21 ms |
| Kyori similarity | 74 µs | 1.3 ms | 4.0 ms |
| Fuse.js 7 | 72 µs | 1.2 ms | 51 ms |
| Damerau–Levenshtein | 37 µs | 0.38 ms | 14 ms |
| Most popular completion | 26 µs | 0.55 ms | — |
| ORDER BY length | 26 µs | 0.52 ms | 0.88 ms |
| Jaro–Winkler | 17 µs | 0.28 ms | 5.7 ms |
| fuzzysort 4 | 17 µs | 0.28 ms | 0.05 ms |
Per query, one core. Every method is interactive on autocomplete lists: 95% of Kyori’s queries finish within 2 ms, and its median past a thousand candidates is 2.4 ms. On long names the methods that compare every character pair separate from the rest, while fuzzysort rejects most names before reading them.
What we learned
The study set out to see 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 on the way it located 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.
Without its tie-break, Kyori's cost left the answer tied in 85% of held-out cases, in groups averaging 227 candidates, with a band from 0.257 to 0.988. A benchmark that breaks ties alphabetically would have reported wherever in that band the alphabet happened to land.
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.
The typed-prefix rule is the prefix edit distance of error-tolerant autocompletion, which Lucene and Elasticsearch ship; the reordering rule is token sort. Two of the seven versions came from reading that prior art rather than from a benchmark. What is Kyori's own is the arrangement, the constants and the fallback formula.
Used as a ranking key, Kyori's word-overlap similarity is 0.133 behind its cost; used for resemblance, it trails the IDF-weighted methods on product titles. Keeping ranking and resemblance as separate contracts holds up, and the similarity side has the most room to grow.
A profile puts 76% of the ranking key's time into normalising strings: both are folded again on every comparison, and the tie-break folds the candidate a second time. The rules themselves are cheap. The fix belongs in the library, not the algorithm.
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, the misspelling group’s distractors are random words, and two of the four title benchmarks are saturated. Read the direction of the results and the tested gaps, not the third decimal.
Does the cost earn a place in front of popularity? Kyori’s cost with search counts as the tie-break, against most-popular-completion alone, on the held-out split with a paired test. If it wins, a string rule and a count belong together; if it does not, the advice to applications is to filter with a string rule and order by counts.
How fast is it with each string folded only once? Normalise the typed text once per call and each candidate once, then measure what is left of the 120 µs. The rules should cost a fraction of it.
Can a third sort key break the ties that remain? Character trigrams leave only 15% of cases tied. After the cost and the length, can they separate equal-length candidates without a popularity signal?
Harder tests for the other two surfaces. Misspellings against near words rather than random ones, reproducible generators for the spelling and synthetic-prefix groups, and a similarity that weighs rare words up.
Every figure on this page was measured on the code released as Kyori 0.5.0. A change to the cost invalidates all of them: the tables, the chart and the worked examples are regenerated together, and the report date moves with them.
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.