HNSW를 벡터 DB보다 그래프 탐색으로 읽게 된 이유

2026년 4월 3일 | 개발 공부

---

HNSW는 Hierarchical Navigable Small World의 약자로, 고차원 벡터들 사이에 다층 그래프를 만들어 근사 최근접 탐색을 빠르게 수행하는 인덱스 구조다. 쉽게 말하면 모든 벡터를 처음부터 끝까지 훑는 대신, 상층에서는 멀리 점프하고 하층에서는 더 촘촘하게 주변을 살피면서 가까운 후보를 좁혀 가는 방식이다. 벡터 DB에서 자주 보이는 이유도 결국 이 구조가 recall과 latency의 균형을 현실적으로 잘 잡아주기 때문이다. 그래서 이 글도 HNSW를 단순한 벡터 DB 옵션이 아니라, 그래프 위를 이동하며 이웃을 찾는 탐색 전략으로 이해하려는 관점에서 정리했다.

벡터 검색을 처음 접했을 때 나는 한동안 이걸 거의 마법처럼 받아들였다. 임베딩만 잘 만들면 비슷한 문서를 금방 찾아주고, 규모가 커져도 생각보다 빨랐기 때문이다. 그런데 조금 지나고 나서야 내가 놓치고 있던 게 보였다. 빠른 이유가 벡터라는 표현 방식 자체에만 있는 게 아니라, 그 벡터들 사이를 어떻게 건너뛸지 미리 구조화해 둔 탐색 방식에 더 가까웠다. 그 뒤로 HNSW를 볼 때 내 머릿속에서는 "벡터 DB의 기능"보다 "가까운 점을 발판 삼아 그래프 위를 이동하는 검색"이라는 그림이 먼저 떠오른다.

이 감각이 생기고 나서야 왜 어떤 인덱스는 recall이 좋고, 왜 어떤 설정은 속도는 빨라지는데 결과가 금방 거칠어지는지 조금 덜 막연해졌다. 예전에는 파라미터 이름을 외우는 쪽에 가까웠다면, 지금은 적어도 각 설정이 그래프를 얼마나 촘촘하게 만들고, 검색 시 얼마나 오래 주변을 더듬게 하는지로 연결해서 보게 된다. 나는 이런 식으로 개념이 바뀌고 나서야 HNSW가 단순한 라이브러리 옵션이 아니라 검색 품질과 지연 시간을 같이 설계하는 자료구조처럼 읽히기 시작했다.

1. 처음에는 왜 이렇게 빠른지보다 그냥 잘 된다는 사실만 보였다

현업에서 벡터 검색을 처음 붙일 때는 대부분 "문서를 임베딩하고 top-k를 뽑는다" 정도의 흐름부터 본다. 나도 그랬다. 작은 데이터셋에서는 브루트포스로도 결과가 그럭저럭 나오고, 라이브러리를 쓰면 인덱스가 알아서 빨라지니까 내부가 얼마나 복잡한지 굳이 의식하지 않게 된다. 문제는 데이터가 커지고 지연 시간 목표가 생기기 시작하면 그때부터다. 같은 임베딩 모델을 써도 인덱스 설정에 따라 체감 품질이 꽤 달라지고, 질의마다 들쭉날쭉한 결과가 나오는 순간이 생긴다.

그때 예전의 나는 자꾸 임베딩 품질만 의심했다. 물론 임베딩이 중요한 건 맞지만, 모든 문제가 임베딩 탓은 아니었다. 어느 시점부터는 검색이 벡터 공간 안에서 무작정 가장 가까운 점을 찾는 일이 아니라, 제한된 시간 안에 꽤 괜찮은 후보를 얼마나 안정적으로 만나는가의 문제가 된다. 이 관점으로 넘어가야 HNSW가 왜 널리 쓰이는지 설명이 된다.

• 작은 규모에서는 브루트포스와 ANN의 차이가 체감되지 않을 수 있다.
• 규모가 커질수록 "정확히 최적"보다 "충분히 좋은 후보를 빨리 찾기"가 더 실전적인 목표가 된다.
• 이 지점에서 검색 알고리즘의 구조가 임베딩 자체만큼 중요해진다.

나는 이걸 이해하고 나서야 벡터 검색 품질을 볼 때 모델과 인덱스를 분리해서 보게 됐다. 표현이 좋아도 탐색이 거칠면 좋은 이웃을 놓칠 수 있고, 반대로 표현이 아주 완벽하지 않아도 탐색 구조가 안정적이면 실사용에서는 꽤 괜찮게 버티는 경우가 있다.

2. HNSW를 이해하는 데 제일 도움이 된 건 '그래프 위에서 점프한다'는 비유였다

HNSW라는 이름을 처음 보면 약간 겁부터 난다. 계층형, 네비게이블, 스몰 월드 같은 단어가 한꺼번에 붙어 있어서 구조가 어렵게 느껴진다. 그런데 내 기준에서 제일 이해가 빨랐던 설명은 의외로 단순했다. 모든 벡터를 일렬로 스캔하는 대신, 각 점이 몇 개의 이웃과 연결된 그래프를 만들고 그 위를 탐색한다고 생각하는 것이다. 그리고 먼 범위에서는 성긴 그래프로 크게 이동하고, 아래층으로 내려올수록 더 촘촘한 그래프에서 미세 조정을 한다고 보면 흐름이 잡힌다.

이 설명이 좋은 이유는, HNSW의 속도를 숫자 최적화가 아니라 이동 전략으로 이해하게 해 주기 때문이다. 시작점이 완벽하지 않아도 주변 이웃을 타고 조금씩 더 가까운 곳으로 이동하면 좋은 후보를 꽤 빨리 만날 수 있다. 완전탐색처럼 모든 점을 확인하지 않더라도, 그래프 연결이 잘 되어 있으면 "먼 곳에서 대충 접근하고 가까워질수록 정밀하게 좁히는" 식의 검색이 가능해진다.

상층 그래프: 멀리 점프하면서 대략적인 위치를 잡는다
하층 그래프: 근처 이웃을 더 세밀하게 훑는다
검색 감각: 전체를 보는 대신 좋은 발판을 따라 내려간다

나는 이 구조를 이해한 뒤에야 HNSW가 단순한 압축 기법이 아니라는 걸 받아들였다. 핵심은 데이터를 덜 보는 게 아니라, 어디부터 봐야 할지를 그래프 연결로 미리 학습해 둔다는 쪽에 가깝다. 그래서 검색은 수학적으로는 근사 최근접 탐색이지만, 구현 감각으로는 길을 잘 찾는 문제처럼 느껴진다.

3. 그래서 recall과 latency의 균형이 그래프 밀도와 탐색 폭으로 바뀌어 보였다

HNSW를 겉으로만 보면 파라미터가 몇 개 안 된다. 그런데 그 몇 개가 전부 검색 성격을 꽤 크게 바꾼다. 내가 특히 이해가 늦었던 건 M, efConstruction, efSearch가 각각 무엇을 희생하고 무엇을 얻는지였다. 문서에는 설명이 있어도 실제 감각으로 잘 안 들어왔는데, 그래프 관점으로 바꾸니 조금 선명해졌다.

M은 대략 각 노드가 얼마나 많은 이웃을 기억할지에 가깝다. 이 값이 커지면 그래프 연결은 더 풍부해지고, 돌아서 가야 할 길이 줄어들 수 있다. 대신 메모리 사용량과 인덱스 구축 비용이 올라간다. efConstruction은 인덱스를 만들 때 후보를 얼마나 넓게 보며 연결을 정교하게 만들지와 연결된다. 이 값이 높을수록 인덱스 품질은 좋아질 가능성이 크지만, 빌드 시간이 더 든다. efSearch는 질의 시점에 얼마나 오래 주변을 탐색할지에 가깝다. 크게 주면 recall은 올라가지만 응답은 느려진다.

설정	내가 이해한 역할	커질 때 주로 얻는 것	같이 늘어나는 비용
M	노드당 연결 폭	더 안정적인 이동 경로	메모리, 빌드 비용
efConstruction	인덱스 생성 시 탐색 폭	더 나은 그래프 품질	구축 시간
efSearch	질의 시 탐색 폭	더 높은 recall	응답 지연

이 표를 내 식으로 줄이면 결국 이렇다. 좋은 그래프를 미리 비싸게 만들어 둘지, 질의 때 더 오래 돌아다닐지를 나눠 조절하는 구조다. 그래서 운영에서는 한 번에 최적값을 찾기보다, 데이터 크기와 지연 시간 예산에 맞춰 어느 쪽 비용을 더 감당할지 정하는 문제가 된다.

4. 실제 서비스 감각에서는 '항상 최고 recall'보다 '덜 흔들리는 recall'이 더 중요했다

문서 검색이나 RAG를 붙이다 보면 top-1이 아주 정확한 날도 있고, 조금만 데이터가 늘어도 결과가 미묘하게 흔들리는 날도 있다. 이때 숫자 하나만 보면 자꾸 최고 recall을 올리는 쪽으로 생각이 기울기 쉽다. 그런데 실제 서비스에서는 평균 최고점보다도 질의 분포가 바뀌어도 결과 품질이 너무 요동치지 않는 상태가 더 중요할 때가 많다. 나는 이 지점을 HNSW가 꽤 현실적으로 풀어준다고 느낀다.

그래프 기반 탐색은 무식하게 빠르기만 한 구조라기보다, 질의마다 조금씩 다른 출발점과 경로를 가지더라도 전반적으로 괜찮은 후보를 만나게 해 주는 안전장치에 가깝다. 물론 데이터 분포가 심하게 바뀌거나 임베딩이 도메인을 잘 못 잡으면 한계가 있다. 그래도 HNSW를 이해한 뒤에는 결과가 흔들릴 때 무작정 임베딩 모델부터 바꾸기보다, 먼저 인덱스 설정과 탐색 폭이 현재 데이터 밀도에 맞는지를 같이 보게 됐다.

• 검색 품질이 흔들릴 때 원인이 항상 임베딩 모델인 것은 아니다.
• 후보 탐색 폭이 너무 좁으면 좋은 문서가 근처에 있어도 쉽게 놓친다.
• 지연 시간을 지나치게 아끼면 시스템은 빨라지지만 검색의 성격이 거칠어진다.

그래서 나는 이제 벡터 검색을 튜닝할 때 "정답을 잘 맞히는가"만 보지 않는다. 그보다 비슷한 유형의 질의에서 결과가 얼마나 일관되게 유지되는지, 인덱스가 커져도 설정이 쉽게 무너지지 않는지를 같이 본다. 이건 모델 평가와 조금 다른 층의 문제인데, 실서비스에서는 오히려 이쪽이 더 자주 체감된다.

5. HNSW를 배운 뒤로는 그래프와 검색을 따로 보지 않게 됐다

흥미로웠던 건 이 개념이 벡터 DB 안에만 머물지 않았다는 점이다. HNSW를 이해하고 나니 그래프 기반 탐색이 왜 여러 검색 시스템에서 반복해서 등장하는지도 조금 더 자연스럽게 보였다. 결국 검색은 전체를 다 보는 일이 아니라, 좋은 다음 후보를 얼마나 빨리 고르느냐의 문제일 때가 많다. 그리고 그 판단을 빠르게 만드는 가장 직관적인 방법 중 하나가 연결 구조를 미리 준비해 두는 것이다.

나는 그래서 요즘 검색 시스템을 볼 때 인덱스를 단순한 저장 포맷으로 보지 않는다. 인덱스는 데이터를 저장하는 그릇이 아니라, 미래의 질의가 어떤 경로로 이동할지를 미리 설계해 둔 지도에 더 가깝다. 이 관점으로 보면 HNSW는 ANN 기법 중 하나이면서 동시에, 운영자가 recall과 latency를 어떤 방식으로 거래할지 드러내는 설계 언어이기도 하다.

물론 모든 경우에 HNSW가 정답이라는 뜻은 아니다. 데이터 업데이트 패턴, 메모리 제약, 하이브리드 검색 필요 여부에 따라 다른 선택지가 더 맞을 수 있다. 그래도 최근접 탐색이 왜 생각보다 잘 버티는지 감을 잡고 싶다면, 나는 여전히 HNSW가 좋은 출발점이라고 느낀다. 벡터 검색을 그냥 기능으로 소비할 때보다, 그래프 위에서 길을 찾는 과정으로 이해할 때 훨씬 덜 막연해진다.

6. 짧게 남겨두고 싶은 내 식의 정리

지금의 나는 HNSW를 볼 때 "고차원 벡터를 빠르게 검색하는 기법"이라는 설명만으로는 조금 부족하다고 느낀다. 내 머릿속에서는 이게 더 이상 추상적인 ANN 약자가 아니라, 좋은 이웃을 발판 삼아 아래층으로 내려가며 후보를 좁혀 가는 그래프 탐색 전략으로 남아 있다. 이 감각 하나만 생겨도 파라미터를 외우는 일과 파라미터를 이해하는 일의 차이가 꽤 커진다.

결국 내가 최근에 배운 건 HNSW 자체보다도 검색을 보는 시선의 변화에 가까웠다. 벡터 표현이 좋다는 말과 검색이 잘 된다는 말 사이에는 늘 인덱스와 탐색 전략이 끼어 있다. 그 중간 층을 그래프 감각으로 이해하고 나니, 검색 품질을 볼 때도 훨씬 덜 막연하고 덜 미신적으로 보게 됐다. 적어도 지금의 나는 HNSW를 볼 때 먼저 벡터를 떠올리기보다, 그 벡터들 사이를 어떻게 건너뛸지부터 떠올린다.