초거대 RAG 시스템의 검색 레이턴시 브레이크: 벡터 데이터베이스와 HNSW 인덱싱의 기만학

사내에 GPT-4 기반의 사내 문서 통합 검색 챗봇(RAG 아키텍처)을 배포했을 때, 1억 건이 넘는 문서 덩어리들을 벡터화(Vector Embedding) 해둔 Postgres(pgvector)가 타임아웃을 뱉으며 쓰러졌습니다. 차원 공간에서 가장 비슷한 문서 의미를 찾는 코사인 유사도(Cosine Similarity) 계산이 엄청난 실수 벡터 병목을 일으켰기 때문입니다. 유저의 검색어 벡터(1536차원 점) 하나를 1억 개의 문서 점들과 개별적으로 거리 계산하여 정렬하는 Exact k-NN 탐색은, 시간 복잡도가 무조건적인 O(N)으로 컴퓨터 성능 자체를 마비시켰습니다. 아무리 SIMD 하드웨어를 끌어다 써도 한계치였습니다. 결국 완전한 정확성(100% 정답)을 단 5%만 포기하는 대신 처리 속도를 만 배 이상 올려버리는 기만적인 근사치 수학 알고리즘 시스템으로 눈을 치켜들어야 했습니다. 이것이 현대 벡터 데이터베이스 검색의 총아, HNSW(Hierarchical Navigable Small World) 인덱스 압축입니다. HNSW 구조는 1억 개의 점을 스몰 월드 그래프 다단계 트리로 묶어 버립니다. 최상위 레이어 그룹에는 데이터 포인트가 단 수십 개만 존재하여 거대한 이정표 역할을 합니다. 검색 벡터가 들어오면, 최상위 층에서 대충 가장 가까운 허브 포인트를 찾아낸 뒤 그 점을 엘리베이터 삼아 하위 층으로 다이브 다운(Dive Down)합니다. 층을 거칠수록 점들의 밀도가 높아지며 지엽적 구역으로 탐색 범위를 포위해 들어갑니다. 매 층마다 이웃 주변만 기웃거리며 비교를 종결해 버리니, 1억 번 수행해야 했던 소수점 거리 계산이 단 100번 만에 O(log N) 탐색으로 끝나게 됩니다. 검색 정답이 설령 2등 문서로 반환될 확률이 5% 남짓 존재한다 하더라도, 유저의 체감 레이턴시는 20초에서 50밀리초(ms)로 기적처럼 날아올랐습니다. 절대적인 진리라는 벽을 부수면 압도적 공간 아키텍처 매트릭스가 나타남을 체험한 쾌거입니다.