BM42: 어휘 검색의 다음 진화

BM42: 어휘 검색의 다음 진화 (BM42)

참고: 이 글의 벤치마크 섹션은 출판 후 평가 스크립트의 오류로 인해 수정되었습니다. BM42는 다른 업체의 BM25 구현을 능가하지는 않습니다. BM42는 생산 환경에서 사용되기 전에 추가 연구와 개발이 필요한 실험적 접근 방식으로 간주해 주세요.

지난 40년 동안 BM25는 검색 엔진의 표준으로 자리 잡았어요. 간단하면서도 강력한 알고리즘으로, Google, Bing, Yahoo를 포함한 많은 검색 엔진이 사용해 왔죠.

벡터 검색의 등장이 BM25의 영향력을 줄일 것처럼 보였지만, 실제로는 부분적으로만 그랬어요. 오늘날 최신 검색 방식은 BM25를 임베딩과 함께 하이브리드 검색 시스템으로 통합하려고 해요.

하지만 RAG의 도입 이후 텍스트 검색의 사용 사례는 크게 바뀌었어요. BM25가 세워졌던 많은 가정이 더 이상 유효하지 않게 됐죠. 예를 들어 전통적인 웹 검색과 현대 RAG 시스템 사이에서 문서와 쿼리의 전형적인 길이는 크게 달라요.

이 글에서는 BM25가 이렇게 오래도록 관련성을 유지한 이유와, 대안들이 왜 BM25를 대체하는 데 어려움을 겪었는지 정리해 볼게요. 마지막으로 어휘 검색(lexical search) 진화의 다음 단계인 BM42에 대해 이야기할 거예요.

출처: 공식문서

BM25는 왜 이렇게 오래 관련성이 유지됐을까?

이를 이해하려면 BM25의 구성 요소를 분석해 봐야 해요.

유명한 BM25 공식은 이렇게 정의돼요:

$$ \text{score}(D,Q) = \sum_{i=1}^{N} \text{IDF}(q_i) \times \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)} $$

이걸 좀 더 쉽게 풀어서 이해해 볼게요.

$score(D, Q)$ — 문서 $D$와 쿼리 $Q$의 각 쌍에 대해 점수를 계산한다는 뜻이에요.
$\sum_{i=1}^{N}$ — 쿼리의 $N$개 용어 각각이 합의 일부로 최종 점수에 기여한다는 뜻이에요.
$\text{IDF}(q_i)$ — 역문서 빈도(Inverse Document Frequency)예요. 용어 $q_i$가 희귀할수록 점수에 더 많이 기여해요. 단순화한 공식은 다음과 같아요:

$$ \text{IDF}(q_i) = \frac{\text{Number of documents}}{\text{Number of documents with } q_i} $$

IDF가 BM25 공식에서 가장 중요한 부분이라고 말해도 과언이 아니에요. IDF는 특정 문서 컬렉션에 대해 쿼리에서 가장 중요한 용어를 선택해요. 직관적으로 해석하면 IDF는 **코퍼스 내 용어 중요도(term importance within the corpora)**라고 볼 수 있어요.

이것이 왜 BM25가 dense 임베딩이 범위 밖(out-of-domain)이라고 간주하는 쿼리를 잘 처리하는지 설명해 줘요.

공식의 마지막 구성 요소는 직관적으로 **문서 내 용어 중요도(term importance within the document)**로 해석할 수 있어요. 이것은 조금 복잡해 보일 수 있으니 쪼개서 살펴볼게요.

$$ \text{Term importance in document }(q_i) = \color{red}\frac{f(q_i, D)\color{gray} \cdot \color{blue}(k_1 + 1) \color{gray} }{\color{red}f(q_i, D)\color{gray} + \color{blue}k_1\color{gray} \cdot \left(1 - \color{blue}b\color{gray} + \color{blue}b\color{gray} \cdot \frac{|D|}{\text{avgdl}}\right)} $$

$\color{red}f(q_i, D)\color{gray}$ — 문서 $D$에서 용어 $q_i$의 빈도예요. 즉 문서 $D$에 용어 $q_i$가 나타나는 횟수예요.
$\color{blue}k_1\color{gray}$과 $\color{blue}b\color{gray}$ — BM25 공식의 하이퍼파라미터예요. 대부분의 구현에서 $k_1=1.5$, $b=0.75$로 설정된 상수예요. 이 상수들은 공식에서 용어 빈도와 문서 길이의 상대적 영향을 정의해요.
$\frac{|D|}{\text{avgdl}}$ — 코퍼스의 평균 문서 길이 대비 문서 $D$의 상대적 길이예요. 뒤에 있는 직관은 이래요: 더 짧은 문서에서 토큰이 발견된다면, 그 토큰이 그 문서에 중요할 가능성이 더 높다.

BM25의 문서 내 용어 중요도가 RAG에서도 동작할까?

보다시피 문서 내 용어 중요도는 문서 내 통계에 크게 의존해요. 게다가 통계는 문서가 충분히 길 때 잘 동작해요. 그래서 웹페이지, 책, 기사 등을 검색하는 데 적합해요.

하지만 RAG 같은 현대 검색 애플리케이션에서도 그렇게 잘 동작할까요? 한번 보죠.

RAG에서 문서의 전형적인 길이는 웹 검색보다 훨씬 짧아요. 사실 웹페이지와 기사를 다루더라도, 우리는 문서를 청크(chunk)로 쪼개는 걸 선호해요. 그 이유는 a) Dense 모델이 처리할 수 있도록 하고 b) 쿼리와 관련된 문서의 정확한 부분을 집어낼 수 있게 하기 위해서죠.

결과적으로 RAG에서 문서 크기는 작고 고정돼요.

이것은 BM25 공식의 문서 내 용어 중요도 부분을 사실상 무용지물로 만들었어요. 문서 내 용어 빈도는 항상 0 또는 1이고, 문서의 상대적 길이는 항상 1이에요.

그래서 BM25 공식에서 여전히 RAG에 관련이 있는 부분은 IDF뿐이에요. 이를 어떻게 활용할 수 있을지 보죠.

왜 SPLADE가 항상 답은 아닐까

새로운 접근 방식을 논의하기 전에, BM25의 현재 최신 대안인 SPLADE를 살펴볼게요.

SPLADE의 아이디어는 흥미로워요. 똑똑한 end-to-end 학습 모델이 우리를 대신해 텍스트의 bag-of-words 표현을 생성하게 하면 어떨까? 모든 토큰에 가중치를 할당하니 통계와 하이퍼파라미터를 신경 쓸 필요가 없겠죠. 문서는 sparse 임베딩으로 표현되는데, 각 토큰은 sparse 벡터의 한 요소로 표현돼요.

그리고 이건 학술 벤치마크에서 동작해요. 많은 논문이 SPLADE가 검색 품질 측면에서 BM25를 능가한다고 보고해요. 하지만 이 성능에는 대가가 따라와요.

부적절한 토크나이저: 이 작업에 transformer를 통합하려면 SPLADE 모델이 표준 transformer 토크나이저를 사용해야 해요. 이런 토크나이저는 검색 작업용으로 설계되지 않았어요. 예를 들어 단어가 (꽤 제한적인) 어휘에 없다면, 하위 단어(subword)로 쪼개지거나 [UNK] 토큰으로 대체돼요. 이 동작은 언어 모델링에는 잘 맞지만 검색 작업에는 완전히 파괴적이에요.
비싼 토큰 확장(Token Expansion): 토큰화 문제를 보완하기 위해 SPLADE는 토큰 확장 기법을 사용해요. 즉 쿼리의 각 토큰에 대해 유사한 토큰 집합을 생성한다는 뜻이에요. 이 접근에는 몇 가지 문제가 있어요:
- 계산과 메모리가 비싸요. 문서의 각 토큰에 대해 더 많은 값을 생성해야 해서 저장 크기와 검색 시간이 늘어나요.
- 토큰 확장을 어디서 멈출지 항상 명확하지 않아요. 토큰을 많이 생성할수록 관련 토큰을 얻을 가능성은 높아지지만, 동시에 관련 없는 결과가 나올 가능성도 커져요.
- 토큰 확장은 검색의 해석 가능성을 희석해요. 문서에 어떤 토큰이 사용됐고 어떤 토큰이 토큰 확장으로 생성됐는지 말할 수 없게 돼요.
도메인 및 언어 의존성: SPLADE 모델은 특정 코퍼스로 학습돼요. 즉 새롭거나 희귀한 도메인에 항상 일반화되지 않아요. 코퍼스의 어떤 통계도 사용하지 않기 때문에, 파인튜닝 없이는 새 도메인에 적응할 수 없어요.
추론 시간: 게다가 현재 사용 가능한 SPLADE 모델은 꽤 크고 느려요. 합리적인 시간 내 추론하려면 보통 GPU가 필요해요.

Qdrant는 앞서 언급한 문제들을 인지하고 해결책을 찾고 있어요. 우리의 아이디어는 양쪽의 장점을 결합하는 거였어요. BM25의 단순함과 해석 가능성 + transformer의 지능, 그리고 SPLADE의 함정은 피하는 것. 그렇게 해서 나온 결과가 이것이에요.

두 세계의 장점

앞서 언급했듯이 IDF는 BM25 공식에서 가장 중요한 부분이에요. 사실 너무 중요해서 우리는 그 계산을 Qdrant 엔진 자체에 내장하기로 결정했어요. 최신 릴리스 노트를 확인해 보세요. 이런 분리를 통해 IDF 계산을 최신으로 유지하면서 sparse 임베딩의 스트리밍 업데이트가 가능해져요.

공식의 두 번째 부분인 문서 내 용어 중요도는 다시 생각해 봐야 해요.

문서 내 통계에 의존할 수 없으니, 대신 문서의 **의미(semantics)**를 사용해 보는 건 어때요? 그리고 의미는 transformer가 잘하는 영역이에요. 따라서 두 가지 문제만 풀면 돼요:

transformer에서 중요도 정보를 어떻게 추출할까?
토큰화 문제를 어떻게 피할까?

Attention is all you need

Transformer 모델은 임베딩을 만드는 데 사용되는 것들조차도 다양한 출력을 만들어요. 그 출력 중 일부는 임베딩을 만드는 데 사용되고, 다른 일부는 분류, 텍스트 생성 같은 다른 종류의 작업을 해결하는 데 사용돼요.

우리에게 특히 흥미로운 출력 중 하나는 attention 행렬이에요.

Attention 행렬은 정사각 행렬로, 각 행과 열이 입력 시퀀스의 토큰에 대응돼요. 입력 시퀀스에서 각 토큰이 서로에 대해 가지는 중요도를 나타내요.

고전적인 transformer 모델은 컨텍스트의 마스킹된 토큰을 예측하도록 학습되므로, attention 가중치는 어떤 컨텍스트 토큰이 마스킹된 토큰에 가장 큰 영향을 주는지 정의해요.

일반 텍스트 토큰 외에도 transformer 모델에는 [CLS]라는 특별한 토큰이 있어요. 이 토큰은 분류 작업에서 시퀀스 전체를 나타내는데, 이게 정확히 우리가 필요한 것이에요.

[CLS] 토큰에 대한 attention 행(row)을 보면, 문서의 각 토큰이 문서 전체에 대해 가지는 중요도를 얻을 수 있어요.

sentences = "Hello, World - is the starting point in most programming languages"

features = transformer.tokenize(sentences)

# ...

attentions = transformer.auto_model(**features, output_attentions=True).attentions

weights = torch.mean(attentions[-1][0,:,0], axis=0)                       
#                ▲               ▲  ▲   ▲                                 
#                │               │  │   └─── [CLS] token is the first one
#                │               │  └─────── First item of the batch         
#                │               └────────── Last transformer layer       
#                └────────────────────────── Average all 6 attention heads

for weight, token in zip(weights, tokens):
    print(f"{token}: {weight}")

# [CLS]       : 0.434 // Filter out the [CLS] token
# hello       : 0.039
# ,           : 0.039
# world       : 0.107 // <-- The most important token
# -           : 0.033
# is          : 0.024
# the         : 0.031
# starting    : 0.054
# point       : 0.028
# in          : 0.018
# most        : 0.016
# programming : 0.060 // <-- The third most important token
# languages   : 0.062 // <-- The second most important token
# [SEP]       : 0.047 // Filter out the [SEP] token

그 결과 BM42 점수 공식은 이렇게 될 거예요:

$$ \text{score}(D,Q) = \sum_{i=1}^{N} \text{IDF}(q_i) \times \text{Attention}(\text{CLS}, q_i) $$

고전적인 transformer는 여러 개의 attention 헤드를 가지므로, 같은 문서에 대해 여러 개의 중요도 벡터를 얻을 수 있어요. 가장 간단한 결합 방법은 그냥 평균내는 거예요.

이 평균화된 attention 벡터들이 우리가 찾던 중요도 정보를 구성해요. 가장 좋은 점은, 추가 학습 없이 어떤 transformer 모델에서든 얻을 수 있다는 거예요. 따라서 해당 언어에 transformer 모델만 존재하면 BM42는 어떤 자연어도 지원할 수 있어요.

구현에서는 sentence-transformers/all-MiniLM-L6-v2 모델을 사용하는데, SPLADE 모델에 비해 추론 속도가 엄청나게 빨라져요. 실제로는 아무 transformer 모델이나 사용할 수 있어요. 추가 학습이 필요 없고, BM42 백엔드로 쉽게 적응할 수 있어요.

WordPiece 재토큰화

풀어야 할 마지막 퍼즐 조각은 토큰화 문제예요. attention 벡터를 얻으려면 네이티브 transformer 토큰화를 사용해야 해요. 하지만 이 토큰화는 검색 작업에 적합하지 않아요. 어떻게 해야 할까요?

사실 우리가 생각해 낸 해결책은 꽤 간단해요. attention 벡터를 얻은 후 토큰화 과정을 역으로 되돌리는 거예요.

Transformer는 WordPiece 토큰화를 사용해요. 어휘에 없는 단어를 만나면 하위 단어로 쪼개요. 이렇게 보이죠:

"unbelievable" -> ["un", "##believ", "##able"]

하위 단어를 다시 단어로 병합할 수 있어요. 다행히 하위 단어는 ## 접두사로 표시되므로 쉽게 감지할 수 있어요. attention 가중치가 정규화되어 있으므로, 하위 단어들의 attention 가중치를 더하면 그 단어의 attention 가중치를 얻을 수 있어요.

그 후에는 전통적인 NLP 기법을 그대로 적용할 수 있어요:

불용어(stop-word) 제거
구두점 제거
표제어 추출(Lemmatization)

이런 식으로 토큰 수를 크게 줄여서 sparse 임베딩의 메모리 사용량을 최소화할 수 있어요. (거의) 정확한 토큰 매칭 능력을 훼손하지 않으면서 말이죠.

실용 예제

Trait	BM25	SPLADE	BM42
Interpretability	High ✅	Ok 🆗	High ✅
Document Inference speed	Very high ✅	Slow 🐌	High ✅
Query Inference speed	Very high ✅	Slow 🐌	Very high ✅
Memory footprint	Low ✅	High ❌	Low ✅
In-domain accuracy	Ok 🆗	High ✅	High ✅
Out-of-domain accuracy	Ok 🆗	Low ❌	Ok 🆗
Small documents accuracy	Low ❌	High ✅	High ✅
Large documents accuracy	High ✅	Low ❌	Ok 🆗
Unknown tokens handling	Yes ✅	Bad ❌	Yes ✅
Multi-lingual support	Yes ✅	No ❌	Yes ✅
Best Match	Yes ✅	No ❌	Yes ✅

Qdrant v1.10.0부터 BM42를 FastEmbed 추론을 통해 Qdrant에서 사용할 수 있어요.

BM42와 jina.ai dense 임베딩으로 하이브리드 검색을 위한 컬렉션을 어떻게 설정하는지 볼게요.

PUT collections/my-hybrid-collection
{
  "vectors": {
    "jina": {
      "size": 768,
      "distance": "Cosine"
    }
  },
  "sparse_vectors": {
    "bm42": {
      "modifier": "idf" // <--- This parameter enables the IDF calculation
    }
  }
}

from qdrant_client import QdrantClient, models

client = QdrantClient()

client.create_collection(
    collection_name="my-hybrid-collection",
    vectors_config={
        "jina": models.VectorParams(
            size=768,
            distance=models.Distance.COSINE,
        )
    },
    sparse_vectors_config={
        "bm42": models.SparseVectorParams(
            modifier=models.Modifier.IDF,
        )
    }
)

검색 쿼리는 dense와 sparse 임베딩 둘 다로 문서를 가져온 다음, Reciprocal Rank Fusion(RRF) 알고리즘으로 점수를 결합해요.

from fastembed import SparseTextEmbedding, TextEmbedding

query_text = "best programming language for beginners?"

model_bm42 = SparseTextEmbedding(model_name="Qdrant/bm42-all-minilm-l6-v2-attentions")
model_jina = TextEmbedding(model_name="jinaai/jina-embeddings-v2-base-en")

sparse_embedding = list(model_bm42.query_embed(query_text))[0]
dense_embedding = list(model_jina.query_embed(query_text))[0]

client.query_points(
  collection_name="my-hybrid-collection",
  prefetch=[
      models.Prefetch(query=sparse_embedding.as_object(), using="bm42", limit=10),
      models.Prefetch(query=dense_embedding.tolist(),  using="jina", limit=10),
  ],
  query=models.FusionQuery(fusion=models.Fusion.RRF), # <--- Combine the scores
  limit=10
)

벤치마크

이 주장을 더 뒷받침하기 위해 BM42가 BM25를 능가하는 사례를 강조하는 몇 가지 벤치마크를 수행했어요. 새로운 모델이 아닌 새로운 접근 방식을 제시하는 것이므로, 완전한 평가를 의도하지 않았다는 점을 유의해 주세요.

실험에는 질문 중복 제거 작업(Question-Deduplication)을 나타내는 quora 데이터셋을 선택했어요.

이 데이터셋의 전형적인 예는 다음과 같아요:

{"_id": "109", "text": "How GST affects the CAs and tax officers?"}
{"_id": "110", "text": "Why can't I do my homework?"}
{"_id": "111", "text": "How difficult is it get into RSI?"}

보다시피 꽤 짧은 텍스트들이라 의존할 통계가 많지 않아요.

BM42로 인코딩한 후 평균 벡터 크기는 문서당 단 5.6개 요소예요.

Qdrant에서 사용 가능한 datatype: uint8을 사용하면, ~530k 문서에 대한 sparse 벡터 인덱스의 총 크기는 약 13MB예요.

참고로 다음을 사용해요:

tantivy를 사용한 BM25
BM42와 동일한 전처리 파이프라인(토큰화, 불용어 제거, 표제어 추출)을 사용한 sparse 벡터 BM25 구현

	BM25 (tantivy)	BM25 (Sparse)	BM42
~~Precision @ 10~~ *	~~0.45~~	~~0.45~~	~~0.49~~
Recall @ 10	~~0.71~~ 0.89	0.83	0.85

* - 값은 평가 스크립트의 오류로 인해 출판 후 수정되었습니다.

참고: 제대로 사용하면 tantivy를 사용한 BM25가 최상의 결과를 냅니다. 우리의 초기 구현은 잘못된 문자 이스케이프를 수행해서 tantivy의 recall@10 값을 과소평가했습니다.

벤치마크를 투명하게 공개하기 위해 평가에 사용한 스크립트를 게시했어요: github 저장소를 확인하세요.

참고로 BM25와 BM42 모두 생산 환경에서 단독으로는 잘 동작하지 않아요. 최상의 결과는 하이브리드 방식으로 sparse와 dense 임베딩을 결합할 때 얻을 수 있어요. 이 시나리오에서 두 모델은 서로 보완적이에요. Sparse 모델은 정확한 토큰 매칭을 담당하고, dense 모델은 의미 매칭을 담당하죠.

우리가 사용했던 기본 sentence-transformers/all-MiniLM-L6-v2 모델보다 더 발전된 모델이 더 나은 성능을 낼 수도 있어요. 임베딩 모델 학습에 참여하는 개발자 분들이 attention 가중치를 추출하는 방법을 포함시키고 BM42 백엔드에 기여해 주시길 권장합니다.

호기심과 실험 키우기

모든 장점에도 불구하고 BM42가 항상 만능 해결책(silver bullet)은 아니에요. 청크가 없는 큰 문서에서는 BM25가 여전히 더 나은 선택일 수 있어요.

transformer에서 중요도 정보를 추출하는 더 똑똑한 방법이 있을 수도 있고, IDF와 attention 점수를 서로 어떻게 가중할지에 대한 더 나은 방법이 있을 수도 있어요.

Qdrant는 모델 학습을 전문으로 하지 않아요. 우리의 핵심 프로젝트는 검색 엔진 자체예요. 하지만 우리가 진공 상태에서 운영되지 않는다는 걸 이해하고 있어요. BM42를 소개함으로써 커뮤니티에 실험을 위한 새로운 도구를 제공하는 데 한 걸음 나아가고 있어요.

우리는 sparse 벡터 방식이 강력하면서도 유연한 결과를 만들어 낼 수 있는 정확한 추상화 수준에 있다고 진심으로 믿어요.

많은 분이 최근 Qdrant 프로젝트를 Discord 채널에서 공유하고 있어요. BM42를 써 보고 어떤 결과를 얻는지 알려주세요.

BM42: 어휘 검색의 다음 진화