Vector Search Flashcards
(111 cards)
1
Q
What does FAISS stand for?
A
Facebook AI Similarity Search
2
Q
Describe the vector search problem
A
We have a set of vectors, and for some query vector, we want to find the vectors that are most similar.
3
Q
What is a Voronoi diagram?
A
It’s a division of the plane into cells, where each cell is all the space closer to one particular point than any others. It’s that point’s “territory.”
4
Q
Conceptually, if some query point falls in a Voronoi cell, what does that mean?
A
It means you know which point is closest.
5
Q
What does “probing” mean?
A
It means searching nearby cells, not just the one you landed on.
6
Q
What does IVF stand for?
A
InVerted File
7
Q
What is the IVF strategy?
A
It’s a strategy for vector search. You pick some set of key points, make a Voronoi diagram of them, and then find the Voronoi cell for your query vector and search all the points in that cell – plus maybe probe some nearby ones.
8
Q
What does PQ stand for?
A
Product Quantization
9
Q
What is the point of PQ?
A
It’s to make the vectors themselves smaller, so that L2 distance is easier to calculate.
10
Q
How do you do Product Quantization?
A
First, chunk the vectors up into subvectors. Then, for a particular set of subvectors, do clustering, so you get centroids. Finally, replace each subvector with the cluster id.
11
Q
PQ maps from what space size to what space size?
A
It maps from the original vector space, like R 100, to a space of the number of subvectors, like R4 if you’re breaking up into 4 subvectors.
12
Q
What are codewords?
A
They’re the centroids from Product Quantization.
13
Q
What is a codebook?
A
The set of all centroids for a particular subvector subspace in Product Quantization.
14
Q
What is Indexing?
A
It’s the strategy you use to store your vectors in your vector space – you put them in an index. And then you need to be able to search within that index.
15
Q
What is a “flat index”?
A
It’s one where you don’t modify the vectors at all and just store them directly.
16
Q
How would you lookup in a flat index?
A
You would literally just do KNN with the entire index.
17
Q
What does KNN stand for?
A
K Nearest Neighbors.
18
Q
How do you do KNN?
A
Calculate distance between the query vector and every single other vector. Then return the top K closest.
19
Q
What are the pros and cons of a flat index?
A
Pros: Search quality is maximized since you are literally just doing KNN. Cons are that this takes forever.
20
Q
What does ANN stand for?
A
Approximate Nearest Neighbors
21
Q
What does LSH stand for?
A
Locality Sensitivity Hashing
22
Q
How do you do LSH?
A
Write some hash function that puts similar vectors in the same hash bucket. Then at lookup time, hash the query vector to get its group of similar vectors.
23
Q
What does it mean “maximize collisions” in the context of LSH?
A
It means you want the hash function to put similar vectors in the same bucket (collide them).
24
Q
What are the pros and cons of LSH?
A
Pros: It’s a middle ground on everything – decent performance but also decent speed and storage. Cons are that it’s not amazing at any one thing, and also susceptible to the curse of dimensionality.
25
What does NSW stand for?
Navigable Small World
26
What is an NSW graph?
It’s one where each node is connected to each of its nearest neighbors.
27
Where does the SW in NSW come from?
It’s “Small World” and it comes from a Facebook study where they found that you can get between any two people in the world in an average of 3.57 steps.
28
What does the H in HNSW mean?
“Hierarchical” – it means you break the graph up into different layers of granularity and go from one to the next.
29
What are the pros and cons of HNSW?
Pros are that it is both high-quality and pretty fast. Cons are it eats up tons of memory.
30
What are the pros and cons of IVF?
Pros are it excels at all three of quality, memory, and speed. Not sure it has cons, other than still being approximate relative to the KNN lookup of a flat index.
31
What is Jaccard Similarity?
It’s a measure of the similarity of two sets – the cardinality of their intersection divided by the cardinality of their union.
32
What is k-shingling? Give an example.
It’s when you slide a window of size k along a string to create tokens of size k. Example: Andrew w/ k=3 is And, ndr, dre, rew.
33
What is MinHashing related to?
It’s a step in LSH, it’s how you create a representation for sparse vectors where they’ll have a high Jaccard score if they’re similar.
34
What is random projection?
It’s when you create a bunch of random hyperplanes that divide the space between 1s and 0s, and then the representation of the vector is the 1/0 from each hyperplane, which you find using the dot product.
35
How can you use the dot product to find which side of a hyperplane a vector is on?
Let the normal vector be the vector orthogonal to the hyperplane. Then take the dot product between it and your vector. Dot product is positive when angle <90, and negative when angle >90. Since angle=90 is the hyperplane, this tells you if the angle puts the vector on one side or the other of the hyperplane.
36
What is the Hamming distance?
It’s the number of mismatches between two vectors, e.g. 1110 and 0110 have one mismatch.
37
What is Quantization?
It’s a generic term referring to compressing data into small space?
38
What is the difference between dimensionality reduction and quantization?
Dimensionality reduction is trying to get fewer dimensions. Quantization is trying to reduce the scope of each dimension, like from 32 bits required to describe a particular dimension down to 4.
39
What is IVFPQ?
It’s IVF (Inverted File, the Voronoid cells indexing strategy) but with PQ first, so that you’re doing IVF just on the PQ centroids.
40
What is recall? In the context of vector search?
It’s the number of true positives divided by all the real positives. So it’s the % of real positives that you were able to identify as positive. In the context of vector search this means the % of the K-nearest-neighbors that you were able to correctly identify with your ANN approach.
41
What are the pros and cons of PQ?
Pros are that it takes like 97% less memory and makes ANN 5-10x faster. Cons are it lowers your recall rate.
42
In IVFPQ what do you do first, the IVF or the PQ?
The PQ.
43
What does OPQ stand for?
Optimized Product Quantization
44
What are you doing in OPQ?
It’s where you transform the vectors to maximize the variance in each subvector space, before running PQ.
45
What problem does OPQ try to solve?
The effectiveness of PQ depends on how the subvectors are broken up.
46
If I write OPQ32_128, what do those numbers mean?
OPQ dimensionality reduction to R128, followed by PQ with 32 subvectors.
47
What is a probability skip list?
It’s a linked list with multiple layers, like maybe the first layer is just 1 -> 5 -> 10. You first jump through that layer to get relatively close to where you’re going, and then search just the segment you’ve found.
48
How are probability skip lists related to HNSW?
The “hierarchical” aspect is kinda like a skip list, where the top level is just a few nodes that get you to the right neighborhood, and then you search with more and more granularity.
49
What is a composite index?
It’s when you combine a bunch of different components, like legos, to build a sophisticated index.
50
What are the four types of components you can combine into a composite index, and what are they?
Vector transform (preprocessing vectors before indexing), Coarse quantizer (organizing vectors into subdomains to reduce search scope), Fine quantizer (compressing vectors into smaller domains to save space), Refinement (ranking results at search time).
51
Give two examples of vector transform
PCA and OPQ
52
Give three examples of coarse quantizer
IVF, HNSW, Flat
53
Give two examples of fine quantizer
PW, LSH
54
What does IVF-ADC stand for?
It’s IVF (Inverted File) with ADC (Asymmetric Distance Computation)
55
What are you doing in IVF-ADC?
You are doing IVF followed by PQ – but the PQ comes after the IVF.
56
Why is it called ADC?
ADC means Asymmetric Distance Computation, and it’s Asymmetric because at search time you don’t quantize the query vector, you find its nearest neighbors based on its full representation.
57
What does IMI stand for?
Inverted Multi-Index
58
What are you doing in IMI?
It’s IVF, where you create Voronoi cells, but first you split the vector into subvectors, and then do IVF for each subvector space.
59
What do you do at search time for IMI?
IMI creates subvector spaces with their own Voronoi diagrams, so you pull the candidate nearest neighbors for each subvector.
60
What is the relationship between Multi-D-ADC and IMI?
They’re the same thing. Multi-D-ADC (ADC means Asymmetric Distance Computation) is the name because the Voronoi cells are split across many dimensions.
61
How does the IVF+HNSW strategy work?
You first do IVF to get centroids of Voronoi cells. Then you make an HNSW graph with those.
62
Why does RAG stand for?
Retrieval-Augmented Generation
63
What is hallucination?
It’s when the LLM doesn’t know an answer, so it dreams up a convincing-sounding lie.
64
What is RAG?
It’s when you fetch new information from an external database, and make it available to the LLM.
65
What are two key types of information you’d want to get with RAG?
Up-to-date information, and context-specific data.
66
Why use RAG when you can just fine-tune?
Fine-tuning (adding context-specific training examples and retraining the model on them) is very expensive and difficult – you would have to fully retrain the model every time there’s important new information, which could be very frequent.
67
What’s the most basic way to do RAG?
Convert proprietary knowledge into embedded vectors and add them to the vector database and its index.
68
What does SELF-RAG stand for?
Self-Reflective RAG
69
What is SELF-RAG doing?
It’s creating “reflection tokens” for a particular query to decide if it needs to get new information, and then “critique tokens” to grade the relevance and quality of that new information.
70
What does CRAG stand for?
Corrective RAG
71
What is CRAG doing?
It has an evaluator that it uses to grade the quality of documents obtained, and if they’re insufficient, use a web search to get more.
72
What is RAG Fusion doing?
Derive multiple new queries from the input query, and do document retrieval for all of them.
73
What is the purpose of SELF-RAG?
It’s to increase the factuality of the responses.
74
What is the purpose of RAG Fusion?
It’s to get more comprehensive answers.
75
What is an agent?
It’s an LLM with built-in logic that lets it reason about the answers the main LLM is giving, and decide if it needs more information.
76
What is a “canonical form”?
It’s a class of user intent, like a certain type of question. For instance “questions about LLMs”.
77
What is RAG with guardrails?
It’s where you detect certain types of questions, or queries, and deterministically trigger certain actions.
78
In what context are canonical forms used?
RAG with guardrails. The canonical forms are the classes of queries that you’re comparing the query to, to see if it matches with some sort of guardrailed scenario.
79
What is the difference between a vector database and a vector index?
A vector index is just for organizing and storing vector embeddings. The database lets you manage those vector embeddings, like adding metadata and doing real-time updates.
80
What is the main question you have to answer with filtering?
Do you filter before vector search, or after.
81
What are three categories of evaluation for a vector database?
Technology, Dev Experience, and Enterprise-Readiness
82
What are four factors to consider when evaluating the technology of a vector db?
Performance, Relevance, Scalability, Cost-efficiency
83
What is the Euclidean distance?
The straight-line distance between two points.
84
What is the problem with Euclidean distance (sometimes)?
It is sensitive to magnitudes – if you don’t care about the specific numbers, it’s not what you want.
85
What is the difference between cosine similarity and dot product?
Cosine similarity totally ignores the magnitude of the vectors.
86
What is the output of cosine similarity?
It’s a number from -1 to 1, comparing two vectors. 1 if they are the same direction, 0 if they are orthogonal, -1 if they are opposite directions.
87
What is chunking?
It’s how you break text up into segments.
88
What do you want when you are doing chunking?
You want each chunk to make sense on its own, without any surrounding context.
89
What is fixed-size chunking?
It’s when you break the text up into segments where each segment has the exact same size.
90
What is context-aware chunking?
It’s where you break the text up based on some semantic consideration, like one chunk per sentence.
91
What is “parametric knowledge”?
It’s the knowledge that is learned during training.
92
What is “source knowledge”?
It’s the knowledge that you would pull in when you are doing RAG.
93
Why don’t you want to stuff the context window when doing RAG?
Research shows that the more documents you stuff, the more performance degrades.
94
What is conversational memory?
It’s where you send the entire conversation up to this point, rather than the most recent query.
95
How do you avoid context stuffing when doing conversational memory?
You use an LLM to summarize the conversation up to this point, and just add that to the context.
96
What is the ReAct framework?
It’s for an agent, which does Reason and Act. It’s going to read what it gets from your LLM, reason about it, and decide what further actions to take.
97
What does EBR stand for?
Embedding-based retrieval?
98
What are you doing in EBR?
Use embeddings to represent both the queries and the documents, and then do NN search in the embedding space.
99
What is the main challenge of using EBR for search, other than the scale?
You want to do term-based matching in addition to semantic matching.
100
What are the two layers of search engines?
Retrieval (getting a set of relevant documents) and Ranking.
101
What is the layer called where you do retrieval, in a search engine?
The recall layer
102
What happens in the recall layer, in a search engine?
It’s where you do retrieval.
103
What is the layer called where you do ranking, in a search engine?
The precision layer
104
What happens in the precision layer, in a search engine?
It’s where you do ranking.
105
What is the Facebook unified embedding?
It’s a model where you add the user information and social context to the text.
106
What is triplet loss?
It’s where you have some anchor point, a positive example, and a negative examples, and the loss wants the negative example to be at least m, for some constant m, further away from the anchor than the positive example (which should be much closer). If that’s not the case, the loss function measures how much closer the negative example is.
107
What is the loss function for the Facebook EBR model?
Triplet loss, with cosine similarity as the distance metric.
108
How did Facebook get positive examples for their EBR model?
It was just the results that people clicked on.
109
What was the main problem Facebook ran into while training their EBR model?
Trying to get good negative examples.
110
What is Unicorn?
It’s the Facebook retrieval engine – seems kinda like SQL or SPARQL.
111
What is “hybrid retrieval” in the context of Facebook EBR?
It’s when you do both term matching and embedding matching.
