벡터 검색: 임베딩과 근사 최근접 이웃(HNSW·Faiss)

왜 필요했나: 단어 맞추기 검색과 느린 문장 비교의 한계

오랫동안 문서 검색의 표준은 TF-IDF나 BM25 같은 키워드 방식이었다. 질문과 문서에 같은 단어가 얼마나 겹치는지를 세고, 역색인(단어→문서 목록 표)으로 빠르게 찾는다. 빠르고 튼튼하지만 단어가 다르면 놓친다. DPR 논문(2004.04906)이 든 예가 있다. "Who is the bad guy in lord of the rings?"라는 질문의 답은 "villain Sauron"이 나오는 문장에 있는데, 'bad guy'와 'villain'은 겹치는 단어가 없어 키워드 검색으로는 찾기 어렵다.

의미를 잘 이해하는 BERT 같은 모델을 쓰면 되지 않을까? 문제는 비용이다. BERT로 두 문장의 유사도를 재려면 두 문장을 한꺼번에 모델에 넣어야 한다. Sentence-BERT 논문(1908.10084)에 따르면 1만 개 문장에서 가장 비슷한 쌍을 찾는 데 약 5천만 번의 추론, 약 65시간이 걸린다. 검색처럼 질문이 들어올 때마다 바로 답해야 하는 일에는 쓸 수 없다.

규모 문제도 있다. DPR 실험에서 쓴 위키백과 문단만 2,100만 개였고, 웹 전체라면 수십억 개다. 의미로 비교하되, 질문 하나에 문서 전부를 일일이 비교하지 않는 방법이 필요했다. 이 두 과제를 푸는 것이 각각 '임베딩'과 '근사 최근접 이웃 검색'이다.

핵심 아이디어: 의미를 좌표로, 검색을 '가까운 점 찾기'로

비유하면 도서관의 모든 문단을 거대한 지도 위의 점으로 찍어 두는 것이다. 뜻이 비슷한 문단은 가까운 곳에, 다른 문단은 먼 곳에 놓이도록 좌표를 정한다. 이 좌표가 임베딩(Embedding)이다. 실제로는 2차원이 아니라 수백 차원의 숫자 목록이다. 질문이 오면 질문도 같은 지도에 점으로 찍고, 그 주변의 가장 가까운 점 몇 개를 가져오면 그것이 검색 결과다.

여기에는 두 가지 생각이 겹쳐 있다. 첫째, 문서 좌표는 미리 한 번만 계산해 둔다. 질문이 올 때는 질문 하나만 모델에 넣으면 되니, BERT로 모든 쌍을 비교하던 비용이 사라진다. 둘째, '가장 가까운 점'을 정확히 찾으려고 모든 점과 거리를 재지 않는다. 대부분 맞지만 가끔 한두 개를 놓칠 수 있는 '근사' 검색을 받아들이는 대신 속도를 크게 얻는다. 이것이 근사 최근접 이웃(ANN, Approximate Nearest Neighbor) 검색이다.

그래서 벡터 검색의 품질은 두 층으로 나뉜다. 좌표를 잘 찍었는가(임베딩 모델의 품질), 그리고 가까운 점을 잘 찾아오는가(색인의 재현율과 속도). 둘 중 하나만 좋아서는 좋은 검색이 되지 않는다.

어떻게 작동하나: 색인을 만들고, 질문으로 찾는다

준비 단계부터 보자. ① 문서를 검색 단위로 자른다(청킹). DPR은 문서를 같은 길이의 문단으로 나눴고, 자연 문단보다 고정 길이가 검색과 최종 정답률 모두에서 나았다고 보고했다. ② 각 조각을 임베딩 모델에 넣어 벡터로 바꾼다. ③ 벡터들을 빠르게 찾을 수 있는 색인 구조에 넣는다. 이 단계는 시간이 걸려도 미리 해 두면 된다.

질문 단계는 이렇다. ④ 질문을 같은 임베딩 공간의 벡터로 바꾼다. DPR은 질문용과 문단용 인코더를 따로 두는 '듀얼 인코더'를 썼고, SBERT는 같은 네트워크를 공유하는 '샴(siamese)' 구조를 썼다. 어느 쪽이든 두 벡터를 내적이나 코사인 유사도로 비교할 수 있게 학습한다. ⑤ 색인에서 질문 벡터와 가까운 상위 k개를 찾는다. ⑥ 필요하면 리랭커로 다시 정렬하거나 LLM에 넘겨 답을 만든다(RAG).

색인 방식은 크게 두 계열이다. 그래프 방식의 대표인 HNSW(1603.09320)는 벡터를 점, 가까운 이웃 관계를 선으로 한 그래프를 여러 층으로 쌓는다. 각 벡터가 들어갈 최고 층은 위로 갈수록 확률이 급격히 줄어드는 무작위 추첨으로 정해서, 위층에는 점이 드문드문하고 연결선이 길며 아래층은 촘촘하다. 검색은 고속도로로 근처 도시까지 간 다음 국도, 골목으로 내려가는 것처럼 맨 위층에서 시작해 한 층씩 내려가며 가까운 쪽으로 이동한다. 다른 계열은 벡터 공간을 여러 구역으로 나누고(IVF, 역파일 색인) 질문과 가까운 구역 몇 개만 뒤지거나, 곱 양자화(PQ)처럼 벡터를 짧은 코드로 압축해 메모리와 계산을 줄이는 방식이다. GPU 유사도 검색 논문(1702.08734)은 바로 이 압축 영역 검색과 전수 비교를 GPU에서 빠르게 하는 설계를 다뤘다.

여기서 성능을 보는 기준은 재현율(recall)이다. 정확히 계산했을 때의 진짜 상위 k개 중 몇 개를 색인이 찾아왔는지다. 탐색 범위를 넓히면 재현율은 오르고 속도는 떨어진다. 이 균형점을 고르는 것이 실제 운영의 핵심 조정 작업이다.

발전 흐름: 다섯 편의 출발점이 각각 새로 한 것

색인 쪽부터 보자. HNSW(2016)는 기존 근접 그래프 방법들이 쓰던 별도의 '거친 탐색' 구조 없이 그래프만으로 검색을 끝냈다. 층마다 연결 거리의 규모를 나누고 맨 위층에서 출발하게 해서 탐색 비용이 데이터 크기에 대해 로그 수준으로 늘게 했다. 또 이웃을 고를 때 단순히 가장 가까운 점만이 아니라 휴리스틱으로 선별해, 높은 재현율 구간과 데이터가 뭉쳐 있는 경우에 성능을 크게 올렸다. 구조가 스킵 리스트와 비슷해 분산 구현이 쉽다는 점도 짚었다.

GPU 유사도 검색 논문(2017)은 GPU의 병렬성을 제대로 쓰지 못하게 막던 병목, 특히 '가장 작은 k개 고르기(k-selection)'를 다시 설계했다. 이론 최대 성능의 최대 55%로 동작하는 k-selection으로 이전 GPU 최고 기록보다 8.5배 빠른 최근접 이웃 검색을 구현했고, 전수 비교·근사·곱 양자화 압축 검색 모두에 적용했다. Maxwell Titan X GPU 4장으로 10억 개 벡터를 잇는 그래프를 12시간 안에 만들었다. 이 구현은 오픈소스로 공개됐다. 이 글 제목의 Faiss는 이런 계열의 공개 유사도 검색 라이브러리를 가리키는 이름으로 흔히 쓰인다.

임베딩 쪽에서는 SBERT(2019)가 BERT를 샴·삼중항(triplet) 구조로 고쳐 코사인 유사도로 바로 비교할 수 있는 문장 벡터를 만들었다. 1만 문장 비교 시간을 약 65시간에서 약 5초로 줄이면서 정확도는 유지했다. DPR(2020)은 이를 열린 도메인 질의응답 검색에 적용했다. 이전에는 좋은 밀집 벡터를 얻으려면 비싼 추가 사전학습이 필요하다고 여겨졌지만, DPR은 질문-문단 쌍만으로 두 인코더를 학습하고, 한 배치 안의 모든 질문-문단 쌍을 서로 비교하는 단순한 목표만으로 BM25를 크게 앞섰다(Top-5 정확도 65.2% 대 42.9%). 검색 정확도가 오르면 최종 답변 정확도도 오른다는 점도 확인했다.

마지막으로 MTEB(2022)는 평가 문제를 다뤘다. 임베딩이 몇 개의 데이터셋에서만 평가되던 상황에서 8개 작업, 58개 데이터셋, 112개 언어로 33개 모델을 비교했다. 결론은 '모든 작업에서 이기는 임베딩 방법은 없다'였다. 유사도 판별에 강한 모델이 군집화나 재정렬에서도 강하리라는 보장은 없다는 뜻이다.

요즘 어디로 가고 있나: 메모리 밖, 조건 붙은 검색, 모델 교체

최근 연구는 '빠르게 찾는다'를 넘어 실제 서비스에서 부딪히는 운영 문제로 옮겨 가고 있다. 첫째는 메모리에 다 들어가지 않는 규모다. RaBitQ-SSD(2610.02652)는 벡터가 DRAM보다 많을 때 SSD에 두고 검색하는 문제를 다룬다. 그래프 탐색은 후보를 한 걸음씩 발견하기 때문에 SSD 읽기를 미리 계획하기 어렵고, IVF는 구역 목록을 통째로 읽어 낭비가 생긴다는 점을 짚었다. 이진 코드의 앞부분만 메모리에 두고 오차 범위가 있는 거리 추정으로 후보를 걸러 꼭 필요한 것만 SSD에서 읽는다. 90% 재현율에서 그래프 기반 방법보다 처리량이 최대 1.74배, SSD 페이지 읽기는 최대 3.8배 적었고, 한 대의 머신과 SSD로 100억 개 벡터 색인을 만들고 검색했다.

둘째는 조건이 붙은 검색이다. 실제로는 '2025년 이후 문서 중에서', '이 부서 자료 중에서'처럼 필터를 함께 건다. VADER(2609.38053)는 필터가 얼마나 많은 벡터를 통과시키는지(선택도), 필터와 벡터 공간이 어떻게 얽혀 있는지(상관)에 따라 같은 질문도 난이도가 크게 달라져 사람이 매개변수를 일일이 조정해야 하는 문제를 짚었다. 사용자가 원하는 재현율 목표만 정하면 예측기가 재현율을 추정하다가 목표에 닿으면 탐색을 멈추는 '선언적 재현율'을 제안했고, 가장 좋은 기준 방법보다 최대 53% 빠르고 결과 품질은 28% 나았다고 보고했다.

셋째는 임베딩 모델을 바꿀 때의 비용이다. DGM(2609.23036)은 그래프 색인의 연결선이 만들 때의 거리로 정해지기 때문에 색인이 특정 임베딩 모델에 묶인다는 점을 문제로 삼았다. 새 모델로 다시 인코딩하면 그래프를 처음부터 다시 만들어야 한다. 그런데 모델이 달라도 같은 대상을 묘사하므로 옛 그래프에서 몇 걸음 안에 새 모델 기준의 진짜 이웃이 상당수 닿는다는 현상(잔여 도달성)을 관찰하고, 이를 이용해 새 색인을 더 빨리 만드는 이전 방법을 제안했다. 세 연구 모두 HNSW와 GPU 검색이 연 '빠른 근사 검색'을 전제로, 규모·조건·변화라는 현실 제약을 다루고 있다.

한계와 쟁점

첫째, 근사는 근사다. ANN은 진짜 가장 가까운 문서를 가끔 놓친다. RAG에서 정답이 든 문단이 상위 k개에서 빠지면 LLM은 근거 없이 답하게 되고, 이것이 환각으로 이어질 수 있다. 재현율 목표를 어떻게 정하고 어떻게 검증할지가 늘 숙제다. VADER 같은 연구가 나오는 이유도 이 조정이 어렵기 때문이다.

둘째, 밀집 검색이 키워드 검색을 대체하지는 않는다. DPR 논문 스스로 밀집 표현은 희소 표현과 '설계상 상보적'이라고 썼다. 의미가 비슷한 문장은 잘 찾지만 제품 코드, 사람 이름, 정확한 숫자처럼 글자 그대로 맞아야 하는 질의는 BM25가 강할 수 있다. 실무에서 둘을 섞는 하이브리드 검색을 많이 쓰는 배경이다.

셋째, 임베딩 선택에 정답이 없다. MTEB는 어떤 방법도 모든 작업을 지배하지 못한다고 보고했다. 공개 순위표 1위 모델이 우리 회사 문서에서도 1위라는 보장은 없다. 또 DGM이 보여 주듯 색인은 임베딩 모델에 묶여 있어서, 모델을 바꾸면 전체 재인코딩과 재색인 비용이 생긴다. 모델 선택은 한 번의 결정이 아니라 장기 운영 비용과 이어진다.

넷째, 메모리와 비용의 균형이다. 그래프 색인은 빠르지만 원본 벡터와 연결선을 메모리에 두어야 하고, 압축(양자화)은 메모리를 줄이는 대신 거리 계산의 정확도를 조금 잃는다. 규모가 커질수록 SSD 활용(RaBitQ-SSD)처럼 저장 위치 자체를 다시 설계해야 한다.

더 공부하려면

비전공자라면 SBERT(1908.10084) 초록부터 읽기를 권한다. '왜 문장마다 벡터를 미리 만들어 두는가'가 65시간 대 5초라는 숫자로 분명하게 드러난다. 그다음 DPR(2004.04906)의 서론을 읽으면 키워드 검색과 의미 검색의 차이, 검색이 RAG 전체 성능에 미치는 영향을 예시와 함께 이해할 수 있다.

색인 구조가 궁금한 개발자라면 HNSW(1603.09320)가 출발점이다. 층 구조와 이웃 선택 휴리스틱이 왜 필요한지 보고 나면 벡터 DB 설정 항목들이 무엇을 조정하는지 감이 온다. 대규모·압축 검색과 GPU 활용은 GPU 유사도 검색 논문(1702.08734)으로 이어 읽으면 된다.

임베딩 모델을 고르는 입장이라면 MTEB(2210.07316)로 평가 관점을 잡고, 운영 단계의 고민이 있다면 RaBitQ-SSD(2610.02652, 대규모·SSD), VADER(2609.38053, 필터 검색), DGM(2609.23036, 모델 교체) 순으로 자기 상황에 맞는 것을 고르면 된다.