CS Paper Radar

CavityRank: Zero-Extra-Byte Residual Routing for Cuckoo Filters

Yongjie Guan

cs.DS ·submitted 2026-08-14 05:31 UTC · v1
code/data

Abstract

Near capacity, a cuckoo filter may reject an insertion even though a legal placement still exists: the table remains structurally feasible, but a bounded policy fails to find an augmenting path. Random kick-out keeps each step cheap but leaves no persistent direction; breadth-first search recovers direction by expanding a frontier and maintaining table-scaled state. CavityRank exploits a resource already present in four-slot packed buckets. Lookup observes only the fingerprint multiset, so query-equivalent lane orders can encode two comparison bits without widening the 64-bit bucket or changing the two-bucket query. The bits form a four-level ordinal residual rank. Insertion follows a minimum-rank edge and re-encodes each modified bucket from its outgoing edges after relocation, propagating the rank actually realized by the packed word. An exact capacity-four orientation oracle separates structural infeasibility from bounded-search loss. In a paired 4,096-bucket XOR16 ladder, CR2 closes 86.47% of Random CF's oracle gap and CavityRank leaves 1.39% of that original gap. A canonical-tie CR2-versus-CavityRank ablation isolates the second implicit bit, which closes 89.95% and 90.69% of CR2's residual gap; the corresponding closures at 65,536 buckets are 83.95% and 84.27%. A separate packed implementation study at 64 MiB and 97.75% load records 42.53 logical reads per insertion, versus 62.67 for explicit labels and 355.74 for depth-10 BFS, with zero extra bytes per bucket and no table-scaled workspace. CavityRank therefore occupies a practical design point between unguided eviction and frontier search.

Comment
8 pages, 7 figures, 2 tables; Code: https://github.com/CodeBoy2006/cavityrank

Closest papers

Nearest neighbours by meaning across the whole index.

Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR Hashing

cs.DS ·2026-11-01 ·Min Liu
theory similarity 0.66
Abstract

Cuckoo filters are a widely adopted approximate membership query (AMQ) data structure that supports insertions, lookups, and deletions with low memory overhead. At high load factors, however, insertion performance degrades sharply due to the random-walk eviction process, which may require a large number of element relocations. Recent work on bucketized cuckoo hash tables has shown that \emph{fresh-priority eviction}, which preferentially evicts elements whose alternate bucket location has not yet been used, achieves $O(\ell m)$ total expected evictions for bucket size~$\ell$, an improvement over the standard random walk. In this paper, we show that this technique transfers to \emph{cuckoo filters} despite their use of XOR-based partial-key hashing. The key insight is that a fresh element's fingerprint, although stored in the table, is not examined by the eviction policy, so when the fingerprint length satisfies $k = Ω(\log m)$, the alternate bucket hash remains a near-uniform random variable, a property we call \emph{latent randomness}. We prove that under this condition the corruption graph remains subcritical and the total number of evictions is $O(\ell m \log m)$; we conjecture the tighter $O(\ell m)$ bound holds via the full amortized analysis of Bell and Kuszmaul. We further propose encoding the fresh/kicked state implicitly by the element's position within its bucket, requiring no additional per-element metadata. Experimental results on a filter with $2^{22}$ slots and $8$-bit fingerprints demonstrate $1.2\times$ to $2.4\times$ fewer evictions at load factors between $94\%$ and $99\%$ for bucket size $\ell = 8$, and a $1.73\times$ reduction in cumulative evictions to full capacity.

0.10

Guided Cuckoo Filter: Full-Pipeline Insertion Optimization

cs.DS ·2026-11-19 ·Min Liu
similarity 0.64
Abstract

Cuckoo filters are widely deployed as space-efficient alternatives to Bloom filters, supporting fast lookups, insertions, and deletions. However, their insertion cost grows steeply at high load factors because the standard insertion procedure is entirely unguided: it places each fingerprint into whichever candidate bucket happens to be tried first, and when both candidates are full, it displaces a random victim in a random walk. These blind random choices occur at two distinct stages of the insertion pipeline, the initial placement decision and the eviction victim selection, yet each stage can be independently replaced with a guided, informed decision. We propose the \emph{Guided Cuckoo Filter}, which optimizes the entire insertion pipeline by steering both stages. At the placement stage, the filter compares the occupancy of both candidate buckets and inserts into the less loaded one, applying the power-of-two-choice principle to reduce how often eviction chains are triggered. At the eviction stage, the filter preferentially displaces the most recently inserted element, whose alternate bucket carries latent randomness that shortens the resulting chain. Because these two guided decisions target orthogonal bottlenecks, eviction frequency and eviction chain length, their benefits compose multiplicatively. Experiments on cuckoo filters with $2^{22}$ slots confirm that the fully guided insertion reduces per-insertion kicks by up to $3.1\times$ at 96\% load and cumulative total kicks by 63\% at the practical capacity ceiling of 95\% load, with negligible computational overhead.

0.23

Preference Is Not Position: Evaluating Reranking on NevIR in Fixed Hybrid Candidate Pools

cs.IR ·2026-10-19 ·Yuning Bian, Lele Xu, Yifan Yuan, Xinyu Yin, Chengyan Zhan
publishedcode/data similarity 0.58
Abstract · 6 pages, 2 figures, 3 tables. Accepted at the IEEE BigData 2026 Undergraduate and REU Consortium. Code: https://github.com/ql-link/LinkRag-E…

Near-identical passages can differ in a decisive condition, such as negation. A ranker may order such a pair correctly while placing the preferred passage far down the retrieved list. We examine this distinction using official NevIR pairs jointly covered by fixed candidate pools from dense, learned sparse, and BM25 retrieval. On 2,736 Test query directions, a pairwise-trained ranker improves strict per-query preference over fixed fusion (56.62% versus 52.30%) while reducing preferred-passage mean reciprocal rank (MRR) from 0.5764 to 0.3055. An exploratory fixed-model replay of a variant with background sampling and revised supervision yields MRR of 0.5859 and strict preference of 54.53%. Bounded pointwise reranking of the fusion top 20 improves both outcomes. Qwen3-14B-AWQ with fusion tie-breaking reaches 77.45% strict preference, 58.99% NevIR-style paired accuracy across 1,363 complete pairs, and preferred-passage MRR of 0.7509. A BGE cross-encoder reaches 69.77% strict preference and MRR of 0.7404. A post-hoc analysis finds that the branch where equal Qwen grades for the two designated passages trigger fusion tie-breaking accounts for 27% of evaluated directions and contains most remaining strict-preference failures. These findings support joint evaluation of pairwise preference, designated-passage position, and computational cost, while distinguishing model judgments from the combined ranking procedure.

0.50

Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

cs.DS ·2026-10-23 ·Andrew Krapivin, William Kuszmaul
top venue similarity 0.55
Abstract · 60 pages, 1 figure, to appear in SODA 2027

In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1 - \varepsilon$ (for some parameter $\varepsilon \in (0, 1)$), while supporting queries, insertions, and deletions in worst-case time $O(\log \varepsilon^{-1})$, with high probability. This result represents an exponential improvement on insertion/deletion time over previous constructions, and disproves a conjecture of Bender, Kuszmaul, and Zhou that the product of worst-case query time and expected insertion/deletion time must be $Ω(\varepsilon^{-1})$.

0.35

Top-K Is Not a Budget for Hybrid Retrieval

cs.IR ·2026-09-14 ·Chunran Zhang
code/data similarity 0.53
Abstract · 5 pages, 2 figures, 3 tables. Code: https://github.com/ln-one/top-k-is-not-a-budget

Modern hybrid retrieval for RAG typically fuses the Top-$L$ results from dense and sparse retrievers, but a fixed truncation depth may not transfer across changing queries and corpora. Exact fusion removes the dependence on a fixed depth, yet completing a specified Top-$K$ still incurs variable access costs. We present DiBud, which takes an access budget directly as input and incrementally certifies and returns an exact prefix of the RRF ranking over the full lists. Selective access increases certified output within the budget, while budgeted stopping bounds accesses per request. Experiments on five query sets reveal long-tailed costs for completing exact Top-20. At a budget of 2048 accesses, DiBud increases mean certified output within the first 100 positions by 7.86% over balanced access. After budget calibration for 95% quality retention, held-out queries retain 95.05%--97.68% of mean nDCG@20 while using 65.92%--99.53% fewer accesses than completing exact Top-20.

0.43

Enrich-Retrieve-Rank: Scaling Capability Discovery Beyond In-Context Routing

cs.CL cs.AIcs.IR ·2026-08-24 ·Nazib Sorathiya, Daniel Zhang, Bardiya Akhbari
top venue similarity 0.52
Abstract · 11 pages, 4 figures, and 12 tables

Agent ecosystems now include thousands of MATS components (Models, Agents, Tools, and Skills), yet their discovery still relies on in-context routing. These systems read a registry (names, hints, or descriptions, as context budget permits), pick a candidate, invoke it, and retry on failure. This pattern degrades with scale, and registries are growing fast. We recast capability discovery as search over a registry by defining an offline enrichment step that turns sparse metadata into searchable profiles, and an online retrieve-then-rank pipeline that returns a ranked shortlist without invoking any candidates online. We show that from N=10 to 7,278 capabilities, in-context routing's top-1 accuracy (Match@1) collapses (0.85 to 0.12), while retrieve-then-rank degrades more gently (0.81 to 0.39) because its reranker still ranks the right capability first 0.70-0.87 of the time once retrieval finds it. In the Nova Micro sweep, the crossover is around N=500. We compare against two in-context baselines. Full-Ctx puts the whole registry in the prompt and asks the LLM to pick. Search&Pick gives the LLM a search tool to narrow candidates before it picks. At full scale the pipeline leads Search&Pick by 6.5 percentage points (pp) on Match@1 at about half the cost. It reduces cost 70x versus Full-Ctx. We use a fixed configuration (same enrichment, retriever, and scorer weights) across agent, tool, and skill registries. The pipeline runs in production as the default capability-discovery layer of a large-scale multi-agent platform.

0.59

Dual-QK: Sharp Queries and Flat Keys for Prunable 2-bit KV Caches

cs.LG ·2026-10-07 ·Sunjoo Whang, Jungjun Oh, Minsung Kim, Dongho Seo, Jisu Shin +3 more
similarity 0.52
Abstract

Long inputs and extended generation increase the storage and access costs of the key-value (KV) cache. Low-bit quantization reduces storage and memory traffic, while query-channel pruning can further reduce key-cache reads. Rotation-based quantization redistributes the energy of key outliers across channels. To maintain computational invariance, the same orthogonal transform must be applied to queries, preserving query-key dot products. However, this rotation can disperse query energy, weakening the separation between a few large components to retain and many small ones to prune. We introduce Dual-QK, which uses paired non-orthogonal query and key transforms to address this conflict. Using calibrated query and key statistics, Dual-QK combines partial key whitening with a query-aligned basis to balance key scales for INT2 quantization and concentrate query energy for dynamic channel pruning. Channel-0 protection and bucket-relative RoPE support low-bit accuracy over long contexts. Experiments on four models across five generative benchmarks and long-context retrieval tasks show improved accuracy over OSCAR on most tasks at 40% query-channel sparsity. At a 128K context, Dual-QK provides $6.8\times$ KV-cache compression and an estimated $8.3\times$ reduction in KV read volume relative to unpruned BF16. Under the evaluated configurations, our SGLang implementation achieves up to $3.75\times$ the decoding throughput of unpruned BF16.

0.19

Prefix Sharing Is a Sorting Problem

cs.DS cs.CL ·2026-09-12 ·Rong He
theorycode/data similarity 0.51
Abstract · 16 pages. v2: Corrected the spanning-tree lower-bound implementation and retrieval summary statistics; clarified the scope of empirical opti…

LLM serving reuses KV cache by exact prefix match, so when a prompt is assembled from a set of reusable pieces -- retrieved passages, tool definitions, few-shot exemplars -- the order chosen for those pieces determines how much computation can be shared. Every deployed system fixes that order by a single global convention. We prove this is optimal only when requests contain at most two pieces, and asymptotically wrong in general. Our main result is a structure theorem: the minimum prefix-trie cost equals min_H sum_x w(x) t_x(H) over binary hierarchies H on the requests, where t_x(H) is the canonical decomposition size of the set of requests needing chunk x. Choosing chunk orders is therefore equivalent to choosing one hierarchy over requests. The identity yields an O(3^m) exact algorithm, identifies the two-chunk case as minimum vertex cover, and shows that on the leave-one-out family the optimum is the minimum external path length of a binary tree -- the merge-sort recursion -- so a global order pays Theta(n^2) against a true cost of Theta(n log n). Agglomerative clustering by common intersection is a tight 1/2-approximation for the achievable saving. On BM25 retrieval traces over three BEIR corpora the resulting layout reduces prefill by 17-36% against production RAG ordering, and the margin widens with retrieval depth as the theory predicts. Serving requests in the hierarchy's DFS order finally lets a cache holding one request's context attain the unbounded-cache optimum exactly, so cache capacity and reorder window act as substitutes.

0.28