Word2VecSynonymProvider returns maxSynonymsPerTerm + 1 synonyms when the query word is missing from its own search hits

Word2VecSynonymFilter (analysis-common, @lucene.experimental) expands each token with the nearest words of a word2vec model, found by Word2VecSynonymProvider.getSynonyms through an HNSW search over the model. The filter documents maxSynonymsPerTerm as the "maximum number of result returned by the synonym search". The provider searches for maxSynonymsPerTerm + 1 neighbours, because the query word is "always the nearest neighbour of itself", then drops the query word and every hit below minAcceptedSimilarity, and never caps the result. When the query word is not among the k + 1 hits and all of them pass the threshold, all of them are returned and emitted: three words with the same vector at k = 1 (c gets [a, b]), or, with distinct vectors and the factory defaults, a word that the search for k + 1 hits stops before reaching, although it is its own strict nearest neighbour (w138 of a 500-word clustered model gets 6 synonyms). The extra synonym is the next-best hit and passes the threshold; nothing fails. It has been there since the filter was added (#12169, first released in 9.7.0), fails on all 24 releases run and on main, and stopping the loop at k fixes it.

• Word2VecSynonymFilter (org.apache.lucene.analysis.synonym.word2vec, analysis-common, @lucene.experimental; factory SPI name Word2VecSynonym, defaults maxSynonymsPerTerm = 5, minAcceptedSimilarity = 0.8). For every input token it asks a Word2VecSynonymProvider for synonyms and emits each as a SYNONYM token at the same position.
• Word2VecSynonymProvider builds an HNSW graph over the model's normalised vectors once, then getSynonyms(term, maxSynonymsPerTerm, minAcceptedSimilarity) searches it with the query word's own vector. Each hit has a score (1 + cosine) / 2.
• HNSW search is approximate: it keeps the best topK hits found so far and stops when no unexplored candidate can beat the worst of them (HnswGraphSearcher.java:177-186, :304-355), so a larger topK can make it explore further (it is not a fixed-size beam), and it can miss true neighbours. That is accepted; returning more than the maximum is a different property.

1. getSynonyms calls HnswGraphSearcher.search(scorer, maxSynonymsPerTerm + 1, hnswGraph, null, Integer.MAX_VALUE) (Word2VecSynonymProvider.java:82-90), with the comment "When looking for the top-k it's always the nearest neighbour of itself so, we look for the top-k+1" (:85-86).
2. The loop over the hits keeps every hit that is not the query word and whose score is at least minAcceptedSimilarity (:93-102). There is no cap at maxSynonymsPerTerm.
3. When the query word is among the hits, at most k others remain. When it is not, all k + 1 remain if they pass the threshold, and Word2VecSynonymFilter emits all of them (Word2VecSynonymFilter.java:95-99, :79-89).
4. Two legal inputs leave the query word out. Ties: at least k + 2 words with the same normalised vector; equal scores break towards the smaller ordinal (NeighborQueue.java:95-96), but which tied word loses its own slot depends on the order in which the search collects them (in the 3-word repro at k = 1 it is c). Distinct vectors: the search for k + 1 hits stops before it reaches the query node.

The search also misses w131, the true nearest other word; that is ordinary approximate recall. The bug is the sixth word, w133 (score 0.9366). The search for 7 hits (k = 6) finds w138 itself, so the search for 6 stops too early; w138 is not unreachable. The 500 vectors are pairwise distinct: every word's cosine with itself beats its best cosine with any other word by at least 0.0209.

• Who. Applications that use Word2VecSynonymFilter (directly, through its factory, or by SPI name, for example with CustomAnalyzer) or call Word2VecSynonymProvider.getSynonyms. The classes are @lucene.experimental and opt-in. With any model and any maxSynonymsPerTerm, the factory defaults included; which words are hit depends on the model.
• Effect. For an affected word, every occurrence gets one synonym more than configured: the (k + 1)-th best hit of the search, a model word that still passes minAcceptedSimilarity. Indexed terms or query expansions differ from what the setting promises; what that does to relevance depends on the application. No exception and no extra search work.
• Scale. Deterministic per model as long as HnswGraphBuilder.randSeed keeps its default 42 (a public, mutable static field "public to expose for testing"; Lucene's core HNSW tests change it, no analysis-common test does), so the same words are affected every time. Measured on synthetic clustered models only (8 to 64 dimensions, 500 to 10,000 words; no real word2vec model was measured):
  • factory defaults (5, 0.8): 1 of 500 words (finder), 4 of 4,000 (independent reproducer), 0 to 2 of 10,000 in four 10,000-word models; 0 to 4 per model in 27 models of 1,000 to 4,000 words, non-zero in 8 of them;
  • maxSynonymsPerTerm = 1 (threshold 0.8): 0.1% to 0.8% of words in the 27 models (at most 33 of 4,000), 0.2% to 0.55% in the finder's 2,000- and 10,000-word models.
• Ties. The tie trigger needs at least k + 2 words with one normalised vector (seven at the default k = 5); how often real models have that was not measured. The tie case is the smallest repro, the distinct-vector case the realistic one.
• How likely. Plausible within the opt-in feature: no special input is needed, but only a small fraction of words is affected, and the extra word looks like a reasonable synonym, so it is easy to miss.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: maxSynonymsPerTerm=1: expected at most 1 synonym of c, got [a, b]
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.assertTrue(Assert.java:42)
       org.apache.lucene.analysis.synonym.word2vec.TestWord2VecSynonymProviderMaxSynonyms.testTiedVectorsMaxOneSynonym(TestWord2VecSynonymProviderMaxSynonyms.java:33)

• Contract. Word2VecSynonymFilter.java:58: "@param maxSynonymsPerTerm maximum number of result returned by the synonym search". The filter passes the value to getSynonyms (:95-96) and emits everything it gets back.
• The provider's own contract, originally. In the first revision of #12169 (2abb1ea6de1), a SynonymProvider interface documented getSynonyms(BytesRef term, int maxSynonymsPerTerm, float minAcceptedSimilarity) with exactly this @param. The interface was removed in review as a single-implementation interface, and the sentence survived only on the filter constructor.
• Upstream test. TestWord2VecSynonymFilter.java:57-81: maxSynonymPerTerm = 2, expected output a plus exactly the two SYNONYM tokens d and e. The query word is among its hits there, so the test supports the bound but does not cover the self-miss case. It passes on stock and with both fixes.
• The + 1 is only room for the query word. The comment at Word2VecSynonymProvider.java:85-86 says so; the factory validates the value as a positive count (Word2VecSynonymFilterFactory.java:72-76).
• History. The #12169 review (33 review comments, 38 conversation comments) discussed thread safety, the visited limit, BoostAttribute and the model reader, never the cap or a missing self-hit. No later commit, test, CHANGES or MIGRATE entry accepts k + 1 results. Silence in a review is weak evidence of intent; the contract, the code comment and the original javadoc carry the argument.

The strongest not-a-bug case (the intended-behaviour devil's advocate): HNSW is approximate by design, so one more approximation artifact is acceptable; the @param may describe the kNN search size rather than the synonym count; getSynonyms has no javadoc and the package is experimental; equal vectors are rare in trained models; and the extra synonym passes the threshold, so it is harmless.

Why it fails: missing some true neighbours is accepted approximation, but returning more than an explicit maximum is a different property, and the code shows the + 1 exists only as room for the query word. Read as "the search size", the sentence is still broken, because the search is called with k + 1. The original interface javadoc ties the sentence to getSynonyms, and the upstream test treats it as the output count (in a case where the query word is among the hits). A read-only reviewer from another model family (OpenAI GPT-5.6) put it as: "Experimental status and approximate-neighbor semantics do not authorize violating an explicit output bound." Only a severity argument survives (one extra, plausible synonym), which is why the bug ranks low. Verdict: not intended.

Two equivalent code fixes were built and run in a scratch worktree at a9779ef3c193; a larger alternative is listed without a run. A is recommended: the smallest change, and it does no extra work.

Add result.size() < maxSynonymsPerTerm to the loop condition in getSynonyms (Word2VecSynonymProvider.java:93) and correct the comment that says the query word is always among the hits.

              // The query vector is in the model, so it is usually its own nearest neighbour:
              // look for the top-k+1 and skip it below. It can be missing from the hits (tied
              // vectors, approximate search), so the loop below also stops after k synonyms.
              maxSynonymsPerTerm + 1,
              ...
      for (int i = 0; i < topDocs.scoreDocs.length && result.size() < maxSynonymsPerTerm; i++) {

Trade-offs

• For positive k (the factory rejects k <= 0; the filter constructor and getSynonyms do not check k), output changes only when the query word is missing from the hits; otherwise at most k others pass anyway.
• With it, c gets [a], w138 gets [w136, w121, w127, w139, w135], and no word of the 500-word model overruns for any k from 1 to 7.
• It does not touch the + 1 itself, which overflows at Integer.MAX_VALUE (a separate bug with a search-size clamp as its fix); the two fixes compose.

What the checks validated

Gradle in a scratch worktree at a9779ef3c193, seed DEADBEEF: the word2vec test package plus the three repro classes, 7 classes, 30 tests, 0 failures, with assertions on and off (the 9 repro tests that fail on stock pass; the 21 upstream tests pass); the whole :lucene:analysis:common:test task with the three repro classes added, assertions on: 342 classes, 1,918 tests, 0 failures (18 skipped by the module itself); :lucene:analysis:common:check -x test with the fix and this doc's test added passes (google-java-format, ecj lint, forbidden APIs). Through the repro runner with the fixed file shadowed, this doc's test passes 2 of 2 with assertions on and off.

After the loop, while (result.size() > maxSynonymsPerTerm) { result.removeLast(); }. Same output as A; it builds one extra entry in the overrun case. Run: the word2vec package plus the three repro classes, assertions on, 30 tests, 0 failures. The same idea in the 9.7.0 code shape (the 9.7.0 file shadowed onto the 9.7.0 jars) passes the finder's test.

      while (result.size() > maxSynonymsPerTerm) {
        result.removeLast();
      }

Trade-offs

Equivalent to A; slightly more work in the overrun case. Not run on the whole module.

Pass acceptOrds that rejects the query word's ordinal to HnswGraphSearcher.search(scorer, k, ...) and drop the term comparison.

Trade-offs

States the intent directly, but Word2VecModel has no public term-to-ordinal lookup (it needs a package-private accessor), and the kept hits shrink from k + 1 to k, so the search stops earlier and results can change for every word, not only the overrunning ones. Not run. A wider search alone is not a fix: ties can still push the query word out.

Method: bounded-exhaustive translation validation (the hunt's "semi-formal" tier): the stock analysis-common jar against an exact-cosine reference of getSynonyms, with the oracles "getSynonyms returns at most maxSynonymsPerTerm" and "the filter emits at most maxSynonymsPerTerm SYNONYM tokens".

• Scope: every 2-D model of 2 to 4 words on a 30-degree direction grid in all insertion orders, 3-D multisets of 3 to 4 of 26 directions, k = 1 to 5, several thresholds.
• Result: 385,120 of 11,048,256 provider checks and 144 of 328,320 filter checks fail, all with tied vectors. Mutants of the other oracles were killed, so the comparison was not vacuous.
• A second harness on clustered models of 2,000 and 10,000 distinct random vectors showed the same overrun without ties: the search for k + 1 hits stops before it reaches the query word itself.
• Both were reduced to a public-API JUnit test on the stock main jar; an independent reproducer wrote its own test from the claim alone and checked by brute force that every overrunning word is its own strict nearest neighbour.