--- title: "LLM 수학 05 — 검색과 RAG" slug: "llm-math-05-retrieval-rag" category: "AI / LLM" topic: "ai-llm" subtopic: "mathematics" tags: ["RAG","BM25","Embedding","Reranking","nDCG"] status: "published" created: "2026-07-21" updated: "2026-07-21" summary: "BM25, dense embedding, contrastive loss, ANN, hybrid fusion과 reranking을 비교하고 Recall·MRR·nDCG로 RAG 실패를 retrieval과 generation 단계로 나눈다." kind: "Study Note" evidence: "검색 원 논문·공식 유도·손계산" series: "공식에서 시스템까지 이어지는 LLM 수학" --- [04편](/posts/llm-math-04-transformer)까지는 model 내부 context를 계산했다. RAG는 외부 corpus에서 근거 후보를 찾는다. 여기서 가장 중요한 구분은 “비슷한 문서를 찾는 score”와 “답을 생성하는 probability”가 다르다는 점이다. ```text question → query transformation → candidate retrieval → filter / fusion → reranking → context assembly → generation → citation / answer validation ``` 각 단계에는 다른 objective와 failure가 있다. ## Retrieval 문제를 먼저 정의한다 query 집합 $Q$, document corpus $D$, relevance label $rel(q,d)$가 있다고 하자. retriever는 score를 만든다. $$ s(q,d)\in\mathbb{R} $$ 그리고 큰 score 순서로 document를 정렬한다. $$ \pi_q=\operatorname{sort}_{d\in D} s(q,d) $$ 핵심은 score 절대값이 아니라 ranking인 경우가 많다. BM25 12.4와 cosine 0.82를 직접 더하려면 scale 의미를 먼저 맞춰야 한다. ### Relevance는 binary만이 아니다 - binary — relevant 1, irrelevant 0 - graded — 매우 관련 3, 관련 2, 일부 관련 1, 무관 0 - passage-level과 document-level - answer-containing과 truly supporting 정답 문자열이 들어 있다고 reasoning 근거로 충분한 것은 아니다. label 정의가 metric보다 먼저다. ## Sparse retrieval의 출발점 ### Term frequency document $d$ 안에서 term $t$가 나온 횟수다. $$ tf(t,d)=\operatorname{count}(t\in d) $$ 많이 나올수록 document 주제와 관련 있을 가능성이 있지만 100번 등장했다고 1번보다 100배 중요한 것은 아니다. ### Document frequency corpus $N$개 중 term $t$를 포함한 document 수다. $$ df(t)=|\{d\mid t\in d\}| $$ 모든 문서에 나오는 흔한 term은 구분력이 작다. ### Inverse document frequency 기본 직관은 $$ idf(t)=\log\frac{N}{df(t)} $$ 이다. rare term일수록 크다. 실제 BM25 implementation은 smoothing과 음수 방지를 위해 다른 형태를 쓸 수 있다. $$ idf(t) = \log\left(1+\frac{N-df(t)+0.5}{df(t)+0.5}\right) $$ “BM25 score가 다르다”면 tokenizer, field, IDF formula부터 확인한다. ## BM25 널리 쓰는 형태는 $$ \operatorname{BM25}(q,d) = \sum_{t\in q} idf(t) \frac{tf(t,d)(k_1+1)} {tf(t,d)+k_1\left(1-b+b\frac{|d|}{avgdl}\right)} $$ 이다. - $|d|$ — document length - $avgdl$ — corpus 평균 document length - $k_1$ — term frequency saturation 정도 - $b$ — length normalization 강도 ### Term frequency saturation $tf$가 커져도 분수는 계속 선형 증가하지 않는다. $tf\to\infty$일 때 $$ \frac{tf(k_1+1)}{tf+K}\to k_1+1 $$ 이다. 같은 term 반복의 효과가 포화된다. ### Length normalization $$ K=k_1\left(1-b+b\frac{|d|}{avgdl}\right) $$ - $b=0$ — length를 무시한다. - $b=1$ — document length 비율을 온전히 반영한다. 긴 문서는 term을 우연히 더 많이 포함할 수 있어 normalize한다. 긴 문서가 항상 나쁘다는 뜻은 아니다. ### Query term frequency 위 식은 short query에서 흔히 쓰는 형태다. 원 BM25 family에는 query term frequency를 다루는 $k_3$ 항과 field-aware BM25F 같은 변형이 있다. search engine의 `BM25`가 정확히 어느 식인지 확인한다. ## BM25 손계산 corpus document 수 $N=100$, term `RAG`를 포함한 document 수 $df=9$라 하자. $$ idf = \log\left(1+\frac{100-9+0.5}{9+0.5}\right) \approx\log(10.6316) \approx2.364 $$ $k_1=1.2$, $b=0.75$, $avgdl=100$, document length $|d|=150$, $tf=3$이면 $$ K=1.2\left(1-0.75+0.75\cdot1.5\right)=1.65 $$ $$ \frac{3(1.2+1)}{3+1.65} = \frac{6.6}{4.65} \approx1.419 $$ term contribution은 $$ 2.364\cdot1.419\approx3.354 $$ 다. query의 다른 term contribution을 더해 최종 score를 만든다. ## Analyzer가 식보다 먼저일 수 있다 BM25는 “term”이 이미 정해졌다고 가정한다. 실제 term은 analyzer가 만든다. ```text raw text → Unicode normalization → tokenization → lowercase → 형태소 분석 / stemming → stopword → synonym / user dictionary → indexed term ``` 한국어 compound, 품번 `AB-123`, snake_case identifier가 어떻게 분해되는지에 따라 $tf$와 $df$가 바뀐다. $k_1,b$를 tuning하기 전에 실제 indexed term을 본다. ## Dense retrieval query encoder와 document encoder가 vector를 만든다. $$ e_q=f_q(q)\in\mathbb{R}^{D} $$ $$ e_d=f_d(d)\in\mathbb{R}^{D} $$ score는 dot product 또는 cosine이다. $$ s(q,d)=e_q^\top e_d $$ $$ s_{cos}(q,d) = \frac{e_q^\top e_d}{\lVert e_q\rVert\lVert e_d\rVert} $$ 양쪽을 L2-normalize하면 둘은 같다. Dense retrieval은 exact term overlap 없이 semantic relation을 잡을 수 있지만 다음을 자동 해결하지 않는다. - 품번 한 글자 차이 - 최신 데이터와 stale index - access control - table row/column relation - domain 밖 language와 acronym - long document의 여러 사실 압축 ## Dual-Encoder와 Cross-Encoder ### Dual-Encoder query와 document를 독립 encoding한다. $$ s(q,d)=f_q(q)^\top f_d(d) $$ document vector를 미리 계산하고 index에 넣을 수 있어 corpus 전체 1차 검색에 적합하다. interaction이 하나의 vector score로 제한된다. ### Cross-Encoder query와 document를 함께 넣는다. $$ s(q,d)=g([q;d]) $$ 모든 token이 cross-attention할 수 있어 세밀하지만 후보마다 model forward가 필요하다. 보통 retriever가 줄인 top-$k$를 rerank한다. retriever가 정답 document를 후보에 넣지 못했다면 Cross-Encoder는 복구할 수 없다. ## Dense retriever의 contrastive loss query $q_i$, positive $d_i^+$, negative 후보 $d_j$가 있을 때 $$ \mathcal{L}_i =-\log \frac{\exp(s(q_i,d_i^+)/\tau)} {\sum_j\exp(s(q_i,d_j)/\tau)} $$ 이다. positive document를 candidate class 중 정답으로 둔 cross-entropy다. ### In-batch negatives batch의 다른 positive document를 query $i$의 negative로 재사용한다. batch size $B$면 query당 후보가 대략 $B$개 생긴다. 장점은 추가 encoding 없이 negative가 늘어나는 것이다. 단점은 실제로 관련 있는 문서가 negative로 들어가는 false negative와 batch 구성 bias다. ### Hard negatives 현재 retriever나 BM25가 높게 찾지만 label상 irrelevant한 document다. 너무 쉬운 random negative보다 decision boundary를 학습시키지만 false negative 위험이 크다. ### Temperature $\tau$가 작으면 score 차이를 키워 distribution을 sharp하게 만든다. embedding norm이 자유로운 dot-product model에서는 norm과 temperature 효과가 얽힐 수 있다. ## Sparse와 Dense는 무엇을 다르게 본다 | 상황 | Sparse 강점 | Dense 강점 | |---|---|---| | 정확한 식별자 | exact token match | 한 글자 차이를 뭉갤 수 있음 | | 동의어·표현 차이 | query expansion 없으면 약함 | semantic similarity 가능 | | 새 고유명사 | index term이면 즉시 검색 | training에 없으면 표현 불안정 가능 | | cross-language | token overlap이 적어 약함 | multilingual training이면 가능 | | 설명 가능성 | matched term 확인 쉬움 | vector coordinate 해석 어려움 | | update | inverted index 갱신 | re-embedding 필요 | 둘 중 하나가 항상 우월하지 않다. query type별 failure set이 겹치는지 본다. ## Learned sparse sparse retrieval이 곧 BM25는 아니다. neural encoder가 vocabulary term별 weight를 학습할 수 있다. 단순화하면 $$ w_t(d)=\max_{i\,\mid\,token_i=t}\phi(h_i) $$ $$ s_{sparse}(q,d) = \sum_{t\in q\cap d}w_t(q)w_t(d) $$ 형태다. inverted index를 사용할 수 있어도 weight가 $tf$, $df$, document length 공식으로 정해지는 BM25와 다르다. BGE-M3의 Sparse score도 learned lexical weight다. ## Multi-vector와 ColBERT query token vector $Q_i$, document token vector $D_j$를 유지한다. ColBERT의 late interaction score는 $$ s(q,d) = \sum_{i\in q}\max_{j\in d}Q_i^\top D_j $$ 이다. 각 query token이 가장 잘 맞는 document token 하나를 찾고 그 maximum을 합한다. single vector보다 세밀하고 Cross-Encoder보다 document representation을 미리 계산하기 쉽다. 비용은 document당 vector 하나가 아니라 token vector 여러 개를 저장·검색한다는 점이다. MaxSim이 negation과 term coverage를 완벽히 이해한다는 보장은 없다. ## Exact nearest neighbor와 ANN corpus 모든 vector와 query를 비교하면 exact search다. $$ \operatorname*{argtop-k}_{d\in D}s(q,d) $$ corpus가 크면 매 query마다 $O(ND)$ dot product가 비싸다. Approximate Nearest Neighbor는 일부 candidate만 탐색해 latency와 memory를 줄이는 대신 true neighbor를 놓칠 수 있다. ### ANN의 세 축 - recall — exact top-$k$ 중 얼마나 찾았는가 - latency 또는 throughput - index memory와 build/update cost `efSearch`, probe 수 같은 parameter를 올리면 보통 recall과 latency가 함께 오른다. exact relevance recall과 ANN recall을 구분한다. ```text 질의 정답 recall = relevant document가 검색됐는가 ANN recall = exact vector top-k를 ANN이 재현했는가 ``` embedding 자체의 exact top-k가 정답을 놓치면 ANN recall 100%여도 RAG는 실패한다. ## Metadata filter와 access control filter $F(q,d)\in\{0,1\}$를 두면 eligible corpus는 $$ D_q=\{d\in D\mid F(q,d)=1\} $$ 이다. 먼저 filter하고 vector search할지, ANN candidate를 뽑은 뒤 filter할지에 따라 recall과 latency가 달라진다. 후처리 filter에서 top-10 중 9개가 탈락하면 반환 결과가 1개뿐일 수 있다. 더 많이 가져오거나 filter-aware index가 필요하다. 권한 filter는 relevance tuning이 아니라 security boundary다. model prompt에 “보면 안 된다”고 쓰는 것으로 대체할 수 없다. ## Hybrid score fusion BM25 score $s_b$와 dense score $s_d$를 단순 합하면 $$ s=\alpha s_b+(1-\alpha)s_d $$ 다. 하지만 두 score range가 다르면 $\alpha$ 의미가 무너진다. ### Min-max normalization $$ \tilde{s}_i = \frac{s_i-s_{min}}{s_{max}-s_{min}} $$ query candidate 안의 outlier에 민감하고 $s_{max}=s_{min}$ 처리가 필요하다. ### Z-score $$ \tilde{s}_i = \frac{s_i-\mu}{\sigma} $$ score distribution이 안정적이어야 하고 작은 candidate set에서는 estimate가 불안정할 수 있다. ### Learned fusion validation relevance data로 weight 또는 learning-to-rank model을 학습한다. query feature, retriever score, document metadata를 함께 쓸 수 있지만 distribution shift와 leakage를 검증해야 한다. ## Reciprocal Rank Fusion score scale 대신 rank만 쓴다. $$ \operatorname{RRF}(d) = \sum_{r\in R} \frac{1}{k+\operatorname{rank}_r(d)} $$ $k$는 상위 rank 한 번의 영향이 지나치게 커지는 것을 완화하는 상수다. 원 논문은 실험에서 $k=60$을 사용했지만 모든 corpus의 최적값이라는 뜻은 아니다. BM25에서 1위, dense에서 10위인 document와 두 system에서 모두 3위인 document를 비교할 수 있다. rank만 보므로 raw score 차이가 아주 큰지 작은지는 버린다. candidate union을 사용하면 단일 retriever보다 최종 후보 budget이 커질 수 있다. hybrid 향상을 score fusion 효과와 candidate recall 증가로 나눠 본다. ## Reranking 1차 retriever가 candidate $C_k(q)$를 만들고 reranker가 새 score로 정렬한다. $$ C_k(q)=\operatorname{top-k}_{d\in D}s_{retriever}(q,d) $$ $$ \pi'_q=\operatorname{sort}_{d\in C_k(q)}s_{rerank}(q,d) $$ reranker가 개선할 수 있는 upper bound는 candidate recall에 막힌다. $$ \operatorname{Recall}_{candidate}@k<1 \Rightarrow \text{놓친 정답은 reranker로 복구 불가} $$ 따라서 top-10 품질이 나쁠 때 먼저 `Recall@100`을 본다. - Recall@100이 낮다 — candidate source, chunk, query, filter, embedding 문제 - Recall@100은 높고 nDCG@10이 낮다 — reranking과 score 문제 ## Chunking을 수학 문제로 본다 document 길이 $L$, chunk size $c$, overlap $o$라면 stride는 $$ s=c-o $$ 단순 sliding window chunk 수는 $$ n = \max\left(1,\left\lceil\frac{L-c}{c-o}\right\rceil+1\right) $$ 이다. $L=2000$, $c=500$, $o=100$이면 stride 400이고 $$ n=\left\lceil\frac{1500}{400}\right\rceil+1=5 $$ 이다. ### Overlap tradeoff - overlap 증가 — boundary 정보 보존 가능성 증가 - chunk 수 증가 — embedding·index 비용 증가 - 유사 chunk 중복 — top-$k$ 다양성 감소 - 같은 근거가 여러 번 prompt에 들어갈 수 있음 고정 token chunk는 표, section, code block을 자를 수 있다. semantic chunk도 parser 오류와 길이 variance가 있다. chunking은 model context length보다 data structure 문제다. ### Parent-child retrieval 작은 child chunk로 검색하고 큰 parent section을 context로 넣는다. retrieval precision과 generation context를 분리한다. parent가 너무 크면 prompt budget과 distractor가 늘어난다. ## Context budget model context 한도 $C$에서 system·history·question·output reserve를 빼면 retrieval budget은 $$ C_{retrieval} =C-C_{system}-C_{history}-C_{question}-C_{output} $$ 이다. chunk $i$의 token 수를 $l_i$라 하면 선택 문제는 $$ \sum_{i\in S}l_i\le C_{retrieval} $$ 제약 아래 relevance와 diversity를 최대화하는 knapsack-like 문제로 볼 수 있다. top score 순서로 자르는 것이 유일한 방법은 아니다. ## Maximal Marginal Relevance 관련성과 이미 선택한 문서와의 중복을 함께 본다. $$ \operatorname{MMR}(d) = \lambda\operatorname{sim}(q,d) -(1-\lambda)\max_{d'\in S}\operatorname{sim}(d,d') $$ - $\lambda$가 크면 relevance 중심 - 작으면 diversity 중심 두 similarity의 scale과 embedding 의미가 맞아야 한다. diversity가 사실 coverage를 높이는지는 query별 평가가 필요하다. ## Retrieval metric query마다 relevance label이 있다고 하자. ### Precision@k $$ P@k = \frac{\#\text{top-k 안 relevant}}{k} $$ 상위 결과가 얼마나 깨끗한지 본다. ### Recall@k $$ R@k = \frac{\#\text{top-k 안 relevant}} {\#\text{전체 relevant}} $$ candidate가 정답을 포함하는지 본다. QA에서 정답 근거가 여러 개일 때 denominator label completeness가 중요하다. ### Hit Rate@k relevant가 하나라도 있으면 1이다. $$ \operatorname{Hit}@k = \mathbf{1}[\exists i\le k\text{ such that }rel_i>0] $$ query 평균을 낸다. relevant 두 개 중 하나만 찾은 경우와 모두 찾은 경우를 구분하지 않는다. ### Reciprocal Rank와 MRR 첫 relevant document rank가 $r$이면 $$ RR=\frac{1}{r} $$ query 평균은 $$ MRR=\frac{1}{|Q|}\sum_{q\in Q}\frac{1}{rank_q} $$ 첫 정답 위치만 본다. 두 번째 이후 relevant document 품질은 반영하지 않는다. ### Average Precision와 MAP binary relevance에서 $$ AP = \frac{1}{R} \sum_{k=1}^{N}P@k\cdot rel_k $$ 이다. relevant가 등장한 rank의 precision을 평균한다. query별 AP 평균이 MAP다. relevance judgment가 incomplete하면 미label 문서를 false로 취급하는 문제가 있다. ### DCG와 nDCG graded relevance를 순위 discount와 함께 본다. 흔한 형태는 $$ DCG@k = \sum_{i=1}^{k} \frac{2^{rel_i}-1}{\log_2(i+1)} $$ ideal ranking의 DCG로 나눈다. $$ nDCG@k=\frac{DCG@k}{IDCG@k} $$ $IDCG@k=0$인 query 처리 정책을 정해야 한다. library마다 gain을 $rel_i$ 그대로 쓰는 변형도 있어 식을 확인한다. ## Metric 손계산 relevance가 rank 순서로 $$ [0,1,0,1,1] $$ 이고 전체 relevant가 3개라고 하자. $$ P@3=\frac13 $$ $$ R@3=\frac13 $$ 첫 relevant가 rank 2이므로 $$ RR=\frac12 $$ AP는 relevant rank 2, 4, 5의 precision 평균이다. $$ AP = \frac{\frac12+\frac24+\frac35}{3} =\frac{0.5+0.5+0.6}{3} \approx0.533 $$ MRR은 첫 relevant만 봐 0.5지만 AP는 이후 relevant 배치도 본다. ## Retrieval evaluation의 함정 ### 같은 corpus에서 random split만 한다 template와 duplicate가 train/test에 함께 들어가면 generalization을 과대평가한다. time, source, entity 기준 split도 비교한다. ### Negative가 너무 쉽다 random document만 negative면 lexical clue만으로 높은 score가 나올 수 있다. 실제 운영의 confusing candidate를 넣는다. ### Label이 하나뿐이다 하나의 annotated positive 외에 실제 relevant 문서가 negative로 취급될 수 있다. false negative audit가 필요하다. ### 평균만 본다 query type별 failure가 상쇄된다. exact identifier, procedure, multi-hop, table, recency, permission으로 나눈다. ### Top-k를 고정하지 않는다 system A top-10과 system B top-100 후보 rerank를 비교하면 candidate budget 효과가 섞인다. ## Original RAG의 probability retrieved passage $z$를 latent variable로 두면 sequence-level 식은 $$ p(y\mid x) \approx \sum_{z\in\operatorname{top-k}(x)} p_\eta(z\mid x) p_\theta(y\mid x,z) $$ 이다. 전체 corpus 합 대신 top-$k$로 근사한다. RAG-Token 형태는 output token마다 다른 document를 marginalize할 수 있다. $$ p(y\mid x) \approx \prod_t \sum_{z\in\operatorname{top-k}(x)} p_\eta(z\mid x) p_\theta(y_t\mid x,z,y_{