💬 NLP

CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

이 논문은 대조 강화 학습을 활용하여 실행 속도를 최적화하는 동시에 정확도를 유지함으로써 고성능 근사 최근접 이웃 탐색 알고리즘을 자동으로 생성하는 새로운 패러다임인 CRINN을 소개하며, 여러 벤치마크에서 최첨단 결과를 달성하고 복잡한 알고리즘 최적화를 자동화하기 위한 LLM의 잠재력을 입증한다.

원저자: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

게시일 2026-07-14

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 방금 입력한 특정 문장과 가장 비슷하게 들리는 책 한 권을 수십억 권의 책이 있는 거대한 도서관에서 찾아야 한다고 상상해 보세요. 컴퓨터의 세계에서 이것은 '근사 근접 이웃 탐색(Approximate Nearest Neighbor Search, ANNS)'이라고 불립니다. 이는 당신의 과거 대화를 기억하는 AI 챗봇이나 유사한 이미지를 찾는 로봇과 같은 멋진 기술 뒤에 숨겨진 엔진입니다. 하지만 문제는, 수십억 권의 책이 있는 도서관에서 완벽한 책을 찾는 것은 매우 느리다는 점입니다. 모든 책을 일일이 확인한다면 영원히 걸릴 것입니다. 그래서 컴퓨터 과학자들은 약간의 정확도를 희생하는 대신 엄청난 속도 이득을 얻는 '스마트한 지름길'을 만들어 왔습니다.

수년 동안 이러한 지름길을 더 빠르게 만드는 것은 인간만의 영역이었습니다. 이것은 마치 레이스 카의 엔진을 튜닝하는 것과 같습니다: 전문 정비사가 엔진 소리를 듣고, 어떤 부품이 발목을 잡고 있는지 추측하고, 나사를 조절하거나 기어를 바꾸고, 다시 테스트하는 과정이 필요합니다. 여기에는 깊은 지식과 많은 인내심이 필요합니다.

여기에 새로운 시스템인 CRINN이 등장하여 거대한 질문을 던집니다: 우리가 AI에게 엔진을 직접 튜닝하도록 가르칠 수 있을까?

초능력을 가진 로봇 정비사

CRINN은 '강화 학습' 프레임워크입니다. 이것을 단순히 추측만 하는 것이 아니라, 게임을 통해 배우는 로봇 정비사라고 생각해보세요. 게임은 간단합니다: 도서관을 검색하는 코드를 작성하고, 실행한 뒤, 얼마나 빠른지 확인하는 것입니다.

보상: 코드가 책을 빠르게 찾아내면 로봇은 높은 점수를 받습니다.
교훈: 로봇은 자신의 새로운 코드와 이전 코드를 비교합니다. 단순히 점수만 보는 것이 아니라, 왜 하나가 더 빨랐는지 그 이유를 살핍니다. 단계를 건너뛰었나요? 아니면 책을 더 잘 정리했나요?
루프: 로봇은 이 비교를 통해 다음번에 더 빠른 버전을 작성합니다. 이 과정을 반복하며 매 시도마다 더 똑똑하고 빠르게 진화합니다.

논문은 이 로봇 정비사가 자신의 직무를 놀라울 정도로 잘 수행한다고 보여줍니다. 여섯 가지 서로 다른 유형의 '도서관'(숫자 이미지부터 단어 임베딩에 이르는 데이터셋)에서 테스트했을 때, CRINN은 세 가지 유형(GIST-960, MNIST-784, GloVe-25)에서 세계에서 가장 빠른 검색 시스템을 구축했으며, 다른 두 가지(SIFT-128, GloVe-25)에서는 1위를 공동 달성했습니다.

어떻게 승리하는 법을 배웠나

그 비결은 **대조 강화 학습(Contrastive Reinforcement Learning)**이라 불리는 것입니다. 로봇에게 두 가지 버전의 코드 조각이 주어졌다고 상상해 보세요: 하나는 1초 만에 실행되고, 다른 하나는 2초 만에 실행됩니다. 로봇은 왜 첫 번째 코드가 더 빠른지 설명해야 합니다. 로봇은 "아, 빠른 코드는 책 세 권을 한 번에 확인하지만, 느린 코드는 한 번에 한 권씩 확인하는구나"라고 알아차릴 수 있습니다. 이러한 패턴을 학습함으로써, 로봇은 자연스럽게 속도를 높이는 기술들을 포함하는 코드를 작성하기 시작합니다.

연구진은 단순히 로봇이 무작위로 추측하게 내버려 두지 않았습니다. 그들은 로봇에게 구체적인 목표를 주었습니다: 속도와 정확도 사이의 최적의 균형을 찾는 것입니다. 그들은 정확도(이를 '재현율(recall)'이라고 함)를 높게 유지하면서, 시스템이 초당 얼마나 많은 검색을 수행할 수 있는지를 나타내는 **초당 쿼리 수(QPS)**를 사용하여 성능을 측정했습니다. 예를 들어, MNIST 데이터셋(손글씨 숫자)에서 CR inward는 매우 높은 정확도 수준(0.999 재현율)에서 기존의 최고 시스템보다 85.25% 더 빨랐습니다. 이는 엄청난 도약입니다!

"원 사이즈 피츠 올(One Size Fits All)"의 놀라움

여기서 정말 흥격미로운 부분이 나옵니다. 로봇은 오직 한 가지 유형의 라이브러리인 SIFT-128 데이터셋만을 사용하여 훈련되었습니다. 이 데이터셋은 '유클리드 거리'(지도에서 직선 거리를 측정하는 것과 같은 방식)라고 불리는 특정한 방식으로 거리를 측정합니다. 당신은 이렇게 생각할 수도 있습니다: "세단용으로 훈련된 정비사가 오토바이를 고칠 수 있을까?"

하지만 논문에 따르면, 유클리드 거리에 대한 CRINN의 훈련은 수학적으로는 다르지만 '각도 거리(Angular distance)'를 사용하는 데이터셋(예: GloVe 단어 임베딩)에서도 놀라울 정도로 잘 작동했습니다. 이는 로봇이 게임의 규칙이 약간 바뀌더라도 적용될 수 있는 일반적인 속도의 원칙을 배웠음을 시사합니다. 그러나 논문은 명확한 한계점도 언급합니다. NYTimes-256 데이터셋으로 테스트했을 때, CRINN은 기존 최고의 시스템보다 오히려 82.85% 낮은 성능을 보였습니다. 이는 로봇이 천재이긴 하지만 마법은 아니라는 것을 말해줍니다. 즉, 자신이 배운 것과 매우 다른 유형의 데이터에는 여전히 어려움을 겪는다는 것입니다.

단계별 업그레이드

연구진은 로봇에게 전체 문제를 한꺼번에 던져주지 않았습니다. 자동차를 단계별로 업그레이드하듯 검색 과정을 세 단계로 나누었습니다:

지도 구축 (그래프 생성, Graph Construction): 도서관이 조직되는 단계입니다. CRINN은 이 단계에서 가장 큰 개선을 이루었으며, 평균 **22.11%**의 속도 향상을 보였습니다. 로봇은 '적응형 검색(adaptive search)', 즉 정말 필요할 때만 더 많은 노력을 기울이는 방식과, 여러 개의 문을 통해 동시에 찾기 시작할 수 있는 '다중 진입점(multi-entry points)' 기술을 학습했습니다.
지도 탐색 (검색, Search): 지도가 구축되면 책을 찾아야 합니다. CR inward는 '배치 처리(batch processing, 책 그룹을 함께 확인)'와 '조기 종료(early termination, 최적의 일치를 찾았다고 확신하면 즉시 검색 중단)'와 같은 기술을 사용하여 이 단계를 18.30% 개선했습니다.
결과 다듬기 (정제, Refinement): 답변을 완벽하게 만들기 위한 마지막 단계입니다. 이 단계에서는 개선할 여지가 적었기 때문에 **9.69%**의 더 작은 향상을 가져왔습니다.

이것이 의미하는 바

이 논문은 CRINN이 강력한 아이디어를 증명한다고 주장합니다: AI는 복잡하고 전문가 수준의 작업을 자동화할 수 있다. 수십 년 동안 이러한 검색 알고리즘을 더 빠르게 만드는 데는 수년간의 훈련을 받은 인간 전문가가 필요했습니다. 이제 자신의 코드를 비교하며 배우는 시스템이 이를 자동으로 수행할 수 있습니다.

저자들은 (NYTimes 결과에서 보았듯이) 이것이 모든 데이터셋에 대한 해결책이 된 것은 아니라고 신중하게 밝히고 있습니다. 하지만 이는 매우 중요한 진전입니다. 그들은 '검색 증강 생성(RAG, AI가 외부 지식을 사용하여 질문에 답하는 방식)'과 같은 AI 애플리케이션이 점점 더 대중화됨에 따라, 모든 설정을 일일이 사람이 조정하지 않고도 모든 것을 빠르게 실행하기 위해 CRINN과 같은 도구가 필수적일 것이라고 제안합니다.

요약하자면, CRINN은 데이터 검색을 위한 마스터 정비사가 되도록 학습한 로봇이며, 적절한 훈련이 뒷받침된다면 기계가 단순히 코드를 작성하는 것을 넘어 인간이 할 수 있는 것보다 더 빠르게 실행하는 방법까지도 스스로 찾아낼 수 있음을 입증했습니다.

기술 요약: CRINN

문제 정의

근사 최근접 이웃 탐색(Approximate Nearest-Neighbor Search, ANNS)은 현대 AI 애플리케이션, 특히 대규모 벡터 데이터베이스로부터의 신속한 검색을 요구하는 검색 증강 생성(RAG) 및 에이전트 기반 대규모 언어 모델(LLM) 시스템에서 핵심적인 구성 요소입니다. FAISS, DiskANN, ParlayANN과 같은 기존의 오픈 소스 ANNS 솔루션들은 HNSW(Hierarchical Navigable Small World)와 같은 견고한 백본에 의존하고 있지만, 이들의 최적화 과정은 여전히 상당 부분 수동적인 프로세스에 머물러 있습니다. 이 과정은 병목 현상을 식출하고, 파라미터(그래프 차수 및 검색 빔 너비 등)를 튜닝하며, 메모리 지역성을 위한 데이터 구조를 설계하기 위해 컴퓨터 아키텍처, 병렬 프로그래밍 및 알고리즘 특성에 대한 깊은 전문 지식을 요구합니다. 본 논문은 이러한 수동적 정교화 작업이 노동 집약적이라는 점을 지적하며, 강화 학습(RL)으로 증강된 LLM이 인간 엔지니어가 간과할 수 있는 최적화 패턴을 발견하기 위해 알고리즘 개선을 자동 생성하고 테스트할 수 있는지에 대한 의문을 제기합니다.

방법론

저자들은 CRINN(Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search)을 제안합니다. 이는 ANNS 최적화를 실행 속도를 보상 신호로 사용하는 강화 학습 문제로 취급하는 프레임워크입니다.

핵심 프레임워크

CRINN은 대조적 강화 학습 모델을 사용하여 ANNS 알고리즘을 모듈별로(구체적으로 HNSW 백본 내의 그래프 구축, 검색, 정제 단계 타겟팅) 최적화합니다. 과정은 다음과 같습니다:

대조적 프롬프팅(Contrastive Prompting): LLM에 이전 코드 구현과 그 실행 점수가 쌍을 이룬 프롬프트가 제공됩니다. 모델은 특정 구현이 왜 다른 구현보다 성능이 우수한지 분석하여, 효과적인 전략과 효과적이지 않은 전략을 구분하도록 지시받습니다.
반복적 생성(Iterative Generation): 이러한 분석을 바탕으로, LLM은 새로운 코드 변형을 합성합니다.
보상 신호(Reward Signal): 생성된 코드는 실행되며, 실행 결과에 따라 보상이 계산됩니다. QPS(초당 쿼리 수)와 재현율(Recall) 사이의 트레이드오프로 인해 ANNS 알고리즘을 비교하는 어려움을 해결하기 위해, 저자들은 특정 평가 전략을 사용합니다:
- 검색 파라미터 $ef$를 변화시켜 (QPS, recall) 점들의 집합을 생성합니다.
- 대부분의 알고리즘이 충분한 데이터와 유의미한 성능 차이를 보이는 "스위트 스팟(sweet spot)"인 $[0.85, 0.95]$ 범위 내의 점들을 필터링합니다.
- 보상은 이 필터링된 점들에 의해 형성된 **곡선 아래 면적(AUC)**으로 정의되며, 이는 RL 목적 함수를 위한 단일 스칼라 값을 제공합니다.
학습 알고리즘: 시스템은 **그룹 상대 정책 최적화(Group Relative Policy Optimization, GRPO)**를 채택합니다. 각 입력 프롬프트에 대해 모델은 일련의 코드 완성본 그룹을 생성합니다. 보상은 그룹 내에서 정규화되며, 참조 정책으로부터 너무 멀어지지 않도록 하는 제약 조건(KL 발산)을 유지하면서 더 높은 보상을 주는 코드를 생성할 확률을 최대화하도록 정책이 업데이트됩니다.

구현 세부 사항

베이스라인: 프레임워크는 초기 시작점으로 그래프 기반 ANNS 라이브러리인 GLASS를 사용하며, 구성 모듈을 순차적으로 최적화합니다.
학습 데이터: RL 모델은 단일 일반화 가능한 코드베이스를 유지하기 위해 오직 SIFT-128-Euclidean 데이터셋만 사용하여 학습됩니다.
출력 구조: LLM은 "성능 분석(Performance Analysis)", "알고리즘 설계(Algorithm Design)", "코드 구현(Code Implementation)"을 포함하는 구조화된 응답을 출력하도록 제약됩니다.

주요 기여

자동화된 최적화 패러다임: CRINN은 ANNS 최적화를 RL 증강 LLM을 통해 자동화하는 새로운 패러다임을 도입하여, 전문 지식과 노동 집약적인 튜닝의 필요성을 제거합니다.
대조 학습 메커니즘: 예시 코드와 실행 메트릭을 프롬프트에 직접 통합함으로써, 모델은 단순한 시행착오를 넘어 직접적인 비교를 통해 성능에 결정적인 패턴을 추론하는 법을 배웁니다.
보상 엔지니어링: 논문은 ANNS를 위한 스칼라 보상을 정의하는 문제를 해결하기 위해, 특정 실용적 재현율 범위( $[0.85, 0.95]$ ) 내에서의 QPS-recall 곡선의 AUC를 활용하여 이산적인 파라미터 설정 간의 공정한 비교를 가능하게 합니다.
점진적 최적화: 시스템은 별도의 모듈(그래프 구축, 검색, 정제)을 순차적으로 최적화하는 것이 누적된 성능 이득을 가져온다는 것을 입증합니다.

실험 결과

저자들은 여섯 가지 널리 사용되는 벤치마크 데이터셋(SIFT-128, GIST-960, MNIST-784, GloVe-100, GloVe-25, NYTimes-256)에 대해 CRINN을 평가했습니다.

성능: CRINN은 세 개의 데이터셋(GIST-960-Euclidean, MNIST-784-Euclidean, GloVe-25-angular)에서 **최고 수준의 성능(best-in-class performance)**을 달성했으며, 나머지 두 개(SIFT-128-Euclidean, GloVe-25-angular)에서는 1위를 기록했습니다.
정량적 이득:
- MNIST-784에서 CRINN은 최고 베이스라인(ParlayANN) 대비 0.999 재현율에서 최대 85.25%의 QPS 향상을 보였습니다.
- GIST-960에서 0.99 재현율 기준 72.68%의 향상을 달s성했습니다.
- 학습 데이터셋인 SIFT-128에서는 재현율 수준에 따라 +3.25%에서 +25.57% 사이의 향상을 보였습니다.
한계점: CRINN은 각도 거리(angular distance) 데이터셋인 NYTimes-256에서 0.9 재현율 기준 베스트 베이스라인보다 82.85% 낮은 성능을 보였습니다. 저자들은 이를 모델이 유클리드 거리 데이터로만 학습되었기 때문으로 돌리며, 각도 유사성을 위한 최적화 패턴이 크게 다를 수 있음을 시사했습니다.
모듈별 기여도: 그래프 구축(Graph Construction) 모듈이 가장 큰 개별 이득(평균 +22.11%)을 냈으며, 검색(Search, +18.30%)과 정제(Refinement, +9.69%)가 그 뒤를 이었습니다.

의의 및 주장

CRINN의 성공은 특정 ANNS 알고리즘의 최적화를 넘어 확장된다고 본 논문은 주장합니다. 이는 강화 학습으로 증강된 LLM이 전통적으로 전문 지식과 노동 집약적인 수동 정교화 과정을 요구했던 정교한 알고리즘 최적화를 자동화하는 데 효과적인 도구로 기능할 수 있음을 검증합니다.

저자들은 RAG 및 에이전트 기반 LLM 애플리케이션의 확산과 함께 효율적인 벡터 검색에 대한 수요가 증가함에 따라, CRINN과 같은 프레임워크가 진화하는 하드웨어 아키텍처 및 애플리케이션 요구 사항에 맞춰 경쟁력 있는 성능을 유지하는 데 점점 더 가치 있는 도구가 될 것이라고 주장합니다. 이 연구는 자동화된 시스템이 특정 맥락에서 인간이 설계한 최첨단 솔루션과 대등할 뿐만 아니라, 때로는 이를 능가할 수 있음을 보여줍니다.