Transcript
0:05 Okay, welcome to lecture three. today we are going to cover rag and agents. So, I will start this lecture by giving you a quick overview of the projects since we already got a lot of questions. overall, I think the general rule of thumb before projects is that we really hope that you can pick a topic that you are very very excited about yourself. so, think about questions such as what a task does your agent do?
0:36 what are research questions drive it? what kind of data or API we have to support it? And which agentic frameworks you are going to use? And more importantly, how would you evaluate that? So, those are some kind of guiding principles. And then, related to this, just to go a little bit deeper here, the goal of this course or the goal of the course project is to help you to enable you to design, build, and evaluate agent systems of your own.
1:10 And the focus here, we encourage you to think about the building agents using retrieval, tool use, memory, multi-agent systems, different optimization hardness, the data agents use, or the evaluation, and how to make agents safe. So, a lot of topics around that would be really good candidates for project. One thing I do want to highlight here is about the rigorous evaluation. so, in the end, we are going to see the demo presentation from you all. A demo that works once, just like it only happened to work during the final presentation, will not score highly.
1:49 we really want you to think about the rigor behind your system. think about like the task. Where does your data come from? What accounts as success here? Think about how to really grade or evaluate your agents. You can think about LLMs as a judge, different rubrics, human ratings, feasibility check, or just like a mixture of many of them. In terms of how to report the results, think about different type of task. It shouldn't just work on one single user or one single data point. Baselines you can incorporate and more importantly, where your agents are failing. So those are some dimensions to think about.
2:33 To give you some kind of sample or example topics. So if you read this long list, there are a lot of exciting topics you can look at such as evaluating agents, cost, latency, safety beyond task success. You can think about how to adapt agents to new environments, new tools, new APIs, new UIs. Robustness of agents to prompt injection, adversary attack. Why agents misuse tools, learning to use, learning a lot of capabilities for agents from limited data.
3:11 Interpreting agent behaviors, long tail, long horizon, edge cases related to agents. Human agent or agent agent teaming, how can we get a group of agents to work well with each other and get agents and human workers to work together. Multi-agent systems around of memory, planning, over set, reward hacking, we'll have some lectures about safety later this quarter. If you read the website, we do offer some kind of example ideas. In the very beginning of designing this course, we really hope that students could build agents to make your life at the Stanford much easier.
3:53 So you can think about the building agents that could read syllabus and then put the deadlines to your calendar automatically. You can think about course schedule optimizer for next quarter. You can think about research paper discovery and the summarization agent. Campus event aggregator and recommendation system. Coding agent specialized for one specific coding code base, framework, or language, as well as rigorous evaluations around the figures and artifacts.
4:26 So, a lot of topics you can choose from. One minor recommendation here, but actually turned out to be very important is you should always consider the availability of data, agentic frameworks, computation, compute, and evaluation. Missing any of them may lead your project to be not as successful. Some final recommendations here. So, start earlier and work on it every week rather than just like a rushing in the final week. Get your data first.
5:01 Make sure what kind of agentic application you want to focus on, where you should get the data. We recommend that you have a very clear, well-defined research question. Novel, creative questions are highly recommended. You probably see that there is one sentence that I bolded bolded here is results should teach us something. So, I think you should use this as a guiding principle. When you build something, when cheers or myself read it, what are we learning from your project?
5:35 Present and visualize your results very well, and more importantly, come talk to us during office hours, and we will be very happy to help. Okay. Any quick questions about projects? Okay, since the content is very clear, now I'm going to move to the content today. We are going to focus on rag. I will first start with a motivation for rag, and then we will go deep into the rag pipeline. we will talk about some very detailed building components such as how you do indexing, how to do retrieval, and agentic rag, as well as some feeder mode here.
6:21 Let's get it started. The learning objective as I wrote here is by the end of this class, you should know how the pipeline is built, where it breaks, where what to index, and how to index, and how to search it. This lecture is related to your homework one. Let's start with one example here that many of you probably recognize. if you ask a LLM when office hours are least crowded, and I think you'll get something like this, where it tells you that try the Wednesday afternoon sessions. Midweek office hours are usually quiet.
7:04 and it look fine. it's a guess from the prior knowledge. There's nothing behind it. Now if you give the same model with the the Q log that we have recorded in terms of how many people show up to office hours, it actually read that Tuesday at 4:00 p.m. had a 14 people waiting and the Thursday at 9:00 only had a three. So it tells you that you should go to Thursday morning office hour with those numbers.
7:32 The difference is here is not about the fluency. I think both answers are fluent here. The difference is actually about the evidence. The second response here, it actually tell you the actual data together with the model response. So the answer is something that you can actually check. So the idea behind the rag or the design principle behind the rag is that we do not want a models to memorize everything. Instead, we want them to think about finding the relevant information just in time at the moment where the model needed.
8:10 And retrieval is actually a mechanism that achieve such goal here. two things I want you to remember. First is that this is a dynamic process, which means that when the facts change, you update the index, not not the weights. And then, it's also very interpretable because the model can point out like where the document they fetched the information. And this give you like citations. And it means that a human, if we want, we can actually go there and verify the answer.
8:46 So, I want to start with a very classic a setup. this is actually, earlier days, people are working on open-domain question answering. And there are two stage that's very similar to the rag we are talking about today. if you have a question coming in here, there is going to be a document retriever that runs over all possible Wikipedia pages and then fetch a handful of articles. And then the document reader takes those articles and extract the answer.
9:20 so here you can see the particular number here. The division of labor is actually the the whole point here. The retriever basically narrow down millions of articles into a few. And then the reader does the very fine-grained processing on those few candidates. you need to have both in order to get the task done here. So, if you go a little bit deep into the retriever-reader framework, so let's just try to formulate them a little bit.
9:52 you have a large collection of documents, D here. This could have been D1, D2, DN here. N is in general very big. It could have been millions of documents. And you do have a question. We want the model to output a answer here, A. So, if you use this formulation, what the retriever does is that it actually try to retrieve key top-ranked passages here. Key here is very small, like 100, 50, or 10.
10:23 And then your reader is going to read those top passages here and then return you a specific answer. Very earlier days, the way how we implement a retriever is actually a very standard TF-IDF processing. this is through a fixed module. And then the reader is actually where a lot of the earlier neural network efforts were about. so, you can have your reader as a neural reading comprehension model. This could be trained on SQuAD, which refers to Stanford Question Answering Dataset, or other type of like question answering datasets.
11:02 Today, you can also use a zero-shot LLMs, ChatGPT, to do this kind of reader function. So, this is the very classic retriever-reader framework. and now this comes to our main focus today called the retrieval-augmented generation, RAG, here. Let's just walk through this figure from left to right before I unpack many of the components here. So, let's see we have a specific query X. The query X actually goes into what we call a query encoder, QX, here.
11:39 The vector actually runs against the document index with algorithms such as maximum inner product search, MIPS. this is the non-parametric process. And then you got those like top key documents. The top key documents will then go through this kind of generator, P theta, here, which is what we call a parametric part. And then we can marginalize over the documents to get the output. So, the important detail here is that this is actually a end-to-end training pipeline. The gradient is going to flow back through the generator and to the query encoder.
12:20 The frozen part of this process is actually the document index because it's huge. We are not going to learn them like all the time. this is also the same model behind the many different task. So if you curious about the question answering, fact verification, even generating like Jeopardy-like questions, I think this is a framework to use. A lot of follow-up work was also built on top of ideas of RAG. So this is a very quick intro to RAG.
12:54 having known that why we need a RAG, I'm now going to go through the detailed process. What the retriever does, what the generator does, and then how are we going to train those two components together. So RAG, you can think about them as two components. As I mentioned, there is this retriever. So basically you have your context X and then you want to return the top K documents for a specific query X.
13:25 The generator is going to write the answer one token at a time giving the query X and then what you have retrieved so far that's relevant to the current query. So the high-level idea here can be really decomposed as for my query X, what is the answer Y here? And then you can actually decompose them into two components. First, how can we get a Z PZ giving X? Second component is once you have X and the Z, how should we generate Y here?
13:58 So this is a very kind of high-level process. One minor thing here that I do want to mention is the actual process of a RAG actually had a two variants here. One's called a RAG sequence. That is you pick one passage and then you generate the whole answer with it. Right a token means that every time we are going to re-weight the passage at every token of the answers. So, you do not kind of fix a passage for the entire answer generation.
14:32 Let's go a little bit of deeper here. So, once you have this kind of retriever and a generator, we need to train this architecture. This is actually done in a joint training fashion where we jointly train the retriever and a generator to really just minimize the negative log likelihood here. This is should be very familiar to many of you. Basically, you have a ground truth answer and then you have a generated answer. We are going to see whether they match. That's the key idea here.
15:05 Now, let's go a little bit of deeper into how retriever is is learned and how to even represent a retriever and a generator. So, in the classic rag fashion, the retriever is dense passage retriever here, DPR. We basically are going to use two BERT encoders here. BERT was used like frequently earlier days. So, basically what it does is that we are going to pass the passage and question to different BERT encoder here. So, we get a query encoder. We also get a document encoder and then we look at the inner product of their those two vectors. This is basically the score we are going to use to rank documents.
15:56 Those passage vectors, they can be computed at once and then stored in a index. So, this often is like in offline. So, at the query time, we only like encode the question and then run this MIPS search to gather the top K. So, basically the document part is what we can actually process offline. then this exponential basically just like turns the score into a distribution over different retrieved passages here.
16:28 And then that's what the sum on the right slice is about. The generator part, again this is a design choice. You can actually try different type of setups. I'm going to use BART which is a earlier encoder-decoder architecture as a illustration here. but you can use any kind of sequence to sequence model here. The input is very simple. We basically concatenated the question and then the retrieved passenger. And then we feed them into the encoder. And then we let the decoder write the answer one token at each time.
17:05 there is no like special architecture for retrieval. And then the retrieved passage is just a actual text in the in the context. And this is also why RAG can easily transferred to modern LLMs where we do the same thing just with a prompt. So let's look at some of the RAG performance. Again this is a little bit more earlier days. today I think a model performance on those data sets are much higher.
17:35 there were two there were like two or four data sets that we use frequently. natural questions is from Google, TriviaQA, web questions, and curated the track here. You can see that compared to just simple DPR or the earlier algorithm, RAG based fashion actually leaded to a lot of boost here. When you also give the output to humans to let humans read for the for the answers from RAG versus from earlier BART or other systems, which one is better? And you can see that from a factuality factuality or specificity perspective, RAG is rated better most of the time.
18:20 So I think it basically point out the the key contribution of rag that is it literally does better grounding compared to a lot of the systems we have because the retrieved the content is really doing the work for us. So, what I just went through is a very classic first rag paper and rag actually has evolved like like significantly in the last a few years. The very left side is the naive rag fashion where you can see user query documents, we do index, we do retrieval, and then we can query the model to answer it.
19:01 You can also add some kind of components there to make rag more more sophisticated and more powerful. In the middle column, you can see that pre-retrieval, you can actually do something like query routing or query rewriting, query expansion. You can actually provide a lot of rich context for your query to make it easily like processable. And then post-retrieval, you can also do maybe you try the different approach to do the retrieval. So, maybe you want to combine them, you want to re-rank them, you want to summarize them, you want to fuse them together. So, there are a lot of like techniques you can actually introduce to make rag better.
19:44 I think like more recently this kind of more modular rag on the right part actually goes one step further. It break everything into modules, search, routing, rewrite, re-rank, memory, and fusion. And then you can compose them into patterns such as retrieve and then read or iterate iterative retrieve and then read. So, this is just what do we have today? I think you can do a lot of design choices on top of those different components.
20:18 Before we move to the specific index, any quick question here? >> For the slide you showed that RAG is performing better than the other models. When something like that is sort of proposed for the first time, do we also think of how much faster or is it due to the other reasons? >> Yeah, great question. The question is, in addition to performance comparison, do we have any benchmarking of speed and the memory and even cost? So, in later in this lecture, I will mention some of the different components in terms of a latency and others when we compare those methods. I do think that this is a very key difference. This is why when I was talking about like for the document index, this is something we can actually process like offline. when we have more kind of encoders that I'm going to talk about, you'll see that some of them you can actually precompute them.
21:10 Some of the other like BERT encoders, you really cannot precompute them because you need to put the context and document in the same matrix and then do attention mechanism. So, this is going to be a big consideration as we move along. >> When using API models on like say ChatGPT or like more frontier models, is RAG kind of already implemented within them or do we need to like add on more like like extra RAG instructions within the agent?
21:46 >> Yeah, the question is, for modern models, are we going to still do RAG explicitly or is it already built in with them? so, the answer is RAG as a principle, it can always work even for frontier models. Let me give you one example. Let's say you run a company and the company is for specific financial services. All the data, all the specific database are just not public online. So, in that situation, it's really hard for the model to know everything. Then when you use the model there, you can give them access to certain kind of like local database. In this way, RAG still applies there, and you can use any kind of frontier models here in in this perspective. I think if it's really just about the general internet search, I think since GPT-4, many of the models already support that. So, like if you're asking a question of what's the weather today in in Palo Alto, it actually can go fetch some of the existing database and answer you the question.
22:53 Okay. Maybe last question. >> I was just wondering like I'm wondering the retriever inside RAG, like do we still use BERT behind the scenes as a model approach, or we are we are we are having better options? >> Yeah. So, I will go detailed in terms of different approach of how we encode it. so, I used BERT as one example here, but we all know that the field has changed dramatically. BERT now is viewed as very historical. so, we are going to move to more modern methods just in a few slides.
23:27 Okay, I'm going to continue. So, I always love the questions. now I want to go like one layer deeper. this is actually a technique called indexing. Basically, when you want to do retrieval, you need to have the unit where you can like provide embeddings for the unit. And then, how do we make sure that each chunk here carries enough context to be found? so, going back to what makes a good retriever.
23:58 so, still embedding is very popular. If you think about a static word examples such as word-to-vec or GloVe, which we covered at the CS224N, here you are going to get embedding for each word for each token. you can also get a contextual embedding, such as using BERT. you can also use different architecture here. Basically, this token representation is going to take care of the context. So, if you have a word like a bank, in this contextual fashion, you are going to encode the financial connotation versus bank its own may have different meanings.
24:41 You can also use the passage as a unit here. You can do sentence bird. You can do DPR that I mentioned earlier. You can also try different architecture here. Then the unit here is not a word. It's not a token. It's actually a like segment of text. You can also have multimodal information here. For example, clip. This actually provides both encodings for text and image tokens. Here, you put a text and image into the shared space.
25:14 You can also go towards like multimodal where you have both audio, image, and text. So, this is just one specific example. We can also go a bit deeper. Graph. You can have node to vector, like node to vec. You can have like different graphic neural network, graph neural network encoder here, GN. And then you your your like embedding is going to capture the node information or the relation between different node.
25:45 This page is just to show you that the reason why rag or a lot of the design principles behind the rag are still powerful is because they do apply to a lot of like task as we will see in the next 10 minutes. One thing that I do want to mention here is that in order to make the retrieval good, in addition to have a good embedding representation per chunk, you also need a similarity metric. In general, people just use cosine or like inner product here. And the simple approach actually work very well.
26:23 So, now let's think about the chunking process here. This is the basic unit in retrieval. And you can imagine if I have a really really long document, how can I segment them into different pieces? The first approach is very simple. Let's just do a fixed size segmentation. You can just segment it based on size. I'm going to have 100 to 500 tokens per segment. If the segment is very small, then the vector does not have enough context.
26:53 If the segment is very large, then a vector may carry or average many many topics. That's also not good. So we want something in the middle and that in the middle needs to be well configured. You may also want to think about that, okay, if I have this segment and that segment, how should I preserve information shared between them? This is a technique called overlap. In general, we are going to have 10 to 20% of the tokens kind of overlap. So those two two like intervals will have some overlap with each other. In this way, we can actually preserve some of the context or center sentence boundary information.
27:36 Beyond that, you can also do some kind of semantic segmentation where you can just be like, I'm going to just use this one sentence as one unit or this one paragraph as one unit. Those are different design choices. Beyond that, you can also do something even more sophisticated. For example, people do this context enriched chunking where each segment actually carry additional metadata or summaries from this particular segment.
28:08 Today, you can also get LLMs to help. This is what we call a AI-driven dynamic chunking. You can use LLMs to detect natural kind of breakpoints. So in this way, you get something that's very very semantically meaningful. Let me show you one example here just to see how that really works. Let's see you are curious about the greeting and And then on my screen, this is the example. grading the project milestone is due week six. This is actually wrong information. Check out website for correct information.
28:42 so, if you are going to only do fixed size chunking, this is actually what you have. You will just have this kind of different segments of the original document. If you do fixed size with overlap, you will see that some of those information are actually overlap with each other. This is the low-level representation behind the scene. And then if you want to do like semantic segmentation, just based on headings of what our website, then you get the entire block here.
29:13 So, this example is just to illustrate that different segmentation technique actually matters when it comes to this very low-level representation for your retrieval unit. If you are paying attention to the field, actually one of the widely used technique today is called a contextual retrieval. so, if you read this query, what was the revenue growth for ACME Corp in Q2 2023? And this is actually the perfect segment we are going to find from the coppers.
29:48 But if you read this result, this is actually not a very intuitive because which company is this the company here? Which quarter are we talking about? This segment does not really carry much information. our query actually ask for this specific company, specific quarter, specific year, and all of those information are just not there in my like retrieved content here. So, how about we can actually have a mechanism to put those words back? So, on the right, what if the retrieved segment for me is actually those words highlighted in yellow here, and then followed by the original segment content? If we can have this, now now we have both the company and timing information in the text. And then mine like vector index or my keyword index can now just like match with each other.
30:44 So if we could have this, that's amazing. how can we achieve that? this is a technique proposed by Anthropic. so basically for each segment, we are going to run a prompt over the whole document and get back around 50 to 100 tokens of the context and then pre prepend it to the segment themself. And then we can index this contextualized segment twice. first time we'll just run them through a embedding model where we can get their vector representation.
31:22 The other is that we are going to put it into a BM25 here to get their sparse index. probably you noticed that we actually did it twice. Why do we need a both of them? In practice, we actually want to use both because embeddings in general give us semantic meaning match. However, TF-IDF BM25, despite it being a very classic traditional metric, they are actually very very powerful. They can help us with exact numbers and then you can you can just take the best of both world and then merge them.
32:02 one thing I I do want to mention as you can imagine, that is if you are going to give a prompt and then to add this additional context, then you basically need to pay a cost per search per segment. And then this is actually something quite expensive just to think about. now comes to the exciting moment. How do you really achieve this kind of context? Well, you write a prompt. And this is actually what it would look like. You basically tell the model that here is the chunk we want to situate within the whole document. Please give a short sufficient context to situate this chunk with the overall document. So, you basically write a prompt, and then the LM actually scan the entire documents, give you a summary of the context.
32:57 nothing sophisticated is here, and I think like now you really leverage the overall context, and then you also have the specific segment. You combine both of them. Now we are good. Compared to a lot of the classic approach, researchers show that contextual embeddings actually reduce retrieve failure rate. So, this metric I'm going to mention it in a few slides later, but they quantify this failed retrieval at 20.
33:31 That is, if you look at the top 20 results, how many of them fail. And then you can see that compared to embedding, contextual embedding actually drop the error rate from 5.7 to 3.7. And then this is a combination, the hybrid approach. it also drops from 5 to 2.9. So, it's actually pretty useful. And also I think you already noticed that having both embedding, like you use embeddings and also BM25, the combination of them actually give us much better performance.
34:13 So, this is about a more kind of like a modern approach of doing retrieval. the last thing that I or maybe not the last, one of the last thing I'm going to mention here is this technique called late chunking here. So, let's just look at the picture. The naive segmentation I talked so far is that you have a long document, and then we segment them into different components, and then for each component we are going to gather their embeddings, and that's going to be the unit we use for retrieval. So, late chunking was asking, "Well, if you do this segmentation, you really lose the idea of the entire document, right? Because if you take each of them separately, you only get to see the information there."
35:00 How can we actually get to know some kind of document-level semantics? So, then you can do this late chunking, where late chunking means that we do the segmentation later in the process. we got a long document, and we are going to pass it to any embedding model. And then you we are you already got like rich embedding information. And then on top of that, we are going to do segmentation. In this way, the segments actually carry some document-level information.
35:32 so, this is why you get like a richer information from this kind of segmentation. Just to quickly show you, I think if you look at the naive versus late chunking here, you definitely see much better performance from this kind of document-level enrichment. one thing that I'm going to point out is if you notice this trend here, so the improvement from late chunking is actually the largest when your chunk size is small.
36:07 This makes sense, right? Because if the the size the segment size is already very big, then this kind of late chunking is not going to add a lot of information. If the size is very small, then this kind of embedding from the document is going to bring in a lot a lot of value. So, this is something to kind of think about from a practical perspective. Okay, now let's go a step further. this is actually a very interesting topic even just for a very specific component called indexing.
36:39 well, we all learned data structures, algorithms. So, so far it's like a very sequential. We just cut them into smaller pieces. What if we can actually make them more hierarchical, tree-based? We can leverage very nice properties of of structures. So, this is actually a research from Stanford called a PeaKtor here. basically, what we are going to do is that for questions whose answer is kind of spread across the document, a single segment may not be very helpful. So, how about we actually take a hierarchical approach here?
37:18 We can build a tree bottom-up. First, we will embed each segment, and then we can collapse them. We summarize them, and we can then just embed the summaries and repeat until we have kind of like a root, like a tree here. And then at the query time, we just retrieve across all levels, and a detail of question may match the leaf node, and then a higher-level semantical question will match a summary node summary node that's like one layer up.
37:54 if you read a specific example here, let's see for Cinderella, we have two questions. What is the central theme of the story, and how did she find a happy ending? Okay. So, if you read this kind of like arrows here, DPR, you can see that it only retrieve those specific like a leaf node here. But then in the PeaKtor example, it actually the boxes we highlighted, it actually find those kind of higher-level box to represent the information.
38:23 Especially for the second question, how did she find a happy ending? I think you need to figure out like who's she, what is a happy ending, etc. So, that requires multiple layer of semantic processing. If you follow this kind of data structure, we we now talk about sequence, we talk about tree. Let's go a step further into graph. So, you can also think about how to really make sure that we we really leverage this kind of high-level information since some questions are not about one specific paragraph or even not one document. They need to be synthesized across many documents.
39:08 no specific chunk or segment will give you that answer. So, then what if we can actually build a knowledge graph first? at indexing time we just segment the documents, ask LLMs to get all the entities and then the relationship between them. we can then connect them into a graph. So, now you can actually do like graph clusterings, like different community detection algorithm here. At a query time, we do not search segments. We are going to ask each community, each cluster summary to answer the question and then merge those partial answers into a global answer. So, this is actually how you could do graph rag.
39:51 to kind of summarize, this is the last page here. In terms of graph rag, I think the reason why this is powerful is because you can really index across rich modalities. Not only text, image, you can even apply that to like biology structures, molecules, social network, citation network, knowledge graph. So, this is why the design principle behind the rag can be really really generalizable.
40:24 Okay, I think there was a question. Yeah. >> Basically, does that work with these like more complex structures where we're actually comparing against every chunk? Is like is it does it get harder to answer some questions that are like really specific because it's not actually looking at the level that that actually has the encoded information? Does that make sense? >> Yeah, so the question is about why we need this very sophisticated like segmentation approach. the reason is that if you think about the very earlier kind of chunky segmentation, they are very kind of localized. they do not take care of the broader document information. This is why we want a contextual retrieval. And then, sometimes you may also need to know multiple, segments in order to derive the answer. This is why we need to put them into a tree structure so that we can get a something higher level.
41:17 graph means that maybe it's not even within the same document. You probably need like 10 documents to figure out how the public perceive a specific topic. For question like that, you want to really look over many different documents. It's more from a community perspective. This is why you want to actually maybe segments them based on some kind of themes, topics, and then do, this kind of question answering with that. so as we go more and more sophisticated, it's actually designed to answer like more higher level questions rather than exact answer match.
41:55 however, you can imagine going back to some of the earlier question, different the chunking algorithm also carry with cost. This is why, like today, if you think about the commercial or a lot of the large-scale, QA systems, they still prefer some of the earlier technique that I mentioned since it's very fast. It covers majority of the questions we have. Yes. >> Given a query time, how do you choose which communities you need to look at for the question?
42:26 Or are all of them queried simultaneously? >> Yeah. So, this is again, think about it from a The question is how do we choose which community to focus? again, this is going to be a design choice. you can define like a relevance score here. If my question is, which sport should I look at this weekend? which game should I look at? And then you may want to fetch those clusters that are talk about sports, talk about games, etc. So, you can define some kind of relevancy estimation and use that. And then, instead of only look at the one cluster output, you can actually aggregate partial answers from multiple clusters to answer your question.
43:09 >> actual retrieval. you you need to use that LLM to attend the conference. So, here, how important is the quality of the LLM? So, if you're using a very cheap LLM, does that affect the quality a lot? >> Yeah. the question is is LLM like is is the choice of LLM sensitive to the setup here and how should we think about that? So, the LLM definitely needs to be somewhat capable, but it does not need to be state-of-the-art.
43:38 you're going to do a parental analysis in terms of the accuracy of the retrieval, the quality of the retrieval, and then the cost of LLMs or the speed of LLMs, and then you make a design choice based on that. In general, the LLM people use here are quite I would say small, capable, rather than like a very large commercial API-based models. Yes. >> So, I'm wondering like is there like an office where it goes back to the original source and actually is that an action like during the whole processing, there might be errors the errors are magnified and also quality.
44:21 Is there a way to reflect that and then actually is like that? >> Yeah, great question. So, the question is that if you think about a rag, the design pattern may suffer from compound errors where the error may cascade along the pipeline. And then, if we made a wrong, let's say retrieval in the first place, there's no way you are going to get a good answer in the end. so, we This is actually one of the limitation of the rag approach. as we move more towards agentic rag, we will add some additional components such as self-reflection or critique, etc. So, we'll add some additional components to make sure we do not suffer from that, but in practice, this is still a concern.
45:04 Okay, I will continue. so, we we now finish chunking, which is a very exciting topic, actually. now, we are going to a little bit higher level to the vector search here. So, if you think about the top key selection for rag, you are provided with a query vector, and you want to get the top key segments. you can definitely do a exact search. This is going to be a very brute-force process, where if you have n documents and then d dimension, your complexity is like O(n)d here. N is in general like, I don't know, like millions of records, so it's going to be very, very expensive if you do exact search.
45:50 again, like you can actually use approximate algorithm here. people use approximate nearest neighbor, like ANN here. You trade a little bit of recall with a lot of speed. So, we do not need to search everything. We only need to search for a small region. different techniques have been proposed, such as IVF here. You basically cluster the index, and you only do search probe in a nearest neighbor region.
46:21 You can also do quantization here. you can compress each vector into a quantized version. So, it's going to be a much shorter code. You reduce the dimension of d here. one approach I'm going to share you here is called HNSW. hierarchical navigable small world. This is actually one of the widely used approach. I will share the high-level idea here, but I'm happy to talk about the details. So, what this does is that, since it's really hard to do exact search, what if we kind of arrange the information at the different layers?
47:01 So, different layers, first all vectors we have will be in layer zero. So, they are all the bottom. As you move a little bit higher level higher level, you have fewer and the fewer samples. So, when we do search, we actually search from the top here. And then you can greedy hope towards the query. if you cannot find the answer, let's see at the layer two, you go to layer one. If you cannot find the answer here, you go to layer zero. And at each layer, you are just doing like a nearest neighbor search. So, this kind of hierarchical representation enable us to do very fast. I think here like all n hops here.
47:41 log n, sorry. This is the HNSW. If you are curious like, "Okay, how is this actually constructed?" I recommend you read the algorithm yourself. It's actually a very interesting random algorithm here. you basically insert a vector at each time. And then you pick its top layer at random. most of node will stay at layer zero. And then few node will reach the top. And then you basically link it at each layer.
48:12 the nearest neighbors and then the heuristic link across to another cluster. So, that the greedy walk across those different layers can happen. And then you do not trap a specific node in a specific layer. So, you can basically construct a layered representation. And then when you do the search, you go from the top layer to middle layer to the bottom layer. Okay. So, this actually concludes our indexing. this is again a very kind of like specific component behind the rag.
48:45 Yeah. And then I'm now going to go towards our retrieval. This is actually a component that answers a lot of the questions about why we need a DPR, do we still need a bird, what are some kind of other choices here? So, first, let's talk about different type of retrievers. I already mentioned those terms. You already see DPR. You can do sentence vectors. You can also do word overlap BM25. You can use neural systems. You can use LMs. Those are just like a different type of retrievers we can have.
49:22 So, let's look at a BM25. This is again the most widely used approach. Very, very classic. It's from 1990s. And it's still the baseline that every retriever paper reports today. I'm going to show you the results. This is literally a TF-IDF-ish setup. So, nothing is very sophisticated here. We are just going to go through this one by one. So, if you read this kind of score, BM25 score here, it's literally two components. You have IDF, you have the kind of like TF here. So, often a specific word in the query QI occurs in the document. And then you do some kind of normalization here.
50:14 And then IDF is going to look at how like NQI here refers to the docs that contain QI. So, basically, the second piece is just like a term frequency with some kind of like length normalization here. And then with those two terms, we just like get to the BM25. I'm not going to go deep into those different parameter choices here. There are different variants of this. The good thing about BM25 is that there's no training, no vector, and it's very hard to beat exact term representation.
50:55 So, I want to provide you some kind of intuitions because if you look at this, definitely feels like, "Okay, this is so complicated. How did they come up with K1 here? What exactly is doing with this kind of IDF? So, instead of walk you through with the terms, let's look at some intuitions behind of this. So, IDF, let's just take them as a whole. If you read the left side, so the x-axis is a document frequency.
51:25 that is how often a term occurs in document. And then the y-axis, we plot the IDF score. So, as you can see, BM25 here, this this line. It definitely has two shapes. So, when it when it is like less than 50%of the document, the term has a positive value. When a term occurs more than half of the documents, it actually receive a negative value.
51:56 so this is actually what we want. We want to find the sense that's very unique to the query. So, this is the intuition behind of the IDF score here. the term frequency, in the earlier thing, you see this kind of like big box here is refers to like term frequency. It has some kind of normalization with K1 here. So, let's just look at what a K1 is doing. If K1 is very small, like 0.5 here, so that's the bottom line, versus K1 is five, which is the top line.
52:28 this literally tells us about the term frequency saturation. you can see that each term actually starts at one here for a single mention. And then a higher K1 will give more credits for repeats before it flattens. small K1 here is nearly like a binary. So, the word is there or it is not. So, if you look at this, it kind of converge very earlier. It basically quantify is the word there or is it not? So, IDF decides which words matters, and then the saturation actually stops any word from being dominated in the output.
53:09 Okay, so this is just a very classic, as I mentioned, like a very fast approach to process information. Now, if we go to this kind of DPR stage, dense passage retrieval here. In the offline, what we do is that for different passages, we pass them through an encoder. This could have been BERT or Roberta or other type of architecture here. You gather different vectors. You store them into your vector index.
53:39 During the online fashion, whenever we get a query, we pass it to a query encoder. And then we can do the dot product. And then you do the top key here. So this is a neural approach. And then one thing I do want to mention is that the passage encoder and the query encoder, they are two separate BERTs here. A quiz you need to answer yourself is which side is expensive. Is it this one or is this one? One's done offline, one's done online.
54:11 one minor thing that I do want to mention is that if you want to go deep, you can also see how we train DPR here. so what do we do is that once you get the representation from the question encoder, the passage encoder, we do a inner product similarity here. And then you can just pass them into a normalization here. so the loss function here is what we call a contrastive loss. That is the negative log soft max of the positive retrievals against the negatives. So that's referred as the P plus here versus P minus.
54:51 So think about the idea. The idea is that we want to promote those correct search to be closer. And then we want to penalize those incorrect or less relevant search. so one of the key design question here is where do the negative come from? I think you can use the other passages in the same batch since you do batch processing. which This is what we call a in-batch negative. Or you can use BM25 hard negatives. That is the passage that the match the question's words, but do not contain the answer. So, you give it a really hard negative here. And those hard negatives are what teach the model to go beyond just like word overlap.
55:39 so you can see that the right line here, this shows how the gradient updates both encoders. So, this is the architecture behind the DPR. I'm going to show you more equations, but they literally means how we do the evaluation since, some people may get a confused as we have so many many different metrics whenever it comes to rank. let's start with a very simple one, hit at K. Again, as the name mentions, it basically means that if I look at the top K positions, is that content relevant or not? So, you basically use this kind of, index function and then look at the whether, the passage is relevant or not, and then you do a normalization.
56:28 So, this is very straightforward, hit at a K. field at a K. Again, same. you just look at, is this relevant or is this not? This is the metric we mentioned earlier for contrast retrieval, and it basically complements hit at a K here. Okay, a much, more common metric, but look a little bit, scary, but let's unpack them. so this is called a NC NDCG at K.
57:00 And then in order to understand this, let's look at the DCG here. It basically means that for the for the current list, if I look at the top key passages, this is their relevance. And then you you basically like discount them by their rank position. So, you basically get like how relevant they are with regarding to their ranking. So, this give you a more accurate description of the relevance. and then since you have ground truth, the IDCG here refers to if you look at your ground truth retrieval and then give them the relevant score and rank key what ideal situation. And then you do a normalization here to refer to the outcome.
57:44 So, again, nothing is is like really new. We are just trying to walk through the the matrix here. Okay, I have two more metrics before we finish. So, the next one is called MRR here. this is also a widely used metric. So, you literally just going to look at the rank of the specific first relevant query and then where is the rank? And then you do the average across all queries. recall the key is also intuitive.
58:17 Like if you look at the top retrieved content, did we find those in the top K? And then across all the relevant passage we have for that query. So, this is a lot of the metrics. you may encounter some of those in your implementation. With those contacts, now let's look at the results. So, DPR is also a very powerful technique. when researchers compared with BM25, you can see that it actually outperforms four out of five data sets.
58:54 this is the match I think Yes. So, here the contrastive loss is actually trained with two parts. The in-batch negative as I mentioned as well as BM25 hard negatives. So, this is a trained DPR and you can see the results compared to BM25 and then the combination of both of them. so single here refers to training the DPR only use a individual data set and then multi means that you are going to combine different data sets to train the DPR.
59:30 two more interesting things that I want to highlight. So on this figure you can see that with the top key accuracy how it kind of like evolve over different training size here. It turns out that only 1,000 annotated pairs you can actually train DPR much better than BM25 here. And then again like more training examples help. So you see this kind of higher line here.
60:01 with no actual pre-training DPR with the 1,000 or like 2,000 QA pairs actually beats like a RAM which is a earlier system from Google that it trains the entire pipeline end-to-end. So this is indeed a very very powerful technique. So last thing that I want to mention here related to this kind of retrieval. The two approach that I mentioned to you so far BM25 they cannot handle semantic paraphrase ish scenarios. And then DPR they will miss the exact match such as specific code numbers, product IDs, etc.
60:47 The reality is that we want to take the best of both world. So what if we can do a hybrid search? We can run both retrievers and then fuse them through their rank list. And then one technique that you will come across is called a reciprocal rank fusion. It give you approach to merge positions instead of raw scores because the score of ranking actually cannot be combined easily. So, we are going to think about how to merge positions here.
61:21 so, again, this approach no per corpus tuning and it works with any number of retrievers. I'll stop here in case there are any questions. >> in the slide you just showed where you're doing the dot product between the query vector and the position vectors to retrieve the top K passages, what is the What is the result like? Is it the index of those passages >> Yeah, so purely you look at the index of those passages, but like use the index to gather their actual embeddings, right? A lot of the embeddings for each segment's passage already processed offline. So, you use the index to get their embeddings and then do the inner product there.
62:08 Any other questions here? I think those are a lot of the metrics, but they literally are more from an illustrative perspective. So, you can use them to understand tables and results. Okay, if there is no more question, I'm going to go a little bit deeper here in terms of enco-encoder. so, this lecture literally contains everything you need to know about the retrieval. so, it really contains like many many different components. so, I would really divide a lot of the representation process into two parts.
62:45 First, you can have what we call a bi-encoder. your query and passage, they are encoded separately. you can also think about what if we could have a cross-encoder. That is, instead of these like two separate encoders for my query, for my passage, I'm going to do this cross-encoder. The query and passage go through the model together and we do full attention across both and then we use the results to do some further processing.
63:16 Similarly to late trunking, we also have late interaction here. And this page is actually very important, so I want to decompose it a little bit. So, the very left side, this is you have a query, you have a document, you do information processing of them separately, and then you look at their inner product. Now, think about what may go wrong in the process. Second is that I'm going to maintain a big matrix here, query and document, and then I process everything together.
63:50 Third is that what if I just concatenate the query and document together, pass it through a transformer or any network, and do it together. The last one is I pass the query through a network, I pass the document at through a network, and then I do some kind of inner like product there in interesting way, and then I got an output. So, now think about what are the pros and the cons of each setup.
64:21 Anyone want to give it a try? Yes. >> It's more faster, but it's it's lost it lost its source, and then but it doesn't care about the position. the sequence that's that's So, if I'm the more it's more complex, it take more time for each query. Because it's more more complex for attention to care about the positions and the selection of the positions.
64:56 >> Yeah, that that's a that's a beautiful answer. So, just to repeat, so, the left side is actually very fast. Actually, the most complicated one is probably B and the C here, especially for C, since you need to put the document and the query together in the same matrix. And then D is actually somewhere in the middle. One thing you do need to remember is that documents, we have a lot of documents. So, documents are representations in general. If we can process them offline, we prefer that. So, you also need to think about decoupling of them. So, the fashion we have in C you really cannot like pre-compute many of them in advance, right? Versus D and A, you can actually easily just like get this blue part pre-processed, and then later you just do a query at inference time, and then their product calculation there. So, this is actually the key difference here.
65:52 the later interaction I'm going to mention for this Colbert here refers to that we're going to keep one vector per token, and then we'll encode the query and the passage still independently. But, then we do a interaction only at the scoring time. And then this is actually what we call max sim here. For each token in the query, we're going to find the token in the document that match this token the most, and then we take that score, and we add it across all the query terms.
66:27 So, this is actually the score we used here. just to zoom in a little bit. So, you have both the query encoder, document encoder. The document encoder is something we can process offline. And then each time we're going to take each specific token, find the which token match them first best from the document encoder, and then do this for every single token there in the query. so, again this is a lot of content to remember, but the high-level idea is that Colbert actually works pretty well.
67:06 If you can see that compared to a lot of the approach we mentioned earlier, it definitely give you much higher number compared to BM25 and a lot of the baselines. on this page you can also see latency get a mention here, and the different type of recall. to summarize this part, so there are different choices. when you build a rag, especially if your application domain is very diverse, you work with graph data, you work with image data, you work with different documents. A document on social media is going to be very different than a financial document that contains a lot of specific entities.
67:51 so if you look at this, we need to think about their pre-precompute whether we can do them offline. The query latency. What a situation is best for which specific retriever? And then where do they fail or break? And then this table actually give you some summarizations based on the empirical results in the two papers we just mentioned. Okay, any quick questions here?
68:22 if not, we're going to finish with the agentic rag. so so far, if you look at the rag that I've mentioned, it's a lot of kind of probability models, encoding, index, etc. But we have AI and agents right now. So everything so far feels like they are not really have the initiative to do something. because the system cannot decide whether to retrieve, what to ask, and when to stop.
68:57 what if we could actually make a retrieval an action that the agent takes? So there will be three decisions they need to make. retrieve or answer directly. Do I need actual information or not? What a query to issue if I need to search additional information? Whether the result is good enough that I should stop. So this is more from a agentic perspective to leverage rag. And I'll share some of the widely used agentic rag system here.
69:26 the first one is called a self-rag. So, how about we teach one model to retrieve, critique, and then generate here? you can just give them some special reflection tokens along with the text. So, if you look at this specific example, how did the US states get their names? step one, we're going to retrieve on demand. The model starts writing and emits retrieval token here when it decides that it needs evidence to answer your question.
70:00 step two here, it actually generates a segment for each retrieved passage in parallel. In step three, it actually critique each response or each segment. And is the passage relevant? Is the segment supported? You ask a lot of question here. It then rank the segments and it keeps the best. So, decisions one and the three are actually trained here into a generator itself. the cost is the training pipeline with the critique labeled data. So, these are the parts we need to have it ready.
70:38 So, through this process, you basically combine this kind of rag design principle with a lot of the self-critique, self-reflect natures of agentic systems. C-rag actually push it further or take a very different approach. How about we do not touch the generator, and we put a evaluator between the retriever and the generator? This evaluator is going to grade the retrieved documents and give us a score, a confidence score, which map to an action. Correct? If the score says this is correct, then we'll keep them.
71:17 we can still refine them, split them into different parts. if it tells us that this is incorrect, then we need to throw them away, rewrite the query, and the search the web again. So, there is more like a judge there. If the query is very ambiguous here, then you need to do both. So, this kind of design is really like a plug-play on any kind of rack stack we can we can we can implement. It answers like a decision tree with a separate very lightweight model, and it does not need to touch the generator at all.
71:56 So, with more and more like kind of reasoning capabilities, people are also looking at it. Can we use like R1 ish thinking to improve the the search process? So, this is a recent work called search R1. Instead of like hand designing the loop, how about we learned with RL? so, this is actually a real trajectory from a search process. The question is who is who is older here? And the model thinks, search, read what comes back, and then think again, search again, and eventually answer your question. It actually searched three times and refined the query each time, and then no one needs to write this plan on how the agent should work. So, remember the difference between workflow and agents here.
72:47 so, one thing to point out here is that a lot of the the passage we are going to retrieve may get truncated here. So, the trace that you see here does not actually reflect the the detailed process. So, how do we train it? we are not going to go deep into PPO and the GRPO here. We we'll have some lectures later this course, but I only want you to look at the architecture and pay attention to the search module.
73:20 So, the entire process here is very similar to a classic PPO or GRPO. Instead, we only add those two additional components here. So, whenever you are going to get a policy, we will do search first. So, that's the only component we added there. Nothing else here. So, basically, during a roll out, the policy generates text, and every time it will emit a search query, and that hit the search engine, and then the results come back into the context as some information tokens. The reward is going to be very classic as other type of reward is only the outcome.
74:00 Is the final answer correct or not? So, this is how you could potentially do it with search R1. The process actually works pretty well. Researchers show that compared to R1, SFT rag, search O1, search R1 actually have much better performance in the process. So, this is actually what do we have for the agentic rag. So, rag as a design principle, you can actually use it in many, many settings. This is why when agentic systems come out, we can still use similar principle here.
74:40 The last two minutes, I'm going to share you some kind of figure mode here. This actually goes back to some of the question asked earlier. Rag is powerful. Some people would see that a rag is out of date today. Others would see that it's really hard to anticipate what may go wrong with rag. So, here, we break them into three parts. The retrieval part, how rag would have failed. You can imagine maybe it didn't catch the right evidence. Maybe the embedding, the offline documents we have are just so out of date.
75:15 Maybe the search actually look at some content which we should not look at. So, all of those questions may happen at the retrieval side. From a reader side, there may be like lost in the middle. Models may get distracted. Evidence we have may conflict with each other. That is, when RAG go outside to fetch evidence, they actually got two evidence. They do not agree with each other. So, how should we think about that?
75:46 From a loop like retriever generator perspective, there may be compound errors. that is something some mistake happened earlier may affect later decisions. there may even be prompt injections in the search process. What if bad actors actually added something to your search the documents and then really attack your entire pipeline. So, those are all the issues we can or we are going to mention about RAG later.
76:19 with that, this is all what we are going to cover for today's class. Thank you all and happy to take a more questions.