FreeTextSuggester can drop its best suggestion when the last typed word is complete: Util.TopNSearcher skips acceptResult for a queued final output

FreeTextSuggester (lucene/suggest, @lucene.experimental) predicts the next word with an n-gram model and stupid backoff, and offers each word once, from the highest-order model that predicts it (FreeTextSuggester.java:521-523 on main 645d4fe14a20). Lower-order models skip already-offered words inside the FST search: a Util.TopNSearcher subclass rejects them in acceptResult (:624-637), with the queue sized num + seen.size() "because we may reject up to seen.size() paths in acceptResult()" (:605-606). But TopNSearcher.search() calls acceptResult on only one of its two result paths (Util.java:391-399): a final output that was queued, such as the start node's own key when the caller passes allowEmptyString=true (as FreeTextSuggester does, :642), is added by the "Empty string!" branch with no filter and no rejection count (Util.java:333-338). So when the last typed word is a complete word that a higher-order model already offered and that ranks in the lower level's top num, it takes a slot and is then dropped by the post-search check (:674-677), and a better backed-off word can be lost: for a model of foo x9, bar x8, barn x7, lookup("foo bar", 1) returns [foo bar] (0.111) instead of [barn] (0.117). No error; isComplete stays true. Every release from 4.6.0 through 10.6.0 and main (the root since 4.1.0). Calling acceptResult in that branch and counting the rejection, as the other path does, fixes it (+5/-1).

• FreeTextSuggester: a Lookup that "uses the stupid backoff language model to smooth scores across ngram models" (FreeTextSuggester.java:93-95 on main 645d4fe14a20); bigrams by default (:116-117, constructor :157-159), n-gram words joined by the separator byte 0x1e (:147-151), @lucene.experimental (:103). ALPHA = 0.4 is the backoff factor (:121-126).
• Seen words: "We only add a given suffix once, from the highest order model that saw it; for subsequent lower order models we skip it" (:521-524).
• Util.TopNSearcher: a best-first search over an FST (Util.java:166-167, Util is @lucene.experimental, :41). addStartPaths offers every arc leaving the start node to the bounded queue through addIfCompetitive, which keeps only competitive paths (:208-252, :264-292); the END_LABEL arc (the start node's own final output) is eligible when allowEmptyString is true (:284). acceptResult is the protected hook a subclass overrides to reject a complete key (:412-423); TopResults.isComplete is rejectCount + topN <= maxQueueDepth (:409, javadoc :434-439).

1. search() pops the cheapest path (Util.java:321). If its arc is END_LABEL, the "Empty string!" branch strips the label and adds the result: no acceptResult, no rejectCount++ (:333-338).
2. Otherwise it follows zero-output arcs to the cheapest completion and there calls acceptResult(path), counting a rejection (:391-399).
3. A final output is queued, and so takes the first path, when it is the start node's own key and the caller passed allowEmptyString=true, or when it is an inner node's key that costs more than its cheapest extension (addIfCompetitive, :209-252). So the start node's own key, once queued, always takes the first path; for a key below the start node, which path it takes depends only on the weights.
4. FreeTextSuggester.lookup runs one search per level with topN = num, maxQueueDepth = num + seen.size() (FreeTextSuggester.java:605-608), rejects seen words in acceptResult (:624-637), and starts with allowEmptyString=true (:642). When the last typed word is a word, the start node is final, so a seen word that ranks in the level's top num leaks through branch 1. The post-search check drops it (:674-677), and nothing fills the slot.

Model from foo x9, bar x8, barn x7 (24 tokens; pairs foo foo 8, foo bar 1, bar bar 7, bar barn 1, barn barn 6). lookup("foo bar", 1):

• Pair level, prefix foo bar: one key, foo bar, score 1/9 = 0.1111; bar becomes seen.
• Single-word level, prefix bar, maxQueueDepth 2: the queue holds bar itself (count 8, the cheapest) and the n arc toward barn (7). bar comes off first through branch 1, fills the one result slot and ends the search; isComplete is true (0 + 1 <= 2). The post-search check drops bar; barn (0.4 x 7/24 = 0.1167) was never reached.
• Result [foo bar]. With the partial word, lookup("foo ba", 1), the search starts above bar, and bar's own key (count 8) is its cheapest way on (the arcs leaving it are 7), so bar is reached through path 2 and rejected, and the result is [barn]. lookup("foo bar", 2) gives [barn, foo bar].

Keys {a=5, ab=1}, acceptResult rejects a, topN=2: the result is [ab/1, a/5] with isComplete=true, with allowEmptyString false and true; with the weights swapped, {a=1, ab=5}, acceptResult is called for a and the result is [ab/5].

• Who is hit. Users of FreeTextSuggester, the "long tail" next-word suggester (FreeTextSuggester.java:82-88), with the default settings, any corpus size, one thread. Downstream, Solr offers it as FreeTextLookupFactory.
• When the slot is wasted. The last typed word is complete (no trailing space), a higher-order model already predicted it, and it ranks in the lower level's top num. Then that level returns at most num - 1 new words.
• When users see it. The final list changes only when the lost word would have outranked every higher-order prediction, because the other words of that level rank above it. With the default bigrams this needs P(word | context) < 0.4 x P(word): a typed pair that follows its context at most 0.4 times as often as the word occurs overall. In the repro, P(bar | foo) = 1/9 = 0.111 < 0.4 x 8/24 = 0.133.
• Effect. Silent: one weaker suggestion in place of a better one; no exception; isComplete stays true, so assert completions.isComplete (:645) does not fire. The same with assertions on and off.
• How likely: rare. An exhaustive comparison with a stupid-backoff reference found 508 disagreements in 41.8M lookups over random 4-sentence corpora; the recorded prior-art searches found no public report since 4.6.0.
• The wider root. Any TopNSearcher subclass with an acceptResult filter can hit the same branch when a key it would reject is queued as an END_LABEL path and then popped. Keys that are prefixes of other keys make that possible but do not guarantee it: it then depends on the weights, ties and queue depth. In Lucene, AnalyzingSuggester/FuzzySuggester (dedup and exact-first, AnalyzingSuggester.java:790) and NRTSuggester (collects only inside acceptResult, NRTSuggester.java:190, :254-256) reach it only when an indexed form contains U+0000, as one symptom each of LFV-601 and LFV-798.

TestFreeTextSuggesterSeenWord (38 lines with the license header, one test method, package org.apache.lucene.search.suggest.analyzing like TestFreeTextSuggester). Public API only: the default FreeTextSuggester(Analyzer), PlainTextDictionary, lookup. MockAnalyzer(random()) splits on whitespace and lower-cases; its only random choice is a test payload filter, which changes neither the tokens nor the counts, and every recorded seed gave the same result. The key is printed with the separator byte 0x1e shown as a space.

Use the same test as the regression test of the fix, as its own class or as one method in TestFreeTextSuggester.

The hunt's larger evidence is not part of the repro: an exhaustive check of TopNSearcher against a brute-force reference (26,810 FSTs, 69.6M searches), a Util-level test, and upstream TestFSTs#testRejectNoLimits with one weight changed.

cp $REPRO/TestFreeTextSuggesterSeenWord.java $LUCENE/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/
cd $LUCENE && ./gradlew :lucene:suggest:test --tests TestFreeTextSuggesterSeenWord -Ptests.seed=5EED1052 -Ptests.asserts=true

TestFreeTextSuggesterSeenWord > testAlreadyPredictedWordDoesNotTakeUnigramSlot FAILED
    org.junit.ComparisonFailure: expected:<[barn]> but was:<[foo bar]>

# the same with -Ptests.asserts=false, through the standalone runner (assertions on and off) and on 10.6.0 and 9.12.3
# with the fix: the test passes

# scores for the same model (doc probe, values divided by Long.MAX_VALUE)
                           stock main          with the fix
lookup("foo bar", 1)       [foo bar=0.1111]    [barn=0.1167]
lookup("foo bar", 2)       [barn=0.1167, foo bar=0.1111] (both)
lookup("foo ba", 1)        [barn=0.1167]       (both)

• The suggester's design. The queue sizing comment (FreeTextSuggester.java:605-606) and assert completions.isComplete (:645) only make sense if seen words are rejected inside the search; the post-search check (:674-677) is a second line.
• The upstream reference model. TestFreeTextSuggester#testRandom (TestFreeTextSuggester.java:318) builds the expected list per model: "First pass, gather all predictions for this model" skipping seen terms (:529-544), "Second pass, trim to only top N" (:559-564), merge, sort, cut to num (:586-590), and asserts equality with lookup() (:600). Its random 1-5 character terms rarely hit the trigger.
• The TopNSearcher contract. The zero-output path calls acceptResult and counts the rejection (Util.java:391-399); isComplete may be false "if the TopNSearcher rejected too many results" (:434-438); LUCENE-5519's CHANGES entry: the result "indicates if the result is complete in the sense of the top N" (lucene/CHANGES.txt:12519-12525).
• Upstream TestFSTs#testRejectNoLimits (TestFSTs.java:1360-1413) asserts that all 4 rejected keys reach acceptResult (:1389) and only the accepted key is returned (:1392). It passes only because adcd does not weigh more than its extension adcde (both 17, :1368-1369; at 16 it passes too); with adcd at 18 its own assertions fail on stock ([aac/7, adcd/18]) and pass with the fix.
• Every in-tree override uses acceptResult as the result filter: FreeTextSuggester (seen words), AnalyzingSuggester (dedup, exact-first, AnalyzingSuggester.java:790), NRTSuggester ("we do not use it, instead collect at acceptResult", NRTSuggester.java:255).
• History. The branch came first (LUCENE-3714, a519b630eea, 2012-02-19), when TopNSearcher was private and had no filter; LUCENE-3842 (f2f91bae46c, 2012-09-28) added acceptResult only on the zero-output path. The reviewed commits, tests, CHANGES and MIGRATE entries, issues and threads show no exemption for queued final outputs.

The intended-behaviour checker and a reviewer from another model family (OpenAI GPT-5.6) built the strongest case: acceptResult has no javadoc of its own and Util and FreeTextSuggester are @lucene.experimental; the branch is labelled "Empty string!" and the caller opts in with allowEmptyString=true, so "the typed prefix is always a result" could be intended; Lookup.lookup promises only "possible completion" with num the "maximum number of results" (Lookup.java:184-192); FreeTextSuggester re-checks seen words after the search (FreeTextSuggester.java:674), as if leaks were expected; and the comment at :515-516 ("Try highest order models first, and if they return results, return that; else, fallback") describes hard backoff, under which [foo bar] would be right.

Why it fails: with allowEmptyString=false the filter is still skipped (keys {a=5, ab=1}), and swapping the two weights makes it run, so the bypass is not limited to the empty string; the queue sizing and the isComplete assertion show the post-search check is a backstop; the committed code and class javadoc merge all levels with stupid backoff (:93-95, :692-709), and the hard-backoff comment is left over from a work-in-progress patch on LUCENE-5214 (#6278); and testRandom's reference model, written in the same commit as the class, gives [barn]. The intended-lens review rated the works-as-designed case "moderate", not sufficient. Verdict: a defect. Do not argue from "top-1 should be the head of top-2": the per-level top-num merge can break that legitimately.

One fix was built and validated; two alternatives were considered and not recommended.

Mirror the zero-output path (Util.java:394-398). acceptResult runs after the END_LABEL is stripped from the input, so the subclass sees the key itself.

         if (path.arc.label() == FST.END_LABEL) {
           // Empty string!
           path.input.setLength(path.input.length() - 1);
-          results.add(new Result<>(path.input.get(), path.output));
+          if (acceptResult(path)) {
+            results.add(new Result<>(path.input.get(), path.output));
+          } else {
+            rejectCount++;
+          }
           continue;
         }

Trade-offs

• One more acceptResult call per popped final output; nothing changes for callers without a filter (the default acceptResult returns true).
• FreeTextSuggester's assert completions.isComplete still holds: each seen word matches at most one completion, so rejectCount <= seen.size().
• AnalyzingSuggester and NRTSuggester now filter these paths too. That clears one symptom each of LFV-601 (a duplicate) and LFV-798 (a hidden suggestion), which reach this branch through U+0000; a CHANGES entry could say so. It does not close LFV-601: two of its four tests still fail with the fix.
• A behaviour change for every subclass. acceptResult is a protected hook (Util.java:412-423) that a subclass may use for more than a yes/no answer: NRTSuggester checks deleted documents and the filter, records seen surface forms and collects the hit inside it, and ignores search()'s list (NRTSuggester.java:190-227, :254-256). With the fix, such a subclass is also called for queued final outputs. Source compatibility is kept, but the module tests cannot rule out a subclass outside Lucene that depends on the bypass.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle, OpenJDK 25: the repro test fails on the stock tree with assertions on and off, and passes with the fix.
• With the fix and the test, the whole lucene/suggest module passes with assertions on and off: 32 suites, 237 tests, 7 skipped, 0 failures (it includes TestFreeTextSuggester, TestAnalyzingSuggester, TestFuzzySuggester, TestSuggestField and TestWFSTCompletion).
• The core org.apache.lucene.util.fst.* tests pass with assertions on and off: 8 suites, 37 tests, 0 failures (TestFSTs with testRejectNoLimits).
• :lucene:core:check :lucene:suggest:check -x test passes (google-java-format, ecjLint, forbiddenApis).
• Earlier, with the same change shadowed: the exhaustive TopNSearcher run drops from 7,456,380 rejected results returned and 4,349,970 wrong-but-complete results to 0 and 0 (the 57,500 that remain are the separate queue = null shortcut, LFV-660); testRejectNoLimits with adcd at 18 passes; LFV-798's minimal repro passes and LFV-601's duplicate test passes (LFV-601's tests: 3 of 4 fail on stock, 2 of 4 with the fix, so LFV-601 stays open).

Pass allowEmptyString = !seen.contains(lastToken) instead of true at FreeTextSuggester.java:642 (from the twin hunt). Not recommended.

Trade-offs

Hides the visible symptom for the start-node case, but leaves TopNSearcher filtering by weight for every other subclass and for inner nodes.

Javadoc only. Not recommended.

Trade-offs

Keeps isComplete true while a rejected key is returned, and every caller would need its own post-filter.

Method: semi-formal, bounded-exhaustive translation validation on the stock jars.

• First finder (2026-10-27). A unit checking FST code compared Util.TopNSearcher with an independent brute-force reference (all completions from the start node, filtered, sorted by cost and input) over every small FST in its scope. The check "every returned result passes acceptResult" failed on the first FST, {""=0} with every result rejected, which returned [""=0].
• Twin. A unit checking FreeTextSuggester against a stupid-backoff reference in the per-level top-N form that testRandom asserts found 508 disagreements in 41.8M lookups, all on random 4-sentence training sets, and then found the branch by reading the code.
• Adjudication unit. Re-ran both, reduced them to one public-API JUnit, re-ran the exhaustive scope on main (26,810 FSTs, 69,647,420 searches: 7,456,380 return a rejected result and 4,349,970 report isComplete=true with a wrong list; 0 and 0 with the fix; a mutant of the reference with the cost order reversed fires, so the check is not vacuous), and ran upstream testRejectNoLimits with one weight changed. The no-noise gate later cut the test to one line of input.