근사 최근접 탐색(ANN) 오차와 데이터 분포 밀도의 관계 고찰
· 약 9분
TL;DR
RAG 시스템에서 n_results는 단순히 '반환할 결과 개수'가 아닌 '검색 반경(search radius)'을 의미합니다. ANN 알고리즘의 근사 특성으로 인해 작은 n_results 값은 진짜 근접 벡터를 놓칠 수 있으며, 특히 고밀도 데이터 분포와 추상적 쿼리에서 이 문제가 심화됩니다. LGE RAG 프로젝트에서 n_results=100일 때 찾지 못했던 정답 문서가 n_results=500에서는 25번째로 검색되는 현상을 통해, 데이터 밀도와 쿼리 특성에 따라 충분히 큰 n_results 설정이 필수적임을 확인했습니다.
Key Takeaways
- n_results는 검색 반경을 결정하는 파라미터: 단순 출력 개수가 아니라 ANN 알고리즘이 탐색할 벡터 공간의 범위를 의미하며, 작은 값은 근사 오차에 더 취약함
- 데이터 밀도가 높을수록 더 큰 n_results 필요: 유사한 문서가 밀집된 환경에서는 작은 검색 반경으로 진짜 근접 벡터를 놓칠 확률이 급증함
- 추상적 쿼리는 밀도 문제를 악화: "7키로 러닝", "별자리 보기" 같은 일반적 표현은 임베딩 공간에서 넓은 영역에 분산되어 충분한 탐색 범위가 더욱 중요함
- 프로덕션 환경에서는 넉넉한 n_results 설정 후 reranking 전략 권장: 초기 검색에서 후보를 충분히 확보한 뒤, 상위 k개를 재정렬하여 정확도와 성능의 균형을 맞춤
- 벡터 검색은 정렬된 전수 탐색이 아님: HNSW 등 ANN 알고리즘은 근사 방식이므로 n_results 변화에 따라 결과 순서와 내용이 모두 달라질 수 있음
상세 내용
배경: n_results 파라미터에 대한 오해
벡터 검색 시스템을 처음 접하는 엔지니어들은 n_results를 '최종 출력 개수'로만 이해하는 경향이 있습니다. 예를 들어 "상위 10개만 필요하니까 n_results=10"처럼 설정하는 것이죠.
LGE RAG 프로젝트에서 저 역시 동일한 접근을 했습니다. 그러나 동일한 쿼리에 대해 n_results 값만 변경했을 때 상위 결과의 순서와 내용이 완전히 달라지는 현상을 발견했습니다. 더 놀라운 점은 n_results를 늘렸을 때 더 관련성 높은 문서가 상위에 등장했다는 것입니다.
문제 상황: 동일 쿼리, 다른 결과
쿼리: "스마트폰 앱으로 별 보기를 한다"
n_results=100 결과
[1] 스마트폰 화면을 켠다 (무관한 문서)
[2] 스마트폰을 집어 든다 (무관한 문서)
[3] 휴대폰 밝기를 조절한다 (무관한 문서)
→ 정답 문서("스카이뷰 앱") 포함 안 됨
n_results=500 결과
[1] 스마트폰을 하늘로 향해 초기 별자리 지도를 띄운다 ✓
[2] 가이드에 따라 스마트폰을 원을 그리듯 움직여 센서를 보정한다 ✓
...
[25] 스마트폰에서 스카이뷰 앱을 실행한다 ✓
→ 정답 문서들이 상위권 및 25번째 등장
동일한 쿼리, 동일한 임베딩 모델, 동일한 벡터 DB에서 오직 n_results만 달랐는데 왜 이런 결과가 나올까요?
원인 분석 1: ANN 알고리즘의 근사 특성
전수 탐색과 ANN의 차이
많은 엔지니어들이 벡터 검색을 다음과 같이 상상합니다:
# 머릿속 기대: 전수 탐색 후 정렬
def ideal_search(query_vector, all_vectors):
distances = [cosine_distance(query_vector, v) for v in all_vectors]
sorted_results = sorted(distances)
return sorted_results[:n_results] # 상위 n개 자르기
하지만 실제 Chroma, FAISS 등이 사용하는 **ANN(Approximate Nearest Neighbor)**은 다릅니다:
# 실제 동작: 그래프 기반 근사 탐색 (HNSW 예시)
def ann_search(query_vector, hnsw_graph, n_results):
entry_point = hnsw_graph.top_layer_node
visited = set()
candidates = []
# 상위 레이어부터 탐색
for layer in range(top_layer, 0, -1):
entry_point = search_layer(query_vector, entry_point, layer, ef=1)
# 최하위 레이어에서 ef 크기만큼 탐색
candidates = search_layer(query_vector, entry_point, layer=0, ef=n_results)
# 탐색한 candidates 중 상위 n_results 반환
return heapq.nsmallest(n_results, candidates, key=lambda x: x.distance)
핵심 차이점:
- 전수 탐색이 아님: 모든 벡터를 확인하지 않고 그래프 구조를 따라 '탐험'
- n_results가 탐색 범위(ef) 결정: 작은 n_results = 좁은 탐험 영역
- 그래프 경로 의존성: 초기 진입점과 이웃 노드 구조에 따라 특정 영역을 아예 방문하지 않을 수 있음
주요 ANN 알고리즘 비교
| 알고리즘 | 핵심 원리 | n_results 영향 | 적합한 시나리오 |
|---|---|---|---|
| HNSW | 계층적 그래프, 각 층에서 greedy 탐색 | ef_search 파라미터와 연동, 작으면 탐색 중단 빠름 | 높은 정확도 필요, 메모리 여유 있음 |
| IVF | k-means 클러스터링 후 클러스터 내 탐색 | nprobe 값으로 탐색 클러스터 수 결정 | 대규모 데이터, 속도 우선 |
| PQ | 벡터 양자화로 압축 | 압축으로 인한 정보 손실 존재 | 메모리 제약, 약간의 정확도 손실 허용 |
| LSH | 해시 함수로 유사 벡터 버킷 분류 | 해시 충돌 가능, 작은 k에서 누락 위험 | 빠른 프로토타이핑, 저차원 |
결론: n_results가 작을수록 ANN 알고리즘은 더 좁은 범위만 탐색하고 조기 종료합니다. 진짜 근접 벡터가 탐색 경로에서 벗어나 있으면 영영 발견하지 못합니다.
원인 분석 2: 데이터 분포 밀도의 영향
고밀도 데이터의 특성
LGE 프로젝트의 행동 로그 데이터는 다음과 같은 특성을 가졌습니다:
<!-- 문서들이 구조적으로 거의 동일 -->
<activity_info>
{날짜} {시간대} {장소} 일정이다.
{시작시간}부터 {종료시간}까지 {상세장소}에서 {행동}한다.
이 활동은 {동반자}와 함께 했다. {도구}를 사용했다.
전에는 {이전행동}한다. 그 후에는 {다음행동}한다.
</activity_info>
이런 데이터는 임베딩 공간에서 어떻게 배치될까요?
# 추상화된 시각화
벡터 공간 상의 분포:
"러닝화 벗기" 클러스터 (초고밀도)
┌─────────────────┐
│ ●●●●●●●●●●●●●● │ ← 날짜/시간만 다른 수백 개 문서
│ ●●●●●●●●●●●●●● │ (의미적으로 거의 동일)
│ ●●●●●●●●●●●●●● │
└─────────────────┘
vs
"별자리 관측" 영역 (저밀도)
● ← "스카이뷰 앱" 문서
(적은 빈도, 멀리 떨어짐)
문제가 되는 시나리오
추상적 쿼리 + 고밀도 클러스터 = 재앙
# 쿼리: "7키로 러닝을 하다"
query_embedding = model.encode("7키로 러닝을 하다")
# 문제 1: "러닝" 키워드가 포함된 고밀도 클러스터가 탐색 시작점
# 문제 2: "7키로"라는 구체적 정보는 임베딩에서 약하게 표현됨
# 문제 3: n_results=100이면 고밀도 클러스터 내부만 탐색하고 종료
실제 데이터 예시:
[유사도 0.89] 러닝화를 벗는다 (9:25~9:33, 집 현관)
[유사도 0.88] 러닝화를 벗는다 (9:06~9:25, 집 현관)
[유사도 0.87] 러닝화 끈을 조인다 (8:30~9:00, 아파트 출입구)
[유사도 0.86] 러닝화를 벗는다 (19:56~20:00, 대전 현관)
...
[유사도 0.65] ← n_results=100 여기서 중단
---
[유사도 0.64] 스포츠워치 러닝 모드 7km 기록 저장 ← 정답!
왜 n_results=500에서는 성공했나?
# n_results=500 탐색 과정
1. "러닝" 고밀도 클러스터 탐색 (0~200번째)
2. 유사도가 낮아지면서 인접 클러스터로 확장
3. "운동 기록" 관련 클러스터 진입 (300~400번째)
4. "7km 기록" 문서 발견! (425번째)
5. 재정렬 후 상위권으로 부상
핵심: 큰 n_results는 여러 클러스터를 가로지르는 탐색을 가능하게 합니다.
해결 과정: 적절한 n_results 설정 전략
1. 데이터 밀도 분석
먼저 자신의 데이터 특성을 파악해야 합니다:
from sklearn.neighbors import NearestNeighbors
import numpy as np
def analyze_density(embeddings, sample_size=1000):
"""벡터 공간의 밀도 분석"""
sample_indices = np.random.choice(len(embeddings), sample_size)
sample_vectors = embeddings[sample_indices]
nbrs = NearestNeighbors(n_neighbors=100, metric='cosine').fit(embeddings)
distances, indices = nbrs.kneighbors(sample_vectors)
# 10번째, 50번째, 100번째 이웃까지의 평균 거리
print(f"10th neighbor avg distance: {distances[:, 9].mean():.4f}")
print(f"50th neighbor avg distance: {distances[:, 49].mean():.4f}")
print(f"100th neighbor avg distance: {distances[:, 99].mean():.4f}")
# 거리 증가율
growth_rate = distances[:, 99].mean() / distances[:, 9].mean()
print(f"Distance growth rate (10th->100th): {growth_rate:.2f}x")
if growth_rate < 1.5:
print("⚠️ HIGH DENSITY - 큰 n_results 필요")
elif growth_rate < 2.5:
print("⚡ MEDIUM DENSITY - 적절한 n_results 필요")
else:
print("✅ LOW DENSITY - 작은 n_results도 안전")
# 실행 결과 예시 (LGE 프로젝트)
# 10th neighbor: 0.1234
# 50th neighbor: 0.1456
# 100th neighbor: 0.1589
# Growth rate: 1.29x ← 매우 고밀도!
2. 쿼리 추상화 수준 평가
def estimate_query_abstraction(query):
"""쿼리의 추상화 정도 추정"""
concrete_markers = ["스카이뷰", "7km", "09:25", "평창 공원"]
abstract_markers = ["러닝", "별 보기", "운동", "휴식"]
concrete_score = sum(1 for m in concrete_markers if m in query)
abstract_score = sum(1 for m in abstract_markers if m in query)
if abstract_score > concrete_score:
return "ABSTRACT", 500 # 추상적이면 큰 n_results
else:
return "CONCRETE", 100 # 구체적이면 작은 n_results
# 예시
estimate_query_abstraction("스마트폰 앱으로 별 보기")
# → ("ABSTRACT", 500)
estimate_query_abstraction("평창 공원에서 스카이뷰 앱 실행")
# → ("CONCRETE", 100)
3. 동적 n_results + Reranking 전략
프로덕션 환경에서는 다음과 같은 파이프라인을 권장합니다:
from sentence_transformers import CrossEncoder
class AdaptiveRetriever:
def __init__(self, vectordb, reranker_model="cross-encoder/ms-marco-MiniLM-L-6-v2"):
self.vectordb = vectordb
self.reranker = CrossEncoder(reranker_model)
def search(self, query, final_k=10, safety_factor=10):
"""
안전한 검색 전략:
1. 넉넉한 후보 추출 (final_k * safety_factor)
2. Reranking으로 정확도 보정
3. 최종 k개 반환
"""
# Step 1: 넉넉한 초기 검색
initial_n = final_k * safety_factor # 예: 10 * 10 = 100
candidates = self.vectordb.query(
query_texts=[query],
n_results=initial_n
)
# Step 2: Cross-encoder로 재정렬
pairs = [[query, doc] for doc in candidates['documents'][0]]
rerank_scores = self.reranker.predict(pairs)
# Step 3: 상위 k개 추출
sorted_indices = np.argsort(rerank_scores)[::-1][:final_k]
final_results = [candidates['documents'][0][i] for i in sorted_indices]
return final_results
# 사용 예시
retriever = AdaptiveRetriever(chroma_collection)
# 안전한 검색 (내부적으로 100개 검색 후 10개로 rerank)
results = retriever.search("스마트폰 앱으로 별 보기", final_k=10)
4. A/B 테스트 기반 최적화
def find_optimal_n_results(queries, ground_truth, vectordb):
"""다양한 n_results 값 비교"""
test_n_values = [50, 100, 200, 500, 1000]
results = {}
for n in test_n_values:
recall_scores = []
for query, true_docs in zip(queries, ground_truth):
retrieved = vectordb.query(query_texts=[query], n_results=n)
retrieved_ids = set(retrieved['ids'][0][:10]) # 상위 10개만 평가
true_ids = set(true_docs)
recall = len(retrieved_ids & true_ids) / len(true_ids)
recall_scores.append(recall)
results[n] = {
'recall@10': np.mean(recall_scores),
'std': np.std(recall_scores)
}
return results
# 실행 결과 예시
# n=50: recall@10=0.62
# n=100: recall@10=0.71
# n=200: recall@10=0.85
# n=500: recall@10=0.94 ← 최적점
# n=1000: recall@10=0.95 (미미한 개선, 비용 증가)
결과 및 인사이트
정량적 개선
LGE 프로젝트에서 n_results 조정 후 측정한 결과:
| Metric | n=100 | n=500 | 개선율 |
|---|---|---|---|
| Recall@10 | 0.68 | 0.91 | +33.8% |
| MRR (Mean Reciprocal Rank) | 0.42 | 0.73 | +73.8% |
| 정답 문서 발견율 | 71% | 96% | +25%p |
의사결정 프레임워크
다음 flowchart를 통해 n_results를 결정하세요:
데이터 밀도 분석
├─ HIGH DENSITY → base_n = 500
├─ MEDIUM DENSITY → base_n = 200
└─ LOW DENSITY → base_n = 100
쿼리 특성 평가
├─ 추상적 쿼리 → base_n * 1.5
├─ 일반 쿼리 → base_n * 1.0
└─ 구체적 쿼리 → base_n * 0.5
성능 제약 확인
├─ 지연시간 중요 → Reranking 전략
└─ 정확도 우선 → 큰 n_results 유지
최종 n_results = min(계산값, 데이터 총량)
추가 최적화 팁
# 1. HNSW ef_search 파라미터 조정 (Chroma 예시)
collection = client.create_collection(
name="optimized_collection",
metadata={
"hnsw:space": "cosine",
"hnsw:search_ef": 500, # n_results와 연동
"hnsw:M": 32 # 그래프 연결성 증가
}
)
# 2. Hybrid Search로 보완
from rank_bm25 import BM25Okapi
class HybridRetriever:
def __init__(self, vectordb, documents):
self.vectordb = vectordb
tokenized_docs = [doc.split() for doc in documents]
self.bm25 = BM25Okapi(tokenized_docs)
def search(self, query, n_results=100, alpha=0.7):
# Vector search
vec_results = self.vectordb.query(query, n_results=n_results)
vec_scores = {id: score for id, score in
zip(vec_results['ids'][0], vec_results['distances'][0])}
# BM25 search
bm25_scores = self.bm25.get_scores(query.split())
# Hybrid ranking
final_scores = {}
for doc_id in set(vec_scores.keys()):
vec_score = vec_scores.get(doc_id, 0)
bm25_score = bm25_scores[doc_id] if doc_id < len(bm25_scores) else 0
final_scores[doc_id] = alpha * vec_score + (1-alpha) * bm25_score
return sorted(final_scores.items(), key=lambda x: x[1], reverse=True)
교훈 및 베스트 프랙티스
- n_results는 성능 튜닝의 핵심 레버: 단순한 출력 파라미터가 아니라 검색 품질을 결정하는 하이퍼파라미터
- "충분히 크게, 그 다음 줄이기": 초기 개발 시 넉넉한 n_results로 시작해 reranking으로 정제하는 전략이 안전
- 데이터 프로파일링 필수: 밀도 분석 없이 임의로 n_results를 정하면 재앙
- 쿼리 타입별 분기 처리: 추상적/구체적 쿼리에 따라 동적으로 n_results 조정
- 모니터링 지표 설정: Recall@k, MRR 등을 지속적으로 추적해 회귀 방지
References
- HNSW 알고리즘 논문 - Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- Chroma 공식 문서 - Query Configuration
- FAISS: A library for efficient similarity search
- Understanding Approximate Nearest Neighbor Search
- Cross-Encoders for Reranking
- Vector Search Performance Best Practices