Source-linked AI summary
Clark Hash: Stateless Sparse Johnson-Lindenstrauss Quantization for Neural Embeddings
Stanislav Kirdey, Clark Labs Inc
TL;DR
Dense embedding storage is expensive, and corpus-trained compression is inconvenient when vectors arrive before training data. Clark Hash addresses this with a stateless deterministic codec that projects, quantizes, and asymmetrically scores embeddings. In the default profile, 48-byte sketches preserve substantial dense-score behavior on multilingual STS data, while remaining distinct from learned quantizers and approximate-nearest-neighbor indexes.
Problem
1536-byte dense storage for each 384-dimensional f32 embedding motivates a compact representation, especially when vectors arrive before corpus training is available.
Method
Clark Hash independently encodes database vectors with deterministic sparse signed projection and fixed scalar quantization while keeping queries in floating point.
Results
On multilingual STS17 and STS22 data, 48-byte sketches tracked dense cosine with 0.9099 and 0.9460 macro Pearson correlation, respectively.
Takeaways & Limitations
Clark Hash offers compact stateless online encoding without fitting codebooks, while its practical scope is storage and sketch scoring rather than ANN indexing.
Takeaways & Limitations
The benchmark measures sentence-similarity score preservation and human-label correlation, not retrieval recall in large production corpora, adversarial streams, or hybrid indexes.
Abstract
from arXiv · showhide
Clark Hash is a small method for storing neural embeddings in less space. It normalizes each database vector, applies a deterministic sparse signed Johnson-Lindenstrauss projection, clips the result, and stores a fixed-width scalar-quantized code. Queries stay in floating point and are scored against the stored sketches. In the default 384-dimensional sentence-embedding setting, Clark Hash stores a cosine-search vector in 48 bytes instead of 1536 bytes for dense f32 storage. This is 32x smaller. The method does not need a training pass, learned codebooks, rotations, or corpus statistics before new vectors can be stored. We describe the codec, the Rust implementation, and a multilingual sentence-similarity evaluation on 9,304 labeled pairs from 29 subsets. With a multilingual MiniLM encoder, the 48-byte sketches reached 0.910 and 0.946 macro Pearson correlation with dense cosine scores on STS17 and STS22. Clark Hash is not a new Johnson-Lindenstrauss theorem and it is not a replacement for approximate nearest-neighbor indexes. It is a simple stateless codec for compact embedding storage.
1 Introduction
Clark Hash targets online embedding storage, where vectors must be encoded individually before corpus-specific training is available. It combines established projection, hashing, and quantization components into a deterministic codec with asymmetric sketch scoring.
- Motivation: 1536 bytes is the storage cost of one 384-dimensional f32 sentence embedding before index overhead.This can increase memory, cache, disk, and network costs.
- Motivation: Corpus-trained compression methods are less convenient when vectors arrive one at a time before a training set is available.Such methods may learn centroids, rotations, codebooks, or calibration parameters from a corpus.
- Clark Hash: Clark Hash encodes each database vector independently with a deterministic seed while keeping query vectors in floating point.Queries are scored against bit-packed database sketches.
- Contribution: Clark Hash combines established Johnson-Lindenstrauss projections, feature hashing, and scalar quantization into a deterministic neural-embedding codec.The contribution is presented as an engineering package rather than new underlying mathematics.
- Pipeline: The codec configures dimensions, bit width, sparsity, clipping, metric, and seed; independently encodes databases, sketches queries, and scores in sketch space.Scoring uses an asymmetric inner product between compressed database vectors and floating-point query sketches.
2 Related Work
Clark Hash builds on established random projection, feature hashing, scalar quantization, and learned retrieval-compression literature. Its distinct tradeoff is stateless online encoding rather than corpus-specific adaptation.
- Projection and hashing: Johnson-Lindenstrauss projections reduce dimensionality while approximately preserving pairwise distances.Sparse and database-friendly variants reduce arithmetic or randomness requirements.
- Projection and hashing: Feature hashing provides stateless signed dimensionality reduction for high-dimensional sparse features.Related sketching ideas also occur in data-stream algorithms such as CountSketch.
- Learned compression: Learned retrieval quantizers, including product quantization variants, can achieve better quality when representative training data is available.Clark Hash instead gives up corpus-specific adaptation for stateless online encoding and a small implementation.
- Evaluation context: Sentence embeddings are commonly evaluated by correlation with human similarity judgments on semantic textual similarity datasets.The paper uses multilingual STS data including STS17 and STS22-style cross-lingual similarity sets.
3 Method
The method normalizes vectors, applies a deterministic sparse signed projection, clips and scalar-quantizes database sketches, and scores floating-point query sketches asymmetrically.
- Sparse signed projection: Clark Hash uses a sparse random matrix with bucket hashes and signed updates to project embeddings into sketch coordinates.The projection is data-oblivious and deterministic given the seed.
- Sparse signed projection: Increasing m reduces projection noise, while increasing s usually reduces sparse-projection noise at higher encoding cost.Variance depends on sketch dimension, sparsity, and hash collisions.
- Cosine mode: For cosine search, Clark Hash sketches the unit direction and rescales raw coordinates by √m before quantization.The rescaling stabilizes coordinate magnitudes for a fixed clipping range such as [−3, 3].
- Fixed scalar quantization: Each scaled coordinate is clipped and uniformly quantized using L = 2^b − 1 levels.The quantization step is Δ = 2c/L.
- Fixed scalar quantization: Clipping adds the residual z_k − clip(z_k, −c, c), so the clip range trades clipping rate against quantization resolution.This residual is distinct from scalar quantization error.
- Asymmetric scoring: Queries remain in floating point while quantized database sketches support an asymmetric cosine estimate.Avoiding query-side quantization means only the database sketch is quantized in the score.
- Asymmetric scoring: Cosine mode stores normalized direction sketches, whereas dot-product mode adds a two-byte log-norm side channel.The final score incorporates the stored norm information in dot-product mode.
4 Implementation
The Rust implementation is stateless after configuration and generates sparse projection structure from a seed. Encoding and scoring costs scale with the sketch parameters rather than the full dense comparison.
- Implementation: The Rust codec stores sketch parameters, seed, quantizer levels, and metric, then deterministically regenerates bucket locations and signs.Database codes contain bit-packed coordinates and may include a two-byte norm channel.
- Complexity: Encoding one vector costs O(ds + m), combining sparse updates with quantization of m sketch coordinates.The stated cost is per vector.
- Complexity: Scoring one compressed database vector costs O(m), and the included FlatIndex scans compressed vectors exactly in sketch space.FlatIndex is a reference tool rather than an approximate nearest-neighbor index.
- Storage: Cosine-mode storage uses the bit-packed sketch, while dot-product mode adds two bytes for the norm channel.Table 1 describes the default 384-dimensional sentence-embedding profile.
5 Evaluation
The evaluation compares Clark Hash sketches with dense cosine scores on multilingual sentence-similarity data, using two MiniLM-family encoders and macro-averaged metrics. The multilingual encoder preserves substantial dense-score behavior, while the English-oriented encoder is limited by cross-lingual model fit; local timings are not general performance claims.
- 5 Evaluation: 9,304 labeled pairs across 29 multilingual subsets were evaluated with macro-averaged correlations and sketch-to-dense score preservation.The benchmark used 17,000 unique sentences from STS17 and STS22-style cross-lingual datasets.
- 5 Evaluation: Two MiniLM-family encoders were tested: an English-oriented model as a cross-lingual stress test and a multilingual model for quantization-loss assessment.The multilingual model provides a more direct view of sketch quality on these corpora.
- 5 Evaluation: 0.9099 macro Pearson correlation was achieved between 48-byte sketch scores and dense cosine scores on STS17 with the multilingual encoder.The same run reached 0.8144 macro Spearman for dense cosine and 0.7460 for the sketch against human labels.
- 5 Evaluation: The all-MiniLM-L6-v2 run indicates that embedding-model fit matters because dense cosine was already weak on many cross-lingual subsets.Clark Hash adds loss in this run, but the passage identifies model mismatch as the main problem.
- 5 Evaluation: Embedding consumed most local benchmark runtime, while quantization and scoring were smaller stages; hardware details were not reported.The timing results should therefore not be interpreted as general performance claims.
6 Discussion and Limitations
Clark Hash targets online compact storage without corpus-fitted codebooks, but this statelessness trades away adaptation that learned quantizers may provide. Its evaluation scope also excludes several production retrieval settings.
- 6 Discussion and Limitations: Clark Hash suits online embeddings that need compact representations without fitting codebooks or calibration tables, but learned quantizers may achieve better quality at the same byte budget.The trade-off is stateless online encoding versus corpus-specific adaptation.
- 6 Discussion and Limitations: The method is a storage codec and sketch-scoring method, not a replacement for product quantization or graph-based approximate-nearest-neighbor indexes.This defines its intended role rather than a general retrieval-index substitute.
- 6 Discussion and Limitations: The benchmark measures score preservation and human-label correlation on sentence-similarity corpora, not retrieval recall in large production corpora, adversarial streams, or hybrid indexes.The paper also states that no fixed sketch dimension can preserve every future pair in an unbounded stream.
- 6 Discussion and Limitations: Users should tune m, b, s, and c for their embedding model and quality target.The recommendation follows the stated scope boundary for fixed sketch configurations.
7 Conclusion
Clark Hash is presented as a compact, deterministic codec for neural embeddings that combines sparse projection, scalar quantization, and asymmetric sketch scoring. Its default profile stores vectors compactly without a fitting stage, while retaining substantial dense-score behavior when the encoder fits the data.
- 7 Conclusion: Clark Hash combines sparse signed random projection, fixed scalar quantization, and asymmetric sketch scoring into a stateless neural-embedding codec.The conclusion frames the contribution as compact storage with deterministic encoding and no fitting stage.
Availability
Source code, benchmark harnesses, and JSON benchmark reports are available in the Clark Hash GitHub repository.
- Availability: Source code, benchmark harnesses, and JSON benchmark reports are available at the Clark Hash GitHub repository.The cited passage provides the repository location.