근사 최근접 이웃 (ANN)

키워드·시맨틱 검색은 retriever의 토대지만, 규모를 키우면 새로운 문제가 생긴다. 특히 벡터 검색은 순진하게 구현하면 확장성이 나쁘다. Module 3은 이 문제를 푸는 벡터 데이터베이스의 세계로 들어가며, 첫 편은 그 심장인 ANN(Approximate Nearest Neighbors, 근사 최근접 이웃) 알고리즘이다.

 

 

1. 가장 단순한 벡터 검색 — KNN

가장 단순한 벡터 검색은 k-최근접 이웃(k-nearest neighbors, KNN)이다. 지금까지 시맨틱 검색에서 본 방식 그대로다.

1. knowledge base의 모든 문서와 프롬프트를 임베딩 벡터로 만든다.
2. 프롬프트 벡터와 모든 문서 벡터 사이의 거리를 계산한다.
3. 거리순으로 정렬한다.
4. 사용자가 정한 개수 k만큼 가장 가까운 문서를 반환한다.

그림 1. KNN — 모든 문서·프롬프트를 벡터화하고, 모든 문서와의 거리를 계산해 정렬한 뒤 가장 가까운 k개를 반환한다.

 

 

2. 확장의 문제

KNN은 이해도 구현도 쉽지만, 확장성이 끔찍하다. 각 검색에 필요한 계산량이 문서 수에 선형으로 비례하기 때문이다. 문서가 1,000개면 검색마다 1,000번의 거리 계산을, 10억 개면 10억 번을 해야 한다. 후자는 전자보다 100만 배 느리다. 규모에서 잘 작동하려면 더 나은 방법이 필요하다.

그림 2. KNN의 계산량은 문서 수에 선형으로 증가한다 — 대규모에서는 감당하기 어렵다.

 

 

3. ANN — 근사로 바꿔 속도를 얻음

KNN을 개선하기 위해 retriever는 ANN(근사 최근접 이웃) 계열 알고리즘을 쓴다. 영리한 자료구조로 검색을 훨씬 빠르게 한다. 대신 결과 품질을 조금 희생한다 — 절대적으로 가장 가까운 문서를 찾는다는 보장은 없지만, 매우 가까운 문서는 찾아낸다.

 

 

4. Navigable Small World (NSW)

대표적인 ANN 알고리즘이 navigable small world(NSW)다. 검색 전에 proximity graph(근접 그래프)라는 자료구조를 미리 만든다. 각 벡터와 다른 모든 벡터의 거리를 계산한 뒤, 문서마다 노드를 하나 두고, 각 문서를 자신과 가장 가까운 몇 개의 문서와 엣지로 연결한다. 그러면 거미줄 같은 구조가 된다 — 엣지를 따라 이웃으로 건너뛰며 그래프를 순회할 수 있다.

그림 3. NSW의 proximity graph — 문서를 노드로, 가장 가까운 이웃들과 엣지로 연결한 거미줄 구조.

 

 

5. 탐색 — 이웃 중 가장 가까운 곳으로

프롬프트가 들어오면 query vector로 만든다. 목표는 이 query vector에 가장 가까운 문서를 찾는 것이다. 알고리즘은 무작위 진입점(candidate vector)에서 시작한다 — 프롬프트와 가깝다는 가정 없이 그냥 그래프의 한 노드다.

그림 4. 무작위 진입점(candidate)에서 시작한다.

 

이제 그래프를 순회한다. 현재 candidate의 이웃들을 보고 query vector에 가장 가까운 이웃을 고른다(이웃이 몇 개뿐이라 매우 빠르다). 그 이웃이 새 candidate가 된다. 이 과정을 반복하다가, 어떤 이웃도 현재 candidate보다 가깝지 않으면 그 candidate를 반환한다. (약간의 변형으로 여러 문서를 반환할 수도 있다.)

그림 5. 매 단계 현재 위치의 이웃 중 프롬프트에 가장 가까운 곳으로 이동하며 그래프를 건너간다.

 

 

 

6. 근사인 이유

이 방식이 knowledge base에서 반드시 최선의 벡터를 찾는 건 아니다. 더 가까운 벡터가 있어도, 알고리즘이 그리로 가는 경로를 못 잡아 도달하지 못할 수 있다 — 전역 최적 경로가 아니라 매 순간의 최선만 선택하기 때문이다. 그래도 실제로는 매우 가까운 벡터를, KNN보다 훨씬 빠르게 찾는다.

그림 6. 매 순간 최선을 따라가므로, 전역적으로 가장 가까운 벡터는 놓칠 수 있다(근사).

 

 

 

7. HNSW — 계층적 NSW

NSW를 더 빠르게 만든 변형이 HNSW(Hierarchical Navigable Small World)다. 여러 계층(layer)을 가진 근접 그래프에 의존한다. 문서가 1,000개라면 이런 식이다.

• Layer 1 — 1,000개 벡터 전부로 정상적인 근접 그래프를 만든다.
• Layer 2 — 무작위로 100개만 남기고 그 100개로 새 그래프를 만든다.
• Layer 3 — 다시 10개만 남겨 그래프를 만든다.

검색은 맨 위 Layer 3에서 시작한다. 무작위 진입점에서 최선 candidate를 찾은 뒤, 그 지점에서 Layer 2로 내려가 다시 탐색하고, 마지막으로 모든 벡터가 있는 Layer 1로 내려가 최종 후보를 찾아 반환한다. 위 계층에서 큰 점프로 대략적인 이웃에 먼저 도달하고, Layer 1에 이를 즈음엔 이미 프롬프트와 매우 가까운 상태다.

그림 7. HNSW — 위 계층일수록 벡터가 적어(10→100→1000) 큰 점프로 빠르게 근방에 진입하고, 아래로 내려갈수록 정밀하게 탐색한다.

 

 

 

8. 왜 규모에서 통하는가

위로 갈수록 벡터 수가 기하급수적으로 적어지므로, HNSW의 실행 시간은 대략 로그(logarithmic)에 가깝다 — KNN이 선형(linear)인 것과 대조된다. 덕분에 벡터 검색이 수십억 개 벡터까지 확장되면서도 수백 밀리초의 지연으로 동작한다.

그림 8. HNSW의 실행 시간은 로그에 가깝고 KNN은 선형이다 — 이 차이가 대규모 벡터 검색을 가능케 한다.

 

 

9. 핵심 정리

ANN 알고리즘을 직접 구현할 일은 없겠지만, 세 가지는 기억하자.

그림 9. ANN 핵심 — ① KNN보다 훨씬 빠르다, ② 절대 최선은 보장하지 못한다(근사), ③ proximity graph 구축에 의존하며 그것은 미리 계산해 둘 수 있다.

 

 

다음 글에서는 이 ANN 알고리즘을 실제로 구현해 주는 도구 — 벡터 데이터베이스를 살펴본다.