M0 gate (G0) results, 2026-09-23 (branch m0/prototype, harness run on 2026-09-23)
Summary
G0 is a PARTIAL PASS: speed passes, ranking quality does not.
- Oracle equality (exact top-k identical to brute force, both TSB modes): PASS.
cargo test -p keyhammeris green. - Latency: PASS. At 274137 words, p95 of the best new mode (new+tsb) is 123.0x lower than the legacy engine (need at least 10x).
- Ranking (MRR of the best new mode at least the baseline "unit edit distance <= 2, then higher weight, then id"): FAIL. 0.389 vs 0.433 at 274137 words, 0.442 vs 0.474 at 100000, 0.526 vs 0.533 at 10000. It fails at every dictionary size and the gap grows with size.
Results
Test suite (cargo test -p keyhammer): cost 9, edge_cases 10, oracle 8, trie 8 tests passed; 0 failed.
Benchmark: 300 typo pairs, three dictionary sizes. Latencies in microseconds; nodes/query is trie nodes expanded per query (new engine only).
10000 words
| Engine | MRR | R@1 | p50 (us) | p95 (us) | nodes/query |
|---|---|---|---|---|---|
| legacy | 0.430 | 0.393 | 258.5 | 1248.0 | n/a |
| baseline | 0.533 | 0.507 | 2160.7 | 2991.4 | n/a |
| new | 0.526 | 0.510 | 108.3 | 151.5 | 731 |
| new+tsb | 0.526 | 0.510 | 87.9 | 117.9 | 489 |
100000 words
| Engine | MRR | R@1 | p50 (us) | p95 (us) | nodes/query |
|---|---|---|---|---|---|
| legacy | 0.313 | 0.253 | 2685.7 | 18421.6 | n/a |
| baseline | 0.474 | 0.437 | 21845.2 | 30657.0 | n/a |
| new | 0.442 | 0.397 | 249.4 | 360.4 | 1385 |
| new+tsb | 0.442 | 0.397 | 203.7 | 290.5 | 907 |
274137 words (full dictionary)
| Engine | MRR | R@1 | p50 (us) | p95 (us) | nodes/query |
|---|---|---|---|---|---|
| legacy | 0.255 | 0.197 | 7434.2 | 44691.7 | n/a |
| baseline | 0.433 | 0.387 | 59450.7 | 79726.6 | n/a |
| new | 0.389 | 0.330 | 299.7 | 462.4 | 1486 |
| new+tsb | 0.389 | 0.330 | 246.3 | 363.2 | 986 |
Literal harness output (cargo run --release -p keyhammer-bench --bin m0 -- bench/data):
300 typo pairs
=== dictionary: 10000 words (10000) ===
new MRR=0.526 R@1=0.510 p50= 108.3us p95= 151.5us nodes/query=731 build=2ms
new+tsb MRR=0.526 R@1=0.510 p50= 87.9us p95= 117.9us nodes/query=489 build=2ms
legacy MRR=0.430 R@1=0.393 p50= 258.5us p95= 1248.0us
baseline MRR=0.533 R@1=0.507 p50= 2160.7us p95= 2991.4us
=== dictionary: 100000 words (100000) ===
new MRR=0.442 R@1=0.397 p50= 249.4us p95= 360.4us nodes/query=1385 build=25ms
new+tsb MRR=0.442 R@1=0.397 p50= 203.7us p95= 290.5us nodes/query=907 build=25ms
legacy MRR=0.313 R@1=0.253 p50= 2685.7us p95= 18421.6us
baseline MRR=0.474 R@1=0.437 p50= 21845.2us p95= 30657.0us
=== dictionary: 274137 words (full) ===
new MRR=0.389 R@1=0.330 p50= 299.7us p95= 462.4us nodes/query=1486 build=65ms
new+tsb MRR=0.389 R@1=0.330 p50= 246.3us p95= 363.2us nodes/query=986 build=65ms
legacy MRR=0.255 R@1=0.197 p50= 7434.2us p95= 44691.7us
baseline MRR=0.433 R@1=0.387 p50= 59450.7us p95= 79726.6us
=== G0 (largest dictionary) ===
p95 legacy / new = 123.0x (need >= 10x): PASS
MRR new 0.389 vs baseline 0.433 (need >=): FAIL
oracle equality: run `cargo test -p keyhammer` (must be green)
The oracle line in the harness output is a pointer to the test suite, not a measurement; see the test counts above.
TSB effect
Note (2026-09-24): new+tsb is now literally SearchConfig::default(); SearchConfig::default() had tsb = false when these runs were made, and the rows set it explicitly. See tsb-default.md for the decision and a re-measurement. The re-measured node counts in tsb-default.md differ slightly from the table below because the rows now use Ranking::Coarse; the numbers below are kept as measured.
Real typo data (the 300 Birkbeck pairs, from the harness): TSB expands about 33-35% fewer trie nodes per query, with identical MRR and R@1, and lower p50 and p95 latency.
| Dictionary | nodes/query new | nodes/query new+tsb | Reduction |
|---|---|---|---|
| 10000 | 731 | 489 | 33.1% |
| 100000 | 1385 | 907 | 34.5% |
| 274137 | 1486 | 986 | 33.6% |
The design hypothesis was at least 30% fewer nodes; it holds on this data.
Separate and informational, from different data: a unit test on 200 RANDOM queries against a 2000-word RANDOM dictionary pushed 88526 queue entries without TSB vs 58014 with it (34.5% fewer, identical hits). This is a count of queue entries, not of expanded nodes, and it is not from the typo corpus.
Why the ranking may lose (hypotheses)
These are UNTESTED HYPOTHESES, not findings.
- The new engine uses weighted costs (neighbouring-key substitution 8 vs 16, doubled-letter edits 8, transposition 12, first-position multiplier 1.5, unit costs 16). Weighted costs mostly do not tie, so the frequency weight may only break rare exact ties. The baseline uses integer edit counts, so many candidates tie and frequency decides.
- The QWERTY-adjacency prior may not match the human errors in this corpus. The Birkbeck corpus may contain many spelling and phonetic errors, not only finger slips.
Suggested next experiments (not run):
- Bucket the cost to whole edits (
ceil(cost/16)) before applying weight. - A blended ranking
cost - lambda*weight. - A run with all costs set to unit, to check that the engine then reproduces the baseline MRR (a sanity check of the ranking path).
Caveats
- One machine, one run; latencies vary from run to run. MRR, R@1 and nodes/query are deterministic by construction (no randomness in either engine or the data files); only one run was made.
- 300 typo pairs from the Birkbeck corpus; dictionary of English words, a-z only.
- Costs are provisional; there was no calibration.
- Final tie-break ids differ between engines: the new engine uses byte-sorted term order, the baseline uses the row index in the shuffled words file. Many words have weight 0, so ties among them are broken alphabetically in one engine and randomly in the other. We expect this to be noise rather than a systematic bias; this was not measured.
- The baseline latency is inflated (its edit-distance routine allocates a matrix per candidate) and is not gated.
- The harness has no warm-up.
- Rust-only numbers, with no JS binding overhead.
- The legacy row is the previous engine (
keyhammer-legacy) with max edit distance 2.
Prior art
See docs/papers.md. Every ingredient of the TSB is already published; only the combination was not found in the works read. The search was limited, so this is not a claim of novelty.
Verdict and next step
G0 applies as a partial pass: speed is well beyond the gate and the TSB reduces work as hypothesised, but ranking quality is below the baseline at every size. The options are: G0 passed, plan F1; G0 partial (speed ok, MRR below baseline), adjust costs or ranking and repeat M0 before F1; G0 failed, rethink the approach. The suggested next step, which the author may reject, is the partial branch: run the experiments listed above and repeat M0 before F1.
Addendum (2026-09-24): ranking by rounded cost
The original report above is left as it was measured; this section records a later change and a new harness run.
What changed and why
The engine used to rank results by the exact weighted cost, then weight, then id. It now ranks, by default (Ranking::Coarse), by the weighted cost rounded up to whole units of 16 (cost::whole_units), then higher weight, then id; the weighted costs still set the budget and generate the candidates, and Hit::cost is still the exact weighted cost. Ranking::Exact keeps the previous order and is reported as new+tsb/exact. The rounded cost is not a count of edits: the x1.5 factor on the first byte makes an ordinary (non-neighbouring-key) edit there cost 24, i.e. two units, while a neighbouring-key substitution there costs 12 (one unit) and a transposition 18 (two units); two cheap edits (8 + 8) count as one. For example, for the query bat with cat (weight 200) and bad (weight 100), both one edit away, bad (cost 16) ranks before cat (cost 24) under both rankings; a test pins this behaviour. The change was motivated by hypothesis 1 of the original report (the frequency weight rarely decides with fine-grained costs); the result below is consistent with that hypothesis, but the hypothesis itself was not tested (see "Ties" below). The oracle tests check the exact top-k for both rankings, with and without TSB.
Results
Test suite (cargo test -p keyhammer): cost 10, edge_cases 13, oracle 9, trie 8 tests passed; 0 failed.
Same 300 typo pairs and dictionaries as above. Latencies in microseconds; nodes/query is trie nodes expanded per query.
| Dictionary | Engine | MRR | R@1 | p95 (us) | nodes/query |
|---|---|---|---|---|---|
| 10000 | new+tsb (rounded cost, default) | 0.541 | 0.527 | 120.4 | 491 |
| 10000 | new+tsb/exact (previous order) | 0.526 | 0.510 | 122.1 | 489 |
| 10000 | baseline | 0.533 | 0.507 | 2799.9 | n/a |
| 100000 | new+tsb (rounded cost, default) | 0.470 | 0.430 | 289.8 | 911 |
| 100000 | new+tsb/exact (previous order) | 0.442 | 0.397 | 279.3 | 907 |
| 100000 | baseline | 0.474 | 0.437 | 27216.7 | n/a |
| 274137 | new+tsb (rounded cost, default) | 0.429 | 0.380 | 370.3 | 995 |
| 274137 | new+tsb/exact (previous order) | 0.389 | 0.330 | 373.2 | 986 |
| 274137 | baseline | 0.433 | 0.387 | 78243.6 | n/a |
The new+tsb/exact MRR and R@1 are identical to the original run above, as expected: that mode is the previous ranking.
Paired comparisons over the same 300 queries (per-query reciprocal ranks; SE is the sample standard deviation of the per-query differences divided by sqrt(300); the interval is the difference +- 1.96 SE):
| Dictionary | Comparison | Difference | SE | 95% interval | Queries that differ |
|---|---|---|---|---|---|
| 10000 | new+tsb minus baseline | +0.007 | 0.009 | [-0.010, +0.025] | 14 |
| 100000 | new+tsb minus baseline | -0.003 | 0.009 | [-0.020, +0.014] | 28 |
| 274137 | new+tsb minus baseline | -0.004 | 0.008 | [-0.020, +0.012] | 30 |
| 10000 | new+tsb minus new+tsb/exact | +0.015 | 0.006 | [+0.003, +0.027] | 13 |
| 100000 | new+tsb minus new+tsb/exact | +0.028 | 0.008 | [+0.013, +0.043] | 39 |
| 274137 | new+tsb minus new+tsb/exact | +0.040 | 0.009 | [+0.022, +0.058] | 48 |
Literal harness output (cargo run --release -p keyhammer-bench --bin m0 -- bench/data):
300 typo pairs
=== dictionary: 10000 words (10000) ===
new MRR=0.541 R@1=0.527 p50= 108.7us p95= 149.2us nodes/query=735 build=2ms ties@10=0.23
new+tsb MRR=0.541 R@1=0.527 p50= 87.8us p95= 120.4us nodes/query=491 build=2ms ties@10=0.23
new+tsb/exact MRR=0.526 R@1=0.510 p50= 88.1us p95= 122.1us nodes/query=489 build=2ms ties@10=0.23
legacy MRR=0.430 R@1=0.393 p50= 271.6us p95= 1183.7us
baseline MRR=0.533 R@1=0.507 p50= 2087.8us p95= 2799.9us ties@10=0.25
paired new+tsb - baseline: diff=+0.0074 SE=0.0089 95% CI [-0.0101, +0.0249] (queries that differ: 14)
paired new+tsb - new+tsb/exact: diff=+0.0149 SE=0.0063 95% CI [+0.0026, +0.0271] (queries that differ: 13)
=== dictionary: 100000 words (100000) ===
new MRR=0.470 R@1=0.430 p50= 258.3us p95= 374.3us nodes/query=1393 build=23ms ties@10=0.55
new+tsb MRR=0.470 R@1=0.430 p50= 203.7us p95= 289.8us nodes/query=911 build=23ms ties@10=0.55
new+tsb/exact MRR=0.442 R@1=0.397 p50= 200.4us p95= 279.3us nodes/query=907 build=23ms ties@10=0.55
legacy MRR=0.313 R@1=0.253 p50= 2753.2us p95= 16648.9us
baseline MRR=0.474 R@1=0.437 p50= 20800.7us p95= 27216.7us ties@10=0.55
paired new+tsb - baseline: diff=-0.0034 SE=0.0086 95% CI [-0.0203, +0.0135] (queries that differ: 28)
paired new+tsb - new+tsb/exact: diff=+0.0281 SE=0.0077 95% CI [+0.0130, +0.0432] (queries that differ: 39)
=== dictionary: 274137 words (full) ===
new MRR=0.429 R@1=0.380 p50= 313.5us p95= 477.8us nodes/query=1514 build=64ms ties@10=0.68
new+tsb MRR=0.429 R@1=0.380 p50= 252.2us p95= 370.3us nodes/query=995 build=64ms ties@10=0.68
new+tsb/exact MRR=0.389 R@1=0.330 p50= 242.5us p95= 373.2us nodes/query=986 build=64ms ties@10=0.68
legacy MRR=0.255 R@1=0.197 p50= 7864.2us p95= 51773.0us
baseline MRR=0.433 R@1=0.387 p50= 57630.3us p95= 78243.6us ties@10=0.69
paired new+tsb - baseline: diff=-0.0037 SE=0.0080 95% CI [-0.0195, +0.0120] (queries that differ: 30)
paired new+tsb - new+tsb/exact: diff=+0.0401 SE=0.0092 95% CI [+0.0221, +0.0581] (queries that differ: 48)
=== G0 (largest dictionary) ===
p95 legacy / new = 139.8x (need >= 10x): PASS
MRR default mode (new+tsb) 0.429 vs baseline 0.433
(c) strict (need >= baseline): FAIL
(c') no evidence of being worse (need diff + 1.96 SE >= 0: -0.0037 + 1.96 x 0.0080 = +0.0120): PASS
G0 under the original criteria remains a partial pass: speed passes, the strict MRR check (c) fails at 100000 and 274137 words. (c') is informational: it says only that these data do not show the new ranking to be worse than the baseline; it does not by itself pass G0, and any non-inferiority margin for a future run should be fixed in advance.
oracle equality: run `cargo test -p keyhammer` (must be green)
Reading the results
- Against the baseline, the default mode is statistically indistinguishable at every size: the 95% interval of the paired difference contains 0 each time. There is no evidence that it is worse and none that it is better. The intervals are about +-0.017 wide, so these 300 pairs cannot show parity to within +-0.005 either; a smaller real difference in either direction cannot be ruled out.
- Against the previous ordering (
new+tsb/exact), the gain is significant at every size: +0.015, +0.028 and +0.040, the last about 4.4 SE above zero. - Speed is unchanged by the ranking mode: nodes/query and p95 of
new+tsbandnew+tsb/exactare within a few percent of each other.
Criterion (c), reworded after the result was seen
The original criterion (c), "MRR of the best new mode at least the baseline", and its FAIL verdict stand unchanged above. The rewording below was made AFTER this result was seen, so it should be read with that in mind. Under the original strict wording the new ranking still FAILS at 100000 and 274137 words (-0.003 and -0.004) and passes at 10000 (+0.007).
MRR is deterministic here, so there is no measurement noise to tolerate; 1/300 is only the granularity of the metric (moving one query by one rank position changes MRR by at most 0.5/300 = 0.0017). The relevant uncertainty is sampling uncertainty over the 300 pairs, about one SE = 0.008 to 0.009, so a fixed tolerance of a few thousandths would have no statistical basis. The harness now applies criterion (c') instead, on the default mode (new+tsb): there is no evidence that it is worse than the baseline, i.e. the 95% interval of the paired difference contains 0 or lies above it (difference + 1.96 SE >= 0). It passes at every size (upper ends +0.025, +0.014, +0.012). This is a weaker claim than parity: it only says that these data do not show the new ranking to be worse.
G0 under the original criteria remains a partial pass: speed passes, the strict MRR check (c) fails at 100000 and 274137 words. (c') is informational: it says only that these data do not show the new ranking to be worse than the baseline; it does not by itself pass G0, and any non-inferiority margin for a future run should be fixed in advance.
Ties
The harness now reports ties@10: the share of queries whose returned top 10 holds at least two terms with the same exact weighted cost (for the baseline, the same unit distance). It is 0.23 / 0.55 / 0.68 for the weighted costs and 0.25 / 0.55 / 0.69 for the baseline at the three sizes. So exact-cost ties somewhere in the top 10 are not rare. This measure does not say whether the ties involve the right word or its rank, so it neither confirms nor rules out hypothesis 1; why rounding the cost helps is not established. It is also a weak measure: at budget 32 only about 11 distinct weighted costs are reachable (0, 8, 12, 16, 18, 20, 24, 26, 28, 30, 32), so a nearly full top 10 almost always contains a tie, and the metric largely tracks the length of the result list. That explains why it matches the baseline and is identical across modes, and "ties are not rare" must not be read as evidence against hypothesis 1 either. A per-query measure, such as "the correct word shares its exact cost with a heavier term", would be informative and was not measured.
Other findings of the experiment
The following is from a throwaway experiment that is not in the repository, single run:
- With all edit costs set to one unit, the engine returned the same top-10 lists as the baseline on 300 of 300 queries, so the search itself was not the cause of the gap.
- Frequency-blended keys (
cost*M + (65535-weight)) were worse than ranking by the rounded cost at every M tried. - The keyboard costs did not measurably improve ranking on this corpus compared with unit costs. The Birkbeck corpus is mostly spelling errors, not finger slips, so this does not judge the keyboard model. The weighted costs do expand fewer nodes (about 990 vs 1609 per query at 274137 words) and give a lower p95.
- About 43% of the 300 pairs are unreachable within the 2-edit budget for every variant tried, which caps R@10 near 0.56. Raising recall would need a larger budget or phonetic candidates; neither was tested.
Caveats
The caveats of the original report still apply: one machine, one run, 300 typo pairs from one corpus, one English dictionary, provisional costs with no calibration, tie-break ids that differ between engines, an inflated and ungated baseline latency, and no warm-up. The 95% intervals use a normal approximation for the mean of the 300 paired differences.