Search engines close the vocabulary gap, where a user and a document describe the same thing in different words, in two ways. They add predicted synonyms to each document's keyword index ("learned sparse expansion"), and they add a dense embedding, a single learned vector per text that captures meaning beyond exact words. Both help, and both make search slow. Expanded keyword indexes make each word's list of matching documents (its "postings list") long and full of low-weight entries. Dense vectors must then be scored in a separate system, and the two candidate lists are merged afterward. We propose to run the whole hybrid query as one compiled loop. For each candidate document, that loop walks the original-term postings, the expansion-term postings, and the dense dot product, keeping the running score in CPU registers.
The compiled loop alone is not the point. Databases learned that compiling machine code for every query costs tens to hundreds of milliseconds, and that is longer than a whole hybrid search takes. The approach here is therefore to compile one hybrid kernel per index and leave runtime hooks in it, so that each query can reorder and skip work. The kernel decides, while it runs, how many low-weight expansion lists are worth reading for this query. It bases that decision on how much the dense score has already settled a document's fate. The stake is concrete. The extra accuracy from expansion should be kept only for the queries that need it, and the rest should run near the speed of plain keyword search.
Core Claim
The query-time cost of bridging the vocabulary gap is uneven. For most queries, the long expansion postings cannot change the top-ranked results once the original terms and the dense score are known. For true lexical-gap queries, the expansion postings are what make the right answer findable at all.
A runtime-adaptive, compile-once hybrid kernel can exploit this. Its scoring is
$$s(q,d)=\alpha\, s_{\text{orig}}(q,d)+\alpha\, s_{\text{exp}}(q,d)+\beta\, s_{\text{dense}}(q,d).$$
Here $s_{\text{orig}}$ sums learned weights over the query's original tokens, $s_{\text{exp}}$ sums them over the expansion tokens, $s_{\text{dense}}$ is the embedding inner product, and $\alpha,\beta$ are fixed fusion weights. Given exactly this function, the kernel would return the same top-$k$ as exhaustive evaluation. It would also deliver latency close to unexpanded keyword search on queries with lexical overlap.
The pruning rule is a bound. Let $\theta$ be the current $k$-th best score and $U_t(d)$ an upper bound on term $t$'s contribution within $d$'s block. The kernel skips the remaining expansion lists $R$ for document $d$ whenever
$$\alpha\, s_{\text{orig}}(q,d)+\beta\, s_{\text{dense}}(q,d)+\alpha\sum_{t\in R}U_t(d)<\theta.$$
This is the logic of the classic early-termination algorithms MaxScore and WAND. The difference is that the exactly-computed dense term supplies most of the certainty. In WAND and MaxScore, by contrast, loose bounds on the sparse terms alone have to do the work. That matters because those algorithms lose effectiveness on learned sparse weights, as Bridging Dense and Sparse Maximum Inner Product Search shows.
Relation to Prior Work
Three groups of papers play different roles.
Work that motivates the gap. SPRINT benchmarks five learned sparse models inside Lucene. It finds that SPLADEv2's expansion drives its zero-shot accuracy, at 0.470 average nDCG@10 on BEIR versus 0.429 for BM25, and that these models run 3.5x to 46x slower than BM25. BEIR shows that dense retrievers alone are fragile out of domain: DPR loses to BM25 on 17 of 18 datasets. Hybrids are therefore needed, not optional. WikiQA finds that 20.3% of correct answer sentences share no content word with the question. That is the population of queries our adaptivity must never prune away.
Hybrid systems we build on and differ from. Lin's representational framework separates the logical scoring function from the physical index. That separation licenses us to keep the scoring fixed and change only execution. Lin's framework stops at the logical level, and its reported hybrids still run two engines. Luan et al. fuse BM25 with multi-vector dense scores, but they generate candidates independently and fuse linearly afterward. Ma et al. concatenate sparse and dense vectors so that a single dot product scores both. They hand the result to a generic nearest-neighbor engine, which bloats the index. We keep the two blocks physically separate and fuse them only inside the loop. HI² and Bruch et al.'s partitioned inverted index both reorganize the index itself. Our work is complementary: we change how a given index is traversed. We will run our kernel over a cluster-partitioned layout in the style of Bruch et al. as well as a plain document-ordered one.
Work that supplies, and constrains, the method. Data-centric pipelining from HyPer and HyPer-sonic supplies the "push one item through all operators in registers" execution style. LMFAO supplies schema-specialized code generation with fixed-size arrays in place of hash tables. Permutable Compiled Queries supplies the decisive design pattern: compiled code with indirection hooks that reorders filters at runtime from observed selectivity, without recompiling. That paper also constrains us, because its premise is that recompilation is too costly to do per adaptation. We treat each expansion postings list like a PCQ filter whose order and cutoff are chosen at runtime. To our knowledge from the file, no prior work applies any of this to postings lists or vector scoring.
Research Program
The kernel. We will build a hybrid kernel in a small intermediate language that compiles to LLVM. It is specialized per index on three things: the posting compression codec, the block size, the dense dimension and quantization, and the fusion weights. A query fills a runtime descriptor with its tokens, partitioned into original and expansion tokens, and their weights. The query does not trigger compilation.
The fused loop. Inside the loop, the kernel advances original-term postings first and computes the dense inner product with SIMD instructions on candidates that survive. It then visits expansion lists in an order kept in an indirection array. Lists are sorted by expected contribution, which is the product of weight and observed hit rate. Each list is either fully read or skipped block by block under the bound above.
Runtime adaptation. Instrumentation counters, following PCQ, re-sort the expansion order every few thousand documents. They also decide whether to probe the dense score before or after the expansion lists. Dense-first is the better order when the dense score is decisive. Expansion-first is the better order on lexical-gap queries, where the original terms barely fire.
Exact and approximate modes. Exact mode keeps the bound safe. An approximate mode scales the $U_t$ bounds by a factor below one, giving an accuracy–speed dial comparable to Bruch et al.'s reported operating points.
Analysis. We will profile the speedup into three parts so that each claimed ingredient is accounted for: instructions removed by specialization, memory traffic removed by fusion, and documents skipped by adaptation.
Baselines
Naive reference point. BM25 in Lucene via Pyserini is the speed floor and the "no gap-bridging" accuracy floor. SPLADEv2 in Lucene, as configured in SPRINT, is the "bridge the gap, pay the price" point. SPRINT reports 0.470 average nDCG@10 on BEIR and a 3.5x to 46x slowdown over BM25. Beating it means matching its effectiveness, or that of our hybrid, at a small multiple of BM25 latency rather than tens of times.
Standard two-engine hybrid. This runs learned sparse search in Lucene and dense search in an HNSW (graph-based nearest-neighbor) index in parallel, then fuses the top lists linearly. On MS MARCO, Lin's framework reports about 0.378 MRR@10 for a TCT-ColBERT plus DeepImpact hybrid, with HNSW needing up to 42 GB of RAM versus 660 MB for Lucene. For fairness we will use the same sparse and dense encoders and the same fusion weights, tuned once on the MS MARCO development split and shared by all systems. Every system runs on the same machine with the same thread count. Beating this baseline means equal or better MRR@10 and Recall@1000 at lower tail latency and less memory. Our fused scoring sees every candidate under both signals, so its recall should be at least as high.
Strongest index-level competitors. These are HI², which reports Recall@100 of 0.916 on MS MARCO against 0.927 for brute force at 8–15 ms, and Bruch et al.'s partitioned inverted index, which reports about 2,000 QPS at 90% accuracy against 150 QPS for linear scan on SPLADE-encoded MS MARCO. We will run their released configurations on our hardware. Our kernel runs over the same index layout, which isolates traversal from index design. Beating them means higher QPS at matched Recall@100 or matched top-10 accuracy.
Ablations isolating our ingredients. The same adaptive plan runs in an interpreted, iterator-style engine, to separate adaptation from compilation. A compiled fused kernel runs with a fixed expansion order and no bound-based skipping, to separate compilation from adaptation. Per-query JIT compilation measures the compile cost we avoid. A hand-written C++ kernel templated on the same parameters tests whether code generation adds anything beyond careful static code.
Why not just…?
Why not just run BM25 or SPLADE and a dense index in parallel and merge? This is the incumbent, and it works. Its costs are a separately resident dense graph, which Lin measures at up to 42 GB on MS MARCO, plus duplicated candidate generation. Nothing in that design lets either signal prune the other. The two-engine baseline above measures the gap directly. If our kernel only ties it on latency, the remaining argument is memory, and we will report that honestly.
Why not just vectorize with SIMD and skip compilation? This is a real threat. On short postings blocks, batched SIMD primitives may capture most of the benefit. PCQ reports up to 2x over the vectorized engine Actian Vector, and LMFAO reports large gains from inlining traversal logic. Both results come from relational workloads, so neither settles the retrieval case. The interpreted-adaptive and hand-written-kernel ablations settle it. If they come within about 20% of the compiled kernel, we will report adaptation as the contribution and compilation as unnecessary.
Why not just rewrite queries upstream, as RaFe does? RaFe trains small rewriters from reranker feedback and gains 2–3% QA accuracy. It addresses what to search for, not how fast the expanded query executes, and it adds a model call before every search. It is orthogonal to our work. We will feed RaFe-style rewritten queries into all systems to confirm that the speedups persist when queries carry more tokens.
Why not just drop low-weight expansion terms with a fixed threshold? This is the simplest threat, and it may capture much of the latency benefit. Its failure mode is predictable: on lexical-gap queries, the low-weight expansion terms are often the only bridge to the answer. We will compare full accuracy–latency curves for static thresholding against our approximate mode. We will also report results on the zero-overlap slice separately, where we expect static pruning to lose recall that adaptive skipping keeps.
Proposed Experiments
Datasets and encoders. The main testbed is MS MARCO passage, about 8.8M passages, scored by MRR@10, Recall@100 and Recall@1000. We also use BEIR with nDCG@10, and BioASQ-style biomedical queries with MAP, where exact identifiers matter. The encoders are SPLADEv2 for sparse and a single-vector dual encoder for dense.
Efficiency measurements. We report median and 99th-percentile single-thread latency, QPS on multiple cores, resident memory, and documents scored per query.
Decisive check 1: exactness. In exact mode, top-$k$ lists must match exhaustive evaluation of the fused score on every query. This is a correctness gate before any speed claim.
Decisive check 2: the lexical-gap slice. On MS MARCO and BEIR, we will define queries whose relevant documents share no content words with the query, which mirrors WikiQA's 20.3% statistic. On this slice, the adaptive kernel should automatically read most expansion lists, approaching full SPLADE cost. On overlap queries, it should approach BM25 latency. If latency does not separate by slice, adaptation is not doing what we claim.
Decisive check 3: attribution. The ablation ladder runs from interpreted adaptive, to static compiled fused, to permutable compiled fused, to per-query JIT. It must show which ingredient carries the speedup. Measured compile time per query should confirm that per-query JIT is uncompetitive at 8–15 ms query budgets.
Decisive check 4: layout independence. The kernel's advantage should hold over both a document-ordered index and Bruch et al.'s cluster-partitioned layout. That would show the contribution lies in traversal, not index design.
References
- Bridging Dense and Sparse Maximum Inner Product Search
- SPRINT: A Unified Toolkit for Evaluating and Demystifying Zero-shot Neural Sparse Retrieval
- BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- A proposed conceptual framework for a representational approach to information retrieval
- Sparse, Dense, and Attentional Representations for Text Retrieval
- Hybrid First-stage Retrieval Models for Biomedical Literature
- Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval
- HyPer: Adapting Columnar Main-Memory Data Management for Transactional AND Query Processing
- HyPer-sonic Combined Transaction AND Query Processing
- A Layered Aggregate Engine for Analytics Workloads
- Permutable Compiled Queries: Dynamically Adapting Compiled Queries without Recompiling
- RaFe: Ranking Feedback Improves Query Rewriting for RAG