AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions David Torres Ramos, Vihan Lakshman, Chen Luo, Todd Treangen, Benjamin Coleman Abstract . We study the problem of building space-efficient, in-memory indexes for massive key-value datasets with highly skewed value distributions. This challenge arises in many data-intensive domains and is particularly acute in computational genomics, where k k -mer count tables can contain billions of entries dominated by a single frequent value. While recent work has proposed to address this problem by augmenting compressed static functions (CSFs) with pre-filters, existing approaches rely on complex heuristics and lack formal guarantees. In this paper, we introduce a principled algorithm, called AutoCSF, for combining CSFs with pre-filtering to provably handle skewed distributions with near-optimal space usage. We improve upon prior CSF pre-filtering constructions by (1) deriving a mathematically rigorous decision criterion for when filter augmentation is beneficial; (2) presenting a general algorithmic framework for integrating CSFs with modern set membership data structures beyond the classic Bloom filter; and (3) establishing theoretical guarantees on the overall space usage of the resulting indexes. Our open-source implementation of AutoCSF demonstrates space savings over baseline methods while maintaining low query latency. 1. Introduction Key-value stores are indispensable components of modern data infrastructure. As data volumes continue to balloon in size, there is increasingly a need to design new data structures for key-value lookups with small memory footprints while still enabling fast queries. When the set of key-value pairs is fixed (or changing infrequently), succinct retrieval data structures have emerged as a state-of-the-art class of techniques for indexing data with minimal space overhead. These retrieval structures offer the guarantee of returning the correct value when queried with any key in the index, but may return arbitrary outputs for any key not in the set. Amongst these succinct retrieval methods, compressed static functions (CSFs) achieve space usage proportional to the empirical entropy of the value set. Thus, when the list of values in the index is highly repetitive, CSFs can achieve significantly improved compression rates compared to distribution-agnostic methods, typically within a constant factor of the information-theoretic lower bound. However, one limitation of CSFs is that, by construction, the index must use a lower bound of at least 1 bit per key. Consequently, if the value distribution is highly skewed, namely when a single value is associated with the majority of the keys, CSFs fall short of achieving optimal compression rates. This barrier is especially prominent in computational genomics where long read k -mer count tables, which map keys of k -length nucleotide substrings to their frequency of occurrence in a given genome, often exhibit extreme skew with over 90% of k -mers having a value of 1. This challenge was previously identified in the literature by 27 who proposed a new index called a Bloom-enhanced Compressed Static Function (BCSF) which augments a CSF with a Bloom filter to handle the dominating value. In particular, a BCSF index first inserts all keys not associated with the dominating value into a Bloom filter. Additionally, since Bloom filters admit false positives, the BCSF index will insert the false positive keys associated with the dominating value into the CSF. At query time, given a key k , a BCSF first checks if k is in the Bloom filter. If the filter returns false, then we can conclude that the associated value must be the dominating entity and simply return that value. If the filter returns true, we query the CSF and return the output. This construction guarantees correctness while eliminating the need to index the dominating value directly. Inspired in part by this work, 13 also leverage this idea of filter augmentation to develop a learned CSF index that allows for improved compression via machine learning. Despite the effectiveness of filter-augmented CSFs, as demonstrated in these prior works in the literature, these data structure compositions introduce additional complexity. In particular, it is not completely clear which key-value distributions might benefit from filter-augmented CSFs or how to set the false positive rate of the filter to minimize the overall space usage. Unlike standalone approximate set membership data structures, which maintain a monotonic relationship between the false positive rate and the size of the resulting filter, the relationship between the false positive rate and the overall index size in filter-augmented CSFs is complex to model. As an illustrative example, increasing the false positive rate of a filter might allow more values to pass through to the CSF, causing the value frequency distribution to be more closely-aligned to powers of 2 and thus more highly compressible by Huffman codes. While the work of ( 27 ) present a set of criteria for making these parameter choices in a BCSF, they are heuristic-driven as opposed to mathematically principled and, as we will demonstrate in this paper, can be misleading and result in suboptimal decisions. Motivated by these shortcomings, we ask the following research questions: (1) Can we develop a mathematically principled decision criterion to determine when a set of key-value pairs would benefit from filter-augmentation to save space versus simply using only a CSF? (2) Given a filter-augmented CSF, can we design an efficient algorithm for determining the optimal parameters for the pre-filter that minimizes the total space usage of the index? (3) Can we design a general framework for Questions (1) and (2) that can be applied to all set membership data structures in the literature, as opposed to just the classical Bloom filter? In this paper, we affirmatively answer all three of these research questions through a single algorithm, which we call AutoCSF. The key insight behind AutoCSF is that while modeling the exact memory cost of a filter-augmented CSF appears to be intractable – or at least unwieldy to analyze – we can derive analytically clean upper and lower bounds on the difference in space usage between a CSF and filter-augmented CSF. In other words, instead of attempting to develop separate cost models for the space usage of a CSF and filter-augmented CSF, we bound the difference in bits per key between the two data structures without ever having to explicitly construct either index . This observation drives the development of our AutoCSF algorithm, which first determines if filter-augmentation is beneficial and then, if a filter is helpful, provides near-optimal settings for the filter parameters. The AutoCSF framework can be applied to any approximate set membership data structure with a known relationship between the memory usage and false positive rate, allowing our results to easily extend to the large number of membership filters that have been developed over the last 50 years ( 3 ; 21 ; 1 ; 24 ; 9 ; 23 ; 22 ; 29 ; 17 ; 11 ; 20 ; 8 ; 25 ) . We implement AutoCSF in practice and verify that our theoretical results align closely with empirical results (i.e. the bounds are tight), thus providing a principled algorithm to effectively compose CSFs with prefilters. In summary, we make the following contributions • We demonstrate that the existing state-of-the-art heuristic-based decision criterion for filter-augmented CSFs (BCSF) can actively degrade performance, recommending filter configurations that increase space usage by up to 1 bit per key relative to a plain CSF (Figure 3 ). • We derive lower and upper bounds on the difference in space usage between a standard CSF and a filter-augmented CSF (Theorems 4.2 and 4.4 ). The key insight is to bound the cost difference directly using Huffman code optimality, rather than attempting to model the cost of each index independently. The lower bound yields a provably safe decision criterion: it never recommends a filter that increases space. • We present a general algorithmic framework, AutoCSF, for determining when to use a filter-augmented CSF and how to set the parameters for the prefilter for space efficiency. AutoCSF applies to any approximate set membership data structure with a known cost-vs-false-positive-rate tradeoff, including XOR filters, binary fuse filters, and Bloom filters with arbitrary hash counts. This extends the filter-augmented CSF paradigm beyond the classical Bloom filter used in prior work. In addition, unlike prior approaches, AutoCSF does not require estimating the full value distribution or entropy. Instead, it relies only on the dominant value fraction and a filter cost model, making it both simpler and more robust in practice. • We empirically validate 1 1 1 Our experimetal code is available at https://github.com/detorresramos/CaramelDB-Benchmarks . that our bounds are tight across three synthetic distributions and five filter types, that the theory-guided parameter selection matches or comes within one discrete step of the empirical optimum, and that AutoCSF achieves Pareto-optimal memory-latency tradeoffs on real genomics workloads with up to 70 million keys. 2. Related Work Succinct retrieval data structures, including CSFs, have garnered intense research interest in the theoretical computer science community for decades. The original CSF constructions involved using a minimal-perfect hash function to index a set of constant-size values, later followed by algorithms that store Huffman codes of the values, and finally culminating in algorithms that compute the Huffman codes of the values through the solution of a randomized binary linear system ( 18 ; 7 ; 2 ) . This binary, XOR-based system undergoes a phase transition as we reduce the space, and there has been considerable theoretical work to migrate from the easier, larger-overhead regime ( 4 ) (where hypergraph peeling solves the system in linear time with high probability) to the minimum-space regime where the system is not easily solvable ( 7 ) . This minimum-space regime was primarily considered a theoretical curiosity and not feasible in practice due to a construction time cubic in the number of keys. The work of ( 10 ) refuted this conventional wisdom by presenting a practical CSF construction algorithm that leverages both sophisticated algorithmic techniques, such as lazy Gaussian elimination and hypergraph peeling, as well as implementation-level optimizations like broadword programming. Following the pioneering work of 10 , which provided the first practically implementable CSF construction, several works have proposed building data systems with CSFs as the foundational indexing primitive ( 5 ; 27 ; 13 ) . The most relevant prior work to our contributions in this paper is that of 27 who proposed the idea of Bloom-enhanced CSFs to handle skewed value distributions, motivated by the problem of indexing skewed k mer count datasets in computational genomics. Our contributions in this paper directly build off the ideas in ( 27 ) . Specifically, as we discuss further in the next section, the heuristic-driven decision criteria used in ( 27 ) to determine when to apply a Bloom filter and how to set the false positive rate can lead to suboptimal configurations in practice. We improve upon this construction with our AutoCSF algorithm. In addition to the work of 27 , several other recent works have studied CSFs from a practical lens. CARAMEL ( 5 ) explores indexing a multi-set of values for each key via an array of CSFs. More recently, 13 proposed a learned CSF (LCSF) that combines tools from the rich literature on learned index structures ( 16 ) as well as Bloom filter augmentations to reduce the memory footprint of CSFs even further, though at the cost of increased query latency and long model training times. In this paper, we include an experimental comparison of our proposed AutoCSF framework with LCSF on skewed distributions where we find that we can in fact achieve comparable space savings without the overhead of training a learned model. This result may be of independent interest in demonstrating that learned indexes, despite their power, may provide limited utility in settings where we can analytically model the cost of an index directly. 3. Warmup: The BCSF Algorithm In this section, we review the BCSF heuristic introduced by ( 27 ) as the design of this algorithm will motivate our efforts to improve upon it in this paper. Let K denote the set of all items in the dataset and let K_{0} denote the set of items with the most common frequency. We have that |K_{0}|=\alpha|K| for some 0\leq\alpha\leq 1 . Our goal is to minimize space by storing the set of non-dominating values in a Bloom filter and the associated counts of these non-dominating values in a CSF (plus the false positives). Assume that the Bloom filter takes C_{BF}\log\frac{1}{\varepsilon} bits per key where \varepsilon denotes the false positive rate. Also assume the CSF takes C_{CSF} bits per key. The total space usage of this Bloom-enhanced CSF data structure is thus C_{BF}(1-\alpha)|K|\log\frac{1}{\varepsilon}+C_{CSF}|K|((1-\alpha)+\varepsilon\alpha) where we assume the logarithm is base 2. To determine if we need a Bloom filter, BCSF needs to verify if the following inequality holds C_{BF}(1-\alpha)|K|\log\frac{1}{\varepsilon}+C_{CSF}|K|((1-\alpha)+\varepsilon\alpha)\frac{C_{BF}\log e}{C_{CSF}+C_{BF}\log e} If \alpha is sufficiently large, we can then construct a Bloom filter with false positive rate \varepsilon^{*} . The question remains: how do we compute C_{BF} and C_{CSF} , the bits-per-key cost of the Bloom filter and the CSF? The BCSF algorithm estimates C_{BF} by the theoretical space coefficient of idealized Bloom filters of 1.44. However, this idealized model is not realistic because it assumes the number of hash functions used by filter is continuous as opposed to a discrete parameter, which is the case in practice. In this paper, we explore whether we can do better by having a more accurate Bloom filter cost model. Secondly, the BCSF algorithm, as described in ( 27 ) , estimates C_{CSF} in terms of the empirical entropy H_{0} , producing the piecewise equation C_{CSF}=\begin{cases}0.22H_{0}^{2}+0.18H_{0}+1.16,\quad\text{if }H_{0}<2\\ 1.1H_{0}+0.2\quad\text{otherwise}\end{cases} However, this CSF cost model is a heuristic and not theoretically principled. In Figure 3 we demonstrate that this heuristic can provide misleading guidance in practice, which motivates our work to design a more principled algorithm with provable guarantees with AutoCSF. The key challenge in designing a principled algorithm is that the cost of the CSF space usage, particularly when coupled with random false positives from the filter, is difficult to model analytically, which is why a data-driven heuristic as in BCSF is a natural choice. However, as we demonstrate in the next section, we can circumvent this difficulty by bounding the difference in cost between a CSF and filter-enhanced CSF as opposed to modeling the cost of each index individually. This insight allows us to derive tight, usable bounds on the bit per key. 4. The AutoCSF Algorithm We describe AutoCSF, our new algorithm for filter-enhanced CSFs in Algorithm 1 . The algorithm is responsible for making two key design decisions: (1) first determine if a given set of key-value pairs would achieve more compression with filter-augmentation as opposed to just a standard CSF; and (2) if filter-augmentation helps, set the filter parameters near-optimally. Algorithm 1 is parameterized by a filter bits-per-key cost function b(\varepsilon) and can thus be applied to any approximate set membership data structure, including recent powerful techniques like XOR filters ( 11 ) and binary fuse filters ( 12 ) that provide a closed-form cost function b(\varepsilon) . The crucial step in Algorithm 1 is to optimize a lower bound on the difference in cost between a CSF and filter-enhanced CSF (which we denote as FSF). By maximizing this lower bound in terms of the filter false positive rate \varepsilon , Algorithm 1 aims to find a parameter setting that maximizes the space savings of using a filter-augmented CSF over a regular CSF. If these savings, even after maximization, are negative, then we conclude that a filter does not help. Otherwise, we build a filter-augmented CSF using the optimal false positive rate \epsilon^{*} . In the next subsection, we formally prove this lower bound on the bits per key difference in cost between the respective indexes. Then, in the following subsection, we prove an analogous upper bound. Although we do not use the upper bound directly in the AutoCSF algorithm, it is nevertheless a useful theoretical result in establishing the first such bound for this problem. In addition, the upper bound can be used for predicting the maximum possible space savings from a filter-augmented CSF, which can be used for making cost-effective decisions on infrastructure to serve these indexes. Algorithm 1 AutoCSF 1: A set of key–value pairs \{(k_{i},v_{i})\}_{i=1}^{N} with n unique values, most frequent token ratio \alpha , and a filter cost function b(\varepsilon) 2: A chosen data structure (CSF or CSF+Filter) built on the full dataset 3: Compute the optimal \varepsilon by maximizing the equation \varepsilon^{*}=\arg\max_{\varepsilon}\bigl(\alpha\delta(1-\varepsilon)-(1-\alpha)b(\varepsilon)\bigr) 4: if \alpha\delta(1-\varepsilon^{*})-(1-\alpha)b(\varepsilon^{*})-n/N>0 then 5: Build a CSF+Filter using the optimal false positive rate \varepsilon^{\star} 6: else 7: Build a CSF without a filter 8: end if 4.1. Proving the Lower Bound We will now proceed with proving our lower bound on filter-augmented CSF space savings. Our proof of this bound critically leverages the optimality of Huffman codes. Theorem 4.1 ( 14 ). Given frequencies F=\{f_{1},f_{2},...f_{z}\} of values V=\{v_{1},v_{2},...v_{z}\} and a Huffman code H(F) with lengths \{l_{1},l_{2},...l_{z}\} , \sum_{i=1}^{z}f_{i}l_{i}\leq\sum_{i=1}^{z}f_{i}l^{\prime}_{i} for any other uniquely decodable code with lengths l^{\prime}_{i} . Using this foundational result on the optimality of Huffman codes, we now state and prove our new lower bound theorem, which we crucially leverage in the AutoCSF algorithm. Theorem 4.2. Let C_{\mathrm{FSF}} and C_{CSF} denote the memory costs of filtered and non-filtered CSFs, where the filter is a set membership oracle with false positive rate \epsilon that requires b(\epsilon) bits per key. \left(C_{\mathrm{CSF}}-\mathbb{E}[C_{\mathrm{FSF}}]\right)/N\geq\alpha\delta(1-\epsilon)-(1-\alpha)b(\epsilon)-n/N Note that, for practical distributions, the vocabulary size n is typically o(N) , making n/N=o(1) . Proof. We suppose that there are n unique values, sorted in order of decreasing frequency V=\{v_{0},...v_{n}\} . We use e to denote the Huffman encoding, l_{i} for the length of the encoding e(v_{i}) and f_{i} for the frequency of v_{i} . Cost of the CSF: The cost to store a compressed static function of n=|V| distinct values is: C_{\mathrm{CSF}}=\delta\sum_{i=0}^{n}f_{i}l_{i}+D_{V}+D_{e} where \delta is a constant that depends on whether 3 or 4 hash functions are used to construct the linear system. With 3 hashes, \delta_{3}\approx 1.089 and with 4 hashes, \delta_{4}\approx 1.024 . The canonical Huffman dictionary requires D_{V} space to store the unique values and D_{e}=n\lceil\log_{2}\max_{i}l_{i}\rceil bits to store the encoding lengths for the set of values. Cost of the filtered CSF: When we prefilter the CSF, we remove (some of) the majority keys from the CSF and change the frequency distribution for the Huffman encoding. Specifically, we reduce the frequency of the majority value from f_{0} to f^{\prime}_{0} , causing the Huffman encoding to change from e to e^{\prime} . Removal of the majority value can potentially update all of the Huffman code lengths, causing them to change from \{l_{0},...l_{n}\} to \{l^{\prime}_{0},...l^{\prime}_{n}\} . The cost D_{V} to store the vocabulary remains the same. The cost of the prefiltered CSF also includes the cost to store the filter, which is b(\epsilon) multiplied by the number of keys in the filter. C_{\mathrm{FSF}}=\delta f^{\prime}_{0}l^{\prime}_{0}+\delta\sum_{i=1}^{n}f_{i}l^{\prime}_{i}+D_{V}+D_{e^{\prime}}+b(\epsilon)(N-f_{0}) Here, f^{\prime}_{0} denotes the number of keys with value v_{0} that erroneously pass through the filter. We insert (N-f_{0}) minority keys into the filter at a cost of b(\epsilon) bits per key, so the filter overhead is b(\epsilon)(N-f_{0}) . Bounding the expected cost: We wish to find a lower bound on the performance improvement offered by the filter. Note that because C_{\mathrm{FSF}} measures the storage cost (entropy), we want C_{\mathrm{FSF}}0 at the theory-optimal \varepsilon^{*} , AutoCSF recommends filtering; otherwise, it defaults to a plain CSF. Across all filter types, distributions, and \alpha values in the alpha sweep, we find that whenever the lower bound recommends filtering, the empirical savings are positive, i.e. the criterion never recommends a filter that increases space. The criterion is conservative, however, for the unique distribution: there is a range of \alpha values (roughly 0.71 – 0.80 for XOR) where filtering produces small empirical savings ( {\sim}0.05 – 0.2 bits/key) but the lower bound remains negative. This gap is driven by the n/N term, which is large for the unique distribution where n\approx N(1-\alpha) . For zipfian and uniform-100, where n/N\approx 0 , the lower bound crossing aligns closely with the point at which filtering first becomes empirically helpful. Parameter selection. In practice, each filter type admits only a small set of discrete configurations (e.g., fingerprint_bits \in\{1,\ldots,8\} for XOR filters, or all (k,\text{bpe}) pairs for Bloom filters), each corresponding to a specific \varepsilon . AutoCSF evaluates the lower bound at each available \varepsilon and selects the configuration whose lower bound is largest. This search is inexpensive since the parameter space is small, and it avoids any mismatch between a continuous optimum and the discrete \varepsilon values that filters can actually realize. To evaluate how well the lower bound serves as a proxy for actual savings, we compare the parameter selected by the lower bound against the empirically optimal parameter found by exhaustive search. The two agree in the large majority of cases, and when they disagree it is always by a single discrete step, with the theory-guided parameter saving at most 0.02 bits/key less than the empirical optimum. 5.3. Comparison with Prior Work The closest prior work to AutoCSF is the Bloom-enhanced CSF (BCSF) of Shibuya et al. ( 27 ) . Like AutoCSF, their method augments a CSF with a Bloom filter to handle the majority value. Their approach differs from ours in three respects: • CSF cost model. They derive the optimal false positive rate \varepsilon^{*} using a heuristic cost model C_{\mathrm{CSF}}(H_{0}) fit empirically to observed CSF sizes, rather than from provable bounds. • Bloom filter cost model. Their Bloom filter cost model uses the idealized constant C_{\mathrm{BF}}=\log_{2}e\approx 1.44 bits per key, which assumes a continuous (real-valued) number of hash functions, rather than a parameterized model that accounts for the discrete choice of hash count k and bits per element. • Decision criterion. Their method recommends no filter when \varepsilon^{*}\geq 1 , but this criterion is rarely triggered in practice: the heuristic C_{\mathrm{CSF}}(H_{0}) produces values large enough that the method recommends filtering even at \alpha=0.50 , where filtering does not reduce space. To compare the two approaches, we restrict AutoCSF to Bloom filters only (selecting the best (k,\text{bpe}) pair via the lower bound) and measure the resulting bits per key across all three distributions. Figure 3 shows the measured bits per key for each method alongside a no-filter baseline. The comparison reveals a clear difference in the decision to filter. At low \alpha , the heuristic recommends filter configurations that increase space usage relative to a plain CSF, with the heuristic curve exceeding the no-filter baseline by up to 1 bit/key for the unique distribution at \alpha=0.50 . This gap persists across all three distributions up to \alpha\approx 0.7 – 0.8 depending on the minority entropy. AutoCSF avoids this by defaulting to a plain CSF whenever the lower bound is negative. When filtering is beneficial (roughly \alpha\gtrsim 0.8 ), both methods achieve comparable space usage, with AutoCSF matching or improving upon the heuristic. These results confirm that AutoCSF improves upon the heuristic both in the decision of when to apply a filter and in the selection of filter parameters. We restrict both methods to Bloom filters in this comparison for fairness, since the BCSF framework only supports Bloom filters. However, as shown in the alpha sweep experiments, AutoCSF can also leverage XOR filters, binary fuse filters, and other set membership structures, which consistently yield further space savings. Figure 3. Results of comparing heuristic and AutoCSF cost models 6. Experiments The previous section validates AutoCSF’s theoretical bounds and decision criterion in isolation. We now evaluate AutoCSF as a complete, end-to-end index and compare it against four baselines that span the landscape of practical approaches to static key-value indexing. Our goal is to answer three questions: (1) Does AutoCSF’s theory-guided filter selection translate into real space savings over competing methods? (2) What are the latency and construction costs, if any, of filter-augmented CSFs? (3) How do these trade-offs change on real-world workloads where the value distributions are not synthetically controlled? 6.1. Baselines We compare AutoCSF against the following methods: • BCSF (Shibuya) ( 27 ) . The Bloom-enhanced CSF described in Section 3. We use 27 ’s heuristic cost model to set the Bloom filter parameters. This baseline isolates the effect of AutoCSF’s improved parameter selection: both methods use a CSF with a pre-filter, but differ in how the filter parameters are chosen. • C++ Hash Table . A standard std::unordered_map storing all key-value pairs. This baseline represents the naive approach with no compression, providing a reference point for memory usage and query latency. • MPH Table . A minimal perfect hash function (via Sux4J’s GOV construction ( 10 ) ) paired with a compact value array. This is a distribution-agnostic baseline as it does not exploit value skew and its memory usage depends only on the vocabulary size. • Learned CSF ( 13 ) . A learned static function that trains a small neural network to predict value distributions from keys. These predictions are used to derive key-specific prefix codes, which are stored in a pair of ribbon-based retrieval structures. By learning correlations between keys and values, this method can break the zero-order entropy barrier of standard CSFs, but at the cost of higher query latency and construction time due to model training. 6.2. Setup Synthetic datasets. We generate key-value datasets with N=100{,}000 keys, sweeping the majority fraction \alpha from 0.50 to 0.99. The majority value is assigned to an \alpha -fraction of keys uniformly at random; the remaining (1-\alpha)N minority keys draw values from one of three distributions: Uniform-100 (100 equally likely symbols), Zipfian (power-law with exponent s=1.5 ), and Unique (every minority key has a distinct value). These distributions span a wide range of minority entropy and stress-test different aspects of each method’s compression strategy. Genomics datasets. We evaluate on the three real k -mer count datasets used in ( 27 ) derived from whole-genome sequencing data, using k=15 : • E. coli (Sakai strain): n=5.3 M keys, \alpha=0.97 , 42 distinct values. • SRR10211353 : n=9.8 M keys, \alpha=0.20 , 228 distinct values. • C. elegans : n=69.7 M keys, \alpha=0.82 , 760 distinct values. These datasets exhibit the diversity of real genomics workloads: E. coli has extreme skew ( \alpha=0.97 ) with very few distinct values, SRR has low skew ( \alpha=0.20 ) with moderate vocabulary, and C. elegans is a large-scale dataset (70M keys) with intermediate skew. Metrics. We report three metrics: memory in bits per key (bpk), query latency as the mean inference time per key in nanoseconds, and construction time in seconds. For AutoCSF and BCSF, we use binary fuse filters ( 11 ) , which offer lower false positive rates per bit than Bloom filters. Learned CSF configuration. We follow the training pipeline of 13 , sweeping four MLP architectures (linear, one hidden layer with 50 or 100 units, and two hidden layers with 50 units each) with float16 quantization and early stopping. For genomics datasets, we use ordinal k -mer encoding as input features, mapping each nucleotide position to \{0,1,2,3\}/3 , since the character-level structure of k -mers is learnable unlike the hash-derived features used for synthetic data. The best model is selected by minimum total size (ribbon storage plus model weights). Construction time includes both model training and index construction. 6.3. Synthetic Benchmarks Pareto frontier. Figure 4 plots memory (bpk) against query latency (ns) on log-log axes for all five methods across the three synthetic distributions plus genomics data. Each method traces a trajectory as \alpha sweeps from 0.5 to 0.99; larger markers highlight \alpha\in\{0.5,0.8,0.95\} . Figure 4. Memory–latency Pareto frontier across synthetic distributions and genomics datasets ( N=100{,}000 for synthetic, real sizes for genomics). Each trajectory sweeps \alpha from 0.5 (right, more memory) to 0.99 (left, less memory). Log-log scale. Several patterns emerge from the Pareto plot. AutoCSF and BCSF consistently occupy the lower-left corner of the Pareto frontier—low memory and low latency—across all three distributions. The hash table offers competitive latency (107–204 ns) but does not compress the data. MPH Table uses 7–70 \times more memory than AutoCSF and its latency is 10–20 \times higher. Learned CSF achieves tighter memory than AutoCSF on Uniform-100 at all \alpha values (e.g., 4.4 vs. 5.2 bpk at \alpha=0.5 ) and on Unique at low-to-moderate \alpha (e.g., 11.4 vs. 26.3 bpk at \alpha=0.5 ), but at 2–4 orders of magnitude higher query latency. On Zipfian, AutoCSF achieves lower memory than Learned CSF at all \alpha values. The log-log scale in Figure 4 is necessary to display these extremes on the same axes. The Unique distribution is the hardest case for all methods: at \alpha=0.5 , half the keys have distinct values, so the CSF must store nearly \log_{2}(N/2)\approx 16 bits of entropy per minority key. Learned CSF achieves 11.4 bpk versus AutoCSF’s 26.3 bpk, demonstrating that a trained model can significantly reduce effective entropy when the value space is large. However, this comes at extreme cost: 4.0M ns query latency ( 34{,}000\times slower than AutoCSF’s 116 ns) and 983 seconds to construct ( 15{,}000\times slower). At higher skew ( \alpha=0.95 ), AutoCSF overtakes Learned CSF in memory (2.7 vs. 3.5 bpk) while maintaining 3{,}000\times faster queries. Construction time. Table 1 reports memory, latency, and construction time for all five methods at \alpha\in\{0.5,0.8,0.95\} . AutoCSF and BCSF build in under 0.1 seconds across all configurations. C++ Hash Table is the fastest to construct ( {\sim}0.006 s). MPH Table builds in 0.4–0.6 seconds. Learned CSF is the most expensive to build: 5–983 seconds depending on distribution complexity, with the Unique distribution requiring over 16 minutes at \alpha=0.5 . At \alpha=0.95 on Uniform-100, where Learned CSF’s memory advantage over AutoCSF is only 0.1 bpk, it takes 440\times longer to construct (5.7 s vs. 0.013 s). \alpha\!=\!0.5 \alpha\!=\!0.8 \alpha\!=\!0.95 Method bpk query (ns) build (s) bpk query (ns) build (s) bpk query (ns) build (s) Uniform-100 AutoCSF 5.2 92 0.030 2.5 116 0.030 0.8 78 0.013 BCSF (Shibuya) 5.5 95 0.028 2.7 120 0.020 0.8 87 0.008 C++ Hash Table 95.1 150 0.006 95.1 121 0.006 95.1 157 0.007 MPH Table 35.0 1412 0.569 49.0 1505 0.438 55.9 1551 0.572 Learned CSF 4.4 6435 5.173 2.2 6160 5.480 0.7 3199 5.733 Zipfian AutoCSF 4.6 98 0.025 2.3 95 0.014 0.8 78 0.007 BCSF (Shibuya) 4.9 93 0.026 2.4 90 0.013 0.8 94 0.008 C++ Hash Table 95.1 111 0.006 95.1 142 0.006 95.1 107 0.006 MPH Table 35.4 1195 0.569 49.2 1344 0.490 56.0 1323 0.470 Learned CSF 4.9 76811 32.064 2.4 39387 22.474 1.4 13530 13.284 Unique AutoCSF 26.3 116 0.067 10.6 103 0.032 2.7 79 0.012 BCSF (Shibuya) 27.3 101 0.057 11.0 93 0.026 2.7 88 0.012 C++ Hash Table 95.1 114 0.007 95.1 204 0.006 95.1 171 0.006 MPH Table 43.9 1363 0.496 52.2 1236 0.487 56.4 1390 0.472 Learned CSF 11.4 3997545 983.000 6.9 1431918 359.657 3.5 243241 85.772 Table 1. Synthetic benchmark results ( N=100{,}000 ). Memory in bits/key (bpk), query latency in nanoseconds (ns), and construction time in seconds. Bold indicates best in each column. 6.4. Genomics Benchmarks Table 2 reports results on the three genomics datasets. The datasets span a wide range of skew: E. coli is highly skewed ( \alpha=0.97 ), C. elegans has moderate skew ( \alpha=0.82 ), and SRR has low skew ( \alpha=0.20 ). This diversity tests whether AutoCSF’s decision criterion correctly adapts its strategy to the data. E. coli ( N =5.3M, \alpha =0.97) SRR ( N =9.8M, \alpha =0.20) C. elegans ( N =69.7M, \alpha =0.82) Method bpk query (ns) build (s) bpk query (ns) build (s) bpk query (ns) build (s) AutoCSF 0.31 92 0.2 4.21 443 2.3 1.26 466 6.6 BCSF (Shibuya) 0.35 126 0.3 4.24 355 2.3 1.39 274 7.0 C++ Hash Table 152.00 488 0.8 152.00 742 1.5 152.00 1034 15.2 MPH Table 11.55 1666 8.1 11.55 1716 13.6 11.55 2054 136.3 Learned CSF 0.32 7843 161.0 3.49 31811 676.9 1.68 29558 4573.5 Table 2. Genomics benchmark results. Memory in bits/key (bpk), query latency in nanoseconds (ns), and construction time in seconds. Bold indicates best in each column. On E. coli, where \alpha=0.97 , AutoCSF achieves 0.31 bpk, less than one-third of a bit per key to index 5.3 million k -mers. This is 37\times smaller than MPH Table (11.55 bpk). Learned CSF is competitive in memory (0.32 bpk) but requires 161 seconds to build versus AutoCSF’s 0.2 seconds ( 805\times slower) and has 85\times higher query latency (7,843 ns vs. 92 ns). The SRR dataset ( \alpha=0.20 ) represents a case where filter augmentation is not beneficial. AutoCSF correctly defaults to a plain CSF, achieving 4.21 bpk with 443 ns query latency. Learned CSF achieves the best memory (3.49 bpk) but at a cost: 677 seconds to build ( 294\times slower than AutoCSF) and 72\times higher query latency (31,811 ns vs. 443 ns). On C. elegans ( n=69.7 M, \alpha=0.82 ), AutoCSF scales to the largest dataset while maintaining its advantages: 1.26 bpk with 466 ns latency and a 6.6-second build time. For context, this means the entire 70-million-entry k -mer count table is indexed in approximately 11 MB of memory. MPH Table would require 100.6 MB for the same data. Learned CSF uses 1.68 bpk (33% more memory than AutoCSF) with 29,558 ns latency ( 63\times slower) and requires over 76 minutes to build. 6.5. Discussion Across all experiments, a consistent picture emerges. AutoCSF dominates the Pareto frontier of memory versus latency, especially when the majority fraction \alpha is moderate to high ( \gtrsim 0.7 ). The margin over heuristic construction is modest (up to 11% in memory) but systematic, confirming that the theory-guided parameter selection from Section 4 translates to measurable improvements in practice over the heuristic approach. The comparison with Learned CSF is particularly instructive. Learned CSF can achieve tighter compression than AutoCSF in several regimes: it consistently uses less memory on Uniform-100, and on Unique it achieves substantially lower bits per key at low-to-moderate \alpha (e.g., 11.4 vs. 26.3 bpk at \alpha=0.5 ), demonstrating that a trained model can exploit distributional structure beyond what a static Huffman code captures. However, these memory savings come at 2–4 orders of magnitude higher query latency due to per-key neural network inference, and construction times ranging from seconds to over 16 minutes due to model training. On Zipfian distributions, where the value distribution follows a smoother power law, AutoCSF achieves lower memory than Learned CSF at all \alpha values without any training overhead. These results suggest that learned approaches offer genuine compression advantages in specific regimes, but for practical deployments where query latency and build time are important, AutoCSF provides a more favorable overall tradeoff. 7. Conclusion We presented AutoCSF, a novel, theoretically principled algorithm that determines both when to augment a compressed static function with an approximate set membership data structure and how to optimally set the parameters for this index to enable fast key-value lookups with a small memory footprint. While the idea of augmenting a CSF with a filter was previously proposed in the literature ( 27 ) , the existing state of the art relied on data-driven heuristics, which, as we showed in this paper, can provide misleading guidance in practice. The core innovation in AutoCSF is the development of novel lower and upper bounds on the difference in cost between a CSF and filter-augmented CSF, using mathematical tools from information theory. We validate that our theoretical results closely align with empirical observations and provide accurate guidance in parameter selection for practitioners. We also compare AutoCSF to other succinct retrieval systems in the literature, such as BCSF and Learned CSF, on both synthetic and real genomics workloads where we find that AutoCSF provides a Pareto-optimal tradeoff in query latency and memory footprint while maintaining low index build times.