RAG Explained: Embeddings, Sentence BERT, and HNSW Vector Databases

[00:00:00]hello guys welcome back to my Channel today we are going to talk about retrieval augmented generation so as you know large language models can only answer questions or generate text based on their training data so for example if we have a language model that was trained in 2018 and we ask it about the covid probably the language model will know not know anything about the covid and one of the way to augment the knowledge of language model is to fine tune the model on the latest data but there is another technique called retrieval augmented generation which is very useful especially for question answering and it has been also been used recently by Twitter to create their new language model called Gro so Gro can access in real time all the data from the tweets and answer question on the latest trends so in this video we will explore what is retrieval augmented Generation all the pipeline all the pieces of the pipeline and the architecture behind each of these building blocks so let's review the uh topics of today uh I will give a brief introduction uction to language models so what they are how they work how we inference them we will then move on to the pipeline that makes up the retrieval augmented generation with particular reference to the embedding vectors and how they are built what they are and the we will also explore the architecture behind sentence birth which is one of the ways to generate embeddings of sentences and then we will move on to Vector databases what they are how we use them and how the algorithm of a vector database works in finding a particular Vector uh that we are looking similar to a query uh what I expect you guys to already know before watching this video is for sure you are a little familiar with the Transformer we will not be going so much in in detail but at least you are familiar with the basic building blocks of a transformer and that you have watched my previous video about bird so if you're not familiar with these topics please I recommend you watch my previous video on the Transformer and my previous video on bird they will give you all the necessary background to fully understand understand the current video now let's start our journey we will start by introducing first of all my cat oo because uh I will be using him for a lot of the examples in my video so if you are not Chinese you don't know how to read his name which is oo which stands for the biscuits Oreo because he's black and white so let's get started the first thing we be talking about is language models now what is a language model well a language model is a probabilistic model that assigns probabilities to sequence of words in practice a language models allows us to compute the following what is the probability that the word China comes after in the sentence Shanghai is a city in so the language model allow us to model the probability of the next token given the prompt and we usually train a neural network to predict these probabilities neural network that has been trained on a very large corpora of text is known as a large language model when we train large language models we usually have a very big corpora of text that is made of colle which is kind of a collection of documents now often language models are trained on the entire Wikipedia or millions of web pages or even thousands of books because we want the language model to acquire as much knowledge as possible and we usually use a Transformer based architecture to mod to create a language model for example llama is usually known as a decoder only Network and bird is usually known as an encoder only Network um because llama has the last part of llama is the basically the the coder of the Transformer without the cross attention plus a linear layer plus a soft Max while bird using only the encoder side and then it has some heads that can be a linear layer uh depending on the task it is we are using it for to inference the language model we usually build a prompt and then we ask the language model to continue this prompt with by iteratively adding tokens such that the tokens that the language model adds make sense in uh in continuity with the prompt so for example here I'm asking chat gbt to to to continue a joke and chat gbd continues the joke by adding few more tokens that when read in their entirety they make sense they are cerent with what I actually wrote you are what you eat so a language model can only output text and information it was trained upon this means that if we train a language model only on English content very probably it will not be able to Output Japanese or French to teach new Concepts to new content to new information to a language model we need to fine-tune the model however fine tune fine tuning is has some cons for example it can be expensive in term of computation power necessary to fine tune the number of parameters of the model may not be sufficient to capture all the knowledge that we want to teach the the model itself so for example llama was introduced with the 7 billion 13 billion and 70 billion parameters why because with 7 billion parameters you it can capture some some knowledge but not as much as the 70 billion parameters model so the number of parameters is a limitation on the amount of knowledge the language model can acquire also fine tuning is not additive uh for example if you have a model that is trained on English content and then you heavily fine tunit on Japanese content the model will not be at the end of the fine tuning will not be as proficient in English and as in Japanese but it may forget some of the English content it was initially trained upon so is we say that the fine tuning is not additive to the knowledge of the language model of course we can compensate for the for the fine-tuning with prompt engineering for example it is possible to ask the language model to perform new task task that it was not specifically trained upon by working with the prompt for example this is a few short prompting technique and the following is an example so uh we first give an EXT instructions to the language model here is the instruction on what is the task the language model is going to perform then we give the language model some example to how to perform this task and then we ask the language model to perform it for example the task here is oo is a cat that likes to play tricks on his friend Umar by replacing all the names in everything he writes with meow for example Umar writes Bob runs a YouTube channel and oo will modify it to meow runs a YouTube channel so what happens if Umar writes Alice likes to play with his his friend Bob how would oo modify it the language model comes up with the right answer which is meow likes to play with his friend meow so J gbt in this case was not um trained on performing this task but by looking at the prompt and the example that we provided it it was able to come up with the right solution and we can use prompt Engineering also for question answering with the same kind of reasoning so we build a very big prompt that includes an instruction part so you are an assistant trained to answer questions using the given context in which we provide some context which is a piece of text in which to retrieve the answer and then we ask the question to the language model how many parameters are there in Gro zero so Gro is the language model that is introduced by Twitter and it's a language model that uh can also access the the latest tweets and we will see later how but the point is I am asking the language model so CH GPT to tell me about Gro zero so very probably chbt was not trained on the it doesn't know about the existence of this Gro zero because it came out very recently so the model chb was able to retrieve the answer by looking at the context so in this case for example he says Croc zero the Prototype llm mentioned in the provided context is stated to have been trained with 33 billion parameters because the the chbt was able to access the context in which we talk about the how many parameters there are in Gro zero which is this line after announcing XI we prototype we train the Prototype llm with 33 billion parameters so the answer is correct and this um this kind of way of working with the prompt is actually very powerful but also uh fine tuning is not necess necessarily wrong or the wrong way to deal with this lack of knowledge problem in the language models because it usually when we find in a model on a specific uh particular content the it results in a higher quality results compared to just prompt engineering and also as you saw before to ask a question to chat GPT we had to build a very big prompt so it means that the number of tokens that we are giving to the model is quite big the more we have uh the bigger the context that we need to provide to answer a particular question and we know that the more context we give the more information the language model will have to come up with the right answer so usually we need a bigger context but the problem is uh bigger context is also computationally expensive so by fine-tuning actually we can reduce this content size because we don't need to provide the context anymore because we are fine tuning the the language model on the specific data on which we will ask questions for so to a language model that has been fine tuned we just need to ask the question so how many parameters are there in gr zero without providing all the context and if the language model has been fine-tuned correctly it will be able to come up with the right answer now we need to introduce the retrieval augmented augmented generation pipeline because that's our next step and we will explore each building block that makes up the pipeline so imagine that we want to do question answering with retrieval augmented generation compared to what we did before before we did it with prompt engineering so uh how many parameters are there in Gro zero this is our query and uh imagine we also have some documents in which we can find this answer these documents may be some PDF documents but they may also be web pages from which we can retrieve this answer what we do is we split all these documents or pieces of text into chunks of text so small pieces of text for example a document may be made up of many pages and each page may be made up of paragraphs and each paragraph is made up of sentences in the usually we split each of these documents into small sentences and also the web pages are split in the same way we create embeddings of these sentences such that each embedding is a vector of a fixed size that captures the meaning of each sentence then we store all of these embeddings into a vector database and later we will see all these embeddings and Vector database how they work then we take also the query which is a sentence we convert it into an embedding using the same model that we have used to convert the documents into embeddings we search this embedding so this query embedding into our database which already have many embeddings each representing a sentence from our document and it will come up with some results with the best matching embeddings for our particular query and each embedding is also um associated with the piece of text it comes from so the vector database is also able to retrieve the original text from which that embedding was created so if we are for example how many parameters are there in gr zero the vector database will search all of its embedding and will give us the embeddings that best match our query so probably it will look for all the piece of text that talk about Gro zero and the parameters it contains now that we have the context and the query we create a template for a prompt so just like the The Prompt we have used before so you are an assistant train to answer questions using the given context we paste the context and the query inside of the prompt template and just like before we feed it to the language model and then the language model will be able to answer our question by using the context provided so we are with retrieval augmented generation we are not fine-tuning a model to answer the questions we are actually using a prompt engineering but we are introducing a database here called the vector database that can access the context given our query so it can retrieve the context necessary to answer our particular question feeded to the language model and then the language model using the context and our question will be able to come up with the right answer very probably now let's talk about embedding vectors what they are and how we work okay first of all why do we use vectors to represent words for example given the words Cherry digital and information if we represent embedding vectors using only two Dimensions so as you remember in the vanilla trans former each embedding Vector is 512 Dimensions but imagine we are in a simpler world we only have two Dimensions so we can plot these embedding vectors on a XY plane and what we do is we hope to see something like this so that words with similar meaning or words that represent the same concept point in the same direction in space so for example the word digital and the word information are pointing to the same direction in space such that the angle between words that have a similar meaning is small so the angle between digital and information is small and the angle between words that have a different meaning is bigger so for example the word cherry and digital have angle that is bigger compared to digital and information indicating that they represent different concepts imagine we have another word called tomato we expect it to point to this vertical Direction here such that the angle between Cherry and tomato should be small how do we measure this angle we usually use the cosine similarity to measure the angle between vectors and later we will see the formula of the cosine similarity now how did we come up with the idea of representing words as embeddings the first idea is that words that are synonyms tend to occur in the same context so surrounded by the same words for example the word teacher and the Professor usually occur by the word School University exam lecture course Etc and vice versa it we can also say that words that occur in the same context tend to have similar meaning this is known as the distributional hypothesis this means that to capture the meaning of a word we also need to have access to its context so to the words surrounding it but this also means that this is also the reason why we employ self attention in the Transformer model to capture the contextual information of each token so as you remember the Transformer model we have this self attention the self attention is a way to relate each token with all the other token in the same sentence uh based also on the position each token occupies in the sentence because we have the concept of positional encoding so the self attention access two things to calculate its score of attention the first is the embedding of the word which captures its meaning the second information it access is the positional encoding so that words that are closer to each other are related differently to words that are far from each other and this self attention mechanism modifies the embedding of each word in such a way that it also captures the contextual information of that word and the words that surround it uh we we train birth on a very particular task which is called the musked language model task to capture information um to create the embeddings of birth this musked language model task is based on the clothes task and we human do it very often let me give you an example imagine I give you the following sentence Rome is the something something of Italy this is why which is why it hosts many government buildings can you tell me what is the missing word well of course the missing word is capital because by looking at the rest of the sentence is the one that makes the most sense how did we come up with the word capital for the missing word well we look at the words that were surrounding the blank space so it means that to the the word Capital depends on the context in which it appears on the words that surround it and this is how we train birth we want the self attention mechanism to Rel all the input tokens with each other so that Bert has enough information about the context of the missing word to predict it for example imagine we want to train bird on the musked language model task and we create an input with the musked word just like before so Rome is the something something of Italy which is why it hosts many government buildings we replace the blank space with a special token called musk this becomes the input of birth which is made of four tokens we feed it to Bert Bert is a Transformer model so it will output its a sequence to sequence model so if the input is 14 tokens the output will also be 14 tokens we ask Bert to predict the fourth token because it's the one that has been masked out we know what is the word which the word is capital so we ask we calculated the loss based on what is the predicted fourth token and what it should be the actual fourth token and then we back prop propagate the uh the loss or to update all the weights of the model when we run back propagation bir the model will also update the input embeddings here so the input embeddings by the back propagation mechanism will be modified in such a way that this word so the word Capital so the embedding associated with the word Capital will be modified in such a way that it captures all the information about it context so the next time bir will have less troubles predicting it given its context and this is uh actually the one of the reason why we run back propagation because we want the model to get better and better by reducing the loss what if I told you that actually we can also create embeddings not of single tokens but also of entire sentences so we can use the self attention mechanism to capture also the meaning of an entire sentence what we can do is we can use a pre-trained birth model to produce embeddings of entire sentences let's see how well suppose we have a simple input sentence for example this one made of 13 tokens called over Professor always gives us lots of assignments to do in the weekend we feed it to birth but notice that I removed the linear layer from birth and I will show you why so the first thing we do is we notice is that the input of the self attention is a matrix of shape 13 by 76 8 why because we have 13 tokens and each token is represented by an embedding with 768 Dimensions which is the dimension uh which is the size of the embedding Vector in birth base so the smaller birth pre-trained model the self attention mechanism will output other metrix with the the shape 13 by 768 so 13 tokens each one with its own embedding of 768 dimensions and the output of the self attention is an embedding that captures not only the meaning of the word or its position in the sentence but also all the contextual information all the relationship between other words and the current word so the output will be 13 tokens each one represented by an embedding of size 768 what we do now each of them is representing kind of the meaning of a single word right so what we do we can average all of them to create the embedding of the sentence so we take all these vectors of size 768 we calculate the average of them which will result in a single Vector with 760 dimensions and this single Vector will represent the sentence embedding which captures the meaning of the entire sentence and this is how we create the embedding of a sentence now how can we compare sentence embeddings in to see if two sentences have similar meaning so for example imagine one sentence is talking about the the query for example before was talking about how many parameters are there in Gro zero and then we have another sentence that talks about how many parameters there are in grock zero so how can we relate these two sentences we need to find a similarity uh function and what we do is we usually use a cosine similarity because they are both vectors and the cosine similarity can be calculated as between vectors and it measures the cosine of the angle between the two vectors a smaller angle results in high cosine sing similarity score while a bigger angle results in a smaller cosine similarity score and this is the formula of the cosine similarity score but there is a problem so nobody told Bert that the embedding it produces should be comparable with the coine similarity so Bert is outputting some embeddings and then we take the average of these embeddings but nobody told birt that this EMB embeddings should be in such a way that two similar sentences should produce similar embeddings um how can we teach birth to produce embeddings that can be compared with a similarity function of our choice which could be aign similarity or the Idan distance well we introduce a sentence birth sentence birth is one of the most popular um models to um to to produce embeddings for entire sentences that can be compared using a similarity function of our choice in this case it's the cosine similarity score so sentence birth was introduced in a paper called sentence birth sentence embeddings using siis birth networks and we will see all of this what does it mean what is a s Network now imagine we have um two sentences that are similar in meaning for example my my father plays with me at the park and I play with my dad at the park we uh the the first one we will call it sentence a and the second one we will call it sentence B we feed them to birth so each of them will be an sequence of tokens for example this one may be 10 tokens and this one may be eight tokens we feed it to bird which will produce output of 10 tokens and eight tokens then we do the pulling the mean pulling that we did before so we take all these output tokens and we calculate the average of them to produce one only uh back VOR of Dimension 768 in case we are using birth base or bigger in case we are using a bigger birth the first one we will call it sentence embeding a so the first Vector is the embeding of the sentence a and the second one is the embedding of the sentence B we then measure the cosine similarity between these two vectors we have our Target coine similarity because we are training this uh birth this model so we for example given these two sentences which which are quite similar in meaning we may have a Target that is very close to one because the angle between them will be small we we hope that the angle between them should be small so we calculated the loss because we have a Target and the output of the model and then we run back propagation on to update all the weights of this model now as you can see this model is made up of two branches that are same so in structure but this is called the Camis Network which is a network that is made of two branches or more branches that are same with each other with respect to the to the architecture but also with respect to the weights of the model so what we do actually when we represent this hes networks we represent it at two branches but when we code this model actually we will actually only have one model so only one branch here that will be produce coine similarities and what we do on a at operating level is that first we run the sentence a through this uh model then we run the sentence B also through this model we calculate the coign similarity between these two output and then we run back propagation such that the back propagation will only modify the parameters of this model here but when we represent it for showing we actually uh we represent it as two branches but remember that there are not actually two branches it's only one branch it's only one weights only one architecture and the same number of parameters this way the birth will if you train birth the sentence Bo like this it will produce embeddings but in such a way that the similar uh sentences have similar cosine similarities have high cosine similarity um so we can compare them using the cosine similarity uh measure also if if you remember birth produces at least birth base produces and beddings of size five 768 if we want to produce a sentence embeddings that are smaller than 768 Dimensions we can include a linear layer here to reduce the dimensions for example we want to go from 768 to 512 in the paper of sentence bird actually they not only use the mean pooling that we used so to calculate the average of all the tokens output by birth to produce one uh Vector that represents the meaning of the entire sentence but they also use max pooling and another technique that they use is the CLS token so if you remember the CLS token is the first token that we give as input to birth and it's also the first token that is output by birth and usually this because of the self attention mechanism this CLS token captures the information from all the other tokens because um of how the self attention mechanism works and uh however the the sentence birth paper they have shown that both me methods so the max pooling and the CLS token don't perform better than mean pulling so they they they recommend using mean pooling which is also one of actually what is used in production nowadays okay now let's review uh again uh what is the pipeline of retrieval augmented Generation Now that we know how embeddings works so we have our query which is how many parameters are there in Gro zero then we have some documents in which we can find this answer so the documents may be PDF documents or web pages we split them into single sentences and we embed these sentences using our sentence birth our sentence birth will produce vectors of a fixed size suppose 768 and we store them all these vectors in a vector DB we will see later how it works the query is also converted into a vector of size 500 12 um 768 dimensions and we search this uh query in the vector DBS how do we search we want to find all the embeddings that best match our query what do we mean by this we mean all the embeddings that I have that when we calculate the cosine similarity score with our query it results in a high value or if you are using another similarity score for example aan distance the the distance is small depending on what distance we are using the coine similarity or the idian distance this will produce the top embeddings that best match our query and we map them back into the text from which they originated from this will produce the context that we feed into our prompt template along with the query we give it to the large language model which will produce the answer as we saw previously augment the knowledge of a language model we have two strategies fine tuning on a custom data set or using a vector database made up of embeddings we can also use a combination of both for example by fine-tuning for a few EPO and then using a vector database to complement with knowledge retrieved from the web whatever strategy we decide to proceed with we need a reliable scalable and easy to use service for building our retrieval augmented generation pipelines that's why I recommend gradient gradient is a scalable AI Cloud platform that provides simple apis for fine-tuning models generating embeddings and running inference thanks to its integration with popular Library Lama index we can build retrieval augmented generation pipelines with few lines of code for example we select the model we want to use in our case it's Lama 2 we Define the set of custom documents that the model can use to retrieve answers we Define the model that we want to use to generate embeddings ask a question for example do you know anyone named oo it voila thanks to the power of retrieval augmented generation the model can now retrieve information about our channels mascot oo gradient helps us build all aspects of a retrieval augmented generation pipeline for example we can also fine tune models on custom data as well as generate embeddings with gradient you have total ownership of your data as well as the weights of fine-tune models open source models are great because they save time on development and the bugging as we have access to their architecture and the support of a vast community of developers gradient also integrates with popular libraries llama index and L chain check the link in the description to redeem your $5 coupon to get started today with gradient let's talk about let's talk about Vector databases what they are and how they're matching algorithm works so how can the vector database search our query in all the vectors that it has stored okay a vector database stores vectors of fixed Dimensions called embeddings such such that we can then query the database to find all the embeddings that are closest or more similar to our query using a distance metric the cosine similarity or thean distance the vector database uses a variant of the KNN algorithm which is stands for the K nearest neighbor algorithm or another similarity search algorithm but usually it's usually a variant of the K&N algorithm and the vector databases are not only used in retrieval augmented generation pipeline they are also used for finding for example similar songs so if we have songs we can create embeddings of them so some embedding some Vector that captures all the information about that song and then we can find similar songs given one one for example we have user who want to find all the similar songs to a given one we will create the embedding of that song and all the others We compare them using some similarity score for example the cosine similarity score for example also Google Images they search similar images using a similar technique so using an embedding um space in which they produce the embedding of a particular image and all the other and then they check the one that match best we can also do the same with the products Etc now K andn is an algorithm that allow us to compare a particular query with all the vectors that we have stored in our database sort them by distance or by similarity depending on which one we use and then we keep the top best matching for example imagine we have a query so how many parameters are there in Gro and imagine we have a database Vector a vector database made up of 1 million embeddings because actually 1 million is not even a big number because if you consider that um uh suppose Gro for example that is accessing the Tweets in real time every day I think we have thousands hundreds of thousands of tweets if not millions of tweets so actually the amount of vectors it has it's actually in the order of billions I think not even Millions so actually Millions looks like a big number but it's not especially when we deal with the textual data also from the web we have billions of web pages that we may need to index so what we do for example in this KNN with the naive approach which is the most simple way of matching a query to all the other vectors is to compare this query with all the other vectors given our uh cosine similarity function for example we may we may have this the with the first Vector it may be 0.3 the second 0.1 0.2 etc etc then we sort uh the we sort them by cosine similarity score so with for example the highest one for example this one should be the first one then the this one should be the second one etc etc and we keep the top K so the top three or the top two depending on how we choose K now this is actually a very simple approach but it's also very slow because if there are and the embedding Vector so in this case 1 million and each one has D Dimensions so in this case for example in the case of birth Bas is 768 the computational complexity is in the order of n multiplied by D which is very very very slow let's see if there are better approaches and we will be exploring one algorithm in particular that is also used U right now in the most popular Vector DBS which is called the hierarchical navigable small words now what we the idea is that we will trade Precision for Speed so before what the algorithm we saw before so the naive K&N U which performs very slowly but it's actually precise because each query the query is compared with each of the vectors so it will always produce accurate results because we have all the possible comparison done but do so to reduce the number of to oh increase the speed we need to reduce the number of comparisons that we do and the metric that we usually care in similarity search is recall so the recall basically indicates that if our suppose that in before the best matching Vector is for example this one and this one and uh this one uh we want our top three query so K&N to R retrieve them all all three of them but imagine it only returns two in this case we we have that the the query returned only two of the best matching Vector so we will say that the recall is 66% or 2/3 so basically the recall measures how many relevant items are retrieved among all the relevant item that it should have retrieved from our search and we will see one one algorithm in particular for approximate nearest Neighbors which is called hierarchical navigable mod words now hierarchical navigable small words is actually used is actually very popular nowadays in Vector databases and in particular it's also the same algorithm that powers the database quadrant which is also the open source Vector database uses by Twitter's Gro llm for example this is the exchange of tweets that I saw the other day between Elon Musk and the team of quadrant in which they uh quadrant says that actually the gro is accessing all the tweets in real time using the vector database which is quadrant and if we check the documentation of this Vector database we will see that the quadrant currently only uses the hierarchical navigable small words as the vector index so this is the algorithm that powers the word the database that is currently used by Twitter to um introduce retrial augment generation in its large language model Gro the first idea behind this hierarchical navigable small words is the is the idea of the six degrees of evolution so actually the hierarchical navigable small words is an evolution of an earlier algorithm called navigable small words which is an algorithm for approximate nearest neighbors that we will see later which is based on the idea of Six Degrees of Separation so in the 1960s there was an experiment which is called the mgram experiment which wanted to test the social connections among people in the USA the participants who were initially located in Nebraska in cence were given a letter to deliver to a person that they didn't know they did not know and this person was in Boston however they were not allowed to send the letter directly to the recipient instead they were instructed to send it to someone who who could best know this target person at the end of the mgram word experiment they found that the letter reached the final recipient in five or six steps creating the concept that people all over the world are connected by six degrees of separation and actually in 2016 Facebook published a blog post in which they claimed that one the 1.59 billion active users on Facebook were connected by an average of 3.5 Degrees of Separation this means that between me and Mark zukerberg there are 3.5 connections which means that on average of course which means that I have a friend who has a friend who has a friend who knows Mark Stenberg and this is the idea of the degrees of separation so let's see what is this navigable small words now the navigable small words algorithm builds a graph that just like Facebook friends connects connects close vectors with each other but keeping the total number of connections small for example every Vector may be connected with up to other six Vector like to mimic the six degree of SE separation for example imagine we have a very small database with only 15 vectors each one representing a particular sentence that we retrieved from um our knowledge source which could be documents or web pages and we have a graph like this in which for example the first text is about the Transformer which is connected to another piece of text that talks about the Transformer model then we have another text that connects the three with the two which is now talking about the can canc with AI so diagnosing cancer with AI and etc etc now how do we find a given query in this particular graph so imagine we have uh our query which is how many encoder layers are there in the Transformer model how does the algorithm find the K nearest neighbors so the best matching K vectors for our query the algorithm will proceed like this it will find first of all an entry point in this graph which is randomly chosen so we randomly choose among all these vectors one node as a random uh as a entry point we visit it and then we compare the similarity score of this query and this node and compare it with the similarity score of the query with the friends of this node so with the number SE with the node number seven and the node number two if one of the friends has a better similarity score then we move it to move it there so the number two for example may have a better similarity score with the Q compared to the number five so we move to the number two and then we do again this process so we check what is the cosine similarity score between the node number three and the query and we compare it with the cosine similarity of the vector number two with the query if the number three has a better cosine similarity score we move there and we keep doing like this until we reach a node in which his the friends of this node so the number eight and the number six don't have a better cosine similarity score with respect to the query compared to the current one so this uh number four has the best cosign similarity score among all of his connections among the 01 08 and the 06 so we stop there and we have visited many nodes basically we order them from the best matching to the lowest matching and we keep the top k also we repeat this search many times by choosing different random entry points and every time we choose we sort all of the results by similarity score and then we keep the top K and these are the best matching K nebor uh K nearest neighbors using the navigable small words algorithm if we want to insert a vector in this graph we just do what we did before so we actually search uh a given for example you want to insert this query from for example we will just do it like a search and then when we have found the top K we just connect the query with the top K and that's how we insert a new item into this graph the second idea of the na hierarchical navigable small words is based on another data structure that is called the skip list so to go from navigable small words to uh hierarchical navigable small words we need to introduce this new uh data structure so the skip list is a data structure that maintains a sorted list and allows to search and insertions with an average of logari logarithmic time complexity for example if we want to search the number nine what we can do in this first of all as you can see this uh this is not only one linked list we have many linked list levels of linked list we have the level zero the level one the level two the level three the bottom level has the most number of items the more we go up the less is the number of items so if we want to search the number line in this uh linked list in this skip list we start from the top level so we start from the head number three we check what is the next item and we compare it with the so the first item is number five We compare it with what is the next item in this case it's the end which means that the number nine must be down so we go down we then comp pair it with the next item which is number 17 which means that it cannot be after this nod because it's 17 so it must be down we go down and then we compare it with the next node which is the number nine and we see okay we reached the number nine now imagine we want to find another number let's say the number 12 we start again from the h three we go to the first item and compare to the next okay it's the end so we go down then we arrive here we compare it with the next next we see it's 17 so it's bigger than 12 so we go down then we see it's nine so the next item is number nine so we visit nine and then we compare it with the next item which is 17 so it's bigger than 12 so we go down we go here and then we compare it with what is the next item which is number 12 and this is the number that we are looking for and we stop there so this is how the skip list works now to create the hierarchical navigable small words we combine the concept of navigable small words with the idea of the skip list in producing a her archical navigable wws algorithm so we start with we have a lower level which has more nodes and more connections and the upper level which has less nodes and less connections so we say that this one is more dense and this one is more sparse how does this search work in this uh graph suppose we have a quer just like before and we want to search in this graph we find a random entry point in the top level of this graph and then we visit it and then we compare the cosign similarity of this node with the query and all of his friends with the query and we see that this one is the best one so we go down we go down and we do again the same uh we we do again the same test so we check the coign similarity of this node with the query and all of his friends with the query and we see that this friend here has a better coine similarity score so we move here then we check this uh node here with all of his friends and we see that this one is the best one so we go down also this one we see that it's the best one among all of his friends for the coign similarity score so we go down and then we do again this test and we say what is the coine similarity score of this uh node and the query and also all of his friends with the query so this node no this node and this node and we move to the one that is best in case there is one and then we stop as soon as we find a local best so the one one node that is not worse than all of his friends we repeat this search just like before by using randomly selected entry points we take all these vectors that we have visited we sort we keep the top K best matching based on the similarity score that we are using or the distance function that we are using okay now that we have seen also how the vector database Works let's review again the pipeline of retrieval augmented Generation by um summing up what we have seen so again we have our query we have some documents from which we want to retrieve the knowledge we split them into pieces of text we create embeddings using sentence birth for example we store all these vectors in a vector database we convert our query in an embedding and and we searching in a vector database using the algorithm that we have seen before so the hierarchical navigable small words this will produce the top K embeddings best matching with our query from which we assoc go back to the text that they were taken from we combine the query and the context retrieved in a template we feed it to the large language model and finally the large language model will produce the answer thank you guys for watching my video I hope you learned lot today because I wanted to create this video for a long time actually but I wanted also to understand myself all the algorithms that were behind this Pipeline and I hope that you are also now familiar with all these Concepts um I know that actually implementing the rug pipeline is very easy there is many popular libraries like Lama index and lung chain but I wanted to actually go deep inside of how it works and each building block how they actually work together uh please let uh let let me know if there is something that you don't understand I will try to answer all the question in the comment section also let me know if you want to uh something that you want better clarified in my future videos or how can I improve my future videos for better Clarity please subscribe to my channel this is the best motivation for me to continue making high quality content and like the video if you like it share the video with your friends with your professors with your students Etc and have a nice day guys