qdf includes an opt-in, lossy codec for []float32 / []float64 fields
that hold embedding vectors or other high-dimensional float data. It trades a
bounded, caller-chosen amount of fidelity for a much smaller wire: at equal
reconstruction quality it produces ~17–22 % fewer bytes per vector than
scalar quantization (and than a TurboQuant-style rotated-scalar codec), while
the default qdf path stays bit-exact.
enc := qdf.NewEncoderWith(qdf.OptBalanced | qdf.OptLossyVec)
enc.SetVectorBudget(qdf.MinCosine(0.999)) // keep cosine similarity >= 0.999
_ = enc.EncodeValue(rows)
data := enc.Bytes()
var out []EmbedRow
_ = qdf.Unmarshal(data, &out) // no flag needed; the 0xFD tag self-describesVisual reference: the lossy-vector diagram shows the encode pipeline (rotation → quantize → entropy → never-worse) and the
0xFDwire format / decode path.
A 768-dim float32 embedding is 3 072 bytes. A corpus of millions of them is
the dominant storage and bandwidth cost of a vector database or a RAG index.
The values are not telemetry that must round-trip bit-for-bit — what matters is
that nearest-neighbour search returns the same results, i.e. that cosine
similarity (or L2 distance) is preserved to a few decimal places. That is
exactly the regime where lossy quantization wins, and it is off by default
so no exact workload is ever silently approximated.
The codec borrows the rotation idea from Google's TurboQuant (KV-cache quantization) but, being a CPU serializer rather than a GPU kernel, it can do two things a fixed-width GPU codebook cannot, which is where its size edge comes from:
- Entropy-code the quantization indices. After the rotation the indices are near-Gaussian (a peaked distribution); an order-0 tANS/FSE pass — the same one the rest of qdf uses — recovers the bits a fixed-width code wastes.
- Use a lattice. The E8 lattice's Voronoi cell is rounder than the scalar cube, so it needs fewer bits for the same distortion.
One blob, not two stores. A typical embedding record is id + metadata +
vector. With qdf you serialize the whole []struct as a single self-describing
blob: the scalar/string fields stay exact, the vector field is batched into one
lossy column block, and Unmarshal rebuilds the records with no flag and no side
schema. You do not run a separate vector store next to a metadata store, and you
do not invent a wire format — it is the same Marshal/Unmarshal you already
use, with one option flipped. See the runnable Example_aiEmbeddingStore in the
package docs.
| Situation | Use it? | Budget |
|---|---|---|
| Embedding store / RAG index (ANN search) | Yes — the headline use case | MinCosine(0.999) (recall-preserving) |
| Bandwidth-bound embedding transfer | Yes | MinCosine or MaxRelError(0.01) |
| Model weight / activation tensors | Yes, with care | MaxRelError / TargetSNR, validate downstream accuracy |
| Scientific / financial floats needing exact values | No — leave OptLossyVec off |
— |
| Short vectors (< 32 elems) or scalar float fields | Won't fire | — (stays lossless automatically) |
Rules of thumb:
MinCosineis the right knob for embeddings used in dot-product / cosine ANN search — it directly bounds the metric the index relies on.MaxRelErrorbounds the per-vector relative L2 error; use it when you reason about reconstruction error directly. Tightereps⇒ more bytes.TargetSNR(dB) suits signal-style data.- A looser budget is smaller and faster; pick the loosest your downstream task tolerates and verify recall on a held-out query set.
The codec only fires when OptLossyVec is set, the slice has ≥ 32 elements,
and the lossy result is not larger than the lossless encoding (the never-worse
guarantee, below). Scalar float fields and short slices stay bit-exact even with
the flag on.
For each float-vector column the encoder runs this pipeline (see the diagram):
- Exception scan —
NaN/±Infcannot be quantized; they are pulled into an exception list and replaced with0for the pipeline, then restored bit-exactly on decode (see NaN/Inf handling). - Randomized Hadamard rotation —
R = (1/√n)·H·D, a seed-driven sign-flip diagonalDcomposed with the Walsh–Hadamard transformH. It spreads per-coordinate outliers evenly so the data becomes approximately Gaussian — the ideal shape for low-bit quantization — and it costs onlyO(n·log n)with no stored matrix (just auint64seed on the wire). - Budget → step
delta— a closed-form distortion model (MSE ≈ delta²·G_lattice) maps the fidelity budget to a quantization step, then a short verify-loop tightensdeltaagainst the actual data until the achieved error meets the budget (so the guarantee holds even when the data is not perfectly Gaussian). - Quantize — both the scalar and (when worthwhile) the E8 quantizer, below.
- tANS/FSE entropy coding — the zigzag-varint integer coordinates are compressed with qdf's tANS/FSE entropy stage (coordinate streams written by the legacy rANS stage still decode).
- Pick the smaller quantizer that meets the budget, then never-worse: if even that is not smaller than the lossless float encoding, emit lossless.
Decode reverses it: entropy decode → dequantize (per the recorded variant) → inverse Hadamard → restore exceptions.
Scalar (Z lattice) maps every rotated coordinate to the nearest integer
multiple of delta. It always produces a valid result and is the floor the
never-worse guarantee is measured against.
E8 lattice groups the rotated coordinates into 8-D blocks and maps each
block to its nearest point on E8 — the densest lattice packing in 8
dimensions. The exact nearest-point search (Conway–Sloane) compares the nearest
point of the integer sublattice D8 against the nearest point of its glue
coset D8 + ½, and keeps the closer; the coset choice is stored as one bit
per 8-D block in a separate stream. E8's normalized second moment
(≈ 0.0717) is below the scalar cube's (1/12 ≈ 0.0833), a ~0.65 dB coding
gain — fewer bits for the same distortion.
The codec runs both quantizers and keeps the smaller block that meets the
budget (recorded in flags bits 1–2, so decode needs no hint). E8 is attempted
only when it can plausibly win: the padded dimension is ≥ 16 (≥ two 8-D blocks)
and the target rel-error is ≤ 0.04 — at looser budgets the per-block coset
bit costs more than the packing saves, so the second pass is skipped.
When you marshal a []struct whose element has a []float32/[]float64 vector
field (the common embedding-store shape — []EmbedRow{ID, Emb}), all rows'
vectors of that field are gathered into one count-N block (wire tag
0xFE, tagVecBatchStruct) instead of one count-1 block per row. This amortizes
the fixed block header and the tANS frequency framing, which a per-row
encoding pays for every vector — on a 256-dim corpus the per-row form costs
~290 B/vec versus ~176 B/vec batched (the size numbers below are therefore the
ones you get in production, not just in a micro-benchmark). Batching kicks in
under OptLossyVec for ≥ 16 rows when the field has the same length in every row
and the batched block beats raw; otherwise each vector stays row-major. Scalar
and string fields, and varying-length / short vectors, are unaffected.
Polar split (varying-norm columns). A single quantization step over a whole batch is driven by the largest-norm vector, so when the per-vector norms vary widely (model weights, un-normalized vectors) the small ones are over-quantized. For such a column the codec stores each vector's L2 norm separately (16-bit in the log domain, ~2 B/vector) and quantizes the unit directions, so one tight step serves every direction — −10…−20 % at equal quality on varying-norm data, and it keeps the codec within budget where a shared step would not. It is never-worse and probe-gated on the norm spread, so unit-norm embeddings (where it cannot win) pay nothing.
Measured on a synthetic Gaussian corpus (2 000 vectors × 256 dims), all methods
compared at matched quality (rel ≈ 0.05) and on equal, buffer-reusing
footing. Reproduce with go run ./cmd/qdf-vecbench -synthetic -n 2000 -dim 256.
| Method | bytes / vector | vs qdf |
|---|---|---|
| qdf-lossy | 143 | — |
| naive scalar (5-bit) | 176 | +23 % |
| TurboQuant-scalar (5-bit) | 184 | +29 % |
qdf is ≈17–22 % smaller at equal reconstruction quality (−18.8 % vs naive, −22.3 % vs TurboQuant at the rel ≈ 0.05 point above). Interpolated to exact iso-quality the win is 12–21 % across the rel 0.02–0.10 range (−16.7 % at rel 0.05, widening to −21.3 % at rel 0.10). PQ (product quantization) does not reach this quality on this corpus at comparable rates.
Encode and decode are timed in isolation — each method's scratch is pre-built,
so the encode loop measures encode only and the decode loop measures decode
only (matching qdf's bl.Decode()).
| Method | enc MB/s | dec MB/s | enc allocs |
|---|---|---|---|
| qdf-lossy | 174 | 526 | 1 |
| naive scalar | 993 | 4054 | 0 |
| TurboQuant-scalar | 543 | 949 | 0 |
This is an honest trade: qdf does strictly more work per vector (rotation + entropy decoding on the read path, plus a verify-loop on encode) than the scalar baselines, so its raw throughput is lower. In exchange you get the smallest wire at a given quality and near-zero steady-state encode allocations — the right trade for write-once, read-many embedding stores where storage and bandwidth dominate. (Throughput figures are single-run laptop measurements; absolute MB/s varies with thermal state, but the relative ordering is stable.)
The encoder reuses its scratch across calls (the pooled Marshal path does this
automatically). On a 256×768 batch this brings the pooled encode from
13 855 → 1 308 allocs/op and 21.2 MB → 2.0 MB/op (≈ 10× each) versus a
naive non-reusing encode, with byte-identical output. The wins come from:
- streaming the budget check (one reused row, no materialized
[][]float64); - per-Encoder reuse of the rotation, coordinate, widen, and entropy-coder buffers;
- skipping the second (E8) quantization when it cannot reduce size.
0xFD tag byte
flags (u8) bit 0: elemF32 (1=float32, 0=float64)
bits 1-2: variant (0=scalar, 1=E8)
varuint dim vector length (pre-padding)
varuint count number of vectors
u64le seed Hadamard rotation seed
f64le delta quantization step size
varuint coordsLen byte length of the coords block
[coordsLen]byte coords tANS-compressed zigzag-varint integers
// E8 variant only:
varuint cosetsLen byte length of the coset stream
[cosetsLen]byte cosets one bit per 8-D block, ceil((count*pdim/8)/8) bytes
// always present:
varuint nExc number of exceptions (0 if none)
nExc × {
varuint vecIdx which vector (0-based)
varuint coordIdx which coordinate (0-based)
u32le / u64le bits raw float32 or float64 bits (per elemF32)
}
pdim = nextPow2(dim). Decode bounds every allocation by dim/count read
from the wire, validates cosetsLen exactly, and rejects an unknown variant.
The encoder builds both the lossy block and the lossless float encoding and
keeps whichever is smaller. OptLossyVec is therefore a hint, never a
commitment to inflate: an incompressible or exception-heavy column falls back to
the lossless codec automatically, and the caller sees no API difference.
Non-finite values round-trip bit-exactly regardless of the lossy budget. They are detected before encoding, stored in the exception list (always present, zero-length when there are none), and written back at their original positions after decode. The caller's input slice is never mutated.
v := []float64{1.0, math.NaN(), math.Inf(1)}
// ...encode with OptLossyVec, decode...
// out[1] is NaN, out[2] is +Inf — exact bit patternsSee ExampleEncoder_lossyVector and ExampleMaxRelError in
example_lossyvec_test.go for compilable, tested
end-to-end usage (encode → decode → verify cosine / rel-error / NaN handling).
type Doc struct {
ID string
Emb []float32
}
docs := loadEmbeddings() // []Doc, dim 384
enc := qdf.NewEncoderWith(qdf.OptBalanced | qdf.OptLossyVec)
enc.SetVectorBudget(qdf.MinCosine(0.999))
if err := enc.EncodeValue(docs); err != nil {
log.Fatal(err)
}
data := enc.Bytes()
var out []Doc
if err := qdf.Unmarshal(data, &out); err != nil {
log.Fatal(err)
}
// out[i].Emb approximates docs[i].Emb with cosine >= 0.999