This first blog post in a series of two on hybrid search discusses
first retrievers in a ranking pipeline, where the first retriever
phase aims to find reasonably good candidates for a query under
a limited computing budget to allow scaling the retrieval phase
to large collections of documents without incurring high costs.
Introduction
Representational approaches in information retrieval involve
converting queries and documents into structured forms, like vectors,
to make retrieval more efficient. Representational approaches allow querying collections of
documents without having to score all documents for a query.
Query and document representations for information retrieval come
in two main types: sparse and dense. For both methods, we can distinguish
between unsupervised and supervised representations.
In other words, the representations of queries and documents could
be learned using supervision or unsupervised by using corpus
statistics.
Let’s pause for a moment to underscore the distinction between
the retrieval and ranking phases. Many developers, accustomed to
working with technologies that offer minimal support for phased
ranking, might
instinctively view this through the lens of systems where retrieval
and ranking are implemented by distinct services. In such systems,
there’s often a separation of technologies, with retrieval handled
by a subsystem—like Apache Solr or Elasticsearch—and ranking primarily
executed within a dedicated ‘ranker’ system that re-ranks a shallow
pool of candidates retrieved by the retriever subsystem.
Unlike systems characterized by discrete retrieval and ranking
technologies, Vespa has rich support for both retrieval and phased
ranking. In Vespa,
the retrieval phase is expressed with the Vespa query language,
using top-k scoring query operators (e.g
nearestNeighbor,
wand).
These operators, with the help of index structures, accelerate the
search for the top-k scoring documents without having to score all
documents in the collection.
Let us illustrate top-k scoring operators with an example from the
database world. Imagine that we have a table products and we want
to find the top-100 most popular products using the following SQL
query:
SELECT * FROM products ORDER BY popularity DESC LIMIT 100;
If we haven’t specified any index on the popularity column, the
above query would likely entail a linear table scan over all the
rows in the products table, followed by a sort operation, and finally, returning the top-100 products sorted by descending popularity.
A simplistic index implementation to speed up such top-k queries,
avoiding reading the popularity value of all the rows, would be to
maintain a sorted data structure with all the unique popularity
values with a pointer to the row ID. Then, at query time, we could
traverse this sorted data structure, starting at the largest
value and traversing it until we have found 100 products. This
illustrates a basic form of efficient top-k retrieval. Things get
more complex as you introduce additional filters to the query and
begin ranking documents based on user-specified information, typically
expressed as a free-text query.
In the following sections, we discuss representational approaches
in information retrieval that involve converting queries and documents
into structured forms, like vectors, to make retrieval (top-k search)
more efficient, allowing querying collections of billions of documents
without scoring all documents for a query.
Sparse representations and retrieval
With sparse representations, documents and queries are represented
as sparse vectors with up to |V| dimensions, where V is the vocabulary
(unique terms in the corpus). Only dimensions (terms) that
have a non-zero weight impact the score.
A popular unsupervised scoring function using sparse representations
is BM25. BM25 can
be expressed as a dot product between the query terms weights and
the document term weights. The term weights are assigned by using
document collection statistics such as inverse document frequency
and term frequency. The BM25 scoring function does not take into
account the order of the terms in the text. Put simply; a document
or a query is represented as a “bag of terms”. BM25 offers the
advantage of easily applying it to your document collection, providing
a decent baseline for text search without any labeled
data.
During index building, it analyzes the corpus to determine term
occurrences and calculates term statistics, such as term frequency
and document frequency. The drawback, however, is its vulnerability
to vocabulary mismatch—if the query uses different terms than those
in the document, retrieval may fail.
Another less dated example of a sparse representational model is
SPLADE (Sparse Lexical and Expansion Model for Information
Retrieval). SPLADE can, given labeled data of the form (query,
relevant document, irrelevant document) learn sparse representations
of documents and queries that optimizes in-domain search ranking
performance.
Compared to BM25, SPLADE representations of both queries and
documents are denser, as queries and documents are expanded with
terms. In addition to more non-zero dimensions, the term weights
are contextualized by other terms in the text within the context
length limitation of the Transformer model that SPLADE uses. As
with BM25, the scoring function of SPLADE is expressed as a dot
product between the non-zero query and document terms.
Top-k retrieval for both mentioned sparse representational methods
can be done in (potential) sub-linear time using inverted indices.
The search for the top-k ranked documents can be accelerated by
dynamic pruning algorithms like
WAND. Dynamic
pruning retrieval algorithms attempt to avoid exhaustively scoring
all documents (linear complexity) that match at least one of the
terms in the query.
The effectiveness of dynamic pruning algorithms for top-k scoring,
as opposed to exhaustive scoring, depends on factors such as k,
sparseness (number of non-zero terms), and the distributions of
term weights. In the case of learned sparse expansion models like
SPLADE, the efficiency of result pruning is influenced by both the
density and wacky weights.
This negative serving performance observation might be unexpected, given
that many have advocated for sparse expansion models based on their
perceived simplicity in utilizing inverted index structures.
Acceleration of sparse top-k retrieval, using dynamic pruning
algorithms like WAND, is the magic sauce of search engine
implementations. Implementing a BM25 scoring function for a query
and document pair is trivial, while implementing top-k pruning
algorithms to avoid exhaustively scoring all documents is not. This
means that technologies that advertise support for sparse vector
representations might not dislodge mature search
engines.
Sparse retrieval in Vespa
There are two WAND algorithm implementations for sublinear top-k
retrieval in Vespa that are useful for retrieval models using
sparse representations:
weakAnd
The
weakAnd()
query operator which fully integrates with language-dependent
linguistic processing of text. This operator does not require much
thinking, define a string field in the Vespa schema, feed the
documents, and issue queries:
{
"query": "what was the manhattan project?",
"yql": "select * from sources * where userQuery()"
}
This is a handy
beginning for
developers. They can easily set up a solid text ranking baseline
for their data without delving into Vespa’s inner workings. Vespa
speeds up the query with the WAND algorithm, skipping the need to
score every matching document in the corpus. It’s worth noting that
for certain cases with smaller document collections (a few million
documents), scoring all documents is doable within 100 milliseconds
on modern hardware, using multithreaded query
execution,
without attempting to prune the result.
wand
The wand()
Vespa
query operator is useful for retrieval using sparse learned
representations of documents and queries, beyond text search use
cases. The wand implementation in Vespa was primarily developed for
efficient retrieval for recommendation use
cases,
using interaction data to learn sparse representations of users and
items for large-scale recommendation use cases and where the wand
operator is used for efficient candidate retrieval.
The developer controls the vocabulary (number of unique dimensions
or “terms”), and where the query and document weights of each
dimension is provided using integer precision. That means, that if
the sparse representational model uses float, the float weights
must be scaled to integer representations to be used with the wand
query operator.
Take SPLADE, for instance, it uses a vocabulary of around 30K words
using the English BERT language model wordpiece tokenizer. Instead
of using the actual words or subword string representation, you can
use subword vocabulary identifiers that fit into the signed int
type in Vespa. For instance, the phrase “what was the manhattan
project” can be represented by the corresponding wordpiece token
identifiers such as 2054, 2001, 1996, 7128, 2622.
Their term weights are assigned by the sparse representational
model. In Vespa, sparse learned representations for top-k retrieval
with the wand query operator, are best expressed using a schema
field of the type
weightedset
schema doc {
field sparse_rep type weightedset<int> {
indexing: summary | attribute
attribute: fast-search
}
}
In ranking phases, one can also use Vespa’s tensors
support, using a
mapped tensor to represent the sparse representation, but this post
focuses on using sparse representations for efficient top-k retrieval,
where we have to currently use integer precision weights.
Then using the model (and converted to integer weights), feed
documents to Vespa:
{
"id": "id:namespace..::doc",
"fields": {
"sparse_rep": {
"2054": 12,
"2001": 9,
"1996": 7,
"7128":34,
"2622": 53
}
}
}
One can then query the sparse representation using the wand query
operator:
{
"yql": "select * from sources * where ({targetHits:100}wand(sparse_rep,@sparse_query_rep))",
"sparse_query_rep": "{2622:45, 7128:23}"
}
Dense representations and retrieval
With dense representations, queries and documents are embedded into
a latent low-dimensional dense vector space where most dimensions
have a non-zero weight.
Scoring a document for a query can be done by a vector similarity
function such as cosine or a dot product. Dense vector text
representations are commonly referred to as text embeddings and
similar to SPLADE, require inference with a Transformer-based
language model for both queries and documents.
Dense representations using language models require in-domain
training data (supervised in the same way as other supervised
retrieval models) or hoping that an off-the-shelf embedding
model transfers to your data in a zero-shot
setting.
Retrieval over dense representations is accelerated by approximate
nearest neighbor search algorithms, for example indexing the document
vector(s)
representations using HNSW indexing.
In addition to single-vector representations, there are also multi-vector
representations of text, which represents a text using multiple
term vectors. Take
ColBERT
for instance, it learns contextual term vector embeddings, and where
scoring uses a multi-vector similarity expression.
Dense retrieval in Vespa
An important difference between needing to perform efficient retrieval
over dense representations and ranking is that the latter does not
require building data structures for fast but approximate nearest
neighbor search.
It’s possible in Vespa to retrieve using a sparse representation
using inverted indices, accelerated by any of the mentioned sparse
retrieval methods, and use dense representational models during
ranking phases.
Such approaches are attractive as they eliminate the need for
HNSW data
structures to facilitate fast dense retrieval, which can be a
significant cost driver for real-time indexing in large-scale
production deployments. This is also true for retrieval and ranking
models that use several dense representational models, adding
HNSW indexes to dense representations that are only used in ranking
phases is a fruitless waste of computing and storage.
The following example defines two document embedding fields where
only the first has an HNSW index enabled (controlled by the index switch).
schema doc {
document doc {
field body type array<string> {..}
field llm_summary type string {..}
}
field embedding1 type tensor<bfloat16>(p{}, x[384]) {
indexing: input body | embed model-1 | attribute | index
}
field embedding2 type tensor<bfloat16>(x[768]) {
indexing: input llm_summary | embed model-2 | attribute
}
}
For this type of schema, we can effectively retrieve over the
embedding1 field with an HNSW index while using embedding2 in
ranking phases without incurring the overhead of the HNSW indexing
embedding2 field. Details on representing text embedding models in
Vespa are found in embedding
documentation.
{
"yql": "select * from sources * where {targetHits:100}nearestNeighbor(embedding1, q1)",
"input.query(q1)": "embed(model-1, \"the query\")",
"input.query(q2)": "embed(model-2, \"the query\")"
}
In the above Vespa query example, we retrieve efficiently over the
embedding1 field with HNSW enabled using the nearestNeighbor query
operator. In addition, we run inference with model-2 to produce
another query vector representation that can be used during Vespa
ranking phases.
Enabling the combination of sparse and dense representations in the
same query enhances the flexibility of the way we can implement
hybrid search. This flexibility helps manage trade-offs involving
indexing speed, resource usage, and query performance. For instance,
the HNSW graph algorithm relies on accessing document vectors during
both query and ingest times.
This implies that, for optimal performance, the vectors must be
stored in memory. However, if vector similarity is not utilized
for top-k retrieval, the vector data can be paged from disk during
ranking phases, because during the ranking phases, we have significantly
less random accesses to vector data.
With Vespa, developers can use the Vespa paged attribute
option that
allows the system to page the tensor data from disk as needed during
ranking.
field embedding2 type tensor<bfloat16>(x[768]) {
indexing: input text | embed model-2 | attribute
attribute: paged
}
Vectors or tensors in general, can easily have a large footprint
per document (above uses 1536 bytes per document). Moving large
amounts of vector data across the network for re-ranking will quickly
saturate network capacity for smaller instance types. With Vespa,
developers can express that the similarity calculations should happen where the data is stored, eliminating the network
throughput scaling bottlenecks.
There is also increasing interest in using sparse representation
models for retrieval, and use semantic (or dense) models for
re-ranking. In Lexically Accelerated Dense Retrieval
(LADR), the authors propose an
interesting approach that combines lexical (sparse) retrieval with
re-ranking using a dense model. LADR uses a two-phase retrieval
process, first retrieving a set of candidate documents using lexical
(sparse) retrieval, for example, BM25. The retrieved documents seed
an exploration of a proximity graph formed by documents to document
similarities. The candidates retrieved by the initial phase and
those discovered through the graph traversal are scored (query,
document) with the semantic (dense representational) ranking model.
Interestingly enough, this approach lifts precision ranking metrics
like nDCG@10 compared to best-case exhaustive dense similarity
search because the initial sparse phase targets exact keyword matches.
Hybrid Retrieval in Vespa
Research indicates that combining dense and sparse methods could
improve the overall ranking effectiveness. The classic hybrid
retrieval approach combines dense and sparse retrieval but requires
technology that supports both retrieval types. Vespa supports
hybrid retrieval, expressed in the same query by combining the
sparse wand and dense nearestNeighbor query operators in the same
query.
There are multiple useful ways to combine these two dynamic pruning
algorithms in the Vespa Query Language for efficient top-k retrieval:
Disjunction (OR)
With disjunction, we can express retrieval using sparse and
dense top-k retrieval algorithms in the same query. The retrieved
hits (potential disjoint set of candidates) are then exposed into
the Vespa ranking phases.
{
"yql": "select * from sources * where ({targetHits:100}nearestNeighbor(embedding1, q1)) or userQuery()",
"query": "the query",
"input.query(q1)": "embed(model-1, \"the query\")"
}
In this example, we ask Vespa to expose 100 (per node involved in
the query) to ranking phases using the nearestNeighbor query operator
or the best lexical matches using the weakAnd query operator.
How these candiates are scored and ranking is determined by the Vespa ranking phases.
One can also use multiple nearestNeighbor search
operators
in the same query request.
RANK ()
The Vespa
rank()
query operator allows retrieval using the first operand and allows
matching features calculated for those documents retrieved by the
first operand using the other operands.
{
"yql": "select * from sources * where rank(({targetHits:100}nearestNeighbor(embedding1, q1)), userQuery())",
"query": "the query",
"input.query(q1)": "embed(model-1, \"the query\")",
}
In the above example, Vespa uses dense retrieval to retrieve top-100 hits into
ranking phases, but at the same time, allows the calculation of sparse
matching features for the best semantic matching documents
The following inverts the above logic. Instead of dense first, it performs sparse retrieval using weakAnd, then uses the dense model for ranking.
This way of querying Vespa does not benefit performance-wise with an HNSW index because the top-k retrieval uses the lexical weakAnd operator.
{
"yql": "select * from sources * where rank(userQuery(), ({targetHits:100}nearestNeighbor(embedding1, q1)))",
"query": "the query",
"input.query(q1)": "embed(model-1, \"the query\")",
}
Both query operators can be combined with the flexibility of
the Vespa query language, for example, constraining the search by
filters. Similarly, one can combine weakAnd with wand in the same
query, or combine all three mentioned query operators.
The Vespa rank() query operator accepts an arbitrary number of operands, but only
the first one is used for top-k retrieval.
Summary
In this post, we explored representational approaches in information
retrieval, focusing on sparse and dense representations for queries
and documents. We made a clear distinction between efficient retrieval
and ranking, without going into details on how to combine different
dense and sparse signals in the ranking phases. That is the topic for the upcoming blog post in this series,
where we will look at how to combine sparse and dense ranking signals for hybrid ranking practically.
