4096차원에 HNSW가 필요한 이유 — 전수 비교의 벽, 차원의 저주, 그리고 그래프를 걸어서 찾는 법 (한국어 검색 스택 4편)
1편에서 가장 좋았던 Qwen3-Embedding-8B는 문장 하나를 4,096개 숫자로 바꿉니다. 문서 589건이면 질문 하나에 589번 내적하면 되니 1초도 안 걸립니다. 그런데 문서가 5,000만 건이면? 같은 방식으로는 질문 하나에 2,000억 번 곱셈이고, 서버가 아무리 좋아도 초 단위입니다. 벡터 DB가 HNSW라는 인덱스를 쓰는 이유가 여기 있습니다. 이 글은 왜 고차원에서는 트리 인덱스가 소용없는지(차원의 저주), HNSW가 어떻게 스킵 리스트와 작은 세상 그래프를 합쳐 로그 시간에 근사 최근접을 찾는지, M·ef_construction·ef_search 세 손잡이가 무엇을 바꾸는지를 그림과 장난감 시뮬레이터로 풀고, 4,096차원 벡터 1만·10만·30만 개로 전수 비교와 hnswlib을 직접 재서 비교합니다. 10만 개에서 전수 비교 56ms 대 HNSW 1.3ms(재현율 0.98). 그리고 4,096차원의 진짜 병목은 그래프가 아니라 벡터 자체라는 것, 그래서 3편의 마트료시카 절단과 양자화가 HNSW와 곱해진다는 것을 메모리 계산기로 보입니다. 인터랙티브 4개와 삽화 8장.
