벡터 검색이 느리다면? HNSW 2-pass·배치 거리·AVX-512로 KNN 속도 끌어올리기

요즘 AI 서비스를 만들다 보면 ‘벡터 검색’이라는 말을 정말 자주 듣게 되거든요. 챗봇한테 우리 회사 문서를 학습시켜서 질문에 답하게 하는 RAG, 비슷한 상품 추천, 이미지나 음악 유사도 찾기 같은 기능이 전부 이 벡터 검색 위에서 돌아가요. 그런데 이게 데이터가 많아지면 갑자기 확 느려진다는 게 문제예요. 오픈소스 검색엔진인 Manticore Search가 자기네 KNN 검색을 어떻게 더 빠르게 만들었는지 정리한 글이 나왔는데, 거기서 쓴 세 가지 기법이 벡터 검색을 만지는 사람이라면 누구나 알아두면 좋은 내용이라 한번 풀어볼게요.

그래서 KNN이 뭐냐면요

KNN은 ‘K-Nearest Neighbors’, 우리말로 하면 ‘가장 가까운 이웃 K개 찾기’예요. 요즘은 글이든 이미지든 전부 숫자 묶음(벡터)으로 바꿔서 다루거든요. 이걸 임베딩이라고 해요. 의미가 비슷한 문장은 벡터 공간에서도 서로 가까운 위치에 찍혀요. 그래서 ‘이 질문과 가장 비슷한 문서 5개’를 찾는다는 건, 결국 ‘이 벡터와 거리가 가장 가까운 벡터 5개’를 찾는 일이 되는 거죠.

문제는 이 ‘거리 계산’이 공짜가 아니라는 거예요. 벡터 하나가 보통 수백~수천 개의 숫자로 되어 있고, 데이터가 100만 개라면 질문 하나 들어올 때마다 100만 번을 일일이 다 비교해야 정확한 답이 나와요. 이걸 brute force(전수조사)라고 하는데, 정확하긴 한데 너무 느려요. 그래서 등장한 게 ANN, 즉 ‘근사 최근접 이웃 검색’이에요. 100% 정답은 아니어도 99% 정도로 거의 맞으면서 훨씬 빠르게 찾자는 거죠.

HNSW: 전수조사 대신 고속도로 타기

ANN의 대표주자가 바로 HNSW예요. 풀어 쓰면 ‘Hierarchical Navigable Small World’, 계층형 그래프 구조인데요. 이게 뭐냐면, 데이터들을 서로 연결한 지도를 만들어 두고 그 위를 점프하면서 목적지에 가까워지는 방식이에요.

비유를 하나 들어볼게요. 서울에서 부산의 어느 골목집을 찾아간다고 해봐요. 모든 길을 다 걸어서 확인하면 평생 걸리잖아요. 대신 일단 고속도로를 타고 부산까지 크게 이동하고(상위 계층), 시내에 들어와서 국도로 동네까지 가고(중간 계층), 마지막에 골목길로 집을 찾아가요(하위 계층). HNSW가 딱 이래요. 위쪽 계층은 듬성듬성 연결돼 있어서 멀리 단번에 점프하고, 아래로 내려갈수록 촘촘해져서 정밀하게 목적지를 찾아요. 덕분에 100만 개를 다 안 봐도 수십~수백 번 점프로 답에 도달해요.

1단계는 빠르게, 2단계는 정밀하게 (2-pass)

여기서 Manticore가 쓴 첫 번째 최적화가 ‘2-pass’, 두 번 훑기예요. HNSW로 그래프를 돌아다닐 때도 거리 계산은 계속 일어나는데, 이 계산을 매번 풀(full) 정밀도로 하면 비싸요. 그래서 1차 패스에서는 가볍고 거친 계산으로 ‘유망한 후보들’을 빠르게 추려요. 그리고 2차 패스에서 그 후보들만 정밀하게 다시 계산해서 순위를 바로잡는 거죠.

마치 서류전형으로 100명 중 10명을 빠르게 거르고, 그 10명만 면접으로 꼼꼼히 보는 거랑 같아요. 모두를 면접 보면 시간이 너무 많이 드니까, 싸게 거르고 비싸게 확정하는 2단 구조로 전체 비용을 확 줄이는 거예요.

거리 계산을 묶어서, CPU를 제대로 굴리기 (배치 + AVX-512)

두 번째랑 세 번째 기법은 한 묶음으로 보면 이해가 쉬워요. 바로 ‘배치 거리 계산’과 ‘AVX-512’예요.

배치 거리 계산은 거리를 하나씩 따로 계산하지 말고 여러 개를 한꺼번에 묶어서 계산하자는 거예요. 거리 계산 자체보다 데이터를 메모리에서 꺼내 오고 함수를 호출하는 부대비용이 의외로 크거든요. 묶어서 처리하면 이 부대비용을 여러 계산이 나눠 가지니까 개당 비용이 내려가요.

그리고 AVX-512는 인텔 CPU에 들어있는 특수 명령어 세트예요. 이게 뭐냐면, 보통 CPU는 숫자 하나 더하기를 한 번에 하나씩 하는데, AVX-512는 한 번의 명령으로 숫자 여러 개(예를 들어 32비트 실수 16개)를 동시에 더하거나 곱할 수 있어요. 이걸 SIMD(Single Instruction, Multiple Data), 즉 ‘명령 하나로 데이터 여러 개’라고 불러요. 벡터 거리 계산은 결국 숫자들을 빼고 제곱하고 더하는 단순 반복이라서 SIMD랑 궁합이 환상적이에요. 배치로 데이터를 가지런히 모아두면 AVX-512가 그걸 한 입에 먹기 딱 좋은 모양이 되니까, 이 둘은 같이 갈 때 시너지가 나는 거예요.

다른 벡터 검색 도구들과 비교해보면

벡터 검색 엔진은 지금 춘추전국시대예요. 페이스북(메타)이 만든 FAISS는 라이브러리 형태로 가장 널리 쓰이고, Milvus나 Qdrant는 벡터 전용 데이터베이스로 인기가 많아요. PostgreSQL 쓰는 사람은 pgvector 확장을 많이 붙이고, Elasticsearch나 OpenSearch도 벡터 검색을 지원해요. 사실 HNSW, 양자화, SIMD 같은 핵심 기법은 이들 대부분이 공유하고 있어요.

Manticore가 특별한 건, 원래 텍스트 전문검색(풀텍스트 서치) 엔진인데 거기에 벡터 검색을 얹어서 키워드 검색과 의미 검색을 한 엔진에서 같이 한다는 점이에요. 요즘 검색 트렌드인 ‘하이브리드 검색’(키워드 + 의미)을 별도 시스템 없이 처리할 수 있다는 거죠. 그러면서 GPU 없이 CPU만으로 속도를 끌어올리는 데 공을 들였는데, 비싼 GPU 없이 일반 서버 CPU로 버텨야 하는 많은 팀에게 현실적으로 와닿는 방향이에요.

한국 개발자에게 주는 의미

당장 RAG나 추천 시스템을 만들고 있다면, 이 세 가지 키워드는 그냥 지나칠 게 아니에요. 벡터 검색이 느릴 때 사람들은 보통 ‘GPU를 더 사자’ ‘인덱스 파라미터를 바꾸자’로 가는데, 사실 2-pass로 거를지, 거리 계산을 배치로 묶을지, CPU의 SIMD를 제대로 쓰고 있는지 같은 저수준 최적화에서 답이 나오는 경우가 많거든요.

특히 AVX-512 같은 SIMD 개념은 벡터 검색뿐 아니라 이미지 처리, 데이터 압축, 암호화 등 성능이 중요한 거의 모든 분야에서 통하는 무기예요. 라이브러리가 알아서 해주니까 평소엔 몰라도 되지만, ‘왜 이 코드가 빠른가/느린가’를 이해하려면 이런 바닥 원리를 알아두는 게 큰 차이를 만들어요. 직접 구현하지 않더라도 라이브러리를 고를 때 ‘이건 SIMD 최적화가 됐나?’를 따질 수 있게 되는 것만으로도 가치가 있어요.