Technical Summary: Clark Hash

Problem Statement

Neural embedding systems frequently require storing vast numbers of dense floating-point vectors. A standard 384-dimensional sentence embedding in f32 format consumes 1,536 bytes per vector, creating significant costs for memory, local cache, disk storage, and network transfer. While existing compression methods (such as product quantization) can achieve high quality, they typically rely on learning centroids, rotations, or codebooks from a representative corpus. These approaches are ill-suited for "online" scenarios where vectors arrive individually and must be stored immediately without access to a pre-existing training set or corpus statistics.

Methodology

Clark Hash is a stateless, deterministic codec designed to compress neural embeddings without a training phase. It combines three established techniques: sparse signed Johnson-Lindenstrauss (JL) projection, fixed scalar quantization, and asymmetric scoring. The process operates as follows:

1. Normalization: For cosine search, the input vector $x$ is normalized to a unit direction $u = x / \|x\|_2$.
2. Sparse Signed Projection: The vector is projected into a lower-dimensional sketch space ($m$ dimensions) using a sparse random matrix $R$. This matrix is constructed via feature hashing, where input coordinates are mapped to buckets with random signs ($\sigma \in \{-1, +1\}$). The projection is data-oblivious and deterministic given a seed.
   • The projection is scaled by $\sqrt{m}$ to stabilize coordinate magnitudes for quantization.
3. Fixed Scalar Quantization: The projected coordinates are clipped to a symmetric range $[-c, c]$ and uniformly quantized to $b$ bits. This produces a fixed-width integer code.
4. Asymmetric Scoring: Query vectors remain in floating-point format. They are projected into the same sketch space (without quantization) and scored against the stored quantized database sketches using an asymmetric inner product. This avoids quantization error on the query side.
5. Dot-Product Extension: For dot-product metrics, a two-byte log-norm side channel is added to store the magnitude of the original vector, allowing the reconstruction of the dot product from the cosine estimate and norms.

The implementation is a stateless Rust crate (clark-hash), where bucket locations and signs are generated on-the-fly using a SplitMix64-style hash function based on the input index and a seed.

Key Contributions

The paper presents Clark Hash not as a new mathematical theorem, but as an engineering package that integrates existing concepts into a compact, stateless solution. Its primary contributions are:

• Stateless Online Encoding: The ability to encode vectors individually without prior corpus statistics, learned codebooks, or calibration parameters.
• Extreme Compression: In the default configuration for 384-dimensional embeddings, the method reduces storage from 1,536 bytes to 48 bytes (a 32x reduction).
• Deterministic Codec: A fixed-width scalar-quantized representation that allows for exact scanning of compressed vectors in sketch space.
• Implementation: A reference Rust implementation and a benchmark harness available for public use.

Results

The method was evaluated on multilingual sentence-similarity tasks using 9,304 labeled pairs from 29 subsets (STS17 and STS22 via MTEB). The evaluation compared dense cosine scores against Clark Hash sketch scores using MiniLM-family encoders.

• Storage Efficiency: The default profile ($m=96, b=4$) stores vectors in 48 bytes.
• Correlation with Dense Scores:
  • On STS17 with the multilingual MultiMiniLM-L12 model, the 48-byte sketches achieved a 0.9099 macro Pearson correlation with dense cosine scores.
  • On STS22, the correlation reached 0.9460.
• Performance: The quantization and scoring steps are computationally negligible compared to the embedding generation step. For example, quantizing 17,000 unique sentences took approximately 0.025 seconds, while scoring took 0.005 seconds.
• Model Dependency: The results indicate that the quality of the sketch is heavily dependent on the underlying embedding model. When the model (e.g., all-MiniLM-L6-v2) was not well-suited for cross-lingual data, the dense baseline was already weak, and the sketch added further loss.

Significance and Limitations

The authors position Clark Hash as a simple storage codec and sketch scoring method, explicitly stating it is not a replacement for approximate nearest-neighbor (ANN) indexes (like HNSW) or learned quantizers (like Product Quantization).

• Significance: It offers a practical solution for scenarios requiring compact, deterministic storage of embeddings where vectors arrive online and no training set is available. It preserves a large portion of the dense-score behavior (high Pearson correlation) when the embedding model fits the data well.
• Limitations:
  • It does not adapt to the corpus, potentially resulting in lower quality than learned methods at the same byte budget.
  • It is not an ANN index; the included FlatIndex performs exact scans in sketch space, which may not scale to massive production datasets without further indexing structures.
  • The fixed sketch dimension cannot preserve every pair in an unbounded stream; users must tune parameters ($m, b, s, c$) based on their specific quality targets.

In conclusion, Clark Hash provides a "small method" for storing neural embeddings that trades corpus-specific adaptation for stateless simplicity and extreme storage efficiency.