Title: Ultra-Quantisation: Efficient Embedding Search via 1.58-bit Encodings Show Chinese title

Title: 超量化：通过1.58位编码的高效嵌入搜索

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. Show Chinese abstract

Abstract: 许多现代搜索领域包含来自神经网络的高维浮点数向量，以嵌入的形式表示。 典型的嵌入大小范围从几百到几千个维度，这使得嵌入的大小以及比较的速度成为一个重要的问题。 量化是一种机制类别，它用更小的表示（例如短整型）替换浮点值。 这样可以以较小的数据表示和更快的比较函数为代价，近似表示嵌入空间。 在这里我们将这个想法几乎推向了极端：我们展示了如何用元素从集合{-1,0,1}中抽取的向量来替代任意精度浮点值的向量。 这种方法在空间和度量评估成本上带来了非常显著的节省，同时保持了相似性测量的强相关性。 这是通过存在于高维空间中的凸多面体类实现的。 在本文中，我们给出了这些对象的大致描述，并展示了它们如何作为这种激进量化的基础，同时保持令人惊讶的准确性。