Erkang (Eric) Zhu

Two Claudes

2026-01-08T17:25:17+00:00

Left: Portrait of Claude Monet by Nadar, 1899 (public domain). Right: Photo of Claude Shannon from Mathematisches Forschungsinstitut Oberwolfach (CC BY-SA 2.0 DE).

Claude Monet painted the same haystack over and over — at dawn, at dusk, in snow, in summer. He started late in the year of 1890 and kept going for seven months, producing around 25 canvases of the same grain stacks sitting in a field near his house in Giverny.

A mosaic of six paintings from Claude Monet’s celebrated Haystacks series (1884–1891). All images are in the public domain, courtesy of Wikimedia Commons.

He didn’t work from first principles. He just painted. When he noticed how quickly the light was changing, he had his stepdaughter wheel out more canvases via wheelbarrow. The theoretical framework for what he’d accomplished came mostly from critics who looked at the work after.

Claude Shannon is an analytical thinker. In 1948, he published “A Mathematical Theory of Communication,” which created the field of information theory. Where Monet captured light empirically, Shannon captured information mathematically. His entropy formula describes the principles of data compression. Every digital system we use today rests on foundations he laid.

Both Claudes changed their fields. But they represent two different ways of advancing knowledge.

Anthropic named their AI assistant Claude after Shannon — the theorist, the one who built frameworks. I wonder if Monet would have been just as fitting. We’re in an era where the tinkerer’s instinct matters more than the theorist’s rigor.

The era of tinkering

Large language models work, impressively well, before anyone fully understands why. The scaling laws that govern them were discovered by running experiments, not deriving theorems. Building effective AI systems today is less about understanding the model’s internals and more about constructing the right scaffolding around it — agent architectures that manage context, tool integrations, coding environments that let the model act on the world. Practitioners develop intuition through building, figuring out what works through trial and error. The theoretical explanation came after, and it’s still incomplete.

This pattern isn’t new. Steam engines powered the Industrial Revolution for decades before thermodynamics explained why they worked. Edison electrified cities through trial and error, not by applying Maxwell’s equations. Theory often follows practice, sometimes by a generation.

What’s different now is the infrastructure. GPUs have gotten dramatically better for AI workloads, and many ideas can now be tested locally on devices like the Nvidia DGX Spark or through API services like Modal and Tinker. GitHub lets you fork someone’s idea and extend it. AI coding assistants compress the time from concept to prototype. The feedback loop between “what if?” and “let’s see” has never been shorter.

The permission problem

A lot of people feel they need permission to build. They want to understand the theory behind systems before trying it themselves. They want to read the papers and understand the math before getting their hands dirty. They feel like impostors using techniques they can’t completely explain.

I think this is backwards. Understanding is a side effect of building, not a prerequisite for it.

Monet didn’t paint 25 haystacks after understanding the physics of light. He was curious and wanted to experiment. The understanding accumulated through repetition, through noticing what worked and what didn’t — empirical knowledge that no amount of studying could have provided.

What makes good tinkering

Tinkering without any feedback is just flailing. The difference between productive experimentation and wasted motion comes down to a few things.

Iteration matters. Monet painted many times. When a canvas wasn’t working, he moved on. He was willing to keep trying.

Taste matters too, but taste isn’t something you arrive with. It comes from extensive, repeated tinkering with real feedback — user signals, system performance metrics, the gap between what you expected and what actually happened. You develop an internal compass for what “good” looks like by building things and watching how they perform. There’s no shortcut.

And there’s a willingness to tackle hard problems without waiting for permission from domain experts. Tinkerers don’t ask whether something is in their wheelhouse. They just try it. Sometimes they fail, but often they discover the problem wasn’t as hard as the gatekeepers thought.

My own path

I learned this through experience. In university, I built websites, games, social media apps — not for credit, just to see what different frameworks felt like. My program taught C and C++. I taught myself Python, Go, JavaScript, Erlang.

In graduate school I worked on database research. The expected output was publications, theoretical contributions. But I still tinkered. I implemented system designs from scratch to understand them. My datasketch library started as an experiment with the most efficient way to compute MinHash using Numpy. Tinkering inside an institution that valued theory, but tinkering nonetheless.

This has served me well in the LLM era. The field rewards people who build. Understanding follows.

Theory will return

I’m not dismissing theory. Shannon’s framework was transformative — it gave us the foundation. The theorists will come back. They’ll use tools built by tinkerers to formalize what we already understand practically. They’ll identify the limits we’ve been bumping against and unlock the next level.

But that’s not the job of today. Today is for building.

If you’ve been waiting for permission, waiting to understand before you build, just pick up the brush.

Please Use Streaming Workload to Benchmark Vector Databases

2023-12-01T21:43:33+00:00

Image by DALLE-3

Vector databases are built for high-dimensional vector retrieval. Today, many vectors are embeddings generated by deep neural nets like GPTs and CLIP to represent data points such as pieces of text, images, or audio tracks. Embeddings are used in many applications like search engines, recommendation systems, and chatbots. You can index embeddings in a vector database, which uses an Approximate Nearest Neighbor (ANN) index to supports fast retrieval of top neighbors by a distance function like Cosine or Euclidian. Latency is 2 to 10 milliseconds for a 1 million vectors index, and scales sub-linearly (i.e., O(log n)) with respect to index size.

In this post, I point to several problems with the way we currently evaluate ANN indexes and suggest a new type of evaluation. This post focuses on ANN indexes for embedding vectors, an area that is getting a lot of attention recently: vector database startups like Pinecone, Zilliz, Qdrant, and Weaviate offer embedding indexing and retrieval as their core service.

1. Static workload benchmark is insufficient.

The standard way to evaluate ANN indexes is to use a static workload benchmark, which consists of a fixed dataset and a fixed query set.

A static workload benchmark. Image by the author.

A static workload benchmark first builds the ANN index from the fixed dataset, and then runs the fixed query set several times with different parameter settings and measures the highest achievable query throughput at each minimum accuracy level. After performing the same procedure for each ANN index, the benchmark generates a plot like the one below:

Figure from ANN Benchmarks (11/25/2023). MIT Licence.

The plot above compares different ANN indexes using a static workload called glove-100-angular, which contains embeddings of words.

This evaluation approach was popularized by the ann-benchmarks project which started 5 years ago. Many vector databases are now measuring their performance using this approach in their tech blogs. See the Qdrant benchmark and Timescale benchmark.

Static workload benchmark has been useful because the result is easy to understand and allows us to compare the accuracy and query performance trade-off across different indexing algorithms using a same plot.

Except it is not nearly a complete evaluation of ANN indexes, and you should not choose ANN index for your project based only on this. It overly stresses on recall accuracy and query performance while skipping other important aspects like indexing performance and memory usage.

Indexing performance should be reflected.

Indexing throughput measures how fast the ANN index can accept new data points. Similar to query throughput, it is typically inversely correlated to recall accuracy. For example, the plot below shows the relationship between indexing throughput and recall of HNSWLIB and DiskANN Vamana indexes.

Recall vs. Indexing Throughput of HNSWLIB and DiskANN Vamana on OpenAI 1M. Image by the author.

This plot is similar to the previous Recall-QPS plot, but from this plot you can see that higher recall is also a tradeoff of index performance. However, if I am interested in both indexing and query performance, this plot is still insufficient because it does not show the margin of which the recall-performance tradeoff is being made, as the static benchmark segregates indexing and querying workloads.

Many ANN indexes support bulk indexing API which can be much more optimized than point indexing (i.e., add vectors one at a time) and can create a more accurate index. For example, cluster-based ANN indexes build clusters of all vectors in batch. The static workload benchmark separates indexing and query workloads, so it encourages bulk indexing which may not be realistic.

One more issue related to indexing is product quantization (PQ). Many ANN indexes use PQ or other forms of vector compression to speed up compute. The static workload benchmark allows ANN indexes to build optimized compression codebook before the query phase starts, but such optimal codebook may not be achievable in practice.

Memory usage matters.

Most of the popular ANN indexes are in-memory, meaning their main data structure stays in volatile storage (DRAM) from which queries are served. Therefore, it is important to measure memory efficiency and its tradeoff with performance and recall accuracy. For example, in this research paper, the authors measured the memory usage of HNSW with 1 billion points to be 490 GB, while NSG is 303 GB, but on the recall and query performance side HNSW only slightly dominates NSG. This kind of trade-off should be front-and-center when it comes to benchmarking ANN indexes.

Still, it is difficult get a realistic picture of memory efficiency with only static benchmark for several reasons. For one, the ANN index algorithm can create a read-optimized index that is very compact at the expensive of subsequent indexing performance. For another, the workload only captures pure indexing or pure query but not a mix of both, which is more likely to happen in a real scenario like Q&A engine or chatbot when new data arrives constantly.

Data distribution shifts over time.

In static benchmark, the data and query sets are unchanged. This is not realistic as data and queries are driven by end users’ interest which changes over time. If the data and query sets are always fixed, then the best index is a cache that memorizes every query result. Recently, research in ANN indexes (e.g., FreshDiskANN) have started to measure out-of-distribution query performance — it is a right step forward.

What about deletes?

Delete API has become standard for ANN indexes, but no static benchmark is measuring this. Being able to handle deletes is important as the emerging AI-related application scenarios like chatbot are using ANN index as an operational storage that resembles online transaction processing (OLTP) databases, as data is constantly being added and modified.

2. Streaming workload tells you a lot more.

If an ANN index supports the following APIs:

Insert(ID, vector)
Query(vector)
Delete(ID)

and if the usage scenario is anything but static data and queries (like, every scenario?), then a streaming workload benchmark can give you more insight into the characteristics of ANN indexes and how well they perform for your specific usage scenario.

A streaming workload benchmark consists of two streams: a data stream that corresponds to a sequence of Insert and Delete API calls, and a query stream for a sequence of Query API calls. It can be realized using an actual streaming system like Kafka, or more simply using a runbook with sequences of pointers to a data set and a query set similar to those used by a static benchmark.

A simple streaming workload benchmark that uses a runbook. Image by the author.

The above diagram illustrates the streaming workload benchmark used in the NeurIPS 23’ Big ANN Benchmarks. Specifically, each step in the runbook corresponds to a batch of vectors, so the operations can be executed in parallel. This approach has the following benefits:

Flexibility: workload patterns and data distribution shifts can be modelled as different streaming workloads which then get compiled to different runbooks.
Realistic: indexing and query are interleaved so the ANN index must accommodate future insertions. Besides, the memory profile more accurately reflects real workload.
Simple analysis: performance can be described using overall throughput rather than indexing vs. query throughputs, so the tradeoff between recall and performance can be visualized easily.
Completeness: insert and delete operations are also evaluated.

In this blog post, I deep dive into (4) above and show you a new insight I discovered using a streaming workload benchmark.

Compare recall stability: HNSW vs. Vamana

When running a streaming workload benchmark, an important metric we collect is the recall of each query operation. We can compare different index setups (parameters, algorithms, etc.) by looking at their recall stability over time, and decide which index is suitable for a given usage scenario.

I measured the recall stability of DiskANN’s Vamana and various HNSW implementations under the streaming workload defined by the final runbook in the NeurIPS 23’ Big ANN Benchmarks.

Some background on Vamana and HNSW: they are both graph ANN indexes, and they are particularly good at handling embeddings. In a graph ANN index, each vector is a node, and query is executed as graph traversal. Directed edges are selectively constructed to limit memory usage while guaranteeing fast traversal from any node to any node. During in-place delete, for each in-coming neighbor node of a deleted node, graph ANN indexes perform edge repair to maintain the directed graph structure.

The first HNSW implementation we use is one based on HNSWLIB, with added Delete API implemented using a repair algorithm called repairConnectionsForUpdate, which is already part of HNSWLIB’s source code. The idea is to perform a “re-insert” of the node to be repaired and update its out-going neighbors at all levels. The figure blow shows the recall over time for both Vamana and HNSW.

Recall stability of DiskANN’s Vamana and an HNSW implementation based on HNSWLIB. Delete API calls are marked as “X”s. Image by the author.

Note that I set Vamana’s maximum degree parameter to 40 (R = 40) and HNSW’s base layer’s maximum degree also to 40 (M = 20, M0 = 40). So, they should use more-or-less the same memory.

It is clear from this plot that deletes have an adverse effect on recall, as recall monotonically decreases during consecutive deletes. In comparison, HNSW is much more affected by deletes than Vamana.

The second HNSW implementation we use replaces HNSWLIB’s edge repair algorithm with Vamana’s, which is quite different. The idea behind Vamana’s edge repair algorithm is to connect each in-coming neighbor of a deleted node to the out-going neighbors of the deleted node, while applying a pruning step to maintain a maximum degree constraint. In this case, we use HNSW’s original pruning algorithm. It is implemented by HNSWLIB in a function called getNeighborsByHeuristic2.

Recall stability of DiskANN’s Vamana and an HNSW implementation using Vamana’s edge repair algorithm to handle deletion. Image by the author.

With all parameters staying the same, changing HNSWLIB’s edge repair algorithm to Vamana’s immediately improved HNSW’s recall stability.

Let’s go an extra mile and change the HNSW’s edge pruning algorithm to Vamana’s. Now the HNSW index is nearly the same as Vamana’s, except that it has multiple layers. We call this index “Multi-layer Vamana”.

Recall stability of DiskANN’s Vamana and an HNSW implementation using Vamana’s edge repair and pruning algorithms — “multi-layer Vamana”. Image by the author.

You can see HNSW’s recall is now slightly higher than Vamana’s while using a similar amount of memory. I haven’t found this is observation in any research paper anywhere. Moreover, while performance is not in the figure, I noticed significant slowdown when switching to Vamana’s pruning algorithm.

In conclusion, by using the streaming workload benchmark, I was able to discover something new about different edge repair and pruning algorithms. A logical next step would be to look into the performance implications of these algorithms, and I can do this using the streaming workload benchmark.

3. Conclusion

To summarize, in this blog post, I pointed out that static workload benchmarks are insufficient for realistic evaluation of ANN indexes, and I described streaming workload benchmark which I think is a better replacement. I also used a specific streaming workload to uncover a new comparison between HNSW and Vamana indexes. Kudos to the team behind the NeurIPS 23’ Big ANN Benchmarks! They have open sourced the streaming workload I used in this blog post.

We need a TPC-C and TPC-H for vector databases.

There is still a lot of work to be done in benchmarking. ANN index is the core feature of vector databases, and they have raised over 350 million dollars. Yet many of them are still measuring performance using an outdated approach that no longer reflect actual usage scenarios. Database systems underwent a similar stage in the 90s and early 2000s. Then, standard benchmarks like TPC-C and TPC-H were developed and are still used today. We should have something like this for vector databases.

Finding Needles in a Haystack — Search Indexes for Jaccard Similarity

2023-08-18T06:07:40+00:00

Finding Needles in a Haystack. Image by the author using Midjourney.

Vector databases are in the news for being the external memory of large language models (LLMs). The vector databases today are new systems built on decade-old research called approximate nearest neighbor (ANN) indexes. These indexing algorithms takes many high-dimensional vectors (e.g., float32[]), and built a data structure that supports finding the approximate neighbors of a query vector in the high-dimensional space. It is like Google Map finds your neighbors’ houses given your house’s latitude and longitude, except the ANN indexes operate in a much higher dimensional space.

This line of research has a history that dates back decades. In the late 90s, ML researchers were hand-crafting numerical features for multimedia data such as image and audio. Similarity search based on these feature vectors became a natural problem. For a while, researchers crowded this area. This academic bubble broke when a seminal paper, When is “Nearest Neighbor” Meaningful?, basically told everyone stop wasting time because nearest neighbor in high-dimensional space of hand-crafted features is mostly not meaningful — an interesting topic for another post. Still to this day, I keep seeing research papers and vector database benchmarks publishing performance numbers on the SIFT-128 dataset, which consists of exactly the hand-crafted feature vectors with meaningless similarity.

Despite the noise around hand-crafted features, there has been a fruitful line of research focusing on one high-dimensional data type with meaningful similarity: set and Jaccard.

In this post I cover search indexes for Jaccard similarity over sets. I will start with the basic concepts, and then move on to exact and approximate indexes.

Set and Jaccard

A set is just a collection of distinct elements. The songs you liked on Spotify is a set; the tweets your retweeted last week is a set; and the distinct tokens extracted from this blog post also form a set. Set is a natural way to represent data points in application scenarios like music recommendation, social network, and plagiarism detection.

Let’s say on Spotify, I follow these artists:

[the weekend, taylor swift, wasia project]

and my daughter follows these artists:

[the weekend, miley cyrus, sza]

A reasonable way to measure the similarity of our music tastes is to see how many artists we both follow — the intersection size. In this case we both follow the weekend, so the intersection size is 1.

Each set represents a user’s following list. The intersection shows the common followings shared by both users. Image by the author.

However, you could imagine another pair of users each follows 100 artists, and the intersection size is also 1, but the similarity in their tastes should be much smaller than the similarity between my daughter’s and mine. To make the measurement comparable across different pairs of users, we normalize the intersection size with the union size. This way, the similarity between my daughter’s and my followings is 1 / 5 = 0.2, and the similarity between the other pair of users’ followings is 1 / 199 ~= 0.005. This is called Jaccard similarity.

For a set A and a set B, the formula for Jaccard similarity is:

Jaccard similarity formula for set A and B.

Why is set a high-dimensional data type? A set can be encoded as a “one-hot” vector, whose dimensions 1-to-1 map to all possible elements (e.g., all artists on Spotify). A dimension in this vector has a value of 1 if the set contains the element corresponding to this dimension, and 0 otherwise. So, the vectorized set of my followed artists look like the following:

High-dimensional vector representation of the set of followings. Image by the author.

where the second, third, and the third from the last dimensions are the weekend, taylor swift, and wasia project. There are over 10 million artists on Spotify, so a vector like this is extremely high dimensional and very sparse — most dimensions are 0s.

Inverted Indexes for Jaccard Search

People want to find things quickly, so computer scientists invented data structures called indexes to make search performance satisfactory for software applications. Specifically, a Jaccard search index is built on a collection of sets, given a query set, it returns k sets that have the highest Jaccard with the query set.

Search index for Jaccard is based on a data structure called inverted index. An inverted index has an extremely simple interface: input a set element, say the weekend, it returns a list of IDs of sets that contain the input element, e.g., [ 32, 231, 432, 1322, ...]. The inverted index is essentially a lookup table whose keys are all possible set elements, and values are lists of set IDs. In this example, each list in the inverted index represents the IDs of the followers of an artist.

Inverted index contains lists of set IDs matching the query set. Image by the author.

Original sets are stored in a separate table for lookup by their set IDs. Image by the author.

You can see the reason why this is called “inverted index”: it allows you to go from a set element to find sets that contain the element.

Exact Search Algorithm

Inverted index is incredibly powerful data structure for speeding up search. Using inverted index, when search, instead of going through all the sets and compare each with the query set — very expensive if you have millions of sets, you only need to process the IDs of the sets that share at least one element with the query set. You can obtain the set IDs directly from the inverted index lists.

This idea is implemented by the following search algorithm:

def search_top_k_merge_list(index, sets, q, k):
    """Search top-k Jaccard using inverted index.

    Args:
        index: an inverted index, key is set element
        sets: a lookup table for sets, key is set ID
        q: a query set
        k: search parameter k

    Returns:
        list: at most k set IDs.
    """
    # Intialize an empty lookup table for candidates.
    candidates = defaultdict(0)

    # Iterate over set elements in q.
    for x in q:
        ids = index[x]  # Get a list of set IDs from the index.
        for id in ids:
            candidates[id] += 1  # Increment count for intersection size.

    # Now candidates[id] stores the intersection size of set with ID id.

    # A simple routine for calculating Jaccard using intersection size and
    # set sizes, based on Inclusion-Exclusion principle.
    jaccard = lambda id: candidates[id] / (len(q) + len(sets(id) - candidates[id]))

    # Find the top-k candidates order by Jaccard.
    return sorted(list(candidates.keys()), key=jaccard, reverse=True)[:k]

In plain English, the algorithm walks through every inverted index list matched by elements in the query set and uses a candidate table to keep track of the number of times each set ID appears. If a set ID appears n times, the indexed set has n overlapping elements with the query set. In the end, the algorithm uses all the information in the candidate table to calculate Jaccard similarities, and then returns the IDs of the top-k most similar sets.

The candidate table in the search_top_k_merge_list algorithm is used to keep track of the overlap counts of indexed sets found through the inverted index.

The search_top_k_merge_list algorithm can be fast when: (1) the number of elements in the query set is small and (2) the number of IDs in the inverted index lists for the query elements are small. In the Spotify scenario, this could be the case if most people follow a few artists (likely true) and all artists have more-or-less the same number of followers (not true). We all know it is a fact that a few top artists are followed by most people and most artists have few followers. After all, the music industry follows the Pareto Distribution.

Taylor Swift has 78 million followers on Spotify, and The Weekend has 67 million. Having them on my following list means the search_top_k_merge_list algorithm will need to walk through at least 145 million set IDs and the candidate table candidates will grow to this astronomical size. Despite the fact that computers today are fast and powerful, on my Intel i7 machine, creating a table of this size still takes at least 30 seconds (Python) and dynamically allocates 2.5 GB of memory.

Most people follow some of these super star artists. So, if you use this algorithm in your search application, you will for sure get a gargantuan cloud hosting bill for large resource usage and terrible user experience for high search latency.

Branch and Bound Optimization

Intuitively, the previous algorithm search_top_k_merge_list processes all potential candidates in a breadth-first fashion because it only uses the inverted index to compute intersection. This algorithm performs poorly due to super star artists with millions of followers.

Another approach is to be more selective about potential candidates. Imagine interviewing candidates for a job and you are the hiring manager. You cannot afford to interview all potential candidates who send you CVs, so you sort the candidates into buckets based on your job criteria and start interviewing candidates who hit the criteria your care about the most. As you are interviewing them one by one you evaluate whether each one actually hit all or most of your criteria and stop interviewing when you found someone.

This approach also works when it comes to finding similar sets of followed artists. The idea is that you want to start from the artist with the least number of followers in your query set. Why? Simply because those artists give you fewer candidate sets to work with, so that you can process less lists of artists from the inverted index and find your best k candidates more quickly. In my Spotify’s following list, wasian project only has 1 million followers — way less than taylor swift. Those much smaller number of people that follows wasian project has the same potential to be in the best k candidates than those much larger number of people that follow taylor swift.

The key insight here is that we do not want to process all potential candidate lists but stop when we processed enough. The tricky part is to know when to stop. The following is a modified version of the previous algorithm that implements the idea.

import heapq


def search_top_k_probe_set(index, sets, q, k):
    # Initialize a priority heap to store the current top-k candidates.
    heap = []

    # Initialize a set for tracking probed candidates.
    seen_ids = set()

    # Iterate over elements in q from the least to the most frequent based
    # on the lengths of their lists in the inverted index.
    for i, x in enumerate(sorted(q, key=lambda x: len(index[x]))):
        ids = index[x] # Get a list of set IDs from the index.
        for id in ids:
            if id in seen_ids:
                continue  # Skip seen candidate.
            s = sets[id]
            intersect_size = len(q.intersection(s))
            jaccard = intersect_size / (len(q) + len(s) - intersect_size)
            # Add the candidate to the priority heap.
            if len(heap) < k:
                heapq.heappush(heap, (jaccard, id))
            else:
                # Only candidates with higher Jaccard than the k-th
                # current candidate will be added in this operation.
                heapq.heappushpop(heap, (jaccard, id))
            seen_ids.add(id)
        # If any new candidate from the remaining lists cannot have higher
        # Jaccard than any of the current best k candidates, we do not need
        # to do any more work.
        if (len(q) - i - 1) / len(q) (<= min(heap)[0]:
            break

    # Return the best k candidates.
    return [id for _, id in heapq.nlargest(k, heap)]

The search_top_k_probe_set algorithm computes Jaccard similarity for every new candidate it found. It keeps track of the current best k candidates at all times, and it stops when the upper bound Jaccard of any new candidate is no greater than the minimum Jaccard of the current best k candidates.

The search_top_k_probe_set algorithm walks through the inverted index lists and computes the Jaccard similarity for every candidate set it encounters and keeps track of the current top-k candidate sets. It stops when the maximum Jaccard similarity of any set in the unseen lists is no greater than the minimum similarity of the current top-k candidates. Image by the author.

How to compute the upper bound Jaccard? After processing n lists of candidates, for any unseen candidate, their maximum intersection with the query set is at most equal to the number of remaining unprocessed lists: |Q|-n. We are giving it the most benefit of doubt by saying that such candidate may show up in every single one of the |Q|-n remaining lists. Now we can use simple math to derive the upper bound Jaccard of such candidate X.

The formula for calculating the upper bound of Jaccard similarity between an unseen candidate indexed set X and query set Q, after walking through n lists of candidates.

This clever technique is called Prefix Filter in set similarity search research literature. I wrote a paper about it that goes into much more details and further algorithmic optimizations. I also created a Python library SetSimilaritySearch that implements a much more optimized version of the the search_top_k_probe_set algorithm that also supports cosine and containment similarity measures.

Approximate Index for Jaccard Search

In the last section, I explained two search algorithms that work on inverted index. These algorithms are exact, meaning that the k best candidates they return are the true k best candidates. Sounds trite? Well, this is a question we should ask ourselves whenever we design search algorithms on large-scale data, because in many scenarios it is not necessary to get the true k best candidates.

Think about the Spotify example again: do you really care if the result of a search may miss a few people with similar taste as yours? Most people understand that in everyday applications (Google, Spotify, Twitter, etc.), the search is never exhaustive or exact. These applications are not mission critical enough to justify exact search. This is why the most widely used search algorithms are all approximate.

There are mainly two benefits of using approximate search algorithms:

Faster. You can cut many corners if you no longer need exact results.
Predicable resource consumption. This one is less obvious, but for several approximate algorithms, their resource usage (e.g., memory) can be configured a priori independent of data distribution.

In this post, I write about the most widely used approximate index for Jaccard: Minwise Locality Sensitive Hashing (MinHash LSH).

What is LSH?

Locality Sensitive Hashing indexes are true wonders in computer science. They are algorithmic magic powered by number theory. In machine learning literature, they are k-NN models, but unlike typical machine learning models, LSH indexes are data-agnostic so their accuracy conditioned on similarity can be determined a priori before ingesting new data points or changing data distribution. So, they are more similar to inverted indexes than a model.

An LSH index is essentially a set of hash tables each with a different hash function. Just like a typical hash table, an LSH index’s hash function takes a data point (e.g., a set, a feature vector, or an embedding vector) as input, and outputs a binary hash key. Except for this, they cannot be more different.

A typical hash function outputs keys that are pseudo-randomly and uniformly distributed over the entire key space for any input data. For example, MurmurHash is a well-known hash function that outputs near-uniformly and randomly over a 32-bit key space. This means that for any two inputs, such as abcdefg and abcefg, as long as they are different, their MurmurHash keys should not be correlated and should have the same probability to be any one of the keys in the entire 32-bit key space. This is a desired property of a hash function, because you want even distribution of keys over hash buckets to avoid chaining or constantly resizing your hash table.

An LSH’s hash function does something opposite: for a pair of similar inputs, with similarity defined through some metric space measure, their hash keys should be more likely to be equal, than another pair of hash keys of dis-similar inputs.

What does this mean? It means that an LSH hash function has higher probability of hash key collision for data points that are more similar. Effectively, we are utilizing this higher collision probability for similarity-based retrieval.

MinHash LSH

For every similarity/distance metric, there is an LSH hash function. For Jaccard, the function is called Minwise Hash Function, or MinHash function. Given an input set, a MinHash function consumes all elements with a random hash function and keeps track of the minimum hash value observed. You can build an LSH index using a single MinHash function. See the diagram below.

A MinHash LSH index with a single random hash function. Image by the author.

The mathematical theory behind MinHash function states that the probability of two sets having the same minimum hash value (i.e., hash key collision) is the same as their Jaccard.

h(A) is the hash values of all elements in A by random hash function h. min(h(A)) is the minimum hash value of all elements in A.

It is a magical result, but the proof is quite simple.

A MinHash LSH index with a single MinHash function does not give you satisfactory accuracy because the collision probability is linearly proportional to the Jaccard. See the following plot to understand why.

Collision probability of a single MinHash function over Jaccard between query set and indexed set. The Y-axis is the collision probability and the X-axis is the Jaccard between the query set and an indexed set. For example, an indexed set having Jaccard = 0.8 with the query set has 80% probability to be retrieved by the index; another indexed set having Jaccard 0.2 with the query set has 20% probability to be retrieved. Image by the author.

Imagine we draw a threshold at Jaccard = 0.9: results with higher Jaccard than 0.9 with the query set is relevant, wheres results with lower than 0.9 Jaccard are irrelevant. In the context of search, the notion of “false positive” means that irrelevant results are returned, wheres the notion of “false negative” means that relevant results are not returned. Based on the plot above and looking at the area corresponding to false positive: if the index only uses a single MinHash function, it is going to produce false positives at a very high probability.

Boosting the Accuracy of MinHash LSH

This why we need another LSH magic: a process called boosting. We can boost the index to be much more attuned to the relevancy threshold specified.

Instead of only one, we use m MinHash functions generated through a process called Universal Hashing — basically m random permutations of the same hash function of 32-bit or 64-bit integer. For every indexed set, we generate m minimum hash values using universal hashing.

Imagine you list the m minimum hash values for an indexed set. We group every r number of hash values into a band of hash values, and we make b such bands. This requires m = b * r.

Minimum hash values of an indexed set in MinHash LSH with m= 16, b = 4 and r= 4. Image by the author.

The probability that two sets having “band collision” — all the hash values in a band collide between two sets, or r contiguous hash collisions, is Jaccard(A, B)^r. That’s a lot smaller than a single hash value. However, the probability of having at least one “band collision” between two sets is 1 — (1-Jaccard(A, B)^r)^b.

Why do we care about 1 — (1-Jaccard(A, B)^r)^b? Because this function has a special shape:

Boosted probability function for retrieval over Jaccard for MinHash LSH Index using b = 32 and r = 32. Image by the author.

In the plot above, you can see by using m MinHash functions, the “at-least-one band collision” probability is an S-curve function with a steep rise around Jaccard = 0.9. Assuming the relevancy threshold is 0.9, the false positive probability of this index is much smaller than the index that uses only one random hash function.

Because of this, an LSH index always uses b bands of r MinHash functions to boost accuracy. Each band is a hash table storing pointers to indexed sets. During search, any indexed set collides with the query set on any band is returned.

A MinHash LSH Index using b = 4 and r = 4. Each band is a hash table whose hash key is a concatenation of minimum hash values from 4 MinHash functions. Image by the author.

To build an MinHash LSH index, we can specify a prior a relevancy threshold and acceptable false positive and negative probabilities conditioned on Jaccard similarity, and calculate the optimal m, b and r, before indexing any data points. This is a great advantage of using LSH over other approximate indexes.

You can find my implementation of MinHash LSH in the Python package datasketch. It also has other MinHash-related algorithms like LSH Forest and Weighted MinHash.

Final Thoughts

I have covered a lot of topics in this post, but I barely scratched the surface of search indexes for Jaccard similarity. If you are interested in reading more about these topics, I have a list of further readings for you:

Mining of Massive Datasets by Jure Leskovec, Anand Rajaraman and Jeff Ullman. The 3rd chapter goes into detail about MinHash and LSH. I think it is a great chapter for gaining the intuition of MinHash. Be aware the application described in the chapter is focused on n-gram based text matching.
JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. The preliminary section of this paper explains the intuitation behind the search_top_k_merge_list and search_top_k_probe_set algorithms. The main section explains how to take cost into consideration when input sets are large, such as a table column.
Datasketch and SetSimilaritySearch libraries respectively implement the state-of-the-art approximate and exact Jaccard similarity search indexes. The issues list of the datasketch project is a treasure trove of application scenarios and practical considerations when applying MinHash LSH.

What about Embeddings?

In recent years, due to breakthroughs in representation learning using deep neural networks like Transformers, similarity between learned embedding vectors is meaningful when the input data is part of the same domain that the embedding model trained on. The main differences between that scenario and the search scenario described in this post are:

Embedding vectors are dense vectors with typically 60 to 700 dimensions. Every dimension is non-zero. In contrast, sets, when represented as one-hot vectors are sparse: 10k to millions of dimensions, but most dimensions are zeros.
Cosine similarity (or dot-product on normalized vectors) is typically used for embedding vectors. For sets we use Jaccard similarity.
It is hard to specify a relevancy threshold on similarity between embedding vectors, because the vectors are learned black-box representations of the original data such as image or text. On the other hand, Jaccard similarity threshold for sets is much easier to specify because sets are the original data.

Due to the above differences, it is not straightforward to compare embeddings and sets because they are distinctively different data types, even though you could classify both of them as high-dimensional. They are suitable for different application scenarios.

GPT-4’s Maze Navigation: A Deep Dive into ReAct Agent and LLM’s Thoughts

2023-05-10T05:12:30+00:00

“A anxious looking robot navigating an ancient greek maze with stone walls.”

The Sparks

My colleagues at Microsoft Research recently published a paper that demonstrated GPT-4’s navigational and mapping capability.

[2303.12712] Sparks of Artificial General Intelligence: Early experiments with GPT-4 (arxiv.org)

They performed this demonstration through a chat with GPT-4. At the beginning of the chat, they provided the description of the navigation task. They gave feedback about the current position and possible next moves after each move by GPT-4. GPT-4 has no access to the complete map throughout the chat. It eventually arrived at the goal room, and generated a map of the house.

This navigational capability is astonishing on the surface: it suggests that GPT-4 has two-dimensional spatial awareness. How does it recognize and memorize the dead ends to avoid repeated visits? How does it plan the next move?

That gave me an idea: what if we challenged GPT-4 to a maze game?

Let’s Build It — A Deep Dive in to ReAct Agent

To visualize the maze and GPT-4’s navigation in real time, I used a Python maze generator. This Python maze generator can create random n x m rectangular mazes with different levels of difficulty. It also has an API allowing me to visualize the moves.

Examples of mazes generated by pyamaze.

I connected GPT-4 with the maze API using Langchain’s Agent framework. My complete code is only 87 lines of Python. Specifically, I used the default zero-shot-react-description agent and two tools:

look(), which returns a list of (x, y) coordinates for the next possible positions.
move(position), which moves the agent to a specified position.

Here are the tool definitions. These tools are member functions of a maze object called game, which stores the internal states and renders graphics.

tools = [
    Tool(
        name="look",
        func=game.look,
        description=(
          "A tool for checking the available next positions to move to. "
          "It takes an empty string as input and returns a list of possible "
          "next positions."
        ),
    ),
    Tool(
        name="move",
        func=game.move,
        description=(
          "A tool for moving in the maze. It takes an input of a target "
          "position (x, y), and returns the result of the move. If the "
          "move was successful, it returns the new position, otherwise it "
          "returns an error. Always use the look tool to check possible "
          "directions before making a move."
        ),
    ),
]

I gave GPT-4 the following instruction:

"""You are an agent in a rectangular maze with {rows} rows and {columns} 
columns. Each cell has a position (x, y) where x is the row index and y is 
the column index. You can move one cell at a time. There may be walls 
between some cells that you cannot move across. You must move toward the 
goal using as few steps as possible. You must think about which direction 
to move using A* search. Your start position is {start}. DO NOT STOP until 
you have successfully reached the goal position at {goal}."""

After everything was set up, GPT-4 started its navigation in a Thought-Action-Observation loop, as shown in the diagram below.

The Thought-Action-Observation loop (i.e., ReAct) used by GPT-4 for maze navigation.

The Thought-Action-Observation loop is a simple but powerful innovation that enables LLM to interact with external APIs, such as the maze object in this case. The loop is two-way conversation between an LLM (such as GPT-4) and a Python handler. It begins with a GPT-4’s response to the instructions. In the response, GPT-4 lays out its first thought and action:

Thought: I need to determine the possible next positions I can move to from my 
current position.
Action: look
Action Input: ""

This message from GPT-4 follows the structure defined in the system prompt for the ReAct agent in Langchain. The Python handler parses this message, calls the look() tool, and returns the next possible positions.

Observation: Next possible positions: (4, 3), (3, 4)

This text is then sent back to GPT-4 as a user message, and GPT-4 replies with a new thought and action:

Thought:I have two possible positions to move to. I will choose the 
position that has the lowest total cost, which is the sum of the 
movement cost (g) and the estimated cost to the goal (h) using A* search.
Action: move
Action Input: (4, 3)

The loop repeats with a different action: move((4,3)), updates the current position in the maze, and returns an observation:

Observation: Moved to position (4, 3).

The loop continues this way:

GPT-4 thinks out loud and replies with a structured action.
The Python handler executes the action and replies with an observation

This goes on until it reaches the goal. Then the Python handler replies:

Observation: Success! You have arrived at the goal at position (1, 1). 
Your path taken is (4, 3), (4, 2), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (3, 3), (3, 2), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (1, 4), (1, 3), (1, 2), (1, 1).

GPT-4 then says:

Thought:I now know the final answer.
Final Answer: I have successfully reached the goal at position (1, 1) by 
following the path (4, 3), (4, 2), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), 
(3, 3), (3, 2), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (1, 4), (1, 3), 
(1, 2), (1, 1).

The Python handler terminates the conversation after this Final Answer.

GPT-4 on a 5x5 Maze (150x playback speed)

GPT-4 on a 6x6 Maze (150x playback speed)

GPT-4 navigates a 7x7 maze. It did not succeed and gave up.

GPT-4 performed pretty well up to size 6x6. It avoided getting trapped in loops, but it did not always take the optimal path. This is not surprising because it only had local information of its immediate surrounding and had to decided based on that. Its memory usage is limited to past moves and observations.

It is also worth noting that GPT-4 follows instruction very faithfully, so clear instructions are enough. This is why I think GPT-4 is superior to other LLMs. Those other ones requires extensive prompt-tuning.

The result is quite interesting. There is a remaining question: how does GPT-4 navigate the maze exactly? It says A* search in its thought, but it is not clear whether it used any special algorithm.

Examine the Thoughts of GPT-4

My tweet about GPT-4 maze navigator

My tweet about GPT-4 maze navigator

Twitter discussions rarely go into any depth. My tweet was no exception. A month has passed and the field of LLM has already gone through several revolutions, but no one has ever followed up on the actual navigation mechanism used by GPT-4. I decided to look into it.

My result shows that GPT-4 clearly learned a pretty good get_next_move(past_moves, past_observations) function through pre-training on next-token prediction. That’s pretty impressive. Some skeptics may suggest that this get_next_move function is just pattern matching against mazes in the training data. I doubt that, as the number of possible mazes is grows exponentially with respect to the maze size. This table lists the number of possible mazes given the number of rows and columns.

================================================================
m\n| 1   2     3       4         5           6             7
---+------------------------------------------------------------
1  | 1   1     1       1         1           1             1 ...
2  | 1   3     8      20        49         119           288 ...
3  | 1   8    45     234      1193        6049         30616 ...
4  | 1  20   234    2423     24455      245972       2473317 ...
5  | 1  49  1193   24455    482443     9469361     185899132 ...
6  | 1 119  6049  245972   9469361   360923899   13742823032 ...
7  | 1 288 30616 2473317 185899132 13742823032 1012326365581 ...
  ...

https://oeis.org/A359573

Based on this table, there are 360923899 different 6x6 mazes. There are probably not that many mazes in the training data.

Some recent academic work looks into the explainability aspect of large language models and finds that their own explanation are sometimes quite good. So, we should take a closer look into the thoughts of GPT-4 when it came up with moves. Let’s examine the thoughts in GPT-4’s messages, and see what techniques does it employes.

Memorizing

This is the first thought I found quite telling:

Observation: Next possible positions: (6, 5), (6, 3), (5, 4)
Thought: Since I have already visited the positions (6, 5) and (5, 4), 
I will now move to (6, 3) as it is the only unvisited position.
Action: move
Action Input: (6, 3)

It clearly uses information from chat history about visited positions to exclude them from possible next moves. We can certainly say that the get_next_move function has access to memory of historical moves.

Backtracking

The following thought shows how GPT-4 does backtracking from (4, 1) to (5, 2) when navigating the 5x5 maze shown earlier:

Observation: Next possible positions: (5, 1)
Thought:I have only one possible next position (5, 1). This will move me 
back to a previous position, which is not helpful. Therefore, I'll 
backtrack to the previous position (5, 1) and try another path.
Action: move
Action Input: (5, 1)

Observation: Moved to position (5, 1).
Thought:I have returned to position (5, 1). Now, I will take the 
untried path from position (5, 2) to (4, 2).
Action: move
Action Input: (5, 2)

Observation: Moved to position (5, 2).
Thought:I have moved to position (5, 2). Now, I will take the untried 
path from position (5, 2) to (4, 2).
Action: move
Action Input: (4, 2)

GPT-4 also showed evidence of backtracking when navigating the 7x7 maze.

Dead-end Labeling

Backtracking is not enough to avoid getting into the same dead-end alley twice. In this thought below, GPT-4 labels a sub-portion of the maze as a dead-end. Humans also use this technique through associative memory when exploring real-life or virtual environments. I think this is probably the most effective technique, and GPT-4 uses it reliably.

Observation: Moved to position (7, 7).
Thought:Now, I am back at the starting position (7, 7). I need to check 
the available next positions again and choose a different path.
Action: look
Action Input: ""
Observation: Next possible positions: (7, 6), (6, 7)
Thought:I have two possible next positions: (7, 6) and (6, 7). Since I 
previously explored the path starting from (7, 6) and reached a dead-end, 
I will now choose the position (6, 7) to explore a different path.

Action: move
Action Input: (6, 7)

A* Search?

In the prompt I suggested using A* search algorithm, which is to use a simple heuristic function for deciding between multiple locally equivalent moves. A typical heuristic is to compare possible moves based on the Manhattan distance to the goal.

Unlike previous memory-based techniques, GPT-4 does not use A* search reliably: it sometimes uses the algorithm, but often times it simply chooses at random. The following example shows how GPT-4 uses A* search.

Observation: Moved to position (5, 4).
Thought:Now, I am at position (5, 4). I need to check the available next positions again.
Action: look
Action Input: ""
Observation: Next possible positions: (5, 5), (5, 3), (6, 4)
Thought:I have three possible next positions: (5, 5), (5, 3), and (6, 4). I should calculate the cost of each position, which includes the cost from the current position and the heuristic cost to the goal position (1, 1). Then, I will choose the position with the lowest total cost. I will not consider (6, 4) since it is the previous position.

Cost Calculation (Position, Movement Cost + Heuristic Cost) :
- (5, 5): 1 + abs(5-1) + abs(5-1) = 1 + 4 + 4 = 9
- (5, 3): 1 + abs(5-1) + abs(3-1) = 1 + 4 + 2 = 7

I will move to the position (5, 3) since it has the lowest total cost.
Action: move
Action Input: (5, 3)

What have we learned?

Based on the evidence collected so far, I can confidently say that GPT-4 has a good grasp of memorization-based navigation techniques such as backtracking and dead-end labeling. However it does not fully possess advanced planning skill such as using the A* search algorithm. What is an explanation for this?

One hypothesis is that since GPT-4 is a transformer, it produces one token at a time and appends each new token to the input for producing the next token. In that sense, it always thinks out loud in a linear chain of thoughts. Moreover, since a transformer produces each token in a constant number of computational steps, it has a limited ability to explore any non-linear search space, such as a maze. GPT-4 performs poorly compared to classical algorithms like Min-Max and Monte-Carlo search. Those algorithms do not think out loud, they plan internally and output with confidence about the expected outcome.

One may object to this hypothesis and argue that we can do better prompt engineering to “coerce” GPT-4 to always follow an advanced planning algorithm, and hook it up with a Python code interpreter tool for executing the algorithm. I think if we do that, we will not be evaluating the raw intelligence of GPT-4, but merely using it as a code interpreter that handles structured input and output — why not just write the code?

In summary, I think we still know very little about the capabilities and limitations of large language models. While training GPT-4 took only a couple of months, it may take years for human to fully understand what we have created.

The code for this blog post can be found on Github.

Human-Aligned Text-to-SQL Evaluation

2023-03-18T18:40:23+00:00

In my last post about Text-to-SQL using GPT-3.5, I pointed out the issue with existing benchmark’s evaluation metric: it rejects perfectly fine SQL queries for not having the same strict execution result as golden (aka. labeled) queries. In this post, I discuss a new metric I created to better evaluate Text-to-SQL performance.

Here is an example from my last post:

-- (Hard) 
-- Question: Which grade has the most high schoolers?
-- pred:
SELECT grade, COUNT(*) AS num_highschoolers
FROM Highschooler
GROUP BY grade
ORDER BY num_highschoolers DESC
LIMIT 1;
-- gold:
SELECT grade
FROM Highschooler
GROUP BY grade
ORDER BY count(*) DESC
LIMIT 1;

In this example, the generated query (top) is marked as an error. Comparing to the golden query (bottom), the generated query has an extra computed column for student counts. In my opinion the query generated by GPT-3.5 returns more informative answer to the original question.

To recap the numbers from my last post: I tested GPT-3.5 on 96 questions from the Spider benchmark (86 from the training set and 10 from the development set) and found that it scored 41.7% in execution accuracy and 38.5% in exact match accuracy. However, after further analysis of the error cases, it became clear to me that most of the queries generated by GPT-3.5 were actually perfectly fine from a human perspective. This highlights the problem with our existing evaluation metrics for Text-to-SQL, as they do not accurately measure human preference.

This issue of mis-alignment between benchmark evaluation metrics and actual human preference is well-known in the research community. For instance, in document summarization benchmarks, the standard evaluation metric is ROUGE, which is based on counting overlapping word phrases between a generated summary and a golden summary. This approach fails to detect correct summaries written in different terms and phrases from the golden summary. Despite this, ROUGE scores are still being used by recent papers.

Human evaluation remains the gold standard in ML research, and automatic metrics are the “unit tests” for new models. Is it possible to have something in between, like a “staging environment” for new models?

GPT-3.5 for Evaluation

GPT-3.5 has been fine-tuned to align with human preference, making it much better at following instructions than GPT-3, which requires careful prompt engineering to work effectively. This got me thinking: can we leverage GPT-3.5 to create an evaluation metric for Text-to-SQL that aligns with human preference? Let’s break it down step-by-step:

First, we need to consider what GPT-3.5 is capable of doing:

It can transform structured data to text, and vice versa.
It can reason based on facts provided directly in the prompt context.

What does a Text-to-SQL task entail?

An input question in natural language text.
Generating a SQL query.
Executing the SQL query and obtaining structured data (i.e., rows).

To evaluate a generated SQL query, we can start by asking GPT-3.5 to answer the input question using the structured data result obtained from executing the query. This will give us a natural language answer to the input question. We repeat this step for the golden SQL query. Then, we ask GPT-3.5 whether the hypothesis answer generated from the generated query is correct, given the input question and the reference answer generated from the golden query’s result. We receive a binary Yes or No response from GPT-3.5.

The diagram below illustrates this design:

Evaluate Text-to-SQL using GPT-3.5. The actual prompts can be found in this script.

By using GPT-3.5 in this way, we can create an evaluation metric for Text-to-SQL that better aligns with human preference.

Experimental Results

I extended the Spider benchmark’s evaluation with this new metric, which I named Answer Accuracy, as part of the LlamaIndex open source project. The code I used can be found here.

Using this new metric, I evaluated the generated SQL queries of the same 96 questions. The overall answer accuracy for GPT-3.5 text-davinci-003 is an impressive 88.54%. In fact, upon reviewing the error cases listed in my last blog post, I found that the cases that I pointed out to be correct were indeed marked as such, and the one true error case was correctly caught

To further validate this new metric, I tested it on outputs from other GPT models, including GPT-4. Here is the a plot of their answer accuracies:

Answer accuracies of GPT models (zero-shot) on 96 questions from Spider benchmark

The resulting answer accuracies are as follows: code-davinci-002 at 79.17%, text-davinci-003 at 88.54%, gpt-3.5-turbo at 85.42%, and gpt-4 at 89.58%. As expected, GPT-4 outperformed the other models, which aligns with our practical experience of these models’ relative performance.

In contrast, the execution accuracies and match accuracies of GPT models do not align with our practical experience. Here is a plot showing these metrics used on GPT models.

Execution and exact match accuracies of GPT models on 96 questions sampled from Spider benchmark

If we use these metrics as the primary measurement of Text-to-SQL performance, we would think gpt-4 is less powerful than code-davinci-002. These results clearly do not match our practical experience with these models.

Key Implications

What are the key implications of this Text-to-SQL experiment?

Firstly, we found that the existing automatic metrics, namely execution accuracy and exact match accuracy, are mis-aligned with human preference. As a result, they should not be relied upon as the primary way to evaluate Text-to-SQL models.

Second, while human evaluation remains the gold standard, large language models (LLMs) such as GPT-3.5 and above can accurately approximate human preference. This is a potential game changer, because they allow us to evaluate Text-to-SQL models and estimate the expected human evaluation result. This is especially useful when human evaluation is not feasible due to budget limitation.

Thirdly, and this is where things get interesting, our use of instruction-tuned LLMs for evaluation could be generalized to many other tasks. This approach is especially useful for tasks whose output consists of simple statements that can be directly reasoned over by LLMs. And there’s a research paper on this very topic called “GPTScore”, which trains GPT-3.5 to evaluate NLP tasks using in-context learning.

Note

This post is intended to provoke a conversation about Text-to-SQL evaluation, not to claim the answer accuracy metric is 100% human aligned or even robust. I am happy to collaborate if you would like to take a step further toward a better evaluation.

What is Coming Next for Text-to-SQL

2023-03-07T23:19:58+00:00

Text-to-SQL is a natural language processing (NLP) task that involves converting natural language questions into SQL queries that can be executed on a database.

Here is a Text-to-SQL example on a TV show database:

Question: What is the content of TV Channel with serial name “Sky Radio”?

Model: SELECT Content FROM TV_Channel WHERE series_name = 'Sky Radio';

Result: music.

The main motivation for Text-to-SQL is that a natural language interface helps users without technical expertise to write SQL queries to interact with databases. Wouldn’t you like to be able to speak to your relational database in English?

In this post, I will review the current state-of-the-art Text-to-SQL systems, experiment with the latest OpenAI GPT model for Text-to-SQL, and finally lay out my thoughts about what is coming next.

The Current State

Text-to-SQL systems are currently evaluated using the Spider benchmark, which includes 10k questions with labeled SQL queries.

The state-of-the-art approaches that score highest on this benchmark typically use a simple framework: they take an existing language model (such as BERT or T5), which has been pre-trained on natural language text, and then perform supervised training on labeled SQL generation examples. This process is called “fine-tuning”. Some approaches build on top of this framework by adding a pre-processing stage to reduce the difficulty of generation, or by adding a post-processing stage to improve the correctness of generated SQLs.

The main issue with this framework (a pre-trained language model + fine-tuning) is cost. Fine-tuning produces a task-specific model that you must host separately from the pre-trained model, only for Text-to-SQL generation tasks. Additionally, there is the compute cost of fine-tuning, which must be repeated to keep up with the latest new examples. As language models get larger, these costs will increase as well.

A New Wave — How good is GPT-3.5?

OpenAI’s GPT-3.5 models, specifically the davinci series and ChatGPT, have impressed us with their mastery of languages and ability to write code. They can even write SQL queries without any fine-tuning: just give them a schema and a question, and they will write SQL for you. With proficiency in over 20 human languages and many programming languages, this ability is not entirely surprising. But how good is it really? To evaluate its performance, I conducted some experiments.

Setup

For this, I used LlamaIndex (version 0.4.19), which has an easy-to-use API utilizing OpenAI’s GPT models for querying structured and unstructured data sources, including text documents, knowledge bases, and relation databases, using natural language. I connected it with the Spider benchmark’s databases and ran the evaluation using the latest GPT-3.5 model, text-davinci-003. If you’re interested, you can find the end-to-end benchmark scripts here.

In the Spider benchmark, execution accuracy measures the fraction of examples in which the predicted SQL queries’ execution output matches that of the golden (i.e., human-labeled) SQL queries. Exact matching accuracy measures the fraction of examples in which the predicted SQL matches the golden SQL syntactically. However, exact matching accuracy is a less robust measure because it flags two equivalent SQLs as a mismatch. See the Spider paper for details.

What I found

In the training examples (where GPT-3.5 is used without fine-tuning, so it’s all blind runs), it achieved 40.7% execution accuracy. On the development (i.e., validation) examples, it achieved 50% execution accuracy.

Refer to the tables below for a summary of the results. To keep costs low for this blog post, I randomly sampled 1% of all questions in the benchmark. As a result, there are 86 questions from training examples and 10 questions from development examples.

Results on Training Examples

+------------------------+-------+--------+-------+-------+------+
|                        | easy  | medium | hard  | extra | all  |
+------------------------+-------+--------+-------+-------+------+
| count                  | 24    | 28     | 17    | 17    | 86   |
| EXECUTION ACCURACY     | 0.833 | 0.357  | 0.176 | 0.118 | 0.407|
| EXACT MATCHING ACCURACY| 0.833 | 0.321  | 0.118 | 0.059 | 0.372|
+------------------------+-------+--------+-------+-------+------+

Results on Development Examples

+------------------------+-------+--------+------+-------+------+
|                        | easy  | medium | hard | extra | all  |
+------------------------+-------+--------+------+-------+------+
| count                  | 3     | 3      | 3    | 1     | 10   |
| EXECUTION ACCURACY     | 1.000 | 0.333  | 0.000| 1.000 | 0.500|
| EXACT MATCHING ACCURACY| 1.000 | 0.333  | 0.000| 1.000 | 0.500|
+------------------------+-------+--------+------+-------+------+

In comparison, the current №1 model on Spider benchmark achieves 84.1% execution accuracy and 80.5% exact match accuracy on the complete development examples. So at first glance this seems to be a huge gap between the zero-shot, blind run performance of the best in-class GPT-3.5 model (50%, 50%) with best fine-tuned Text-to-SQL model (84.1%, 80.5%).

Error Analysis

Through past experimentation with GPT-3.5 models including ChatGPT, I have found that they can generate very complex queries and suggest rewrites with better execution performance with just a few hints. It seems to me that these models really understand the SQL language. So the accuracy number from the Spider benchmark is surprising. After all, while baseline models can only perform Text-to-SQL, GPT-3.5 models can also write Python!

So I took a closer look at the error cases in the development examples. What I realized is that the Spider benchmark’s accuracy measure is too strict: many generated SQLs are semantically correct for humans, but still marked as error. Here are the 5 errors in the development examples.

Error Example 1.

-- (Medium) 
-- Question: List the cost of each treatment and the corresponding treatment 
-- type description.
-- pred:
SELECT Treatments.cost_of_treatment, Treatment_Types.treatment_type_description
FROM Treatments
INNER JOIN Treatment_Types
ON Treatments.treatment_type_code = Treatment_Types.treatment_type_code;
-- gold:
SELECT T1.cost_of_treatment, T2.treatment_type_description
FROM Treatments AS T1
JOIN treatment_types AS T2
ON T1.treatment_type_code = T2.treatment_type_code;

The predicated SQL query is really the same as the golden SQL in this case, apart from different alias and JOIN hints — which doesn’t really matter here.

Error Example 2.

-- (Median) 
-- Question: What is the TV Channel that shows the cartoon
-- "The Rise of the Blue Beetle!"? List the TV Channel's series name.
-- pred:
SELECT TV_Channel.series_name
FROM Cartoon
INNER JOIN TV_series ON Cartoon.id = TV_series.id
INNER JOIN TV_Channel ON TV_series.Channel = TV_Channel.id
WHERE Cartoon.Title = 'The Rise of the Blue Beetle!';
-- gold:
SELECT T1.series_name
FROM TV_Channel AS T1
JOIN Cartoon AS T2 ON T1.id = T2.Channel
WHERE T2.Title = "The Rise of the Blue Beetle!";

GPT seems to have produced an unnecessary JOIN with TV_series. This is probably due to the mention of “series” in the question. This did not affect the number of results.

Error Example 3.

-- (Hard) 
-- Question: Which grade has the most high schoolers?
-- pred:
SELECT grade, COUNT(*) AS num_highschoolers
FROM Highschooler
GROUP BY grade
ORDER BY num_highschoolers DESC
LIMIT 1;
-- gold:
SELECT grade
FROM Highschooler
GROUP BY grade
ORDER BY count(*) DESC
LIMIT 1;

GPT added an extra column for count, which I actually think is better than the golden query.

Error Example 4.

-- (Hard) 
-- Question: Find the name of the winner who has the highest rank points
-- and participated in the Australian Open tourney.
-- pred:
SELECT winner_name
FROM matches
INNER JOIN rankings ON matches.winner_id = rankings.player_id
INNER JOIN players ON matches.winner_id = players.player_id
WHERE tourney_name = 'Australian Open'
	AND rankings.ranking_points = (SELECT MAX(ranking_points) FROM rankings)
ORDER BY rankings.ranking_points DESC;
-- gold:
SELECT winner_name
FROM matches
WHERE tourney_name  =  'Australian Open'
ORDER BY winner_rank_points DESC
LIMIT 1;

The question is unclear as it mentions “highest rank point and participated in the Australian Open tourney”, which seems to be two independent conditions. So I wouldn’t fault GPT for this one. Maybe it should use “LIMIT 1”, however the number of results here doesn’t matter much in practice in my opinion. In fact, the results are all “Serena Williams”.

There is only one objective failure case.

Error Example 5.

-- (Hard) 
-- Question: What are the names of the dogs for which the owner has not spend more than 1000 for treatment ?
-- pred:
SELECT D.name
FROM Dogs D
INNER JOIN Owners O ON D.owner_id = O.owner_id
INNER JOIN Treatments T ON D.dog_id = T.dog_id
WHERE T.cost_of_treatment <= 1000;
-- gold:
SELECT name
FROM dogs
WHERE dog_id NOT IN (
    SELECT dog_id
    FROM treatments
    GROUP BY dog_id
    HAVING SUM(cost_of_treatment) > 1000
);

In this case, GPT did not use the correct SUM aggregate to filter the dogs. This is an error.

My Takeaways

If the results were evaluated by a human, such as myself, the first four supposedly erroneous cases should have actually been marked as correct, resulting in an accuracy of 90%. However, it still falls short of achieving 100% accuracy. Therefore, I will not trust GPT to write my future SQL queries yet, but it can be a useful assistant for generating a draft or completing a template that I have laid out.

What’s Next — In-Context Learning

GPT-3.5 models have demonstrated that they can be trained to perform specific tasks by providing them with examples. However, several months before their release, researchers were already discussing a new approach to teach machine learning models task-specific abilities known as “in-context learning” or “few-shot learning.”

To train a GPT model using in-context learning, you simply provide some instruction and a few informative input-output examples within the prompt, and the model will learn how to perform the task based on the examples provided. Note that this method does not involve fine-tuning the model, which means that a generic GPT model can be used without requiring expensive hardware. Additionally, the latest GPT model, davinci, can handle up to 4000 tokens, which is sufficient for a few input-output examples even for complex SQL queries.

Here is an example I created to demonstrate in-context learning. The following is a prompt to OpenAI’s text-davinci-003 model.

Given a question, generate a SQL query in the dialect of PostgreSQL. 
Use the following format:

Schema: "a create table statement here"
Question: "question here"
Query: "the SQL query here"

Here are some examples. 
The comments between /* and */ are for demonstration purpose.

Example 1
Schema: create table orders (
tstamp timestamp,
volume float
);
Question: generate a time series of order volumes using.
Query: select ts_aggregate(tstamp, volume) as ts from orders;
/* A table with values:
|| tstamp || volume ||
| 2021-03-23 | 32.1 |
| 2021-04-21 | 55.2 |

Result of the query
|| ts ||
| { (2021-03-23, 32.1), (2021-04-21, 55.2) } |
*/

Schema: create table rides (
tstamp timestamp,
distance float,
vehicle_id int
);
Question: generate a time series of distance traveled for each vehicle.
Query:

In the above prompt, I begin by outlining the task at hand, which is Text-to-SQL conversion. I then provide a clear instruction for the model to follow a specific communication protocol, which enables me to programmatically parse the output if necessary. Additionally, through a single example, I introduce a new user-defined aggregate function called ts_aggregate, which is not part of Postgres. This function outputs a custom time series data type, which I also made up.

Subsequently, I pose a slightly different question that requires the use of a GROUP BY construct. The purpose of this question is to test the model’s understanding of ts_aggregate as an aggregation function and its ability to work alongside GROUP BY.

The following is the output of text-davinci-003. It correctly produced the GROUP BY SQL. You can try it out yourself.

select vehicle_id, ts_aggregate(tstamp, distance) as ts from rides group by vehicle_id;
/* A table with values:
|| tstamp || distance || vehicle_id ||
| 2021-03-23 | 3.2 | 1 |
| 2021-04-21 | 5.5 | 1 |
| 2021-03-30 | 2.4 | 2 |

Result of the query
|| vehicle_id || ts ||
| 1 | { (2021-03-23, 3.2), (2021-04-21, 5.5) } |
| 2 | { (2021-03-30, 2.4) } |
*/

From this example, we can see that the model has learned and understood the usage of ts_aggregate, which was not specified in any other way in the prompt. Instead of relying solely on input-output examples, it is also possible to specify ts_aggregate using its functional signature, documentation, or implementation.

Why is this important?

As mentioned previously, “traditional” Text-to-SQL models have relied on a framework of pre-trained models followed by fine-tuning. This approach is inherently limiting because these models are designed for single-use and require dedicated hardware. For example, if a Text-to-SQL service is set up on fixed hardware, it may experience little utilization when users are offline but become unavailable when many users are online, making it a poor service.

In contrast, setting up a “multi-use” model to serve several different tasks, including Text-to-SQL, and using in-context learning to specialize the model for each task could be a more efficient solution. With this approach, there may be more flexibility to invest in hardware and better manage workload demand.

Research has already been conducted in this direction, as outlined in this paper. It will be exciting to see how this approach advances as the baseline capabilities of GPT and other large language models continue to grow.

Is Text-to-SQL Production Ready?

From this evaluation exercise, it is clear that the GPT model can write complex SQLs, but with some chance of errors, making it more human-like. The model can also get confused by unclear prompts, which is similar to how humans can sometimes misunderstand instructions. Perhaps the model is better suited for writing simple queries. Nonetheless, it cannot achieve 100% accuracy, as natural language itself cannot be precise, while SQL is a precise specification. Moreover, when the question is extremely complex, it becomes difficult to specify it precisely using natural language, and therefore, we should not expect a Text-to-SQL system to guess our latent intent correctly every time. However, this does not mean that we should give up.

One way to view the situation is that we already have very good Text-to-SQL generation for single table filter and project queries. These queries are also easily verified by humans. If the scenario is the retrieval of relevant rows in a table (and cross-compile with other pieces of information to produce a natural language response to a question, as in the case of LlamaIndex), the result needs to include the generated SQL query for a simple follow-up validation by the user.

Since the user still needs to validate each query, SQL will remain a necessary tool. However, can we make it easier for people to write SQL? Copilot is excellent for Python, but writing correct SQL requires access to the underlying schema, constraints, and user-defined objects. The ideal application scenario should involve generating useful templates and pieces that are easy to verify and incorporate into a workflow that makes the user more productive.