Modern search engines increasingly store documents in a proximity graph. In this structure each document is a node linked to its most similar neighbors, and a query is answered by walking greedily toward closer and closer nodes. These graphs are fast. They can also be updated in place when documents are added or deleted, which avoids rebuilding the whole index. The repair methods developed for them, however, are judged almost entirely by average recall on dense-embedding queries. Our concern is a different and more fragile group of queries: those whose only usable signal is a rare word fragment. Examples include a misrecognized surname in a speech transcript, an unseen Finnish compound, or a drug code that a semantic embedding blurs into its neighbors. For such queries a document may be reachable only through one or two nodes that happen to share the rare fragment. If those nodes are deleted and the graph is patched by embedding similarity alone, the path can vanish while average recall barely changes.
We propose to build a single graph whose edges combine embedding similarity with overlap in morphs. Morphs are morpheme-like word pieces learned without supervision, as in the Finnish track of Morpho Challenge 2009. We would maintain this graph under streaming churn with two mechanisms. The first is a deletion-repair rule that reserves edges for preserving rare-morph connectivity. The second is a local re-weighting procedure for the case where the morph segmenter itself is retrained on new text and the meaning of the lexical features shifts. We also measure what nobody currently measures, which is how much "rare-term reachability" survives as the index changes. The framing is deliberately falsifiable. If a plain inverted morph index running beside a dense graph keeps tail recall at equal or better throughput, the unified design has no reason to exist, and the experiments are built to show that outcome if it is true.
Core Claim
In a hybrid graph that mixes dense and morph-level lexical similarity, repair after deletion and drift in the segmenter damage two different things. They damage the routes that carry rare-morph queries far more than the routes that carry ordinary semantic queries. A repair rule that explicitly protects shared-rare-morph edges can recover most of that loss at small cost. So can re-weighting only the edges touched by changed segmentations. The resulting system should match a separate inverted morph index on tail recall while keeping the throughput advantage of a single graph.
Where This Sits
Three bodies of work motivate the proposal.
Morph indexing. Morph indexing shows that unsupervised word pieces recover much of the vocabulary mismatch caused by inflection and transcription errors. Unsupervised morphs in a BM25 index reach about 0.47 MAP on Finnish, against 0.49 for the hand-built TWOL analyzer (Morpho Challenge 2009). LSI over morphs further smooths spoken-document noise (Turunen and Kurimo). Subword lattices keep out-of-vocabulary terms reachable in speech (s-PSPL; Lee et al.). All of these use static inverted files or matrices, and none considers a graph or deletion.
Vocabulary mismatch. Work on mismatch shows the problem is common. In WikiQA, 20.3% of correct answers share no content word with the question. Translation-induced synonym shifts in mMARCO break BM25 while dense models hold up. This is why we keep a dense component and do not use morphs alone.
Graph maintenance. Maintenance work supplies our method and also bounds our claims. The DiskANN library keeps over 95% recall across 50 churn cycles by retaining deleted nodes as routing bridges, then consolidating them. SPatch (Mishra et al.) models greedy search as a random walk and replaces a deleted node with a sparsified clique among its neighbors. This clique comes from the star-mesh transform, which preserves walk behavior. SPatch reports 2.5–3x faster queries than tombstones and up to 35x faster deletion than global reconnection, and it frees memory. Both methods assume a fixed dense metric. Allan-Poe (Li et al.) is the closest system to ours. It already fuses dense, sparse and keyword signals in one GPU graph and reports 1.5x–186.4x throughput over multi-index baselines. It uses whole words, though, and handles deletion only by tombstones. DEG (Yin et al.) shows that edges can be kept useful across a runtime-varying mix of two similarity measures, but it does not handle churn.
Our contribution differs from Allan-Poe in three ways: it uses morph-level features, it repairs deletions structurally rather than with tombstones, and it handles segmenter drift. It differs from SPatch in applying repair to a non-Euclidean hybrid similarity, with an explicit rule for preserving lexical connectivity.
Research Program
The graph. We build a Vamana-style graph over documents. The similarity between two documents $u$ and $v$ is $s(u,v) = \cos(e_u, e_v) + \beta \, \mathrm{BM25}_m(u,v)$. Here $e$ is a frozen dense embedding, $\mathrm{BM25}_m$ is a symmetric BM25-style overlap computed over Morfessor morphs, and $\beta$ is tuned on held-out queries. Construction uses this similarity together with the relaxed pruning of the DiskANN library.
Morph-aware deletion repair. When a node $x$ is deleted, SPatch would connect its neighbors in a clique and keep the top $t$ edges by random-walk conductance. We keep $t-r$ edges by that rule. The remaining $r$ slots go to the neighbor pairs with the highest rare-morph score
$$ \rho_x(u,v) = \sum_{m \in M(u)\cap M(v)\cap M(x)} \mathrm{idf}(m), $$
where $M(\cdot)$ is a document's morph set and $\mathrm{idf}(m)$ is the inverse document frequency of morph $m$. The intuition is simple: $x$ was the bridge for the morphs it shared with both endpoints, so the patch should keep at least one direct route carrying those morphs. We will test whether reserving slots is needed, or whether simply adding $\rho$ to the conductance weight suffices.
Segmenter drift. When Morfessor is retrained on newly arrived text, some word types get new segmentations, and the lexical similarity of affected documents changes. Following the span-alignment idea of VocAgnoLM, we record each morph feature as a character span within its word type. This lets us identify exactly which word types changed, and therefore which documents and incident edges need their similarity recomputed and re-pruned. Everything else stays untouched. The empirical question is how local segmenter updates really are. If retraining changes most frequent types, local repair degenerates into a rebuild, and we will report that.
The measurement. We split each query set into a tail-lexical subset and a semantic subset. Tail-lexical queries are those whose relevant documents are retrieved by morph BM25 but not by the dense model alone, which follows the WikiQA-style zero-overlap analysis in reverse. We track tail recall separately throughout churn.
Baselines
Do nothing. The naive reference is a dense-only Vamana graph maintained with the DiskANN consolidate policy. It shows how much tail recall a strong dense index loses to begin with. On this setting we found no reported result on Lacuna for tail-lexical recall under churn. The only churn figure is DiskANN's own report of over 95% average recall across 50 cycles on dense benchmarks.
Dual index. The strongest competitor on our question is a separate inverted morph index running beside a dense graph, with results merged by reciprocal rank fusion. An inverted index never loses a posting when a document is deleted, so on tail recall it is the ceiling to match, not a straw man. It will receive the same morph segmentation, the same embedding model, the same hardware and the same fusion-weight tuning budget as our system. Beating it means matching its tail recall within one point of recall@100 while delivering higher queries per second at equal recall. Allan-Poe's reported 1.5x–186.4x throughput gain over multi-index pipelines is the reference figure, although it was measured without churn and with whole words.
Strongest graph-maintenance method. This is SPatch applied unchanged to our hybrid similarity, with the same $t$. The comparison isolates the reserved rare-morph slots. A second variant runs SPatch on Allan-Poe-style whole-word sparse features instead of morphs, which isolates segmentation. Tombstones are also included, because SPatch's reported 2.5–3x speed gap over them should be reproduced first as a sanity check.
Drift ablations. For segmenter drift we compare three options at each refresh: keeping a frozen segmenter, doing a full rebuild, and doing local re-weighting.
Beating SPatch means a statistically significant gain in tail recall at the end of churn, with semantic recall and query speed within a few percent.
Why not just…?
Why not just keep a separate inverted morph index next to the dense graph? This is the real threat. Inverted files handle insertion, deletion and even re-segmentation cheaply, and they preserve rare-term reachability by construction. The argument for one graph is throughput and the absence of a merge step, which Allan-Poe documents only for static whole-word indices. Our headline comparison is exactly this baseline under churn. If it matches us on tail recall and is within a small factor on throughput, we will report that the unified graph is not worth its complexity for morph retrieval.
Why not just use character n-grams, which never change and so never drift? Morpho Challenge's Arabic track shows that splitting words into raw letters can beat sophisticated segmenters. A fixed n-gram vocabulary would also eliminate the drift problem entirely. The cost is spurious overlap: short fragments collide across unrelated words. In a graph this matters more than in an inverted index, because false overlap creates false edges that misdirect greedy search. We include an n-gram variant of the whole system. If it matches morphs on Finnish tail recall, the drift mechanism is unnecessary and we would drop it.
Why not just fix mismatch at query time with a rewriter? InteR reaches 50.0 MAP on TREC DL'19, against BM25's 30.1. RaFe trains cheap rewriters from reranker feedback. Rewriting, however, cannot guess how an ASR system corrupted an unseen surname, and InteR's iterative LLM passes add latency. RaFe also acknowledges that rewriters suffer semantic drift. Rewriting is complementary to our index rather than a replacement for it, so we run RaFe-style rewriting on top of the dense-only baseline as an extra comparison on the speech and Finnish sets.
Why not just retrain a generative retriever like MINDER? Generative retrievers store the corpus in model weights. Deleting a document therefore requires fine-tuning, which conflicts with the per-cycle update regime studied here. We do not run this comparison.
Proposed Experiments
Streaming protocol. We use the 50-cycle insert/delete protocol of the DiskANN library, and add non-uniform deletion: whole topic clusters, and documents carrying a given rare morph family, are purged together. This is the fragmentation case the research file flags as hard for SPatch. Morfessor is retrained every ten cycles on the text that has arrived.
Corpora. The corpora are chosen to stress morphology, jargon and speech. The Morpho Challenge 2009 Finnish IR collection tests morphology; its static BM25 MAP of about 0.47 is the reference our hybrid should not fall below at cycle zero. MS MARCO passages and TREC-COVID test general and jargon-heavy text. The Finnish spoken news corpus of Turunen and Kurimo (270 stories, 17 topics) is a small probe of ASR-noisy reachability.
Metrics. We report MAP and recall@100 separately on the tail-lexical and semantic subsets, together with queries per second, deletion throughput, memory, and the fraction of edges touched per segmenter refresh.
Decisive checks. Four results settle the proposal. First, does SPatch on the hybrid graph lose more tail recall than semantic recall under clustered deletion? If not, the premise fails. Second, do the reserved rare-morph slots close most of that gap relative to the dual-index ceiling? Third, does local re-weighting touch a small fraction of edges and stay within a point of full rebuild in recall? Fourth, does the unified graph beat the dual index on throughput at matched tail recall? A negative answer to the first or fourth question is itself a useful finding: it would mean rare-term reachability is either not fragile in graphs, or best kept outside them.
References
- Overview and Results of Morpho Challenge 2009
- Using latent semantic indexing for morph-based spoken document retrieval
- Subword-based position specific posterior lattices (s-PSPL) for indexing speech information
- Open-Vocabulary Retrieval of Spoken Content with Shorter/Longer Queries Considering Word/Subword-based Acoustic Feature Similarity
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- mMARCO: A Multilingual Version of MS MARCO Passage Ranking Dataset
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search
- Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
- All-in-one Graph-based Indexing for Hybrid Search on GPUs
- DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph
- Overcoming Vocabulary Mismatch: Vocabulary-agnostic Teacher Guided Language Modeling
- Synergistic Interplay between Search and Large Language Models for Information Retrieval
- RaFe: Ranking Feedback Improves Query Rewriting for RAG
- Multiview Identifiers Enhanced Generative Retrieval