Entropy-Punctured Bloom Filters for Memory-Efficient Machine Learning

John Cartmell; Mihaela Cardei; Ionut Cardei

cs.LGSep 12, 2026

Entropy-Punctured Bloom Filters for Memory-Efficient Machine Learning

Authors: John Cartmell, Mihaela Cardei, Ionut Cardei

Organizations: Department of Electrical Engineering and Computer Science Florida Atlantic University Boca Raton, FL, USA

Abstract

Memory-efficient feature representations are increasingly important in machine learning settings where storage, transmission cost, bandwidth, or privacy constraints limit access to raw data. Bloom Filter (BF) encodings provide compact probabilistic representations of engineered features, but their behavior under structural compression and their applicability to regression tasks remain underexplored. In this work, we propose entropy-punctured Bloom Filters, a memory-aware encoding strategy that removes low-variability bit positions identified using empirical entropy. Starting from fixed-length BF encodings of quantized features, the proposed approach produces reduced representations that preserve predictive structure while improving predictive efficiency relative to encoded representation size. We evaluate the approach on diverse regression datasets, comparing raw features, Principal Component Analysis (PCA), Random Projection (RP), and Bloom Filter variants under leakage-free evaluation protocols and approximately matched representation sizes. Performance is assessed using ridge regression, XGBoost, and neural networks, with predictive efficiency measured as R2 relative to encoded representation size per sample. Results show that Bloom Filter encodings remain competitive with classical compressed representations while achieving substantial storage savings. Entropy-based puncturing further reduces representation size with minimal loss in predictive fidelity, yielding improved predictive efficiency. These findings demonstrate that entropy-punctured Bloom Filters provide an effective representation-level compression approach for memory-constrained machine learning.

Figures & tables

Dataset	Type	Samples	Features	Raw Size (bytes per sample)
Abalone	Tabular	4,177	8	64
Airline	Time series	144	12	96
Allstate	Tabular	188,318	130	170
Bike	Time series	17,379	24	192
Boston	Tabular	506	13	104
California	Tabular	20,640	8	64

TABLE I: Summary of Datasets

Dataset	$m$ Bytes	$k$ Hashes	$\tau$ Threshold
Abalone	32	3	0.30
Airline	192	3	0.05
Allstate	256	2	0.10
Bike	108	2-3	0.15
Boston	32	3	0.30
California	64	2	0.10

TABLE II: Bloom Filter Encoding Parameters Used for Each Dataset

Dataset	Raw	Non-BF	PBF
Abalone	0.593	0.627	0.591
Airline	0.994	0.990	0.879
Allstate	0.567	0.521	0.558
Bike	0.943	0.938	0.912
Boston	0.882	0.785	0.819
California	0.852	0.795	0.764

TABLE III: Best predictive performance (

R^{2}

) achieved for each representation type across datasets.

Dataset	Non-BF	PBF	Best
Abalone	0.0203	0.0293	PBF
Airline	0.0309	0.0898	PBF
Allstate	0.0027	0.0093	PBF
Bike	0.0085	0.0084	RP
Boston	0.0082	0.0380	PBF
California	0.0124	0.0449	PBF

TABLE IV: Predictive efficiency measured as

R^{2}

relative to encoded representation size per sample.

Fig. 1: Effect of varying Bloom Filter size ( $m$ ) and hash count ( $k$ ) on XGBoost $R^{2}$ performance for the California Housing dataset.

Fig. 2: Bit occupancy as a function of Bloom Filter size and hash count.

Fig. 3: Entropy behavior under varying Bloom Filter size and hash count.

Fig. 4: Predictive fidelity ( $R^{2}$ ) as a function of entropy puncturing threshold for the Parkinson’s dataset.

Fig. 5: Predictive efficiency as a function of entropy puncturing threshold for the Parkinson’s dataset.

Fig. 6: Predictive fidelity ( $R^{2}$ ) as a function of the fraction of Bloom Filter bits removed under different removal strategies.

Fig. 7: Predictive efficiency under different Bloom Filter bit removal strategies.

Keep Ratio	Bytes	$R^{2}$	$R^{2}$ /Byte
1.00	64	0.8824	0.0138
0.90	58	0.8828	0.0152
0.80	52	0.8819	0.0170
0.70	45	0.8809	0.0196
0.60	39	0.8752	0.0224
0.50	32	0.8807	0.0275

TABLE V: Effect of Bloom Filter folding on predictive fidelity and predictive efficiency for the Parkinson’s dataset using XGBoost.

Dataset	Method	$R^{2}$	Bytes	PE
California	PBF	0.7622	23.6	0.0323
	FH	0.0844	24.0	0.0035
Parkinson’s	PBF	0.8830	32.4	0.0273
	FH	0.3654	32.0	0.0114

TABLE VI: Storage-matched comparison with feature hashing.

Oct 19, 2026

Communication Complexity of Universal Features

Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes

X\sim D

and produces a finite encoding before a task

f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}

is specified. For each task, a decoder must predict

f(X)

with error at most

\varepsilon

under

D

. We construct an encoder that outputs a representation with

O(d^{*}\log(1/\varepsilon))

bits, where

d^{*}

is the dual VC dimension of

\mathcal{F}

. Our encoder greedily selects

O((d^{*}/\varepsilon)\log(1/\varepsilon))

functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every

d^* \ge 1

and

\varepsilon < 1/4

up to a universal constant factor, and instance-wise optimal for every family

\mathcal{F}

up to an

O(\log(1/\varepsilon))

factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.

Lunjia Hu, Anish Jayant, Peter Li +2

Northeastern University · Georgia Institute of Technology · Harvard University

Representation Learning Communication Complexity Shared Representation Learning

Ask PDF

Sep 18, 2026

An Introduction to Compression-Based Machine Learning

Any lossless compression algorithm (like gzip) may be converted into a machine learning method, via either Normalized Compression Distance or the Minimum Description Length principle. Any auto-regressive model may be converted into a lossless compression method via entropy coding. This seemingly circular dependence has unrealized potential in modern artificial intelligence and machine learning, and we survey and formalize the various strategies that have been used to leverage compression for machine learning. We introduce and empirically validate a design framework for compression-based ML, finding compression-based methods competitive with conventional baselines and decisively stronger on malware. We find that varying these design choices yields accuracy gains of up to 0.62.

John Hurwitz, Edward Raff, Charles K. Nicholas

University of Maryland, Baltimore County · CrowdStrike · Syracuse University

Minimum Description Length

Ask PDF

May 22, 2026

Efficient Learned Image Compression without Entropy Coding

Entropy coding is widely used in typical learned image compression (LIC) that converts latents into a compact bitstream. However, entropy coding is typically sequential and becomes the coding latency bottleneck. To overcome it, we present Entropy-Coding Free Learned Image Compression (EF-LIC), a multi-rate framework that generates compact representation by removing statistical and correlation redundancy with low coding latency. First, we introduce unconstrained vector quantization and prove that its index distribution approaches the maximum-entropy bound, yielding minimal statistical redundancy. Second, we propose a context-conditioned autoregressive transform that directly reparameterizes the latents to reduce inter-dependency. Theoretical analysis shows that EF-LIC can remove correlation redundancy as effectively as typical LIC with entropy coding, leading to comparable compression performance. Experiments show EF-LIC achieves up to 67.86% bitrate reduction over MS-ILLM on Kodak with LPIPS. Ablation studies further show EF-LIC matches the compression performance of its entropy-coding based variant while achieving over

3\times

faster encoding and

5\times

faster decoding.

Hao Cao, Wenqi Guo, Zhijin Qin +1

Department of Electronic Engineering, Tsinghua University · Department of Automation, Tsinghua University · State Key Laboratory of Space Network and Communications +1

Learned Image Compression Vector Quantization

Ask PDF

Abstract

Explore similar work

Communication Complexity of Universal Features

An Introduction to Compression-Based Machine Learning

Efficient Learned Image Compression without Entropy Coding