LLM 수학 05 — 검색과 RAG

04편까지는 model 내부 context를 계산했다. RAG는 외부 corpus에서 근거 후보를 찾는다. 여기서 가장 중요한 구분은 “비슷한 문서를 찾는 score”와 “답을 생성하는 probability”가 다르다는 점이다.

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가 만든다.

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을 구분한다.

질의 정답 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_{<t})

production의 retrieve-then-prompt pipeline은 보통 이 식을 end-to-end 학습하지 않는다. retriever score를 probability처럼 generator loss에 넣지 않을 수 있다.

RAG failure를 분해한다

Retrieval failure

필요한 근거가 candidate에 없다.

측정 후보는 다음과 같다.

evidence Recall@k
answer-containing Recall@k
filter rejection rate
index freshness lag
ANN recall

Ranking failure

정답이 큰 candidate에는 있지만 prompt에 들어가는 top- $k$ 밖에 있다.

측정 후보는 다음과 같다.

MRR
nDCG@k
reranker delta

Context construction failure

정답 chunk가 잘렸거나 중복과 distractor가 budget을 차지한다.

측정 후보는 다음과 같다.

context precision
evidence coverage
duplicate ratio
token utilization

Generation failure

근거가 context에 있는데 model이 무시하거나 잘못 합성한다.

측정 후보는 다음과 같다.

answer correctness
faithfulness 또는 groundedness
citation entailment
unsupported claim rate

System failure

권한, timeout, stale cache, parser, OCR 문제다. model metric만으로 잡히지 않는다.

End-to-end metric만으로 부족한 이유

answer accuracy가 낮을 때 원인이 여러 개다.

P(\text{correct answer}) = P(R)P(C\mid R)P(G\mid R,C)

단순화해

$R$ — 필요한 근거 retrieval 성공
$C$ — context assembly 성공
$G$ — generation 성공

으로 분해할 수 있다. independence를 가정한 식이 아니라 conditional probability chain이다.

retrieval 성공률이 0.8, 그 조건의 context 성공률 0.9, 앞 조건에서 generation 성공률 0.85라면

0.8\cdot0.9\cdot0.85=0.612

end-to-end upper path는 약 61.2%다. generator만 85%에서 90%로 올리면 64.8%지만 retrieval을 80%에서 90%로 올리면 68.85%다. 실제 개선 우선순위는 conditional failure data로 정한다.

Latency와 cost

sequential pipeline이면 단순 근사 latency는

T_{total} =T_{query}+T_{retrieve}+T_{rerank}+T_{prompt}+T_{generate}

이다. parallel retrieval이면 합이 아니라 critical path의 max가 들어간다.

Cross-Encoder가 candidate $k$ 개를 scoring할 때 batch 처리 여부에 따라 latency가 선형처럼 보이지 않을 수 있지만 compute는 candidate 수와 함께 증가한다.

index 비용은

\text{embedding count}\times D\times\text{bytes per element}

에 metadata, graph, posting list overhead가 더해진다. chunk overlap은 embedding count를 늘린다.

평균 latency뿐 아니라 p50, p95, p99와 timeout rate를 본다. tail latency가 user-visible failure를 만든다.

RAG와 MCP의 경계

RAG는 외부 지식을 검색해 model context에 제공하는 system pattern이다. MCP는 host와 server가 tool, resource, prompt를 주고받는 protocol이다.

MCP resource나 tool 뒤에 vector search가 있을 수 있지만 MCP가 BM25, embedding, reranking algorithm을 정하지 않는다. 반대로 RAG는 MCP 없이도 구현할 수 있다.

실험 순서

exact field lookup을 별도 baseline으로 둔다.
analyzer를 확인한 BM25 baseline을 만든다.
dense exact search로 embedding ceiling을 본다.
ANN recall과 latency를 따로 조정한다.
query type별 Recall@k를 측정한다.
candidate recall이 충분할 때 reranker를 붙인다.
hybrid는 같은 final budget에서 비교한다.
context assembly와 generation 평가를 분리한다.
end-to-end latency와 cost를 마지막에 함께 본다.

새 model 하나로 모든 단계를 동시에 바꾸지 않는다.

완료 체크

다음 글은 model adaptation과 preference 학습을 지나 tool을 고르고 MCP로 실행하는 system 경계를 다룬다. LLM 수학 06 — Fine-tuning, agent와 MCP.

Reference

Stephen Robertson, Hugo Zaragoza. The Probabilistic Relevance Framework — BM25 and Beyond, 2009.
Vladimir Karpukhin 외. Dense Passage Retrieval, 2020.
Omar Khattab, Matei Zaharia. ColBERT, 2020.
Gordon V. Cormack, Charles L. A. Clarke, Stefan Büttcher. Reciprocal Rank Fusion, 2009.
Patrick Lewis 외. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, 2020.
Nandan Thakur 외. BEIR, 2021.
Jianlv Chen 외. BGE M3-Embedding, 2024.