Field Log · Entry
Sparse Retrieval 기초: 역색인·TF-IDF·BM25 직접 계산하기 (3/10)
오늘의 결론
- BM25는 문서를 이해하는 LLM이 아니라 query term이 등장한 문서를 빠르게 점수화하는 함수입니다.
- 역색인은 모든 문서를 매번 읽지 않고 term의 posting list만 방문하게 합니다.
- IDF는 희귀 term을 크게, TF saturation은 같은 단어의 무한 반복을 제한합니다.
E104, 제품명, API field, 법 조항처럼 exact term이 중요한 질문에서 sparse 검색은 강한 baseline입니다.- analyzer가 term을 어떻게 자르고 정규화했는지가 BM25 parameter보다 먼저입니다.
앞 글에서 검색 단위인 chunk를 만들었습니다. 이제 query와 chunk가 얼마나 관련 있는지 점수를 매겨야 합니다.
가장 먼저 만들 검색기는 BM25가 좋습니다. embedding API가 없어도 실행되고, 점수가 어떤 term에서 나왔는지 설명할 수 있으며, dense retrieval의 개선 여부를 판단할 기준선이 되기 때문입니다.
그림 1. query term별 posting list에서 후보를 모은 뒤, 희귀도·문서 내 빈도·문서 길이를 반영해 점수를 더한다. BM25는 term 순서와 깊은 의미를 직접 표현하지 않는다.
Sparse라는 말은 무엇이 비어 있다는 뜻일까
문서 vocabulary가 100만 term이라고 합시다. 한 chunk에 실제로 등장하는 term은 수십~수백 개뿐입니다.
vocabulary 좌표
[환불, 보존, E104, timeout, GPU, ... 999,995개]
chunk vector
[0, 0, 1, 2, 0, ... 대부분 0]대부분의 차원이 0이므로 sparse representation이라고 부릅니다. 실제 검색 engine은 이 거대한 vector를 그대로 저장하기보다 **역색인(inverted index)**을 사용합니다.
Forward index와 inverted index
일반적인 문서 관점은 “문서에 어떤 term이 있는가?”입니다.
D1 → 오류, 코드, E104, 연결, 시간, 초과, 해결
D2 → E104, 인증, 토큰, 만료, 재발급
D3 → 연결, 시간, 초과, 재시도, 설정역색인은 방향을 뒤집습니다.
E104 → (D1, tf=1), (D2, tf=1)
연결 → (D1, tf=1), (D3, tf=1)
시간 → (D1, tf=1), (D3, tf=1)
초과 → (D1, tf=1), (D3, tf=1)query가 E104 연결 시간 초과이면 이 네 posting list만 읽어 후보를 만듭니다. corpus 전체 chunk와 비교하지 않아도 됩니다.
posting에는 구현에 따라 다음 정보가 들어갑니다.
- document 또는 chunk ID
- term frequency
- term position
- field
- skip pointer와 압축 정보
position을 저장하면 phrase query나 proximity scoring도 구현할 수 있지만, 기본 BM25 식 자체는 term 순서를 사용하지 않습니다.
Boolean match에서 TF-IDF로
가장 단순한 검색은 query term이 하나라도 있으면 후보로 만드는 것입니다. 하지만 문서, 설정처럼 흔한 term과 E104처럼 희귀한 term을 같은 가치로 보면 순위가 약합니다.
TF-IDF는 두 직관을 결합합니다.
TF: 문서 안에서 자주 등장하는가
TF(t, D) = 문서 D 안에서 term t가 등장한 횟수관련 문서라면 query term이 여러 번 나올 가능성이 있습니다. 하지만 10번 등장한 문서가 1번 등장한 문서보다 항상 정확히 10배 관련 있지는 않습니다.
IDF: corpus 전체에서 희귀한가
전체 문서가 N개이고 term t가 등장한 문서가 n(t)개이면, 한 형태의 IDF는 다음과 같습니다.
IDF(t) = log(N / n(t))모든 문서에 있는 term은 구분력이 작고, 소수 문서에만 있는 term은 구분력이 큽니다. 실제 BM25 구현은 음수 방지와 smoothing을 위해 다른 IDF 변형을 사용할 수 있습니다.
BM25 식을 세 조각으로 읽는다
많이 쓰이는 BM25 형태는 다음과 같습니다.
score(D, Q) = Σ IDF(qᵢ) ×
f(qᵢ,D) × (k₁ + 1)
─────────────────────────────
f(qᵢ,D) + k₁ × (1 - b + b × |D| / avgdl)기호를 하나씩 풀어 봅니다.
| 기호 | 의미 |
|---|---|
Q | query term 집합 |
D | 점수를 계산할 document/chunk |
f(qᵢ,D) | D 안에서 query term의 빈도 |
| ` | D |
avgdl | corpus의 평균 document 길이 |
k₁ | TF saturation의 세기 |
b | 길이 정규화의 세기 |
1. IDF: 희귀 term의 가중치
Lucene 계열에서 볼 수 있는 smoothing 형태를 단순화하면 다음과 같습니다.
IDF(t) = log(1 + (N - n(t) + 0.5) / (n(t) + 0.5))E104가 두 문서에만 있고 오류가 거의 모든 문서에 있다면 E104의 점수가 더 큽니다.
2. TF saturation: 반복의 한계효용
f가 증가해도 score가 선형으로 끝없이 커지지 않습니다.
f = 1 → 큰 첫 증가
f = 2 → 추가 증가
f = 20 → 증가 폭이 점점 작아짐k₁이 클수록 반복 빈도의 영향을 더 오래 허용합니다. 흔한 시작값은 1.2 부근이지만 corpus 평가로 정합니다.
3. Length normalization: 긴 문서의 우연한 match 보정
긴 chunk는 term을 포함할 기회가 많습니다. b는 document 길이를 평균 길이와 비교해 이 효과를 보정합니다.
b = 0: 길이를 무시b = 1: 길이를 완전히 반영- 흔한 시작값:
0.75
chunk 길이를 이미 좁게 통제했다면 b의 최적값이 일반 web 문서와 다를 수 있습니다.
세 문서로 직접 계산한다
간단한 analyzer가 다음 token을 만들었다고 가정합니다.
D1 (길이 7): 오류 코드 E104 연결 시간 초과 해결
D2 (길이 5): E104 인증 토큰 만료 재발급
D3 (길이 5): 연결 시간 초과 재시도 설정
Q: E104 연결 시간 초과
N = 3, avgdl = 17 / 3 ≈ 5.67
k₁ = 1.2, b = 0.75query의 네 term은 각각 두 문서에 등장합니다.
IDF = log(1 + (3 - 2 + 0.5) / (2 + 0.5))
= log(1.6)
≈ 0.470모든 term의 f=1일 때 길이별 TF factor는 다음과 같습니다.
D1 factor ≈ 0.912 → term 하나당 0.470 × 0.912 ≈ 0.429
D2 factor ≈ 1.051 → term 하나당 0.470 × 1.051 ≈ 0.494
D3 factor ≈ 1.051query term match 수를 곱하면 다음 순서가 됩니다.
D1: 4 terms × 0.429 ≈ 1.716
D3: 3 terms × 0.494 ≈ 1.482
D2: 1 term × 0.494 ≈ 0.494D1은 조금 길어 length penalty를 받지만 E104와 timeout을 표현하는 term을 모두 포함해 1위입니다.
실제 점수는 analyzer, IDF 변형, field boost, discount overlap 설정에 따라 달라집니다. 서로 다른 engine의 raw BM25 score를 같은 scale이라고 가정하면 안 됩니다.
작은 BM25를 Python으로 구현한다
원리를 확인하기 위한 in-memory baseline입니다. production 역색인의 압축과 최적화를 대신하는 코드는 아닙니다.
from collections import Counter, defaultdict
from dataclasses import dataclass
import math
@dataclass(frozen=True)
class BM25Hit:
doc_id: str
score: float
matched_terms: tuple[str, ...]
class BM25Index:
def __init__(self, k1: float = 1.2, b: float = 0.75):
self.k1 = k1
self.b = b
self.lengths: dict[str, int] = {}
self.postings: dict[str, dict[str, int]] = defaultdict(dict)
self.doc_count = 0
self.avgdl = 0.0
def add(self, doc_id: str, terms: list[str]) -> None:
if doc_id in self.lengths:
raise ValueError(f"duplicate doc_id: {doc_id}")
frequencies = Counter(terms)
self.lengths[doc_id] = len(terms)
for term, frequency in frequencies.items():
self.postings[term][doc_id] = frequency
def finalize(self) -> None:
self.doc_count = len(self.lengths)
if self.doc_count == 0:
raise ValueError("empty index")
self.avgdl = sum(self.lengths.values()) / self.doc_count
def idf(self, term: str) -> float:
document_frequency = len(self.postings.get(term, {}))
return math.log(
1.0
+ (self.doc_count - document_frequency + 0.5)
/ (document_frequency + 0.5)
)
def search(self, query_terms: list[str], k: int = 5) -> list[BM25Hit]:
if self.doc_count == 0:
raise RuntimeError("call finalize() before search")
scores = defaultdict(float)
matched = defaultdict(set)
for term in set(query_terms):
term_idf = self.idf(term)
for doc_id, frequency in self.postings.get(term, {}).items():
length_ratio = self.lengths[doc_id] / self.avgdl
denominator = frequency + self.k1 * (
1.0 - self.b + self.b * length_ratio
)
tf_factor = frequency * (self.k1 + 1.0) / denominator
scores[doc_id] += term_idf * tf_factor
matched[doc_id].add(term)
ranked = sorted(scores, key=scores.get, reverse=True)[:k]
return [
BM25Hit(
doc_id=doc_id,
score=scores[doc_id],
matched_terms=tuple(sorted(matched[doc_id])),
)
for doc_id in ranked
]실행해 봅니다.
documents = {
"D1": "오류 코드 E104 연결 시간 초과 해결".split(),
"D2": "E104 인증 토큰 만료 재발급".split(),
"D3": "연결 시간 초과 재시도 설정".split(),
}
index = BM25Index()
for doc_id, terms in documents.items():
index.add(doc_id, terms)
index.finalize()
for hit in index.search("E104 연결 시간 초과".split()):
print(hit)matched_terms를 함께 출력하면 왜 결과가 올라왔는지 debugging할 수 있습니다.
Analyzer가 실제 vocabulary를 결정한다
BM25 식보다 먼저 query와 document에 동일한 분석 규칙을 적용해야 합니다.
원문 → Unicode normalization → tokenization → case 처리
→ 형태소/compound 처리 → stopword 정책 → term한글에서 공백 split만 쓰면 생기는 일
문서: "접속시간초과를 해결합니다"
질문: "접속 시간 초과"공백 split만 하면 서로 겹치는 term이 없을 수 있습니다. 한글 형태소 analyzer, dictionary, decompound 정책을 검토해야 합니다.
반대로 모든 것을 aggressive하게 분해하면 제품 코드가 깨질 수 있습니다.
원문 식별자: AB-1200, error_code, v2.1.0, E104
잘못된 결과: AB / 1200, error / code, v2 / 1 / 0, E / 104따라서 field를 분리하는 방식이 유용합니다.
body.analyzed : 자연어용 analyzer
body.raw : 정규화만 한 exact field
identifiers : keyword 또는 code-aware analyzer
title : 별도 boost가 있는 fieldquery에서도 코드 패턴을 감지해 identifiers field를 함께 검색합니다.
Stopword를 무조건 제거하지 않는다
일반 검색에서 흔한 단어를 제거하면 index가 작아질 수 있습니다. 그러나 domain에서는 짧은 function word나 부정어가 의미를 바꿀 수 있습니다.
"승인 없이 가능" vs "승인 시 가능"
"not supported" vs "supported"현대 engine은 posting 압축과 IDF로 흔한 term의 영향을 낮출 수 있습니다. stopword list는 corpus와 질문을 보고 결정합니다.
Field별 중요도를 주는 BM25F 관점
제목의 환불 정책과 본문 구석의 환불 정책을 같게 볼 필요는 없습니다. field별 길이 정규화와 boost를 결합한 계열을 BM25F로 볼 수 있습니다.
score ≈ title_BM25 × 2.0
+ heading_BM25 × 1.5
+ body_BM25 × 1.0
+ identifier_exact × 3.0숫자는 예시입니다. title을 과도하게 boost하면 제목만 비슷한 문서가 본문 근거보다 위로 갈 수 있습니다.
heading text를 모든 chunk 본문에 반복할지, 별도 field로 색인할지도 실험합니다. 별도 field가 중복 TF를 통제하기 쉽습니다.
Filter와 relevance score를 구분한다
권한, tenant, 날짜, 문서 상태는 relevance가 아니라 후보 자격 조건입니다.
filter: tenant_id = "acme" AND acl contains "employee" AND active = true
score : BM25(query, title/body/identifiers)허용되지 않은 문서를 먼저 점수화한 뒤 제거하면 top-k가 비거나 정보가 trace에 노출될 수 있습니다. 가능한 한 검색 전에 filter를 적용합니다.
다만 filter가 매우 선택적이면 index 구조와 latency에 영향을 줍니다. filtered query의 p95 latency와 후보 수를 따로 관찰합니다.
BM25가 잘하는 질문과 놓치는 질문
강한 경우
- 오류 코드, SKU, API 이름, 사람·제품 고유명
- 법 조항과 버전 번호
- query와 문서가 같은 domain terminology를 사용
- 신조어나 embedding 학습에 드문 term
- 왜 match됐는지 설명해야 하는 검색
약한 경우
- 동의어:
자동차와차량 - paraphrase:
계정을 되찾는 법과사용자 인증 복구 절차 - 다국어 표현
- 의미상 관련 있지만 공통 term이 없는 문장
- term 순서와 관계가 핵심인 질문
이 약점을 dense retrieval이 보완합니다. 그렇다고 dense가 BM25를 완전히 대체하는 것은 아닙니다. 두 방식의 실패가 다르기 때문에 이후 hybrid search로 합칩니다.
BM25 baseline을 평가하는 방법
같은 chunk와 query set에서 다음을 기록합니다.
{
"question_id": "q-104",
"query_terms": ["E104", "연결", "시간", "초과"],
"filters": {"tenant_id": "acme"},
"hits": [
{
"chunk_id": "D1",
"rank": 1,
"score": 1.716,
"matched_terms": ["E104", "연결", "시간", "초과"]
}
],
"index_version": "bm25-ko-v3"
}질문을 bucket으로 나눕니다.
| bucket | 예시 | 기대 |
|---|---|---|
| exact identifier | E104, API field | BM25 강함 |
| natural paraphrase | 계정 되찾기 | dense 보완 |
| mixed | E104 원인 설명 | hybrid 후보 |
| multi-hop | 정책 A와 B 비교 | query 분해 필요 |
전체 평균만 보면 특정 bucket의 심각한 regression을 놓칩니다.
Parameter tuning 전에 할 일
k₁과 b를 tuning하기 전에 다음 순서를 지킵니다.
- 정답 text가 parsed chunk에 있는지 확인
- query와 document analyzer output 출력
- 코드와 고유명이 보존되는지 확인
- title/body/identifier field 설계
- ACL·tenant filter 확인
- chunk 길이 분포 확인
- 그 다음
k₁,b, field boost 비교
잘못 tokenized된 E104는 b=0.7과 b=0.8을 비교해도 돌아오지 않습니다.
Production 체크리스트
- query와 index analyzer가 의도대로 대응한다.
- 한글 compound와 형태소 정책을 실제 query로 검증했다.
- 코드·SKU·version용 exact field가 있다.
- IDF와 matched term을 trace에서 확인할 수 있다.
- title·heading·body field boost를 평가셋으로 정했다.
- ACL·tenant·active filter가 후보 생성 전에 적용된다.
- BM25 index와 analyzer version을 기록한다.
- exact/paraphrase/mixed query bucket별 Recall@k를 본다.
- dense·hybrid 비교를 위한 고정 baseline으로 보존한다.
스스로 확인하기
- 역색인은 query마다 corpus 전체를 읽지 않아도 되는 이유가 무엇인가?
- IDF, TF saturation, length normalization은 각각 어떤 편향을 보정하는가?
- 동일한 문서에서 chunk를 작게 만들면
avgdl과 length normalization은 어떻게 달라질까? - 한글 analyzer가
E104를E와104로 나누면 어떤 검색이 실패하는가? - BM25가 0점인 질문을 parameter tuning보다 먼저 어떻게 진단할 것인가?
다음 글에서는 query와 passage를 같은 vector 공간에 배치해 표현이 달라도 찾는 Bi-Encoder·Contrastive Learning·DPR 기반 Dense Retrieval을 다룹니다.