Dense Vector Search

A traditional tokenized inverted index can be considered to model text as a "sparse" vector, in which each term in the corpus corresponds to one vector dimension. In such a model, the number of dimensions is generally quite high (corresponding to the term dictionary cardinality), and the vector for any given document contains mostly zeros (hence it is sparse, as only a handful of terms that exist in the overall index will be present in any given document).

Dense vector representation contrasts with term-based sparse vector representation in that it distills approximate semantic meaning into a fixed (and limited) number of dimensions.

The number of dimensions in this approach is generally much lower than the sparse case, and the vector for any given document is dense, as most of its dimensions are populated by non-zero values.

In contrast to the sparse approach (for which tokenizers are used to generate sparse vectors directly from text input) the task of generating vectors must be handled in application logic external to Apache Solr.

There may be cases where it makes sense to directly search data that natively exists as a vector (e.g., scientific data); but in a text search context, it is likely that users will leverage deep learning models such as BERT to encode textual information as dense vectors, supplying the resulting vectors to Apache Solr explicitly at index and query time.

For additional information you can refer to this blog post.

Given a dense vector v that models the information need, the easiest approach for providing dense vector retrieval would be to calculate the distance (euclidean, dot product, etc.) between v and each vector d that represents a document in the corpus of information.

This approach is quite expensive, so many approximate strategies are currently under active research.

The strategy implemented in Apache Lucene and used by Apache Solr is based on Navigable Small-world graph.

It provides efficient approximate nearest neighbor search for high dimensional vectors.

See Approximate nearest neighbor algorithm based on navigable small world graphs (2014) and Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (2018) for details.

The dense vector field gives the possibility of indexing and searching dense vectors of float elements.

For example:

[1.0, 2.5, 3.7, 4.1]

Here’s how DenseVectorField should be configured in the schema:

To use the following advanced parameters that customise the codec format and the hyperparameter of the HNSW algorithm, make sure the Schema Codec Factory, is in use.

Here’s how DenseVectorField can be configured with the advanced hyperparameters:

Please note that the knnAlgorithm accepted values may change in future releases.

DenseVectorField supports the attributes: indexed, stored.

Here’s how a DenseVectorField should be indexed:

Because dense vectors can have a costly size, it may be worthwhile to use a technique called "quantization" which creates a compressed representation of the original vectors. This allows more of the index to be stored in faster memory at the cost of some precision.

This dense vector type uses a conversion that projects a 32 bit float precision feature down to an 8 bit int (or smaller) by linearly mapping the float range of each dimension down to evenly sized "buckets" of values that fit into an int. For example: with 8 bits we can store up to 256 discrete values, so a float dimension with values from 0.0 to 1.0 may be mapped as

[0.0, 0.0039) ⇒ 0, [0.0039, 0.0078) ⇒ 1 …​ etc

As a specific type of DenseVectorField, this field type supports all the same configurable properties outlined above as well as some additional ones.

Here is how a ScalarQuantizedDenseVectorField can be defined in the schema:

Binary quantization is a quantization technique that extends scalar quantization, and is even more aggressive in its compression; able to reduce in-memory representation of each vector dimension from a 32 bit float down to a single bit. This is done by normalizing each dimension of a vector relative to a centroid (mid-point pre-calculated against all vectors in the index) with the stored bit representing whether the actual value is "above" or "below" the centroid’s value. A further "corrective factor" is also computed and stored to help compensate accuracy in the estimated distance. At query time asymmetric quantization is applied to the query vector (reducing its dimension values down to 4 bits each), but allowing comparison with the stored binary quantized vector via bit arithmetic.

This implementation comprises of LVQ, proposed in Similarity Search in the Blink of an Eye With Compressed Indices by Cecilia Aguerrebere et al., previous work on globally optimized scalar quantization in Apache Lucene, and ideas from Accelerating Large-Scale Inference with Anisotropic Vector Quantization by Ruiqi Guo et al.

This vector type is best utilized for data sets consisting of large amounts of high dimensionality vectors.

Here is how a BinaryQuantizedDenseVectorField can be defined in the schema:

BinaryQuantizedDenseVectorField accepts the same parameters as DenseVectorField with the only notable exception being similarityFunction. Bit quantization uses its own distance calculation and so does not require nor use the similarityFunction param.

The knn k-nearest neighbors query parser matches k-nearest documents to the target vector.

In addition to the common parameters described above, it takes the following parameters:

Here’s an example of a simple knn search:

The search results retrieved are the k=10 nearest documents to the vector in input [1.0, 2.0, 3.0, 4.0], ranked by the similarityFunction configured at indexing time.

Here’s an example of a knn search using the early termination with input parameters:

Here is an example of a knn search using a seedQuery:

The search results retrieved are the k=10 nearest documents to the vector in input [1.0, 2.0, 3.0, 4.0]. Documents matching the query id:(1 4 10) are used as entry points for the ANN search. If no documents match the seed, Solr falls back to a regular knn search without seeding, starting instead from random entry points.

Here is an example of a knn search using a filteredSearchThreshold:

The knn_text_to_vector query parser encode a textual query to a vector using a dedicated Large Language Model(fine tuned for the task of encoding text to vector for sentence similarity) and matches k-nearest neighbours documents to such query vector.

In addition to the parameters in common with the other dense-retrieval query parsers, it takes the following:

Here’s an example of a simple knn_text_to_vector search:

The search results retrieved are the k=10 nearest documents to the vector encoded from the query hello world query, using the model a-model.

For more details on how to work with vectorise text in Apache Solr, please refer to the dedicated page: Text to Vector

The vectorSimilarity vector similarity query parser matches documents whose similarity with the target vector is a above a minimum threshold.

In addition to the common parameters described above, it takes the following parameters:

Here’s an example of a simple vectorSimilarity search:

The search results retrieved are all documents whose similarity with the input vector [1.0, 2.0, 3.0, 4.0] is at least 0.7 based on the similarityFunction configured at indexing time

Let’s see when to use each of the dense retrieval query parsers available:

Pre-Filtering the set of candidate documents considered when walking the graph can be specified either explicitly, or implicitly (based on existing fq params) depending on how and when these dense vector query parsers are used.

Both dense vector search query parsers can be used to rerank first pass query results:

Following is a complete example of setting up a collection with cuVS.