WordBreakSpellChecker.suggestWordBreaks can skip better splits once an earlier branch fills its suggestion queue (maxChanges >= 3)

WordBreakSpellChecker.suggestWordBreaks splits an unknown term into indexed words and should return the best maxSuggestions splits by Lucene's own order: fewest breaks first, then the highest (or summed) word frequencies. Since 9.12.0 (#12100) it returns early once its result queue is full, on the stated assumption that every split it has not generated yet has more breaks than every queued one. That holds for a breadth-first search, but the search finishes one sibling branch's whole subtree before the next, so the queue can already hold splits with as many or more breaks. With setMaxChanges(3) or more, a better split can then be lost: on the words a ab b c d e, abcde with one suggestion gives a b c d e (4 breaks) instead of ab c d e (3 breaks), while two suggestions give both in the right order and maxChanges 3 gives the right one. It happens with an unlimited evaluation budget, the default maxChanges 1, and 2, are not affected, and only splits into 4 or more words can be lost. The releases run from 9.12.0 to 10.5.2 and main fail (the others in that range carry the same file); 9.11.1 passes. Returning early only when the queue's worst split has fewer words than any deeper split can have fixes it (2 code lines replace 1), and the suggest module's tests pass with it.

• WordBreakSpellChecker (lucene-suggest, org.apache.lucene.search.spell) suggests splitting an unknown term into words that are in the index (icecream -> ice cream), or combining terms.
• suggestWordBreaks(term, maxSuggestions, reader, suggestMode, sortMethod) returns at most maxSuggestions splits. A split's score is its number of breaks. BreakSuggestionSortMethod orders them "by Number of word breaks, then by the Maximum [or Sum] of all the component term's frequencies" (WordBreakSpellChecker.java:54-62).
• setMaxChanges(n) caps the breaks per split (default 1, :37, :441-449). setMaxEvaluations(n) caps the work (default 1000) and "might improve result quality" when raised (:451-459).

1. The best splits are kept in a bounded priority queue whose head is the worst split; when it overflows the worst is dropped (:91-97, :283-287).
2. Each call of generateBreakUpSuggestions (:241-330) first queues the two-word splits of its text whose words pass the frequency threshold and records the valid first words (phase 1, :265-290, within the maxEvaluations budget).
3. Then it returns at once if the queue is full (:299-303), "because any subsequent suggestions are guaranteed to have more changes then anything currently in the queue, and not be competitive" (:295-296).
4. Otherwise it recurses into the rest of the text after each valid first word, finishing one sibling's whole subtree before the next (phase 2, :305-327).
5. So when a call that runs after an earlier sibling subtree (its own earlier sibling's or an ancestor's) reaches its check, the queue may hold splits from that subtree with as many or more breaks than the call's own deeper splits. The call returns before it generates them, although they can rank higher.

At the top level the comment is right (only 1-break splits are queued, and everything later has 2 or more). Every call runs its phase 1 before the check, and the top level returns only when its queue is full of 2-word splits, so no competitive split of 2 or 3 words is lost: maxChanges 1 and 2 are not affected (a finite maxEvaluations can still cut any search short, as documented). With maxChanges 3 a split is lost only to one with the same 3 breaks and lower frequency; with 4 or more, also to one with more breaks.

Default NUM_CHANGES_THEN_MAX_FREQUENCY, maxEvaluations 1000, stock main:

• Top level, phase 1 on abcde: valid first words a and ab; no two-word split. The queue is empty, so phase 2 starts.
• Branch a: bcde -> b + cde -> c + de -> phase 1 queues a b c d e. The queue is full (1 of 1).
• Branch ab: phase 1 on cde finds no two-word split (de is not indexed). The queue is full, so it returns; ab c d e, one level further down, is never generated. A docFreq-lookup trace shows the search ending with the lookups ab, c, de, cd.
• With maxChanges 3, branch a stops at depth 3 without queuing anything, and branch ab finds ab c d e.

• Who. Users of lucene-suggest's WordBreakSpellChecker.suggestWordBreaks with maxChanges 3 or more, set directly or through a downstream component that forwards a configured maxChanges and the request's suggestion count. Upstream TestWordBreakSpellChecker.testBreakingWords itself uses maxChanges 3, 4 and 5.
• Not affected. The default maxChanges 1, and 2; suggestWordCombinations (no such shortcut; 400,000 combination checks found no wrong result); terms whose competitive splits have at most 3 words. Lucene's query matching and the index are not affected; the immediate effect is the suggestion list.
• Effect. Silent: no error, and the returned split is still a valid split into indexed words. With maxChanges 3 a split with the same breaks but lower frequencies replaces a better one; with 4 or more, one with more breaks can too. Raising maxChanges can make the answer worse. It happens with an unlimited maxEvaluations too, and needs no minimum index size (one document suffices); the index's words and docFreqs decide whether it triggers.
• How often. It needs a term whose competitive splits have 4 or more words and an earlier branch that fills the queue first. In an oracle over dense random dictionaries of 1-3-letter words with an unlimited budget, about 0.1-0.3% of checks were wrong at maxChanges 3 and 1.5-3.8% at 4-6. Natural vocabularies were not measured; registry likelihood: rare.
• Downstream (from reading source, nothing run there). Apache Solr's WordBreakSolrSpellChecker forwards its configured maxChanges and the request's count, and a Solr sample configuration sets maxChanges to 10. GitHub code search found no WordBreakSpellChecker use in Elasticsearch or OpenSearch.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<a[]b c d e> but was:<a[ ]b c d e>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.spell.TestWordBreakFullQueue.testFewestBreaksSplitFirst(TestWordBreakFullQueue.java:56)

• The order is defined. BreakSuggestionSortMethod: "Sort by Number of word breaks, then by the Sum [Maximum] of all the component term's frequencies" (:54-62); both comparators rank fewer words first, then higher frequency (:461-485), and the queue keeps the best maxSuggestions by that order.
• The shortcut was meant to be lossless. Code comment: "any subsequent suggestions are guaranteed to have more changes then anything currently in the queue, and not be competitive" (:295-296); the method calls itself a "Two phase breadth first search" (:260). Issue #12100 (hossman): "we know that candidates with fewer NUM_CHANGES... are _always_ better, a breadth first approach can can actually short-circuit and return much earlier then I originally suggested, if the suggestions queue is already "full"".
• The change promised better matches. CHANGES 9.12.0, Optimizations: "WordBreakSpellChecker.suggestWordBreaks now does a breadth first search, allowing it to return better matches with fewer evaluations". Upstream testSmallMaxEvaluations calls the fewest-changes result "optimal".
• The behaviour contradicts it. The top 1 is not the head of Lucene's own top 2; 9.11.1 returned the expected top N, by the ranking keys, on every input tried; an unlimited budget fails the same way; raising maxChanges from 3 to 4 makes the answer worse.
• Why the tests missed it. The two maxEvaluations tests as #12100 left them (it added testSmallMaxEvaluations and rewrote testMaxEvaluations, which #12077 had added) use "plenty" maxSuggestions (maxEvals * 2, maxEvals * 10), so the full-queue return never fires in them, and the maxChanges 3-5 cases of testBreakingWords have no earlier sibling that fills the queue. No upstream test asserts the current output; with the fix every suite in the module passes.

The strongest works-as-designed case (the cross-model lenses, the independent reproducer, the devil's advocate and the adjudication): the suggestWordBreaks javadoc says only that "a lower score is generally preferred over a higher score" (:64-67); BreakSuggestionSortMethod "Determines the order to list word break suggestions", which could mean the order of the returned list rather than which splits are selected; setMaxEvaluations admits that "A higher value might improve result quality", so quality is openly heuristic; #12100 is filed under Optimizations and changed results on purpose; and maxChanges 3 or more is opt-in.

Why it fails: the loss happens with the budget unused, so the setMaxEvaluations trade-off does not cover it. The only justification the code gives, the comment at :295-296, is false for the committed algorithm, and #12100 argues for the shortcut on exactly the property the repro breaks. The top N is not a prefix of Lucene's own top N+1, and 9.11.1 returned the expected top N. The results #12100 changed on purpose are budget-limited ones; this loss happens with the budget unused, and nothing in #12100 suggests it was known or accepted. Verdict: not intended; a regression of #12100.

Two fixes were built and run in a scratch worktree at a9779ef3c193. A narrows the shortcut and is recommended (the finder's guard, with a rewritten comment); C drops the shortcut. A real breadth-first rewrite and a javadoc-only change were not run.

In generateBreakUpSuggestions, require that the queue's worst split (suggestions.peek()) has at most newNumberBreaks words before returning on a full queue, and replace the comment that claimed the return is always lossless. 2 code lines replace 1 in WordBreakSpellChecker.java.

// if we are about to exceed our maxChanges *OR* we have a full list of
// suggestions that all have fewer words than any deeper suggestion can have
// (at least newNumberBreaks + 1), we can return now.
final int newNumberBreaks = numberBreaks + 1;
if (totalEvaluations >= maxEvaluations
    || newNumberBreaks > maxChanges
    || (suggestions.size() >= maxSuggestions
        && suggestions.peek().suggestWords.length <= newNumberBreaks)) {
  return totalEvaluations;
}

Trade-offs

• Why it is right. peek() is the worst queued split (both comparators put more words first, then lower frequency, and the queue polls its head). A recursion from this call yields splits of at least newNumberBreaks + 1 words; if the worst queued split has at most newNumberBreaks words, every deeper split ranks strictly below it and would be dropped at once, so skipping phase 2 loses nothing. With newNumberBreaks + 1 or more words, a deeper split can tie on words and win on frequency, so the bound is tight. "Loses nothing" is by the ranking keys: tied splits have no defined order (both comparators return 0 on equal keys), as on 9.11.1.
• Keeps #12100's gain where it is valid: at the top level and in every call whose queue holds only shorter splits, it prunes exactly as today.
• Cost. It explores the subtrees the shortcut wrongly skipped. A docFreq-lookup trace (made with the finder's guard, the same condition) counted 26 lookups with the fix vs 23 stock (21 on 9.11.1) for the minimal case, and 103 vs 90 (102 on 9.11.1) for the number-word top 3; these are lookups, not maxEvaluations units, which count phase-1 split positions. Work stays capped by maxEvaluations and maxChanges. Not benchmarked. With a finite maxEvaluations results stay budget-dependent, as setMaxEvaluations documents; the exhaustive checks used an unlimited budget.
• Open draft PR #16847 changes only the frequency types, in other hunks of this file, not the shortcut; fix A applies cleanly to the file at its current head (6aea7b57d734, checked 2026-10-28), so the two do not conflict.

What the checks validated

• Gradle in a scratch worktree at a9779ef3c193, seed DEADBEEF: the whole :lucene:suggest:test with the 3 repro classes added, 34 classes, 245 tests, 0 failures (7 skipped by the module itself), with assertions on and off; the 8 repro tests that fail on stock pass.
• Upstream TestWordBreakSpellChecker (which has a random test) and the repro classes, 10 iterations, seed 5EED0538: 140 tests, 0 failures.
• :lucene:suggest:check -x test with the fix and the brief's test (format, ecj lint, forbidden APIs): BUILD SUCCESSFUL.
• On ea57360912ed the finder's identical condition: the hunt's bounded-exhaustive check drops from 984 wrong rankings at maxChanges 3-4 to 0, a separate oracle from 3,822 of 269,760 to 0, and upstream TestWordBreakSpellChecker passes 25 of 25. Not benchmarked.

The condition becomes totalEvaluations >= maxEvaluations || newNumberBreaks > maxChanges, with the comment updated.

Trade-offs

Simplest and plainly exact (by the ranking keys) with an unlimited budget, but it gives up #12100's short-circuit everywhere: a full queue no longer saves any work, and under the default budget of 1000 deep branches spend evaluations the shortcut used to save. Not benchmarked.

What the checks validated

Gradle, assertions on, seed DEADBEEF: the 3 repro classes and upstream TestWordBreakSpellChecker, 14 tests, 0 failures. The whole module was not run with C.

Finish all splits with k breaks before any with k + 1, for example with a frontier of (prefix, rest) states per level; the original shortcut is then valid as written.

Trade-offs

Matches #12100's intent, but it is a larger rewrite, keeps a frontier in memory, and changes which splits a finite budget reaches. Not run.

A javadoc note on suggestWordBreaks.

Trade-offs

Leaves the regression from 9.11.1 and contradicts the code comment and #12100. Not recommended.

Method: translation validation against an exact reference (the hunt's "semi-formal" tier).

• The reference enumerates every split of the term into indexed words with at most maxChanges breaks, applies the documented word-length, frequency and SuggestMode rules, orders the splits by the BreakSuggestionSortMethod keys (ties as sets) and keeps the top maxSuggestions.
• Bounds: 200 random indexes over the 126 strings of length 1-6 over {a, b}, all 510 queries of length 1-8, 12 random configurations each (maxChanges 0-4, both sort methods, several maxSuggestions and modes, unlimited maxEvaluations): 1,224,000 break checks. 984 were wrong, all at maxChanges 3 or 4, and 0 with the fix shadowed. (A separate maxChanges=0 discrepancy class in the same run is a different question, not part of this bug.) A mutant reference was used to show the check is not vacuous.
• A second search on the index of upstream TestWordBreakSpellChecker found the natural examples thousandonehundredeight and thousandninehundredeight; the finder turned them and a minimal case into a public-API JUnit test.