Add deterministic BM25 retrieval for generic graph queries

[forhappy]

Problem Statement

Compass has two lexical retrieval paths. Typed search uses a persistent SQLite FTS5 accelerator for JSON graphs and exact term postings for store graphs, while generic and traversal-controlled natural-language queries scan and normalize every graph node for every request. The generic path therefore has weaker retrieval scalability and still needs stronger independently qualified recall.

The morphology and compound-identifier work in #205 improves lexical matching but does not create a reusable candidate index. Natural-language output remains exploratory and must not be treated as authoritative without reviewed judgments.

Solution

Add a deterministic native fielded BM25 index for the generic graph text-traversal path. The index is derived lazily from the validated graph, remains local and disposable, and is reused for the lifetime of the loaded graph. BM25 supplies bounded candidates only; existing exact-match priority, structural evidence, ambiguity handling, deterministic tie-breaking, and graph traversal continue to decide and explain results.

Deliver this in two stages. The first adds an opt-in shadow profile and qualification evidence without changing default behavior. The second promotes the profile only after an explicit relevance, determinism, memory, and latency review.

Typed FTS5/store search remains unchanged in the first deliverable. Persistent and incremental maintenance of the generic BM25 index is specified separately in #208.

Commits

1. Add independently reviewed baseline judgments for Python, Rust, and TypeScript queries. Cover exact symbols, morphology, compound identifiers, source anchors, ambiguity, no-answer, must-not-return, pagination, and truncation. Record baseline metrics without changing retrieval behavior.

2. Consolidate deterministic lexical normalization used by graph labels and query terms. Preserve all existing public behavior and add parity tests for Unicode, camel case, snake case, inflections, stop words, and repeated terms.

3. Introduce the lazy lexical-index data model. Build one bounded document per graph node from stable identifiers, display labels, kinds, and source paths. Store deterministic postings, field frequencies, document lengths, corpus document frequencies, and average document length. Leave the index unused by production queries.

4. Add the pure fielded BM25 scorer under versioned profile text-ranker/bm25-v1. Start with k1=1.2, b=0.75, and explicit field weights. Preserve exact identifier and display-name priority outside BM25.

5. Add bounded top-candidate retrieval. Retain exact matches and the best candidate for every query term even when the global candidate budget is reached. Return explicit truncation state instead of treating a limit as an empty result.

6. Add deterministic structural reranking over BM25 candidates. Preserve source-backed declaration preference, callable/type preference, generated/test penalties, compound-identifier evidence, and stable node-ID tie-breaking.

7. Integrate the new scorer behind an opt-in internal profile. Keep text-ranker/full-scan-v1 as the default and retain it as a rollback path. Existing text traversal, graph direction, provenance rendering, and pagination remain unchanged.

8. Add differential integration tests between full-scan and BM25 profiles. Verify exact IDs, repeated labels, Unicode, ambiguity, no-answer, source-backed declarations, generated/test distractors, stable ordering, and repeated-run determinism.

9. Add controlled relevance and performance qualification. Measure Success@1, MRR, Recall@5/20, nDCG, no-answer precision, first-query latency, warm p50/p95 latency, peak memory, and index construction cost on reviewed fixtures and representative real repositories.

10. Publish the reviewed qualification summary. Promote BM25 in a separate pull request only if the approved gates pass; otherwise leave it opt-in and document the failed criterion.

Decision Document

• graph.json remains the authoritative graph and its schema does not change.
• The first implementation targets only generic text-traversal queries.
• The lexical index is lazy, in memory, derived, bounded, and disposable.
• The initial global candidate ceiling is 512 nodes.
• BM25 retrieves candidates; it does not invent graph direction or relationship meaning.
• Exact IDs, exact names, source anchors, structural kinds, and deterministic tie-breaking remain authoritative ranking signals.
• The initial profile uses k1=1.2, b=0.75, label/name weight 4.0, qualified identifier/ID weight 3.0, kind weight 1.0, and source-path weight 0.5.
• The existing typed query response schema does not change.
• Typed JSON/store search remains byte-identical and unchanged in the first deliverable.
• Existing FTS5 ranking is not used directly because it would diverge from the store backend.
• No new runtime service, credential, model, vector database, or external product dependency is introduced.
• Promotion is a separate reviewed cutover, not part of the shadow implementation.

Testing Decisions

Good tests assert externally observable ranked identities, source anchors, ambiguity/no-answer behavior, truncation, deterministic ordering, and graph traversal output. They do not derive expected results from the ranker being tested or assert private posting layout.

The graph model receives deterministic index-construction and bounded-lookup coverage. The query module receives profile, ranking, seed-selection, and traversal behavior coverage. The CLI and shared query contracts are rerun to prove no default behavior or machine-schema change. Existing relevance qualification, natural-query goldens, scale tests, store parity tests, CompassQL gates, and product-boundary checks provide prior art.

Promotion gates require no regression in exact Success@1, edge direction, path acceptance, no-answer precision, or must-not-return judgments; at least 10% relative improvement in reviewed Recall@5; non-regressing MRR; identical repeated ordering; at least 30% better warm latency on the 100,000-node workload; and no unreviewed first-query or memory regression above 10%.

The previous required-substring probe remains diagnostic and is not a semantic acceptance gate.

Out of Scope

• Embeddings and vector databases.
• Changing the graph JSON schema.
• Requiring SQLite for ordinary graph JSON queries.
• Replacing typed query operations or CompassQL.
• Changing typed FTS5/store ranking in the first deliverable.
• Indexing arbitrary graph attributes.
• Adding external-product runtime, test, configuration, or fallback dependencies.
• Rewriting historical graph or store realizations.

Further Notes

The shadow implementation is stacked on #205. The default ranker must not change before the qualification checkpoint is reviewed. Follow-up #208 defines the fully persistent, incremental, generation-safe index and the separate evidence-gated BM25 default cutover.