Pith. sign in

REVIEW 4 major objections 8 minor 15 references

Ultra-Quantisation: Efficient Embedding Search via 1.58-bit Encodings

T0 review · 4 major / 8 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Shrink embeddings to 1.58 bits per value and keep search rank at 0.96

desk verdict A practical and fast 1.58-bit embedding quantisation with strong measured correlations, but the geometric proof is deferred and partly flawed, and generality beyond uniform high-dimensional data is untested. read the letter →

arxiv 2506.00528 v1 pith:44LJN5EI submitted 2025-05-31 cs.LG cs.DB

Richard Connor , Alan Dearle , Ben Claydon This is my paper
classification cs.LGcs.DB
keywords ternaryquantisationembeddingsearchEqui-Voronoipolytope1.58-bitencodingbitwisescalarproductk-nearestneighbourhigh-dimensionalgeometryvectorcompression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that any set of $\ell^2$-normalised high-dimensional embedding vectors can be compressed to ternary vectors with exactly $2d/3$ non-zero entries drawn from $\{-1,0,1\}$, and that the bitwise scalar product of these compressed vectors gives a proxy for Euclidean distance that preserves rank order with Spearman correlation as high as 0.96. This would mean $k$-nearest-neighbour search over millions of embeddings can run tens to hundreds of times faster on commodity hardware with little loss of result quality. The mapping is generic: it does not depend on the source of the embeddings, only on the geometry of high-dimensional spheres. The authors ground the mapping in a family of convex polytopes they call Equi-Voronoi Polytopes, whose vertices define equal-volume Voronoi cells on the hypersphere.

What carries the argument

The $\{x,d\}$ Equi-Voronoi Polytope (EVP): the convex polytope whose vertices are all $d$-vectors with exactly $x$ non-zero entries each drawn from $\{-1,0,1\}$. The nearest-vertex mapping selects the $x$ largest absolute coordinates, assigns $1$ or $-1$ by sign, and zeroes the rest; choosing $x = 2d/3$ maximises the vertex count. Distance between two ternary vectors is computed as the bitwise scalar product $\mathrm{b2sp}(v,w) = (\mathrm{bsp}(v^+,w^+) + \mathrm{bsp}(v^-,w^-)) - (\mathrm{bsp}(v^+,w^-) + \mathrm{bsp}(v^-,w^+))$ over two bit vectors per ternary vector, using only SIMD-friendly bit-count operations.

What would settle it

Sample pairs from a real embedding set such as GloVe-100, compute the angles $\angle(v_i, v_j, u_j)$ and $\angle(v_j, v_i, u_i)$ for each pair's nearest EVP vertices, and check whether the angles are tightly concentrated near $\pi/2$; a wide spread would falsify the geometric bound that the proxy depends on.

Watch

Extended reading notes

Core claim

The central discovery is that the nearest vertex of an Equi-Voronoi Polytope, computed by keeping the signs of the largest-magnitude coordinates and zeroing the rest, yields a distance-preserving proxy in high dimensions. Because a hypersphere in high dimensions concentrates almost all of its volume near its surface, a random point is nearly equidistant from its Voronoi centre, and angles subtended at the two Voronoi vertices by a point and the other vertex are tightly concentrated near right angles. These constraints leave little variance in the length of the unknown side between two points, so the vertex-to-vertex distance is a strong predictor of the true distance. The practical consequence is that the scalar product of two such ternary vectors, evaluated as a bitwise operation over two-bit encodings, reproduces the rank order of Euclidean distance on real datasets such as GloVe, PubMed, and CLIP.

Load-bearing premise

The method assumes that high-dimensional geometry guarantees a sampled vector is nearly equidistant from its nearest vertex and that the angles at the two nearest vertices are near right angles; this fails for data with low effective dimensionality or strong axis alignment.

Editorial extensions

If this is right

  • On the three million-element real-world datasets tested, exhaustive 100-query searches are 33x, 103x, and 158x faster with the bitwise form than with floating-point Euclidean distance.
  • The Spearman correlation between the proxy and true distances exceeds both 1-bit and 1.58-bit baselines on every dataset, reaching 0.96 on the Laion CLIP embeddings.
  • An $\{x,d\}$ EVP representation of a 384-dimensional vector occupies 1024 bits, about 8% of the space of a 32-bit float vector, with the gap widening as dimensionality grows.
  • Because the mapping is defined by a simple coordinate-wise rule and uses only bit-count operations for comparison, it can be dropped into existing approximate-neighbour search pipelines as a fast prefilter.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The random rotation the authors apply to the Laion data before mapping hints that real embeddings with axis-aligned principal components may need a similar pre-rotation for the concentration assumption to hold; this preprocessing would be a natural extension for other datasets.
  • The masked-addition variant, in which only one operand is quantised while the other stays in floating point, could offer better accuracy for mixed-precision workloads and is a direct, untested extension of the same geometry.
  • The same vertex-space mapping could support approximate, multiplication-free matrix multiplication by applying the top-magnitude sign rule to one factor of each scalar product; the paper notes this possibility without evaluating it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 8 minor

Summary. The paper proposes replacing ℓ2-normalised d-dimensional embedding vectors with ternary vectors in {-1,0,1}^d having exactly x non-zero entries, obtained by keeping the x coordinates of largest absolute value with their signs; this is shown to be the nearest vertex of the authors' 'Equi-Voronoi polytope' (Section 2.4). The manuscript claims that the Voronoi cells of these vertices have equal volume on the hypersphere (Section 2.5) and that, by concentration-of-measure arguments, vertex-to-vertex distances closely proxy the true distances between the points in the corresponding cells (Section 3); the full geometric argument is deferred to the in-preparation reference [9]. Encoding a ternary vector as a pair of bit masks v+ and v- allows the scalar product to be computed exactly by the bitwise function b2sp using four AND operations and additions (Section 5.1.2). Experiments on uniform, GloVe-100, PubMed-384, and PCA-reduced and randomly rotated Laion data (around one million vectors each) report Spearman correlations up to 0.96 (Table 2), 30@n recall values that improve with n (Figures 5-6), and end-to-end speedups of 33-158x for 100 exhaustive queries over 1M vectors (Table 5), with comparisons against 1-bit and b1.58 quantisation baselines.

Significance. If the empirical results are taken at face value, this is a practical and simple contribution: the mapping threshold is derived (x = 2d/3 from maximising the EVP vertex count), no parameters are fitted to the target data, the bitwise function b2sp computes the ternary scalar product exactly, and the representation is SIMD-friendly at about 2 bits per coordinate. The reported correlations beat the 1-bit and b1.58 baselines on all five data configurations, and speedups of one to two orders of magnitude for exhaustive search over one million vectors are substantial. The weakness is that the theoretical narrative is not commensurate with the claims: the geometric explanation is explicitly outsourced to an unpublished companion (Section 3), the only self-contained lemma rests on a false premise (Section 2.5), and the 'entirely generic' applicability claim is undermined by the need to randomly rotate the Laion data (Section 5.1). These are fixable within the scope of a revision, and the paper would then be a credible contribution to practical embedding search.

major comments (4)
  1. [2.5] The equi-volume proof rests on a false premise. The text states that for uniformly distributed points on a hypersphere 'each vector element is necessarily drawn from an identical and independent distribution', but the coordinates of a uniform point on the sphere are identically distributed and not independent (for d=2, |y| is determined by |x|; the joint distribution is supported on a submanifold, and reference [15] itself derives a marginal Beta distribution rather than independence). Consequently the equiprobability of the nearest vertex does not follow as written, and the inference about equal cell volumes is not proven. The conclusion is in fact true, but only via a different argument: the signed permutation group acts transitively on the vertex set and preserves the uniform measure on the sphere, so the spherical Voronoi cells are congruent. Since equi-volume is stated in Section 2.2 as a defining property of EVPs, the paper should replace the given argument with the symmetry argument.
  2. [3] The theoretical core of the paper is an outline. Section 3 explicitly refers the reader to an unpublished companion paper [9] for the full geometric explanation, and items 4-5 assert the concentration of the angles ∠vi vj uj and ∠vj vi ui and of the tetrahedron rotation angle by citing [7,8] without giving a quantified statement. As written, the manuscript does not deliver the 'principled geometric analysis' promised in Section 6, and there is no derivation of, e.g., a bound on the variance of ℓ2(ui, uj) conditional on ℓ2(vi, vj). A theory should also be consistent with the ordering in Table 2, where the uniform data - the case the concentration reasoning addresses most directly - show the lowest correlations (0.79-0.80) and the real data show the highest (0.94-0.96); the paper should either supply the full argument in this manuscript or explicitly characterise the conditions under which the proxy error is small.
  3. [5.1] The claim of generic applicability (Abstract; Section 1.3: 'entirely generic') is not supported. The mapping in Section 2.4 selects coordinates by largest absolute magnitude and is therefore coordinate-aligned, while the geometric justification in Section 3 concerns the uniform measure on a high-dimensional sphere. Real embedding sets can have low effective rank or be aligned with the coordinate axes; in such cases the same coordinates tend to be selected for many vectors, and the residual directions that determine fine rank order may be discarded. The paper itself randomly rotates the Laion data 'to avoid the principal components being tightly aligned with the EVP vertices' (Section 5.1, item 4), which is an implicit admission that the proxy can fail in non-generic positions; yet no experiment is reported without this rotation and the method description in Sections 2 and 5 does not instruct practitioners to rotate. I request that the Laion experiments be repeated without rotation and with several rotation seeds, and that the paper state explicitly the data conditions under which the proxy is expected to be valid.
  4. [Table 5] The experimental configuration for the Laion data is internally inconsistent. Section 5.1 item 4 and Table 2 state that the CLIP data was reduced by PCA to 500 dimensions and mapped with a {333,500} EVP, while Table 5 lists 'Laion' with 768 dimensions and a {512,768} EVP and attributes to that row the 158x speedup; the Table 5 header row also reads 'Glove Dino Laion', although no Dino dataset appears elsewhere in the paper. Because the 158x speedup is a headline quantitative claim, the authors must correct these inconsistencies and state exactly which configuration produced Tables 2, 5, and Figure 6.
minor comments (8)
  1. [1.1] The line 'Since P_i xi = P_i yi = 1' should read 'since Σ x_i^2 = Σ y_i^2 = 1'; as printed, the displayed sums are not the squared norms and the derivation of the correlation between ℓ2 distance and negative scalar product is hard to follow.
  2. [5.1.1] The continuous Γ-function argument identifies a continuous maximiser at x = 2d/3, but the EVP requires an integer x; the paper should state the exact rounding rule used (e.g., floor, ceil, or nearest integer) for each d and clarify the sense of 'always' for small d.
  3. [Title / 1.2] The paper calls the encoding '1.58-bit', but for x = 2d/3 the vertex set has per-coordinate entropy log2(C(d, 2d/3) 2^{2d/3})/d ≈ 1.98 bits, and the implementation stores two bit masks (v+, v-) per coordinate, i.e., 2 bits per element before padding to 256-bit words; this terminology should be clarified relative to the unconstrained ternary set.
  4. [Table 2] The Spearman ρ values are computed over pairs whose true-distance distributions differ strongly across data sets (uniform data concentrate near √2, compressing the dynamic range and mechanically lowering ρ); within-dataset method comparisons are valid, but cross-dataset comparison of ρ should be interpreted with care, and confidence intervals would strengthen the claim.
  5. [Tables 4-5] The reported exhaustive-query times should state whether they include the cost of mapping the query vector to its EVP vertex (top-x selection), and whether the data index or query index is rebuilt during the measurement; also, the code URL and the sketch reference in Section 4.2 currently appear as '[?]' placeholders.
  6. [Figure 2] The caption asserts that the Voronoi partitions corresponding to the cuboctahedron vertices are congruent, while the figure shows non-uniform faces; the claim needs a brief justification or a more careful wording distinguishing the spherical Voronoi cells from the faces of the polytope.
  7. [5.1.1 / 6.3] The choice x = 2d/3 is justified only by maximising the number of vertices; no experiment in the paper varies x, so the claims in Section 6.3 that this configuration 'generally gives the best search results' and that smaller x decreases accuracy are asserted without the supporting ablation.
  8. [4.3 / Table 2] The b1.58 baseline needs one implementation sentence: how its variable number of non-zero entries is handled when the b2sp function is applied, and whether the 30@n recall for that baseline is computed in exactly the same way as for the EVP representation; without this, the baseline comparison is difficult to reproduce.

Circularity Check

1 steps flagged · score 4.0 of 10

No definitional circularity in the mapping or the bitwise proxy; the main concern is that the geometric guarantee is deferred to an in-preparation self-citation ([9]) and to angle-concentration results from the authors' own prior work ([7,8]).

  1. self citation load bearing [Section 3, opening paragraph of 'Geometric constraints']
    "The full geometric explanation for the phenomenon is complex, and we refer the interested reader to a fuller exposition [9] we give elsewhere."

    The paper's theoretical premise—that distances between nearest EVP vertices approximate distances between original points—is not derived in the manuscript. The proof is deferred to reference [9], listed as 'in preparation' and authored by the same group (Connor et al.). The outline that follows also relies on [7] and [8], both self-authored, for the angle-concentration facts that yield the tight bounds on ℓ2(ui,uj) (items 4–5). Because [9] is unavailable and the cited angle results come from the authors' own prior work rather than an external, checkable source, the geometric justification is load-bearing on a self-citation chain. This is not a definitional equivalence, but it is a self-citation chain supporting the central accuracy claim.

full rationale

The core quantisation pipeline is not circular: the mapping rule (Section 2.4) is a deterministic top-magnitude sign rule; x=2d/3 is derived by maximising the EVP vertex count, not fitted to any data; and b2sp is exactly the ternary scalar product (Section 5.1.2), so the bitwise operation is not a fitted surrogate. The Spearman correlations and 30@n recalls are measurements over queries, not quantities forced by construction. The main issue flagged by the manuscript itself is Section 3's deferral of the full geometric proof to [9], an in-preparation self-citation, with the outline relying on [7,8] from the same authors; this makes the theoretical justification load-bearing on unavailable self-cited work, though the empirical results remain independent. The random rotation applied to the Laion data (Section 5.1, item 4) is an explicit limitation: it forces the data into the generic position required by the concentration-of-measure argument, and the paper does not instruct practitioners to rotate; this weakens the unqualified 'arbitrary vectors' claim but is a correctness/assumption issue, not circularity. Overall the paper does not reduce its predictions to its inputs by definition; the circularity-adjacent issue is the self-citation chain for the geometric explanation.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The scheme has a single design parameter, x = 2d/3, derived to maximise the vertex count. The main axioms are standard high-dimensional geometry plus two concentration assumptions inherited from the authors' prior papers. The false independence claim in Section 2.5 is flagged. No new physical entities are introduced.

free parameters (1)
  • x (number of non-zero elements in each ternary code) = 2d/3
    Chosen as the value that maximises the vertex count C(d,x)*2^x; not fitted to the evaluation data, but it is a design parameter that controls the accuracy/speed trade-off and is not derived from a uniqueness theorem.
assumptions (4)
  • domain assumption Each coordinate of a uniformly distributed point on a hypersphere is drawn from an identical and independent distribution (Section 2.5).
    Used to argue that every EVP vertex is an equiprobable nearest neighbour and hence that Voronoi cells have equal volume. The premise itself is false: coordinates on the sphere are dependent. The equal-volume conclusion can be recovered from signed-permutation symmetry, but the stated reason is wrong.
  • domain assumption For a point u and its nearest EVP vertex v in a high-dimensional space, the angle ∠v_i v_j u_j is very likely near a right angle with small variance (Section 3, item 4, citing [7]).
    This is the load-bearing concentration-of-measure premise that gives tight bounds on the unknown distance ℓ2(ui, uj). The paper cites its own prior work for the result and does not prove it here.
  • domain assumption The dihedral angle between the two triangles sharing the edge v_i v_j is also very likely near a right angle with small variance (Section 3, item 5, citing [8]).
    Second concentration premise needed to restrict the tetrahedron geometry; again deferred to the authors' earlier work.
  • standard math Any four points in Euclidean space can be isometrically embedded as a tetrahedron in three dimensions (Section 3, item 3, citing [4,6]).
    This is a standard property of Euclidean distance geometry: four points span at most a three-dimensional affine subspace.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ultra-Quantisation: Efficient Embedding Search via 1.58-bit Encodings." pith.science (2026). https://pith.science/paper/44LJN5EI

@misc{pith2026250600528,
  author       = {Pith},
  title        = {Pith review of: Ultra-Quantisation: Efficient Embedding Search via 1.58-bit Encodings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/44LJN5EI}},
  note         = {Machine review of arXiv:2506.00528}
}
read the original abstract

Many modern search domains comprise high-dimensional vectors of floating point numbers derived from neural networks, in the form of embeddings. Typical embeddings range in size from hundreds to thousands of dimensions, making the size of the embeddings, and the speed of comparison, a significant issue. Quantisation is a class of mechanism which replaces the floating point values with a smaller representation, for example a short integer. This gives an approximation of the embedding space in return for a smaller data representation and a faster comparison function. Here we take this idea almost to its extreme: we show how vectors of arbitrary-precision floating point values can be replaced by vectors whose elements are drawn from the set {-1,0,1}. This yields very significant savings in space and metric evaluation cost, while maintaining a strong correlation for similarity measurements. This is achieved by way of a class of convex polytopes which exist in the high-dimensional space. In this article we give an outline description of these objects, and show how they can be used for the basis of such radical quantisation while maintaining a surprising degree of accuracy.

Figures

Figures reproduced from arXiv: 2506.00528 by the authors.

Figure 1
Figure 1. A Voronoi partition in 2D based on a regular set of points. Each cell [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The vertices and 3D form of a cuboctahedron, which is a [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. A tetrahedral net and its 3D rendering based only on the distance [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Shepard diagrams showing correlations for randomly selected pairs of [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Histograms of 30@30 and 30@100 recall for PubMed data [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: Search results over the real-world data sets [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [9]

    Connor, R., et al.: A geometric basis for approximate scalar product (2025, in preparation)

    work page 2025

  2. [15]

    Voelker, A.R., Gosmann, J., Stewart, T.C.: Efficiently sampling vectors and coordinates from the n-sphere and n-ball. Tech. rep., Centre for The- oretical Neuroscience, Waterloo, ON (01 2017) 17

    work page 2017

  3. [1]

    Aumueller, M., Bernhardsson, E., Faitfull, A.: Ann benchmarks,https: //ann-benchmarks.com/index.html 15

    work page

  4. [2]

    Blum, A., Hopcroft, J., Kannan, R.: High-Dimensional Space, p. 4–28. Cambridge University Press (2020)

    work page 2020

  5. [3]

    Claren- don Press (1953)

    Blumenthal, L.M.: Theory and applications of distance geometry. Claren- don Press (1953)

    work page 1953

  6. [4]

    Bulletin of the Amer- ican Mathematical Society39(6), 423–426 (1933)

    Blumenthal, L.M.: A note on the four-point property. Bulletin of the Amer- ican Mathematical Society39(6), 423–426 (1933)

    work page 1933

  7. [5]

    Chavez, E., T´ ellez, E., Aumueller, M., Mic, V.: Sisap challenges,https: //sisap-challenges.github.io/2025/index.html

    work page 2025

  8. [6]

    ACM TRANS- ACTIONS ON INFORMATION SYSTEMS35(3), 17–27

    Connor, R., Cardillo, F., Vadicamo, L., Rabitti, F.: Hilbert exclusion: im- proved metric search through finite isometric embeddings. ACM TRANS- ACTIONS ON INFORMATION SYSTEMS35(3), 17–27

    work page

Show all 15 references
  1. [7]

    In: Similarity Search and Applications

    Connor, R., Dearle, A.: Sampled angles in high-dimensional spaces. In: Similarity Search and Applications. pp. 233–247. Springer International Publishing (2020)

    2020

  2. [8]

    ACM Transactions on Knowledge Discovery from Data18(6), 1–44 (2024)

    Connor, R., Vadicamo, L.: nSimplex Zen: A novel dimensionality reduc- tion for Euclidean and Hilbert spaces. ACM Transactions on Knowledge Discovery from Data18(6), 1–44 (2024)

    2024

  3. [10]

    Information Sciences270, 1–27 (2014)

    Gracia, A., Gonz´ alez, S., Robles, V., Menasalvas, E.: A methodology to compare dimensionality reduction algorithms in terms of loss of quality. Information Sciences270, 1–27 (2014). https://doi.org/https://doi.org/10.1016/j.ins.2014.02.068,https: //www.sciencedirect.com/scie...

    2014 doi

  4. [11]

    58 2b4t technical report

    Ma, S., Wang, H., Huang, S., Zhang, X., Hu, Y., Song, T., Xia, Y., Wei, F.: Bitnet b1. 58 2b4t technical report. arXiv preprint arXiv:2504.12285 (2025)

    2025 arXiv

  5. [12]

    arXiv preprint arXiv:2402.17764 (2024)

    Ma, S., Wang, H., Ma, L., Wang, L., Wang, W., Huang, S., Dong, L., Wang, R., Xue, J., Wei, F.: The era of 1-bit llms: All large language models are in 1.58 bits. arXiv preprint arXiv:2402.17764 (2024)

    2024 arXiv

  6. [13]

    In: Empirical Methods in Natural Language Processing (EMNLP)

    Pennington, J., Socher, R., Manning, C.D.: Glove: Global vectors for word representation. In: Empirical Methods in Natural Language Processing (EMNLP). pp. 1532–1543 (2014)

    2014

  7. [14]

    github.io/2024/datasets/#768d_clip_embeddings_clip768 16

    Schuhmann, C., Beaumont, R., Vencu, R., Gordon, C., Wightman, R., Cherti, M., Jitsev, J.: Laion-5b: An open large-scale dataset for training next generation image-text models (2022),https://sisap-challenges. github.io/2024/datasets/#768d_clip_embeddings_clip768 16

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.