Skip to content

Latest commit

 

History

History
431 lines (305 loc) · 15.5 KB

scoring.md

File metadata and controls

431 lines (305 loc) · 15.5 KB

Search ranking

This document describes the production search pipeline shared by the VS Code/Cursor extension and the Neovim sidecar. For installation and everyday use, start with the project README. For settings and preset values, see Configuration.

Design goals

The ranker is built around four constraints:

  1. Recall before speed shortcuts. A fast rejection must never remove a file that the full matcher could accept.
  2. Explicit text before inferred context. A decisive lexical winner must remain protected from an unusually large repository prior.
  3. Bounded work on every keypress. Index-time features, prefix reuse, early exits, and top-K selection keep the typing path small.
  4. Deterministic output. Equal scores use stable filename, path, identity, and original-order tie breakers.

Result publication is a separate adapter responsibility. The ranker returns detached arrays; the VS Code picker, protocol server, and Neovim picker each enforce the one-publication rule described in Cross-editor architecture.

Pipeline

flowchart TD
    A["Immutable file catalog"] --> B["Reuse safe prefix candidate pool"]
    Q["Normalize current query"] --> B
    B --> C["Letter-mask rejection"]
    C --> D["Lexical token scoring"]
    D --> E["Context scoring"]
    D --> F["Measure top lexical confidence"]
    F --> G["Scale and cap repository priors"]
    E --> H["Bounded top-K heap"]
    G --> H
    H --> I["Detached ranked and matched arrays"]
Loading

For one non-empty query:

  1. normalize the query;
  2. choose the narrowest safe cached prefix pool;
  3. reject candidates that cannot contain all query letters;
  4. require every token to match;
  5. score lexical structure;
  6. add local editor context and query-learning scores;
  7. estimate whether the top lexical results are genuinely ambiguous;
  8. add confidence-gated contributor/worktree priors when the adapter supplies them;
  9. retain only the bounded visible top-K while still returning the complete lexical match set for future prefix reuse.

The empty query skips lexical work and ranks the browse view by frecency.

Index-time candidate features

Each candidate carries its immutable display identity plus fields reused on every input:

  • basename and relative path;
  • directory;
  • nearest package root from package.json or project.json;
  • workspace-root identity for multi-root separation;
  • lowercase basename and path;
  • final-extension-free filename stem;
  • module-family stem with conventional role suffixes removed;
  • basename acronym;
  • a 26-bit ASCII-letter presence mask.

Module-family suffixes currently include:

  • .test, .tests;
  • .spec, .specs;
  • .story, .stories;
  • .d;
  • .gen, .generated.

For example, queryCompiler.test.ts has:

  • filename stem querycompiler.test;
  • module stem querycompiler;
  • acronym qct.

This lets explicit selection memory choose a test counterpart without making unrelated names such as content-config.ts equivalent to config.ts.

The mask is built from the same lowercased search path used by matching. That detail preserves recall for Unicode characters whose lowercase form introduces an ASCII letter.

Query normalization

Production ranking:

  1. trims outer whitespace;
  2. converts \ to /;
  3. lowercases;
  4. splits on one or more whitespace characters.

All tokens use AND semantics. A candidate missing any token is removed.

Selection learning additionally applies Unicode NFKC normalization and collapses repeated whitespace before using a query as a persisted key.

Safe incremental candidate reuse

IncrementalSearchMatchCache retains a small least-recently-used map of normalized queries to their complete lexical match arrays.

If the next normalized query extends a cached query, the new search starts from that cached match array rather than the full workspace:

c -> co -> component

This is recall-safe because adding characters to the current query cannot make a file that failed the shorter prefix become a match. Deleting, replacing, or reordering text falls back to the narrowest compatible prefix or the full catalog.

Ignored files are included in cached lexical membership even when hidden from the current display. Changing visibility therefore cannot poison an exact-query cache entry.

Replacing the catalog atomically clears the cache.

Fast lexical rejection

Letter-presence mask

Before substring or fuzzy work, the ranker computes the query's ASCII-letter mask. A candidate is discarded if its precomputed mask lacks any required bit.

The mask ignores order, multiplicity, digits, punctuation, and non-ASCII code points. It is only a necessary-condition filter, never the final matcher.

Selective token plan

Token membership is commutative, so longer tokens are tested first as a cheap proxy for selectivity. The user's original order is retained separately for path-structure scoring.

This often rejects a candidate on the rare token before running work for a generic token.

Repeated-token validation

A query such as risk risk must consume two distinct path occurrences. After the fast token pass, repeated-token queries use the structured lexical aligner, which enumerates useful occurrences and uses dynamic programming to select monotonically ordered, non-overlapping ranges.

One occurrence can never satisfy the same repeated token twice.

Per-token match hierarchy

For each candidate and token, matching stops at the first applicable category:

Order Match kind Example or behavior
1 Basename exact button.tsx → button.tsx
2 Filename-stem exact button → button.tsx
3 Module-family stem exact querycompiler → queryCompiler.test.ts
4 Full-path exact src/search/config.ts → the complete path
5 Full-path prefix Used only when the token expresses path intent
6 Basename prefix button → button-grid.tsx
7 Basename boundary Separator or lower-to-upper camel-case boundary
8 Basename acronym qc → QueryCompiler; hs → HTTPServer
9 Basename substring Lower-value containment
10 Package exact/prefix/etc. Matches the basename of the nearest package root
11 Full-path boundary Boundary match elsewhere in the path
12 Full-path substring Lower-value path containment
13 Basename fuzzy Ordered-character subsequence
14 Package fuzzy Ordered-character subsequence against the package name
15 Full-path fuzzy Final ordered-character fallback

Boundary matching recognizes:

  • start of value;
  • /, \, -, _, ., or space;
  • a lower-case/digit to upper-case camel transition.

Acronym extraction additionally splits an upper-case run followed by a capitalized word, such as HTTP|Server. The basename acronym excludes the final extension. foo.ts therefore has acronym f, not ft.

Fuzzy scoring

Fuzzy matching is an ordered-character subsequence. It rewards:

  • each matched character;
  • an early start;
  • contiguous streaks;
  • boundary hits;
  • ending on the target's final character.

It penalizes:

  • skipped gaps;
  • a late start;
  • excess target length.

Fuzzy matches remain available for abbreviated input, but their base tier is far below exact, stem, prefix, and boundary intent in the balanced and exact presets.

Multi-token structure

After every token matches, the scorer:

  • rewards tokens landing in multiple path segments;
  • rewards forward movement through the path;
  • penalizes reversed or non-progressing path order;
  • rewards a package token paired with a basename token;
  • subtracts a small full-path length penalty.

Membership is still AND-based, so a reversed query can match when every token is present. It simply loses to a candidate matching the user's structural order.

Context scoring

Context is added after lexical filtering.

Frecency

Frecency uses time-decayed visits and a logarithmic score transform. The active preset controls:

  • half-life;
  • browse and non-empty-query multipliers;
  • dwell threshold for implicit visits;
  • implicit and explicit open weights;
  • duplicate-visit window.

The empty browse view uses only frecency. Non-empty queries interpolate from the browse multiplier to the query multiplier over the first three non-space characters.

The store is bounded to 20,000 persisted records. Cold records are pruned, writes are debounced, and mutations arriving during an in-flight write are preserved for the next atomic snapshot.

Query-selection memory

Selecting a file records:

  • the exact normalized query;
  • bounded meaningful token forms;
  • bounded character prefixes of the full query and tokens.

Exact forms receive full weight; generated token and prefix forms receive lower weights. Lookup is an O(1) map access on the typing path—no fuzzy learning lookup occurs during ranking.

Defaults:

  • 30-day half-life;
  • at most 8 candidate associations per query;
  • at most 12 forms recorded per selection;
  • at most 4,096 total associations.

Pinned associations receive a fixed strong score and do not decay out. The Ranking Preferences command can pin, unpin, delete, or reset records.

Unlike active/open/directory signals, a learned query association is not tapered by short-query length. Its bounded and logarithmic contribution is intentional.

Editor and Git-tracking context

For a non-empty query, the following signals ramp from zero to full strength over the first three non-space characters:

  • tracked boost;
  • ignored and untracked penalties;
  • open-file boost;
  • active-file boost;
  • same-package boost;
  • same-directory boost;
  • shared leading-directory segments.

Multi-root identities include the owning workspace folder. A same relative path in two roots does not share frecency, learning, package, or active-file identity accidentally.

These editor-context values are not lexical-confidence-gated. Their configured score scale and the large gaps among lexical tiers protect explicit intent. The additional confidence gate described next applies specifically to repository priors.

Lexical confidence and repository priors

VS Code/Cursor can supply a contributor prior and a current-worktree session prior. Neovim does not currently construct those two signals.

The scorer does not use total result count as its ambiguity measure. A decisive exact match should not become "ambiguous" merely because 100,000 weak fuzzy files exist.

Instead it retains the best and runner-up lexical scores and derives:

  • the lexical score gap;
  • a score temperature proportional to the top score;
  • a bounded ambiguity scale;
  • an absolute contextual score cap.

The raw repository prior is transformed logarithmically, multiplied by short-query strength, then both scaled and clamped by lexical confidence.

Consequences:

  • a near tie can be reordered by strong local repository evidence;
  • a clear exact/stem winner leaves little or no room for the prior;
  • a pathological outlier prior cannot jump across a protected lexical gap;
  • a huge weak tail does not weaken a decisive winner.

The underlying contributor and session models are documented in Contributor intelligence.

Gitignored visibility

Visibility is applied inside the shared SearchEngine, before visible ranking but without corrupting incremental lexical caches.

  • hide: never display ignored files;
  • show: make indexed ignored files eligible for every query;
  • auto: reveal directly indexed ignored files only for an exact filename query containing an extension.

Examples accepted by auto include .env.local and button.component.tsx. Queries such as button, src/button.tsx, or mobile button keep ignored files hidden.

Bounded top-K selection

The picker normally displays at most 200 VS Code/Cursor results or 100 Neovim results.

Sorting every lexical match would cost O(n log n) even though only the first K rows are visible. Production ranking instead maintains a bounded worst-first heap:

  • scan time: O(n log K);
  • retained ranked memory: O(K);
  • final heap sort: O(K log K).

The complete lexical match array is still retained for safe prefix reuse. Tests assert that every bounded result equals the same prefix of a full ordering and that exact ties remain deterministic.

Quality evaluation

evaluateSearchQuality replays every non-empty prefix of labeled query scenarios without publishing anything to an editor. It reports:

  • mean reciprocal rank;
  • success at 1, 3, and 10;
  • first keystroke reaching top 1/3/10;
  • median and p95 prefix latency;
  • adjacent-prefix top-result volatility.

A caller may provide a shadow ranker to compare a proposed model against production over the same chronological scenarios. Learning order remains explicit and outside the evaluator.

The publication invariant is intentionally stricter than the volatility metric: results may differ between two different input revisions, but one revision cannot republish itself.

Performance benchmarks

Synthetic scorer benchmark

bun run bench:search --assert

The benchmark generates 4,000, 50,000, and 100,000 immutable candidates and measures median:

  • broad one-character full-pool search;
  • selective full-pool search;
  • forward and reversed two-token search;
  • zero-hit search;
  • final incremental-prefix search.

--assert enforces deliberately padded CI budgets rather than machine-specific marketing numbers.

Current workspace pipeline

VS Code/Cursor exposes Better Go To File: Benchmark This Workspace. It:

  • builds representative query shapes from the captured index;
  • measures the scorer and the full item-projection pipeline separately;
  • reports cold, median, p95, and maximum duration;
  • yields between samples and supports cancellation;
  • writes detailed per-query rows to the Better Go To File output channel.

The command uses an immutable entry snapshot and does not modify learning or visible search results.

Scoring presets

Five presets change lexical/context weights and visit behavior:

  • balanced;
  • exact;
  • recent;
  • nearby;
  • fuzzy.

The active preset and optional sanitized override produce one immutable ranking configuration for a picker revision. See Scoring presets and custom scoring for the complete user-facing configuration.

Scoring CLI

The CLI runs the same local scorer against any repository without opening an extension host.

bun run score -- --help

Rank a query:

bun run score:search -- --repo /path/to/repository --limit 10 queryCompiler

Include detailed lexical, context, learning, and repository contributions:

bun run score:search -- --repo /path/to/repository --debug queryCompiler

Explain one path and its neighboring ranks:

bun run score:explain -- --repo /path/to/repository queryCompiler src/queryCompiler.ts

Useful controls include:

  • --preset;
  • --customPreset;
  • --activePath;
  • repeated/comma-separated --openPath;
  • --gitignored;
  • --contributorName and --contributorEmail;
  • --frecencyFile or --noFrecency.

The CLI auto-discovers compatible local frecency and contributor snapshots when available.