Searches in RAG

Documents has to be fed to chunker in Retrieval Phase, so that these provide context to LLM when query is asked by user.
But only relevant documents if fed would be helpful
Before feeding the documents to chunker, we should select the relevant documents, Hence we do searching.
There are 2 types of searches in RAG for finding the relevant docs to feed chunker:
1. Keyword search
2. Semantic Search

1. Keyword/Lexical Search

This looks for the same words in the query and in the documents.
It does not understand meaning. If the word is not present, the chunk is not a match.
Example: query says OUTBOUND_BLOCK → it finds documents/chunks that contain the token OUTBOUND_BLOCK.
Query says why is internet blocked → keyword search may miss a chunk that only says DENY dst=8.8.8.8, because the words are different even though the meaning is the same.

User query:  "Show firewall policies blocking outbound traffic"
                  |
                  |  split into words (tokens)
                  \/
tokens = [show, firewall, policies, blocking, outbound, traffic]
                  |
                  |  look for these words inside chunks
                  \/
Chunk A  FIREWALL_DENY ... policy=OUTBOUND_BLOCK     ← match: firewall, outbound
Chunk B  Policy OUTBOUND_BLOCK denies outbound traffic ← match: policy, outbound, traffic
Chunk C  VPN_LOGIN_FAILED user=john.doe              ← no useful word match
                  |
                  \/
top-k chunks (A, B) go into the augmented prompt → LLM answers
      

TF-IDF and BM25 are the two common ways to score those keyword matches (which chunk is a better match).

1. TF-IDF (Term Frequency − Inverse Document Frequency)

1. TF(Term Frequency):
- How often does this word appear in this chunk?
- More times in this chunk → this chunk is more about that word.
2. IDF(Inverse Document Frequency)
- How rare is this word in all documents?
- More rare the word is, it matters more. Rare words (OUTBOUND_BLOCK) matter more than common words (the, deny, policy)

TF(word, chunk)  =  count of word in chunk  /  total words in chunk
IDF(word)        =  log( N / df(word) )
TF-IDF           =  TF × IDF
chunk_score      =  sum of TF-IDF for every query word

2. BM25 (Best Matching 25)

This is used by Elasticsearch, OpenSearch, Lucene
Rules for BM-25:
1. Same idea as TF-IDF (rare matching words matter more)
2. It guards against
  2a. Term frequency saturation(k1 ≈ 1.2 to 2.0) That means overly repeated words. if there are 20 documents and mentions FIREWALL_DENY, then TF-IDF will count the score as wordx20
  2b. Document length normalization (b ≈ 0.75) A short, exact match (one FIREWALL_DENY line) is not punished just because it is short. Long documents are slightly penalized.

Formula for BM25(chunk, query) =
  sum over each query word qi:

      IDF(qi)  ×  (tf × (k1+1)) / (tf + k1 × (1 − b + b × |D|/avgdl))

  tf     = how many times qi appears in this chunk
  |D|    = length of this chunk
  avgdl  = average chunk length in the index
  k1     = saturation (typical 1.2)
  b      = length penalty (typical 0.75)

You do not need to memorize the formula. Remember the behavior:

Query: OUTBOUND_BLOCK

Short exact log line
  FIREWALL_DENY policy=OUTBOUND_BLOCK          ← BM25 likes this

Huge handbook that says "outbound" 50 times
  Chapter 9: outbound routing, outbound NAT,   ← TF-IDF may over-rank this
  outbound VPN, outbound ...                   ← BM25 damps the repeats

2. Semantic Search

Semantic search uses Vector Embeddings to find documents which have closely meaning words as mentioned in Prompt.
It converts User's query and Documents into vectors on embedding space, similar meaning words are placed together in embedding space.
This determine how close each document is to your query
Sort the documents by their similarity score and select the top few as the most relevant
Two Methods to find distance between words

1. Cosine Similarity

This evaluates how close two vectors are based on their angle.
if Cosine Similarity is the closer to 1, that means two words are more similar

Measures the cosine of the angle θ(Range: -1.0 to 1.0) between two vectors:

cosine similarity = vector1 x vector2 / |vector1| x |vector2|
      

2. Euclidian Distance

This calculates the "straight-line" distance between two vectors(range 0 to ∞) in the embedding space
Similar words have a smaller euclidian distance

                      2            2
d = underroot (x1 - x2) / (y1 - y2)
      

Code

Calculate cosine similarity, Euclidian distance 1 embedding from other

3. Hybrid Search(Keyword+Semantic)

Supposer, Keyword search provided 10 relevant documents and semantic search provided 10 documents.
Algorithm for combining these documents is called Reciprocal Rank Fusion

Reciprocal Rank Fusion (RRF)

We can search documents using both techniques(Keyword, semantic)
But documents get ranking based on position in each list
Each document scores 1/ranking.

Place   Rank
1st     1/1=1
2nd     1/2=0.5

Document-X gets Rank=2(Keyword Search)=1/2=.05, Rank=10(Semantic Search)=1/10=0.1
Total Score= 0.6

These scores are used to re-rank all the documents

Code

Perform Semantic, Hybrid search in vector DB Weaviate