Proposal: Improving Orangu's Code Search with Hybrid Retrieval

[Youssef-joe]

Proposal: Hybrid (lexical + semantic) ranking for semantic_search

Summary

Add a lightweight BM25 index over the existing Tree-sitter symbol chunks, and fuse its ranking with the current cosine ranking using Reciprocal Rank Fusion (RRF) — before the existing diversity and graph-expansion steps. The semantic_search tool keeps its current interface. As a side effect, the lexical half works without an embeddings server, so the tool can still return ranked results when embeddings are unavailable.

I'd like to start with a proof of concept plus a small, committed benchmark on orangu's own repository, and only propose merging if the numbers justify it.

Problem

Today semantic_search ranks symbols purely by embedding similarity. That works well for conceptual queries ("where do we retry failed requests?") but is weaker for queries that hinge on an exact token:

• identifiers and constants (EMBED_BATCH_TOKEN_BUDGET, GraphStore::lookup)
• error and log strings ("graph_store mutex poisoned")
• config keys, endpoint paths, library names

Orangu already has lexical tools, but none of them produce a ranking that can be combined with semantic results:

Tool	What it does	Limitation for this use
search_text	Regex, line-level, .gitignore-aware	Unranked; only offered to custom agents that allowlist Grep
graph_lookup	Substring match on symbol names, sorted by degree	Names only, not bodies; no relevance score
rg via run_shell_command	Fallback suggested when embeddings are off	Unranked, costs the agent extra turns and context

Two specifics in the current pipeline (src/embeddings/index.rs, EmbeddingIndex::search) make this more than a theoretical gap:

1. Sketch pre-filtering can drop exact matches. Before cosine scoring, chunks are restricted to files whose module sketch matches the query vector (threshold 0.35), plus the 3 most recently modified files. A file containing the exact identifier the user typed can be filtered out before it is ever scored.
2. No embeddings server → no ranked search at all. The subsystem stays dormant and the tool returns an error pointing to graph_lookup or rg.

Current pipeline (for reference)

• Chunking (src/embeddings/chunk.rs): one chunk per extracted symbol, text = "<symbol> in <file>\n<body>", body truncated to 1,600 chars. Chunk ids equal graph node ids.
• Index: vectors in ~/.orangu/workspace/<hash>/embeddings/chunks.json, incremental via per-file sha256. Chunk text is not persisted.
• Search: sketch pre-filter → cosine ranking → diversity penalty (×0.5 above 0.85 similarity) → graph expansion of top seeds along call edges (×0.6) → token-budget cut.

Proposed design

                     query
                       │
          ┌────────────┴────────────┐
          ▼                         ▼
   BM25 over chunks           sketch filter
   (no sketch filter)               │
          │                   cosine ranking
          │                         │
          └──────────┬──────────────┘
                     ▼
            RRF fusion (k = 60)
                     ▼
     diversity penalty   (existing)
                     ▼
     graph expansion     (existing)
                     ▼
     token budget cut    (existing)
                     ▼
               semantic_search

Lexical index

• Built over the same chunks, during the same refresh, keyed by the same per-file sha256 map — so only changed files are re-tokenised.
• Code-aware tokenisation: split camelCase, snake_case, :: and paths; lowercase; keep the original full identifier as an extra token so exact matches score highest.
• Field weighting: symbol name and file path weighted above the body.
• In-memory BM25 (a few hundred lines, no new heavy dependency). Workspaces here are thousands of symbols, not millions, so tantivy or similar seems unjustified unless the benchmark says otherwise.
• Persist either chunk text or the token postings next to chunks.json (open question below).

Fusion

• RRF(d) = Σ 1 / (k + rank_i(d)) over the lexical and semantic lists, k = 60 by default.
• Rank-based, so BM25 scores and cosine similarities never need to be put on the same scale.
• Lexical candidates bypass the sketch pre-filter, which fixes problem 1.
• The fused list feeds the existing diversity and graph-expansion steps unchanged, so lexical hits also get their callers/callees pulled in.

Degradation

• Embeddings available → hybrid.
• Embeddings unavailable → lexical-only ranking (plus graph expansion, since the graph does not need embeddings), instead of an error.
• Lexical index failure → current semantic-only behaviour.

Interface

• semantic_search { query } unchanged. Output format (format_hits) unchanged, optionally tagging each hit with which list(s) it came from.
• No new config knobs in the PoC; add a strategy setting only if the benchmark shows a case for it.

--> Updated Design — Based on Maintainer Feedback

Following the discussion and maintainer feedback, the PoC design has been refined as follows.

1. Lexical Index Architecture

• Introduce an independently versioned lexical postings sidecar.
• Share file discovery and SHA-256 computation with the existing embedding index.
• Maintain independent per-file processing state for each cache.
• Index the full extracted Tree-sitter symbol range without changing the existing embedding truncation behavior.
• Store postings and the necessary symbol metadata rather than retaining entire source files.

2. Query Processing and Verification

• Use BM25 over the lexical postings.
• For quoted phrases, intersect query-term postings to identify candidates, then verify phrase order and adjacency against source.
• Group candidates by file, load each candidate file once per query, and verify matches only within the corresponding symbol source range.
• Treat source verification as a reranking/validation mechanism, not a general recall guarantee.

3. Ranking and Fusion

• Prioritize verified exact identifier and phrase matches for explicit identifier or quoted-phrase queries.
• Apply Reciprocal Rank Fusion (RRF, k=60) to combine the remaining lexical and semantic candidates.
• Preserve the existing diversity penalty, graph expansion, and token-budget behavior.

4. Fallback Behavior

• Support lexical-only retrieval when the embedding server is unavailable at startup.
• Support lexical-only fallback if the embedding server becomes unavailable after startup.
• Preserve semantic-only behavior when lexical retrieval is unavailable but embeddings remain operational.
• Test lexical-only behavior through both /search and semantic_search.

5. Benchmark and Evaluation

• Compare semantic-only, lexical-only, and hybrid retrieval using indexed symbols emitted by the current Rust extractor.
• Evaluate MRR, Recall@5, latency, indexing time, and sidecar disk size.
• Track standalone constants that are not currently extracted as separate coverage gaps rather than treating them as retrieval ranking failures.

The implementation will remain scoped to the lexical postings sidecar, BM25 retrieval, phrase verification, RRF integration, fallback behavior, and benchmarks. Changes to the existing symbol extraction strategy remain outside the initial PoC scope.

[jesperpedersen]

@sksingh2005 PTAL

[ecleon26]

currently the Chunk_file generates text for embedding, but EmbeddedChunk just keeps the vector and metadata (chunk.rs, index.rs). The chunk text is not retained by the current index.

i think you should determine if text is persisted or postings/tokens are stored in the lexical index. A distinct, versioned lexical sidecar that is updated from modified source files is what I would suggest

it will also avoid keeping the entire source text while enabling lexical search from cache.

[Youssef-joe]

WOW, Agreed، I'll go then for a separate, versioned lexical sidecar (postings + per-chunk lengths) next to chunks.json, updated incrementally from the same per-file sha256 map, and not persist chunk text. Keeping its version independent from INDEX_VERSION means tokenizer changes won't force re-embedding, and building it straight from the Tree-sitter output keeps lexical-only search possible without an embeddings server.

Two details I'd plan for --> (1) phrase/exact-string queries.. rather than storing positions, I'd verify the top-N lexical candidates against the source file at query time, which also gives a matching line to show;

(2) BM25 corpus stats (doc frequency, avg length) would be recomputed on load rather than appended, since they change with every file update.

How abt that ?

[ecleon26]

seems like a sound plan, i will recommend considering source verification a reranker rather than a recall guarantee. If you don't verify all top N BM25 candidates, you may miss a phrase match that falls outside top N. For quoted phrases or exact-string queries, we intersect the term postings of the query and check those candidates against source. For common queries, scan a larger candidate set, get more matches.

also read each candidate file once. group candidates by file, load each file once per query, and check only the symbol’s source range

and be explicit about the indexed text boundary. decide whether lexical indexing should cover the full extracted symbol range or intentionally share the embedding truncation.

[Youssef-joe]

Thanks, these are important points. I agree that source verification should be treated as a reranking/validation step, not as a guarantee of recall.

For exact-string and quoted-phrase queries, I'll explore intersecting the query terms postings first, then verifying phrase order and adjacency against the original source as well

and for broader queries, I'll use a larger candidate set rather than relying on a small fixed top-N.

will also group candidates by file, load each candidate file once per query, and verify matches only within the corresponding Tree-sitter symbol range.

Regarding the indexed text boundary, my initial preference is to index the full extracted symbol range lexically, while keeping the existing 1,600-character truncation for embeddings. This gives lexical search coverage beyond the embedding input limit without changing the existing embedding behavior. I'll account for the additional index size and benchmark it.

and for sure i see incorporating these decisions into the PoC design before implementation though is the right direction right?

[sksingh2005]

Yes, I think that’s the right direction for the PoC. I’d go with the independently versioned postings sidecar and index the full extracted symbol range. Share the file walk and hash computation with the embedding index, but let each cache track which files it has successfully processed.

For quoted phrases, intersecting the postings and reading each candidate file once sounds right. I’d also give verified exact matches priority for explicit identifier or phrase queries. With RRF alone, a result that appears in both lists can outrank an exact hit that only appears in the lexical list.

I’d test lexical-only behavior through both /search and semantic_search, including when the embedding server goes down after startup. One benchmark correction: our Rust extractor doesn’t emit standalone constant definitions, so MAX_CHUNK_CHARS and EMBED_BATCH_TOKEN_BUDGET can’t be expected as direct hits with the current chunking. I’d use indexed symbols for the ranking comparison and track those constants separately as coverage gaps.

[Youssef-joe]

okayyy big thanksss

from that --> this clarifies several important implementation details.

I'll incorporate these decisions into the PoC:

• A separately versioned lexical postings sidecar, sharing file discovery and SHA-256 computation with the embedding index while maintaining independent per-file processing state.
• Full extracted symbol-range coverage for lexical indexing, without changing the existing embedding truncation.
• Verified exact identifier and phrase matches will receive priority over ordinary RRF results, while RRF will continue to fuse the remaining candidates.
• Phrase verification will intersect term postings, group candidates by file, load each file once, and inspect only the relevant symbol ranges.
• i'll test lexical-only behavior through both /search and semantic_search, including an embedding server failure after startup.

and for the benchmark, I'll use symbols that are actually emitted by the current Rust extractor for ranking comparisons, and document standalone constants such as MAX_CHUNK_CHARS and EMBED_BATCH_TOKEN_BUDGET separately as extraction coverage gaps.

then will review the existing cache and extraction lifecycle before settling the sidecar format and implementation details. Thanks for the guidance!