그래프 기반 근사 최근접 탐색의 복잡도

그리디 탐색은 실측에서 수 밀리초를 지키지만 최악 경우 보장은 최근까지 비어 있었고, 2025년의 확률적 분석이 그 자리를 채우기 시작했습니다.

그리디 탐색이 빠른 이유

근사 최근접 이웃(Approximate Nearest Neighbor, ANN) 탐색은 가장 가까운 벡터를 정확히 찾는 대신 충분히 가까운 후보를 빠르게 돌려주는 문제입니다. 그래프 기반 방법은 각 벡터를 노드로 두고 가까운 벡터끼리 간선으로 이은 근접 그래프(proximity graph)를 미리 만들어 둡니다. 질의가 들어오면 진입점 하나에서 출발해, 현재 노드의 이웃 중 질의에 더 가까운 노드로 옮겨 가는 그리디 탐색을 반복합니다.

이 절차가 빠른 이유는 이동 한 번이 후보 공간을 크게 줄이기 때문입니다. 간선이 실제로 가까운 벡터끼리 이어져 있으면 몇 번의 이동으로 질의 근방에 도달합니다. 코퍼스가 커져도 지연이 크게 늘지 않는 실측 특성이 여기서 나옵니다.

멈춘 지점이 전역 최근접 이웃이라는 보장은 없습니다. 더 가까운 이웃이 없다는 종료 조건은 지역 최적(local optimum)에서도 성립하기 때문입니다. 실무 구현은 후보를 하나만 들고 다니는 대신 폭이 있는 큐를 유지하는 빔 탐색으로 이를 완화합니다. Hierarchical Navigable Small World(HNSW)는 계층 그래프로 진입점을 개선하고, efSearch로 빔 폭을, M으로 노드당 최대 이웃 수를 조절합니다.

이 완화는 경험적입니다. M과 efSearch를 얼마로 두면 어떤 재현율이 나오는지는 데이터셋마다 파라미터 sweep으로 찾습니다. Ma 외(2025, arXiv:2509.15531)는 이 상태를 이론과 실무 최적화 사이의 간격으로 규정했습니다.

SNG pruning 규칙의 계보

간선을 어떻게 고르는지가 그래프 인덱스의 성격을 결정합니다. Arya와 Mount가 1993년에 제안한 Sparse Neighborhood Graph(SNG)는 각 점의 나가는 이웃을 그리디하게 고르는 pruning 규칙을 정의합니다. 점 p의 후보 집합을 나머지 전체 점으로 두고, 가장 가까운 점으로 간선을 하나 추가한 뒤 그 점에 더 가까운 후보를 제거하는 과정을 후보가 빌 때까지 반복합니다.

SNG-prune(p, S):            # S = 전체 점 집합에서 p를 제외한 후보
    while S is not empty:
        p* = argmin_{q in S} dist(p, q)
        add edge p -> p*
        for q in S:
            if dist(p*, q) <= dist(p, q):   # p*가 q에 더 가까우면 q 제거
                remove q from S

제거 조건 $d(p^*, q) \le d(p, q)$는 중복 간선을 없앱니다. p에서 q로 직접 가지 않고 p*를 거쳐도 q에 가까워지므로, p에서 q로 향하는 간선은 없어도 됩니다. 방향마다 대표 간선 하나만 남으므로 차수가 줄고, 어느 방향으로든 전진할 수 있는 경로는 유지됩니다.

현재 널리 쓰이는 인덱스들은 이 규칙의 변형입니다. NSG는 단조 상대 근접 그래프(Monotonic Relative Neighborhood Graph, MRNG)를 근사하도록 설계됐습니다. MRNG는 어떤 질의에 대해서도 거리가 단조 감소하는 경로가 존재함을 보장하므로, 로그 시간에 가까운 탐색 복잡도를 갖습니다. DiskANN의 Vamana 그래프는 제거 조건을 $\alpha \cdot d(y^*, y) \le d(x, y)$로 완화합니다. $\alpha$가 클수록 더 성긴 그래프가 됩니다.

보장이 끊기는 지점이 여기입니다. MRNG는 단조 경로를 보장하지만 구성 비용이 커서 그대로 쓰지 못하고, NSG는 그 근사이므로 원래 보장을 물려받지 않습니다. Vamana는 $\alpha$로 성김을 조절할 뿐 경로 길이에 대한 진술을 하지 않습니다.

차수와 경로 길이의 교환

그래프 인덱스의 비용은 두 값으로 갈립니다. 노드당 나가는 간선 수인 차수(out-degree)와, 진입점에서 목표 근방까지의 이동 횟수인 경로 길이입니다. 한 번 이동할 때마다 현재 노드의 이웃 전부와 질의의 거리를 재므로, 탐색의 거리 계산 횟수는 대략 두 값의 곱에 비례합니다.

두 값은 반대 방향으로 움직입니다. 간선을 많이 남기면 먼 곳으로 건너뛰기 쉬워 경로가 짧아지지만, 이동마다 재야 할 거리가 늘고 인덱스도 커집니다. 간선을 세게 잘라내면 이동 비용은 줄지만 경로가 길어지고 지역 최적에 걸릴 확률도 올라갑니다.

의미 있는 복잡도 진술이 두 값을 함께 묶어야 하는 이유가 여기 있습니다. 차수만 작다고 좋은 그래프가 아니고, 경로만 짧다고 싼 그래프도 아닙니다. pruning 규칙의 강도를 정하는 truncation parameter는 정확히 이 교환의 손잡이입니다.

하한 쪽은 아직 비어 있습니다. 아래에서 볼 2025년의 두 결과는 모두 상계와 조건부 보장이고, 하한은 다루지 않습니다. 임의의 고차원 데이터에서 차수와 경로 길이의 곱을 얼마 아래로 줄일 수 없는지는 이 결과들의 범위 밖입니다.

Martingale 분석이 준 상계

Ma 외(2025)는 SNG 구성 과정을 확률 과정으로 모델링해 두 값의 점근적 경계를 처음으로 증명했습니다. 후보 집합이 간선을 하나 추가할 때마다 확률적으로 줄어드는 과정을 martingale로 다룬 것이 핵심입니다. martingale은 다음 단계의 조건부 기댓값이 현재 값과 같은 확률 과정으로, 집합이 줄어드는 속도를 단계별로 통제할 수 있게 해 줍니다.

두 경계가 함께 나온 것이 중요합니다. 경로가 $O(\log n)$이라도 차수가 통제되지 않으면 이동마다 비용이 폭발하고, 차수가 작아도 경로가 길면 이득이 없습니다.

같은 모델에서 truncation parameter $R$의 닫힌 형태(closed-form) 최적화 규칙이 나옵니다. 기존에 수 시간짜리 sweep으로 찾던 값을 계산으로 대체한다는 뜻입니다. 실제 데이터셋 실험에서 인덱스 구축 시간이 평균 5.9배, 최대 15.4배 단축됐고, 재현율은 기존 방법과 동등하거나 더 나은 수준을 유지했습니다.

경계가 말하는 규모는 실무 파라미터와 다릅니다. $n$이 100만이면 $n^{2/3}$은 1만 규모이고, 실무에서 쓰는 M은 대개 16에서 64 사이입니다. 이 경계는 차수가 폭발하지 않는다는 사실을 말해 줄 뿐, 어느 값을 쓰라고 지정해 주지는 않습니다.

poly-log 시간 정확 탐색 보장

Li 외(2025, arXiv:2510.05975, SIGMOD 2026)는 다른 각도에서 접근합니다. α-convergent graph(α-CG)라는 근접 그래프를 새로 정의합니다. pruning은 shifted-scaled triangle inequality로 후보 이웃을 제거하는 방식입니다. Vamana의 $\alpha$ 완화와 같은 계열이지만 겨냥하는 대상이 다릅니다.

보장의 형태는 조건부입니다. 질의와 정확한 최근접 이웃 사이 거리가 상수 $\tau$ 이내이면 poly-logarithmic 시간에 정확한 최근접 이웃을 찾는다는 것이 증명 대상입니다. 그 외의 경우에도 같은 시간 복잡도로 근사 최근접 이웃을 돌려줍니다.

전제가 하나 붙습니다. bounded intrinsic dimensionality, 즉 데이터가 실제로는 낮은 차원 구조 위에 놓여 있어야 합니다. 임베딩 차원이 1024라도 데이터가 그보다 훨씬 낮은 매니폴드에 몰려 있으면 조건이 성립하므로, 성립 여부는 데이터셋에 달려 있습니다.

실용 변형인 α-CNG는 기존 근접 그래프 대비 거리 계산을 15% 이상, 검색 단계를 45% 이상 줄였습니다. Ma 외가 구성 비용을, Li 외가 탐색 시점의 정확도 보장을 다룬다는 점에서 두 결과는 서로 보완적입니다.

이론이 실무 파라미터와 만나는 지점

HNSW의 M은 pruning 규칙의 truncation parameter에 해당합니다. M을 키우면 차수가 늘어 경로가 짧아지고, 줄이면 반대가 됩니다. Ma 외의 닫힌 형태 규칙이 대체하려는 것이 바로 이 값을 찾는 sweep입니다.

efSearch는 다른 축에 있습니다. 빔 폭을 넓히면 지역 최적을 빠져나갈 확률이 오르지만, 유지할 후보가 늘어 지연이 커집니다. 이론 결과가 다루는 것은 그리디 탐색의 경로 길이이고, 빔 폭이 재현율을 얼마나 끌어올리는지는 여전히 실측 영역입니다.

이 보장들은 모두 필터 없는 순수 최근접 이웃 탐색을 가정합니다. 우아한형제들 기술블로그의 실시간 추천 사례가 그 가정이 깨지는 지점을 보여줍니다. 배달 가능 지역처럼 런타임에만 정해지는 pre-filter 조건이 있으면, 미리 구축한 정적 그래프 인덱스를 그대로 쓸 수 없습니다.

이 팀은 순수 ANN 그래프 인덱스 대신 pgvector 0.5.0의 HNSW를 RDS 위에서 운용하는 쪽을 택했습니다. 부하 테스트에서 RDS(pgvector)가 OpenSearch와 Atlas MongoDB 대비 가장 높은 처리량과 가장 낮은 실패율을 기록했습니다. 여러 쿼리를 UNION으로 묶어 데이터베이스 왕복을 줄이고 Reciprocal Rank Fusion으로 결과를 병합해 필터 문제를 우회했습니다. 점근적 복잡도가 개선되어도, 필터 요구가 있는 서비스에서는 인덱스 구조 선택보다 시스템 통합 방식이 성능을 더 크게 좌우합니다.

정리

그래프 기반 ANN 탐색은 30년 넘게 쓰인 SNG pruning 규칙 위에 서 있고, 그 규칙의 차수와 경로 길이 경계는 2025년에야 증명됐습니다. Ma 외는 martingale 모델로 최대 차수 $O(n^{2/3+\epsilon})$과 예상 경로 길이 $O(\log n)$을 증명했습니다. 같은 모델에서 나온 truncation parameter의 닫힌 형태 규칙은 인덱스 구축 시간을 평균 5.9배 줄였습니다.

Li 외는 bounded intrinsic dimensionality 전제 아래 poly-logarithmic 시간 정확 탐색을 보장하는 α-CG를 제시했습니다. 두 결과 모두 상계와 조건부 보장이라 실무 파라미터를 직접 정해 주지 않고, 최악 경우 경계와 실제로 쓰는 M 사이에는 자릿수 차이가 남아 있습니다. 필터가 붙는 서비스에서는 이 보장이 애초에 적용되지 않으므로, 인덱스 구조보다 통합 방식을 먼저 정하는 편이 낫습니다.