Pretrained Transformer Language Models for Search - Part 1: A Deep Dive into Retrieval and Vector Search

Pretrained Transformer Language Models for Search - Part 1: A Deep Dive into Retrieval and Vector Search

Introduction:

In the world of information retrieval and search algorithms, there are various techniques and models that have been developed to enhance the efficiency and accuracy of search results. Two popular approaches include lexical-based retrieval scoring functions like BM25 and vector search indexes. In this article, we will explore the concepts behind these approaches and how they can be utilized to improve search functionalities.

Lexical-based Retrieval Scoring Functions:

One widely used lexical-based retrieval scoring function is BM25. This function allows for sub-linear time retrieval by utilizing inverted indexes and dynamic pruning algorithms like WAND. By avoiding the exhaustive scoring of all documents that match the query terms, BM25 significantly speeds up the retrieval process. This technique is particularly useful in scenarios where there is a large corpus of documents to search through.

Dense Retrieval and Approximate Nearest Neighbor Search:

Another approach to search is dense retrieval, which involves representing documents as vectors in a high-dimensional space. One way to accelerate dense retrieval is by employing approximate nearest neighbor search. This can be achieved by indexing the document vector representations using techniques like HNSW graph indexing.

Building a Vector Search Index:

In a fascinating experiment, a simplified vector search index was built using just 200 lines of Rust code. The process involved randomly selecting two vectors, calculating their midpoint, and building a hyperplane that passes through the midpoint and is perpendicular to the line segment connecting the two vectors. The vectors were then classified as "above" or "below" the hyperplane, splitting them into two groups.

For each group, if the size exceeded a configurable parameter called the "maximum node size," the process was recursively applied to that group to build a subtree. If the size did not exceed the maximum node size, a single leaf node was created with the vectors or their unique ids. This randomized process continued until the leaf nodes contained no more than the maximum node size vectors.

The resulting tree structure allowed for efficient vector search, where internal nodes represented hyperplane definitions and the left and right subtrees contained vectors "below" and "above" the hyperplane, respectively. This approach demonstrates how simple yet powerful techniques can be utilized to build effective search indexes.

Connecting the Dots:

Although lexical-based retrieval scoring functions and vector search indexes may seem like distinct approaches, there are common points that can be identified. Both techniques aim to enhance the efficiency and accuracy of search by organizing and indexing documents or vectors in a way that enables faster retrieval.

Additionally, both approaches benefit from dynamic pruning and approximate search algorithms. Dynamic pruning, as seen in BM25, avoids scoring all documents by selectively targeting those that match the query terms. Approximate nearest neighbor search, on the other hand, helps accelerate dense retrieval by efficiently indexing the vector representations.

Actionable Advice:

1. Consider implementing a lexical-based retrieval scoring function like BM25 to improve search efficiency. By utilizing inverted indexes and dynamic pruning algorithms, you can significantly speed up the retrieval process.

2. Explore the possibilities of dense retrieval and approximate nearest neighbor search. By representing documents as vectors and utilizing techniques like HNSW graph indexing, you can achieve faster and more accurate search results.

3. Experiment with building a vector search index using simple yet effective techniques. By randomly selecting vectors, creating hyperplanes, and recursively splitting them based on a maximum node size, you can construct a powerful search index with minimal code.

Conclusion:

In this article, we delved into the concepts of lexical-based retrieval scoring functions and vector search indexes. We explored how lexical-based retrieval scoring functions like BM25 can improve search efficiency by leveraging inverted indexes and dynamic pruning algorithms. Additionally, we discovered how dense retrieval and approximate nearest neighbor search can be utilized to accelerate search using vector representations.

Furthermore, we examined a fascinating experiment where a vector search index was built using just 200 lines of Rust code. The process highlighted the power of simple techniques in constructing efficient search indexes.

By considering these approaches and implementing the actionable advice provided, you can enhance the search capabilities of your applications and systems. Whether it's through lexical-based retrieval scoring functions or vector search indexes, the goal remains the same: to provide users with faster and more accurate search results.