Wave 4 / Search: lexical query results are irrelevant — bigram index yields near-uniform BM25F scores and misses exact matches

[dean0x]

Summary

skim search "<text>" (the Wave-1 lexical layer that every other layer composes on top of) returns irrelevant results for essentially every query. Exact identifiers return files that do not contain the term, true-positive files are absent or buried below noise, and BM25F scores collapse to a near-constant value regardless of whether the query term is present. A gibberish string matches 100 files.

This is the primary blocker for the North Star goal of standing toe-to-toe with grep (#174): on every symbol/identifier query tried, grep returns the correct files instantly and skim search returns almost none of them.

Root cause: the lexical index is a byte-bigram index with no exact-match verification. Bigrams are far too coarse to discriminate code identifiers.

Severity

🔴 Blocker for the #174 North Star ("beat grep"). The compound engine (#198/#200/#201/#202) fuses lexical ∩ AST ∩ temporal — so this noise propagates into every compound result that includes a text query (see #356).

Environment / how it was found

• Branch wave/wave4-search @ 674582458, freshly built ./target/release/skim (v2.10.0), clean working tree.
• Dog-fooded against this repo (666 files indexed). Reproduced on a pristine index built into a fresh SKIM_CACHE_DIR (/tmp/...), so this is not stale-state corruption.

Reproduction

export SKIM_CACHE_DIR=/tmp/skim-repro          # clean-room cache (macOS default is ~/Library/Caches/skim/)
./target/release/skim search "lock" --limit 1 >/dev/null   # cold-start builds a pristine index

# 1. Exact symbol that exists in 10 files / 53 occurrences (verify with grep):
grep -rln "CompositeWeights6" --include='*.rs' crates/      # => 10 files (compound/weights.rs, merge.rs, ...)
./target/release/skim search "CompositeWeights6" --limit 12 # => 0 of those 10 files; only JSON fixtures + unrelated tests

# 2. The file that DEFINES a symbol does not rank:
./target/release/skim search "reparse" --limit 8           # #1 hit = crush.rs:15 "/// Crush session provider." (no "reparse")
                                                           # compound/reparse.rs buried below ~99 irrelevant files

# 3. Gibberish that grep finds 0 times:
grep -rc "zxqwvbnmkjhgfdsa12345" --include='*.rs' crates/  # => nothing (exit 1)
./target/release/skim search "zxqwvbnmkjhgfdsa12345" --limit 100 --json | grep total   # => "total": 100

Evidence

Query	grep ground truth	skim search top results
CompositeWeights6	53 hits in 10 files	0 of the 10 files in top-12 (JSON fixtures, unrelated tests)
reparse	6 files incl. compound/reparse.rs	#1 = crush.rs "Crush session provider" (no match); real file below rank ~99
CrushProvider	defined in crush.rs, session/mod.rs	neither defining file in top-5
intersect_and_rank	8 files incl. compound/intersection.rs	none of the 8 in top-5
zxqwvbnmkjhgfdsa12345 (gibberish)	0	100 matches, score 13.22

Scores are degenerate — e.g. for reparse: 4.96, 4.96, 4.96, 4.96, 4.95, 4.95, 4.95, 4.94. A near-constant score across all docs means the ranking signal is effectively flat: a file containing the query term gets no meaningful boost over a file that merely shares the query's letter-pairs (which is nearly every file).

Root cause

The n-gram is a 2-byte bigram keyed into a u16:

• crates/rskim-search/src/ngram.rs:50 — pub struct Ngram(pub(crate) u16);
• crates/rskim-search/src/ngram.rs:58-60 — from_bytes(b1, b2) = (u16::from(b1) << 8) | u16::from(b2)
• crates/rskim-search/src/ngram.rs:198 — index extraction walks bytes.windows(2) (bigrams)
• crates/rskim-search/src/ngram.rs:243-311 — extract_query_ngrams_with_weights decomposes the query into a covering set of bigrams.
• There is no exact-substring / token verification anywhere in the scoring path: a bigram match is taken as final (the result's is_match line frequently does not contain the query term).

Why this can't work for code search: there are at most ~65k possible bigrams, and common code bigrams (re, in, er, pa, se, ar, …) occur in nearly every file. So (a) IDF can't separate relevant from irrelevant documents, and (b) BM25F length-normalization then lets short files (JSON fixtures) win on incidental bigram overlap. The same mechanism makes the index enormous (see linked size/latency issue) because common-bigram posting lists are huge.

Design directions for a fix (not prescriptive — needs a design pass)

Any one or a combination, to be evaluated:

1. Increase n-gram width to trigrams (or token-aware n-grams). Trigrams (u32/24-bit key) are dramatically more selective; the existing covering-set + BM25F machinery can likely be retained. Re-tune the sparse weight table.
2. Exact-match verification pass. Keep bigrams (or trigrams) purely as a candidate generator, then verify the literal query substring/token actually occurs in each candidate before scoring/ranking (cheap on a bounded candidate set). This directly fixes "gibberish matches" and "term-absent top hits."
3. Identifier/token-aware indexing. Split CamelCase/snake_case into sub-tokens and index whole tokens, so CompositeWeights6 indexes composite,weights,6 rather than letter pairs.
4. Re-examine BM25F field/length normalization once selectivity is fixed, since the degenerate-score symptom is partly amplified by short-doc favoritism.

Whatever is chosen will need a re-tune of the AST/IDF weight tables (crates/rskim-search/src/ast_weights.rs is auto-generated via rskim-research).

Acceptance criteria

• For an exact identifier present in the corpus, the file(s) that contain it rank in the top results; the file that defines it ranks at/near CLI language argument uses unexpected kebab-case names #1.
• A query term that is absent from the corpus returns 0 results (gibberish test passes).
• Every returned is_match line actually contains the query term (or a documented fuzzy variant).
• A relevance regression test (e.g. precision@k against a small labeled fixture set) guards this so it can't silently regress again. Note: existing search tests assert "returns some results" but do not assert the correct file ranks first — that gap let this ship.

Related

• Tracking: North Star: 3-Layer Code Search System (skim search) #174 (Wave 4)
• Lexical layer origin: Wave 1 (Wave 1a: Sparse n-gram algorithm (bigram weights, covering set) #177 sparse n-gram algorithm, Wave 1c: BM25F scoring engine with AST-derived field weights #180 BM25F)
• Propagation into compound intersection: Wave 4 / Search: compound text+--ast intersection silently drops valid matches — CANDIDATE_POOL_K couples --limit to the lexical candidate pool #356 (--limit/CANDIDATE_POOL_K)
• Index size/latency consequence: Wave 4 / Search: index size (~455% of source) and query latency exceed #174 targets #358