DirectSpellChecker with a custom StringDistance prunes candidates on the wrong scale and returns worse suggestions

DirectSpellChecker draws spelling candidates from the term dictionary with FuzzyTermsEnum (Damerau-Levenshtein) and, when you call setDistance, is documented to rank them with your metric. Since 7.0.0 it stores the metric's score in ScoreTerm.boost, a field documented as the enumerator's internal similarity, and then uses it twice as if it were that similarity: to skip later candidates as uncompetitive and to tell the enumerator to lower its edit distance. The two scores are on different scales, so a better word can be skipped before it is scored and the enumeration can end early. With default settings, the index {lucen, lucena, lucenb, lucenc, lucend, lucenes} and the query lucene, LevenshteinDistance returns lucen (0.833) instead of lucenes (0.857). Lucene's default distance and a separate LuceneLevenshteinDistance instance are not affected. Changing 3 code lines restores the 4.0-6.6.6 logic.

• DirectSpellChecker suggests corrections straight from the term dictionary. For a query word it walks the terms within 1 edit (then, if it found too few, within maxEdits, default 2) with a FuzzyTermsEnum and keeps the best numSug * maxInspections candidates (default maxInspections 5) in a bounded queue. The survivors are sorted by score and the top numSug are returned.
• Internal similarity (the enumerator's boost): 1 - edits / min(term length, query length). For lucene (6 letters): lucena 0.833 (1 edit / 6), lucen 0.800 (1 edit / 5), lucenes 0.833 (1 edit / 6).
• The configured metric (setDistance): LevenshteinDistance is 1 - edits / max(length), so lucenes scores 0.857 (1 / 7) and lucen..lucend 0.833. JaroWinklerDistance and NGramDistance use other formulas. The default, INTERNAL_LEVENSHTEIN, is the internal similarity itself.
• Pruning. Once the queue is full, a new term whose boost is not above the queue's worst entry is skipped, and the worst entry's value is passed to FuzzyTermsEnum.setMaxNonCompetitiveBoost. The enumerator then drops from 1 edit to 0 when that value reaches 1 - 1 / query length, the best any 1-edit term can score: no 1-edit term could beat it.

1. For a metric other than the internal one, the loop overwrites score with the metric's value and stores it as st.boost (DirectSpellChecker.java:452-459, :467). The field's javadoc says boost is "the similarity from the FuzzyTermsEnum (internal similarity score)" (:487).
2. The uncompetitive check compares the next term's internal similarity with that metric-scale number (:435), and setMaxNonCompetitiveBoost hands it to the enumerator (:474-475), which reads it on its own 1 - maxEdits / termLength scale (FuzzyTermsEnum.java:204-210).
3. So a better candidate can be skipped before it is scored, and the enumeration can stop early. The queue, ordered by the metric (:503-511), then holds neither the documented pool nor the metric's top N.

Default settings, one document per word, query lucene, LevenshteinDistance:

Main returns lucen, which is not even among the 5 best by internal similarity. With the fix the queue's worst entry is lucen at 0.800, lucenes (0.833) gets in, scores 0.857 and is returned. With JaroWinklerDistance main returns lucen (0.972) instead of lucenes (0.981). With maxInspections 1 and the index {lucen, lucenes}, all three shipped metrics return lucen, although lucenes is better under the internal similarity and under each metric. A trace of the term reads on main shows lucenes read from the term dictionary but given no docFreq and no getDistance call, and the enumerator re-opened at 0 edits.

• Who. Opt-in: the default distance is not affected, and neither is a separate LuceneLevenshteinDistance instance (same scale). By reading downstream source (nothing run there): Solr's DirectSolrSpellChecker maps distanceMeasure to setDistance; the term and phrase suggesters of Elasticsearch and OpenSearch map string_distance levenshtein, jaro_winkler and ngram to these classes, and their damerau_levenshtein to the unaffected LuceneLevenshteinDistance.
• When. Default settings otherwise; the index size does not matter (the example has six terms): it shows when the 1-edit candidate queue (numSug * maxInspections) fills before a better term comes up in term order, so dense neighbourhoods and small maxInspections are hit most. Raising maxInspections makes it rarer; the comparison stays on the wrong scale.
• How often (default settings, the suggest module's 50,000-word test vocabulary, 20,000 queries per row): a suggestion strictly worse than a member of the documented pool in 0.12% / 0.04% / 0.02% of single-typo queries (Levenshtein / JaroWinkler / NGram) and 0.46% / 0.51% / 0.12% of double-typo queries; none with the fix. The original word came back 0.1 to 2.5 percentage points less often. The rates hold for that query generator (words of 5-12 letters, one or two random edits that keep the first letter, queries not in the list, numSug 1), not for lookups in general.
• Examples from that run: saxo (from "saxon") gives salo (Levenshtein 0.750) although saxon (0.800) is in the pool, and sax (0.942) instead of saxon (0.960) with JaroWinkler; toilte gives tilde instead of toilets. On Lucene's Reuters test text, with numSug 1, 8 (JaroWinkler) to 23 (Levenshtein) of 2,000 single-edit lookups got a different top suggestion than with the documented behaviour (0 for the internal control); cops (from "crops") gives cos instead of crops.
• Silent. The wrong word looks plausible; there is no error and no search hit is involved.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<abc[de]> but was:<abc[]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.spell.TestDirectSpellCheckerLevenshteinDistance.testBestCandidateIsInspected(TestDirectSpellCheckerLevenshteinDistance.java:45)

• Contract. Class javadoc (DirectSpellChecker.java:39-41): "Candidates are presented directly from the term dictionary, based on Levenshtein distance. This is an alternative to SpellChecker if you are using an edit-distance-like metric such as Levenshtein or JaroWinklerDistance." setDistance (:279-284): "because this spellchecker draws its candidates from the term dictionary using Damerau-Levenshtein, it works best with an edit-distance-like string metric. If you use a different metric than the default, you might want to consider increasing setMaxInspections(int) to draw more candidates for your metric to rank." ScoreTerm.boost (:487): "The boost representing the similarity from the FuzzyTermsEnum (internal similarity score)".
• The enumerator's side. setMaxNonCompetitiveBoost "may allow switching to a lower max-edit automaton" (FuzzyTermsEnum.java:162-166) and compares the value with 1 - maxEdits / termLength (:205). On #10608 (LUCENE-9568) a committer explained that changing that scale "will break most of the top-N optimizations".
• Design. On #3581 (LUCENE-2507, 2010) the class's author wanted "re-ranking against the existing StringDistance metrics" and wrote "if you are ranking by an edit-distance like function such as Levenshtein or Jaro-Winkler, it makes more sense to get your candidates via the same or similar algorithm!".
• History. 4.0.0-alpha to 6.6.6 kept final float boost = boostAtt.getBoost(), boost <= stQueue.peek().boost and st.boost = boost; 6.2.1, 6.3.0 and 6.6.6 return lucenes. faf3bc3134c ("LUCENE-7439: clean up FuzzyQuery/FuzzyTermsEnum sources") removed the enumerator's scale factor and changed the loop to st.boost = score, which is neutral for the internal distance only. On #8491 the author called the patch "just this cleanup; it doesn't change the behavior on short terms" (the issue's topic); nobody mentioned the spellchecker, the only LUCENE-7439 CHANGES entry is about FuzzyQuery and short terms and sits under 6.3.0 (the clean-up commit itself was master-only and first released in 7.0.0), and 7.0.0's MIGRATE.txt has no note. On the 7.0.0 jars the parent's two files pass, the commit's fail and a 3-line revert passes.
• Tests. No test under lucene/ calls DirectSpellChecker.setDistance; the other metrics are used as spellchecker metrics only with the separate-index SpellChecker (the metric classes have their own unit tests). With the fix every suite in the module passes.
• Both scales agree. In the maxInspections 1 case the returned lucen is worse than lucenes under the internal similarity and under each metric, so the expectation does not depend on how "the pool" is read.
• Metamorphic check. (float) Math.sqrt of LuceneLevenshteinDistance keeps the order of the internal similarity, and on the test's short words distinct scores stay distinct after the float rounding; with accuracy 0 it must return what the internal distance returns. On main it returns abc instead of abcde and differs in 74 of 8,000 random checks, all at maxInspections 1 (0 of the 4,000 at the default 5); the identity control differs in 0. It supports the semantics argument; the default-settings failure rests on the lucene and abcd examples.
• Design intent, not a formal guarantee. "The documented pool" is read from the setDistance and ScoreTerm.boost javadocs; suggestSimilar promises a list "sorted ... according to the comparator", not the globally best word. The maxInspections 1 example does not depend on that reading.

The strongest works-as-designed case (the cross-model lenses, the independent reproducer, the devil's advocate and the adjudication): the class is @lucene.experimental; candidate selection is a documented heuristic budget; setDistance itself advises raising maxInspections for another metric, and the maxInspections 1 repro ignores that advice; the class's author discouraged n-gram metrics here ("if you use NGramDistance, use the existing spellchecker!"); ScoreTerm is "for internal usage"; and st.boost = score could be read as a deliberate choice to order the queue by the metric.

Why it fails: the default-settings case fails too, and the returned word is worse under both scales. If the queue were meant to hold the metric's top N, the pruning would compare metric with metric; it compares metric with the enumerator's boost and stops the walk on that number, so the queue is the top N of a truncated walk. The change came from a clean-up commit with no note about spell checking, it contradicts the field's own javadoc, and an order-preserving transform of an internal-equivalent metric changes the results (at maxInspections 1). NGramDistance is the weak part. Verdict: not intended, a regression.

Two fixes were built and run in a scratch worktree at a9779ef3c193; A restores the documented behaviour and is recommended.

Remember e.getBoost() as boost, use it for the uncompetitive check and store it in st.boost; the metric's value stays in score and st.score, which the final sort uses. The queue order and setMaxNonCompetitiveBoost then use the internal similarity again, as the field's javadoc says. For the internal distance nothing changes (boost == score). +6/-5 in DirectSpellChecker.java; the finder's and the independent reproducer's separately written fixes are the same logic (with other comments and variable names).

// the internal similarity (1 - ed/minTermLength); for FuzzyQuery, boost is the score
final float boost = e.getBoost();
float score = boost;
// ignore uncompetitive hits: compare internal similarity with internal similarity
if (stQueue.size() >= numSug && boost <= stQueue.peek().boost) {
  continue;
}
...
st.boost = boost;   // was: st.boost = score
st.score = score;   // the metric's score, used for the final ranking

Trade-offs

Restores the documented pool (the numSug * maxInspections best by Damerau-Levenshtein, ranked by the metric), so a metric that is not edit-distance-like can still miss candidates outside that pool, as setDistance documents. Nothing changes for the internal distance. For another metric it changes the suggestions existing users get (back to the pre-7.0 behaviour) and can read more or fewer terms than main: in the security probe's randomized lookups both directions occurred. Not benchmarked.

What the checks validated

Scratch worktree at a9779ef3c193, gradle, seed DEADBEEF: the whole :lucene:suggest:test task with the 3 repro classes added, 34 classes, 244 tests, 0 failures (7 skipped by the module itself), with assertions on and off. :lucene:suggest:check -x test (format, ecj lint, forbidden APIs) passes. With the fix as a shadow class on main: the three repro tests pass with several seeds, upstream TestDirectSpellChecker 6 of 6, the finder's harness reports no mismatch in 900,000 lookups, and the 50,000-word measurement finds no worse-than-pool suggestion. Not benchmarked.

Skip the uncompetitive check and the setMaxNonCompetitiveBoost call unless distance == INTERNAL_LEVENSHTEIN, and keep st.boost = score. +8/-3.

Trade-offs

The queue becomes the metric's top N of the eligible terms within 1 edit (those that pass the exact-match, docFreq and accuracy filters), or within maxEdits when that gives fewer than N: arguably a better pool, but a different contract from the javadoc, and each custom-metric 1-edit pass runs its automaton to the end, with no early switch to fewer edits (bounded by the unpruned enumeration). A separate LuceneLevenshteinDistance instance loses the pruning too.

What the checks validated

Gradle: the 3 repro classes and TestDirectSpellChecker, 14 tests, 0 failures, with assertions on (this doc's run) and off (the independent fact check's run). The whole module and the cost were not run.

Rewrite the ScoreTerm.boost and setDistance javadocs to describe metric-ordered pruning.

Trade-offs

Does not fix it: the enumerator would still read a metric score on its own scale, so the walk stops on a number with no meaning there. Not recommended.

Method: bounded translation validation (the hunt's "semi-formal" tier: a hypothesis formed while modelling, then witnessed by a tool on the real jar; no model checker, solver or proof).

• The finder wrote a reference model of suggestSimilar from its documentation: a pool of numSug * maxInspections terms drawn by the internal Damerau-Levenshtein similarity, the 1-edit then maxEdits passes, the docFreq, accuracy and suggest-mode filters, then ranking by the configured StringDistance.
• While writing it, they noticed that ScoreTerm.boost is assigned the custom score. The harness then compared the stock main jar with the reference over 30,000 random indexes and 900,000 lookups: 412 strictly dominated results (a returned term worse than an unreturned candidate under both the internal similarity and the metric: 109 Levenshtein, 170 JaroWinkler, 133 NGram) and no mismatch for the internal distance.
• With the fix shadowed the harness reported no mismatch at all, and a deliberately wrong reference was caught, so the check is not vacuous.
• The finder reduced it to a JUnit test; an independent reproducer wrote its own test with other words, which is the primary repro here.