Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

이 논문은 현대 AI 애플리케이션의 다양한 요구사항을 충족하기 위해 투영 기법을 그래프 인덱스에 통합하여 기존 방법보다 5 배 빠른 검색 속도와 우수한 성능을 제공하는 새로운 근사 최근접 이웃 검색 프레임워크인 '투영 증강 그래프 (PAG)'를 제안합니다.

핵심

1. 문제 상황: 도서관의 혼란 (기존 기술의 한계)

상상해 보세요. 수백만 권의 책 (데이터) 이 있는 거대한 도서관이 있습니다. 손님이 "이 책과 가장 비슷한 책 10 권을 찾아줘"라고 요청합니다.

• 기존의 방식 (HNSW 등): 사서가 모든 책의 제목을 하나하나 읽어보며 비교합니다. 정확하지만, 책이 너무 많으면 시간이 너무 오래 걸려 손님이 화를 냅니다.
• 다른 방식 (양자화 등): 책의 제목을 줄여서 (예: "로봇"만 기억하고 "로봇과 미래"는 "로봇"으로 통일) 빠르게 찾습니다. 속도는 빠르지만, 중요한 뉘앙스를 놓쳐서 엉뚱한 책을 건네줄 때가 많습니다.

현대 AI 가 원하는 것:

1. 속도: 손님이 요청하면 즉시 찾아줘야 함.
2. 정확도: 엉뚱한 책을 주면 안 됨.
3. 메모리: 도서관이 너무 커지면 건물을 지을 수 없으므로, 책장을 적게 차지해야 함.
4. 유연성: 책이 계속 추가되거나 (온라인 삽입), 찾는 책의 수 (10 권 vs 1,000 권) 가 변해도 똑같이 잘 작동해야 함.

기존 기술들은 이 모든 조건을 동시에 만족시키기 힘들었습니다.

---

2. PAG 의 해결책: "스마트한 사서"와 "예측 시스템"

이 논문이 제안한 PAG는 도서관 사서에게 두 가지 강력한 도구를 줍니다.

① "예측 안경" (Projection - 투영)

사서는 모든 책을 다 읽지 않습니다. 대신 책의 표지나 첫 페이지만 빠르게 훑어보는 **'예측 안경'**을 낍니다.

• 이 안경을 통해 "아, 이 책은 저 책과 너무 달라서 비교할 필요 없겠군"이라고 미리 걸러냅니다.
• 하지만 안경이 100% 정확하지는 않으므로, "아마 비슷할 것 같은" 책들은 나중에 정밀하게 비교합니다.
• 핵심: 불필요한 정밀 비교를 아껴서 속도를 5 배까지 높입니다.

② "오류 수정 메모장" (Test Feedback Buffer - TFB)

예측 안경이 가끔 실수를 할 때가 있습니다. ("이건 다를 거야"라고 했는데, 알고 보니 비슷했음).

• 기존 기술들은 이 실수를 그냥 버렸습니다.
• PAG 의 TFB는 이 실수한 책들을 **'오류 수정 메모장'**에 적어둡니다.
• 다음에 비슷한 책을 찾을 때, 이 메모장을 보고 "아, 전에 이 책이 실수였으니 이번엔 꼭 확인하자"라고 재사용합니다.
• 효과: 실수를 반복하지 않아서 검색 속도가 더 빨라지고, 인덱스 (목록) 를 만드는 시간도 단축됩니다.

③ "새로운 길 찾기" (Probabilistic Edge Selection - PES)

기존 도서관은 책과 책 사이의 연결고리 (길) 가 너무 좁아, 특정 책에 도달하지 못하는 경우가 있었습니다.

• PAG는 "이 길은 좁지만, 저쪽에서 발견된 다른 책들이 이 책과 비슷할 수도 있겠다"라고 확률적으로 새로운 길을 찾아 연결해 줍니다.
• 이렇게 도서관의 길 (그래프) 을 더 촘촘하게 만들어서, 어떤 책을 찾아도 빠르고 정확하게 도달할 수 있게 합니다.

---

3. PAG 가 가져온 변화 (결과)

이 새로운 시스템 (PAG) 을 적용한 결과, 다음과 같은 놀라운 변화가 일어났습니다.

• 🚀 속도의 폭풍: 기존 최고 성능 기술 (HNSW) 보다 최대 5 배 더 빠릅니다. 손님이 요청하면 찰나에 답을 줍니다.
• 🏗️ 빠른 건축: 도서관을 짓는 시간 (인덱스 생성) 도 훨씬 빠릅니다. 즉시 배포가 가능합니다.
• 💾 작은 공간: 책장을 차지하는 공간이 적어서 메모리 부담이 줄었습니다.
• 🔄 유연한 적응: 찾는 책의 수가 10 권이든 1,000 권이든, 책의 종류가 텍스트든 이미지든 상관없이 똑같이 잘 작동합니다.
• 📝 실시간 업데이트: 새로운 책이 들어와도 도서관을 다시 짓지 않고, 바로 그 자리에 끼워 넣을 수 있습니다 (온라인 삽입).

---

4. 요약: 왜 이것이 중요한가?

지금의 AI 는 매일 새로운 경험과 데이터를 학습하며 스스로 진화하고 있습니다. (예: 챗봇이 새로운 정보를 배우거나, 추천 시스템이 사용자의 취향을 실시간으로 파악하는 것).

이런 살아 움직이는 AI에게는 "정확하지만 느린" 도서관이나 "빠르지만 엉뚱한" 도서관은 쓸모가 없습니다. PAG는 "빠르고, 정확하며, 유연하고, 실시간으로 업데이트 가능한" 완벽한 도서관 사서를 만들어낸 것입니다.

이 기술은 앞으로 우리가 사용하는 모든 AI 서비스 (검색, 추천, 대화형 AI 등) 가 더 빠르고 똑똑하게 작동하는 데 핵심이 될 것입니다.

기술 요약

현대 AI 를 위한 근사 최근접 이웃 검색 (ANNS): 투영 증강 그래프 접근법 (PAG) 기술 요약

이 논문은 현대 AI 애플리케이션 (이미지 검색, 추천 시스템, RAG 등) 의 요구사항을 충족시키기 위해 기존 ANNS (Approximate Nearest Neighbor Search) 방법론의 한계를 극복하고, **투영 증강 그래프 (Projection-Augmented Graph, PAG)**라는 새로운 프레임워크를 제안합니다.

1. 문제 정의 (Problem)

기존의 ANNS 솔루션들은 주로 쿼리 효율성 (QPS) 에 최적화되어 있으나, 현대의 대규모 및 고차원 데이터 워크로드가 요구하는 6 가지 핵심 요구사항을 모두 충족하지 못합니다.

• 현대 AI 의 6 가지 요구사항:
  1. 높은 쿼리 효율성 (High Query Efficiency): 높은 QPS 와 Recall.
  2. 빠른 인덱싱 (Fast Indexing): HNSW 와 같은 그래프 기반 방법은 인덱스 구축 시간이 길어 실시간 배포에 부적합함.
  3. 낮은 메모리 풋프린트 (Low Memory Footprint): 메모리 사용량과 정확도 간의 균형 필요.
  4. 고차원 확장성 (Scalability to High Dimensionality): CLIP 등 최신 임베딩 모델은 차원이 매우 높음 (1024~3072 차원).
  5. 검색 크기 (K) 에 대한 강건성 (Robustness across K): RAG(K=10) 부터 추천 시스템 (K=수천) 까지 다양한 K 값에서 성능 유지 필요.
  6. 온라인 삽입 지원 (Support for Online Insertions): 자아 진화 에이전트 등 지속적인 데이터 업데이트가 필요한 시나리오 지원.

기존 그래프 기반 방법 (HNSW) 은 정확하지만 계산 비용이 높고, 양자화 기반 방법 (Quantization) 은 빠르지만 정확도가 낮으며, 투영 기반 방법은 이론적 보장은 있으나 실제 성능이 떨어짐. 또한 기존 그래프 + 투영/양자화 하이브리드 방법들은 인덱싱 시간, 메모리, 온라인 삽입 지원 등에서 여전히 한계가 있었습니다.

2. 방법론 (Methodology: PAG)

PAG 는 그래프 인덱스 구조에 투영 (Projection) 기술을 통합하여, 불필요한 정확한 거리 계산을 줄이는 비대칭 비교 (Asymmetric Comparison) 방식을 도입했습니다. PAG 는 세 가지 핵심 구성 요소로 이루어져 있습니다.

2.1. 핵심 구성 요소

1. 확률적 라우팅 테스트 (Probabilistic Routing Test, PRT):

   • 목적: 그래프 탐색 중 정확한 거리 계산이 필요한 노드를 선별.
   • 원리: 랜덤 투영 (Random Projection) 을 사용하여 정확한 거리 대신 근사 거리를 계산하고, 이를 통계적 테스트를 통해 비교합니다.
   • 특징: 정확한 거리와 근사 거리를 비대칭적으로 비교하여, 확률적으로 "더 큰 값"인지만 판단함으로써 정확성을 유지하면서 계산 비용을 절감합니다.

2. 테스트 피드백 버퍼 (Test Feedback Buffer, TFB):

   • 목적: PRT 에서 발생하는 위양성 (False Positive, FP) 노드를 재사용하여 인덱싱 및 검색 효율 향상.
   • 원리: PRT 를 통과했으나 실제 거리 조건을 만족하지 못해 버려진 노드 (FP) 들을 버퍼 (Ring Buffer) 에 저장합니다. 이후 라운드에서 이 FP 들을 재평가하여 임계값 (Threshold) 을 점진적으로 조정합니다.
   • 효과: 기존 방법 (PEOs, KS2) 보다 더 작은 작업 집합 (Working Set) 을 유지하며, 불필요한 거리 계산을 줄이고 인덱싱 속도를 획기적으로 개선합니다.

3. 확률적 엣지 선택 (Probabilistic Edge Selection, PES):

   • 목적: 그래프의 연결성 (Connectivity) 강화, 특히 RobustPrune 전략이 놓칠 수 있는 유망한 진입 엣지 (In-edges) 발견.
   • 원리: 방문한 모든 노드에 대해 PRT 결과를 기반으로 확률적 테스트를 수행하여, 기존 RobustPrune 만으로는 선택되지 않았더라도 유망한 엣지를 추가로 선택합니다.
   • 효과: 고차원 데이터에서 그래프의 연결성을 강화하여 검색 성능을 향상시키며, 인덱싱 오버헤드는 미미합니다.

2.2. 작동 방식

• 인덱싱: 데이터 포인트를 순차적으로 삽입할 때, PRT-TFB 를 통해 효율적으로 후보 노드를 필터링하고, PES 를 통해 그래프의 연결성을 보강합니다.
• 검색: 쿼리 시 PRT-TFB 기반의 ANNS 를 수행하여 정확한 거리 계산 횟수를 최소화합니다.
• 온라인 삽입: HNSW 와 유사한 검색 - 삽입 패러다임을 따르며, TFB 와 PES 메커니즘을 통해 점진적 업데이트를 지원합니다.

3. 주요 기여 (Key Contributions)

1. PRT-TFB 테스트: 기존 라우팅 테스트의 한계를 극복하고, 위양성 노드를 재사용하여 인덱싱 및 검색 속도를 동시에 최적화하는 새로운 테스트 메커니즘 제안.
2. PES (Probabilistic Edge Selection): 그래프 연결성을 강화하여 고차원 데이터에서의 검색 성능을 개선하는 통계적 엣지 선택 알고리즘 제안.
3. 통합 프레임워크 (PAG): PRT, TFB, PES 를 통합하여 6 가지 현대적 요구사항 (QPS, 인덱싱 속도, 메모리, 고차원 확장성, K-강건성, 온라인 삽입) 을 모두 충족하는 단일 프레임워크 구축.
4. 이론적 기반: 투영 기반 통계적 테스트의 이론적 근거 (Theorem 3.1) 를 제시하고, 이를 그래프 구축에 적용하는 방법을 체계화함.

4. 실험 결과 (Results)

현대 데이터셋 (DBpedia, WoltFood, DataCompDr, MajorTOM 등) 과 레거시 데이터셋 (SIFT, GIST 등) 에서 다양한 ANNS 솔버 (HNSW, Vamana, SymQG, ScaNN 등) 와 비교 실험을 수행했습니다.

• 쿼리 성능 (QPS-Recall):
  • PAG-Base 는 모든 현대 데이터셋에서 HNSW 대비 최대 5 배 빠른 QPS를 달성하면서도 높은 Recall 을 유지했습니다.
  • 특히 고차원 데이터 (1536 차원, 3072 차원) 에서 성능 우위가 두드러졌습니다.
  • 검색 크기 (K) 가 10 에서 1000 으로 증가해도 성능이 유지되는 강건성을 보였습니다.
• 인덱싱 속도:
  • PAG-Lite 는 양자화 기반 방법과 유사한 수준의 빠른 인덱싱 속도를 보였으며, PAG-Base 도 HNSW 대비 20~40% 의 인덱싱 시간 단축 효과를 보였습니다.
• 메모리 효율성:
  • 검색 및 인덱싱 시 메모리 사용량이 SymQG 등 다른 최신 방법보다 낮거나 동등한 수준을 유지했습니다.
• 온라인 삽입:
  • 삽입 및 검색이 교차하는 워크로드에서 HNSW 대비 최대 5 배 빠른 처리 속도를 보여주었습니다.

5. 의의 및 결론 (Significance)

이 논문은 현대 AI 애플리케이션이 직면한 복잡한 요구사항 (고차원, 대규모, 실시간 업데이트 등) 에 맞춰 ANNS 기술을 재정의했습니다.

• 실용성: 기존 HNSW 의 인덱싱 병목 현상을 해결하면서도, 양자화 기반 방법의 정확도 저하 문제를 극복하여 "빠르고 정확한" 검색을 가능하게 합니다.
• 범용성: 텍스트, 이미지, 멀티모달 데이터 등 다양한 도메인과 차원 수에 걸쳐 일관된 성능을 발휘합니다.
• 미래 지향성: 자아 진화 에이전트나 실시간 추천 시스템과 같이 데이터가 지속적으로 유입되고 변하는 환경에서 필수적인 온라인 인덱스 업데이트를 효율적으로 지원합니다.

결론적으로 PAG 는 현대 AI 시스템의 근간이 되는 벡터 검색 기술의 새로운 표준으로 자리 잡을 잠재력을 가진 획기적인 접근법입니다.