왜 모두 비교하는 게 비쌀까?: 상세 설명과 예제 (RAG)

1. 개요

RAG(Retrieval-Augmented Generation) 파이프라인에서 retrieval 단계는 일반적으로 질문의 벡터를 수십만 개의 passage 벡터와 비교하는 작업입니다. 가장 단순한 방법 — 각 벡터를 순차적으로 비교하는 것 — 은 항상 정확한 결과를 주지만, 데이터 크기에 따라 비용이 선형으로 증가합니다. 이 글은 ’모두 비교하는 것’이 왜 비싼지, Inverted-File Index (IVF)가 클러스터링으로 비용을 어떻게 줄이는지, 그리고 근사 결과를 받아들일 때 치러야 하는 대가를 설명합니다. 이 글을 다 읽고 나면, Java로 간단한 flat index와 IVF index를 직접 작성할 수 있고, 속도와 recall 간의 트레이드오프를 측정할 수 있으며, 언제 근사 검색을 사용해야 할지 — 혹은 하지 말아야 할지 — 알게 될 것입니다.

2. 문제: Flat Index와 O(n) 복잡도

2.1. Flat search는 어떻게 작동하는가

Flat index(또는 brute-force search)는 query를 데이터셋의 모든 벡터와 비교한 다음, 점수(보통 cosine similarity 또는 dot product)가 가장 높은 벡터를 선택합니다. 중간 필터링 단계는 없습니다.

public record Passage(String id, float[] vector) {}

public class FlatVectorIndex {

    private final List<Passage> passages;

    public FlatVectorIndex(List<Passage> passages) {
        this.passages = passages;
    }

    public List<Passage> search(float[] query, int topK) {
        return passages.stream()
                .sorted(Comparator.comparingDouble(p -> -cosine(query, p.vector())))
                .limit(topK)
                .toList();
    }

    private double cosine(float[] a, float[] b) {
        double dot = 0, na = 0, nb = 0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            na += a[i] * a[i];
            nb += b[i] * b[i];
        }
        return dot / (Math.sqrt(na) * Math.sqrt(nb));
    }
}

매번 search를 호출할 때마다 stream() 내의 암시적 루프는 모든 passages와 cosine을 계산해야 합니다. 데이터셋에 n개의 벡터가 있고 각 벡터가 d차원이라면, 각 query의 비용은 O(n × d)입니다. passage의 개수를 두 배로 늘리면, 비교 횟수도 두 배가 됩니다 — 이것이 바로 ’O(n)’의 의미입니다.

주의: Flat search는 “exact” 결과를 제공합니다 — 즉, 선택한 거리 공식에 따라 수학적으로 정확합니다. 하지만 “exact”는 passage가 의미론적으로 올바른 답변을 포함한다는 뜻은 아닙니다. 기하학적 정확성과 의미론적 정확성은 다릅니다.

2.2. 데이터 크기에 따른 비용 측정

public static void main(String[] args) {
    for (int n : List.of(10_000, 100_000)) {
        var passages = TestData.generatePassages(n, 128, 42);
        var index = new FlatVectorIndex(passages);
        float[] query = TestData.randomVector(128, 7);

        long start = System.nanoTime();
        index.search(query, 5);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        System.out.printf("n=%d -> %d ms%n", n, elapsedMs);
    }
}

개발 머신에서의 결과 예시입니다(실제 수치는 하드웨어에 따라 달라지지만, 추세는 항상 같습니다):

n=10000  -> 18 ms
n=100000 -> 176 ms

데이터가 10배 증가하면 시간도 거의 10배 증가합니다 — O(n) 예측과 정확히 일치합니다. 백만 개의 passage와 초당 많은 query가 있으면, 이 비용은 매우 빠르게 누적됩니다. 이것이 flat index가 프로덕션 RAG 시스템에서 잘 확장되지 않는 이유입니다.

3. 솔루션: Inverted-File Index (IVF)

3.1. 클러스터링 개념

IVF는 모든 벡터와 비교하지 않음으로써 비용을 줄입니다. 대신:

인덱스를 구축할 때, 클러스터링(보통 k-means)을 실행하여 각 벡터 그룹을 대표하는 “centroid”를 찾습니다.
데이터셋의 각 벡터는 가장 가까운 centroid를 가진 그룹에 할당됩니다.
검색할 때, query에 가장 가까운 centroid를 가진 몇몇 그룹만 선택하고, 그 그룹 내의 벡터하고만 비교합니다.

백만 개의 passage가 1000개 그룹으로 나뉜다고 상상해보세요. 10개 그룹만 스캔하면, 백만 개 대신 약 10,000개의 passage를 비교합니다 — 비용을 거의 100배 줄입니다.

3.2. nprobe 파라미터

스캔되는 그룹의 수를 nprobe라고 합니다. 더 많은 그룹을 스캔하면 일반적으로 recall(올바른 결과를 찾을 확률)이 향상되지만, 비용도 증가합니다. 이것은 프로덕션에서 직접 튜닝할 파라미터입니다.

public class IvfIndex {

    private final List<float[]> centroids;
    private final Map<Integer, List<Passage>> buckets = new HashMap<>();

    public IvfIndex(List<Passage> passages, List<float[]> centroids) {
        this.centroids = centroids;
        for (Passage p : passages) {
            int cluster = nearestCentroidIndex(p.vector());
            buckets.computeIfAbsent(cluster, k -> new ArrayList<>()).add(p);
        }
    }

    public List<Passage> search(float[] query, int topK, int nprobe) {
        List<Integer> clusters = nearestCentroidIndices(query, nprobe);
        return clusters.stream()
                .flatMap(c -> buckets.getOrDefault(c, List.of()).stream())
                .sorted(Comparator.comparingDouble(p -> -cosine(query, p.vector())))
                .limit(topK)
                .toList();
    }

    private int nearestCentroidIndex(float[] v) {
        return nearestCentroidIndices(v, 1).get(0);
    }

    private List<Integer> nearestCentroidIndices(float[] v, int k) {
        return IntStream.range(0, centroids.size())
                .boxed()
                .sorted(Comparator.comparingDouble(i -> -cosine(v, centroids.get(i))))
                .limit(k)
                .toList();
    }

    private double cosine(float[] a, float[] b) {
        double dot = 0, na = 0, nb = 0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            na += a[i] * a[i];
            nb += b[i] * b[i];
        }
        return dot / (Math.sqrt(na) * Math.sqrt(nb));
    }
}

nearestCentroidIndices는 query에 가장 가까운 k개의 centroid를 찾습니다 — 이것이 search(query, topK, nprobe)를 호출할 때 nprobe가 작동하는 곳입니다. 인덱스 구축 부분(생성자)은 한 번 실행되고, 검색 부분은 매 query마다 실행됩니다 — 이것이 IVF가 쿼리 시점에서 훨씬 빠른 이유입니다.

주의: 위의 예제는 코드를 간단히 유지하기 위해 미리 만들어진 centroid(데이터에서 샘플링)를 사용합니다. 실제로는 클러스터 품질을 높이기 위해 실제 k-means를 실행(여러 번의 centroid 업데이트 루프)해야 합니다 — FAISS, Milvus, pgvector 같은 라이브러리가 이 작업을 대신합니다.

3.3. pgvector로 실제 연결

PostgreSQL에서 pgvector 확장을 사용 중이라면, IVF와 nprobe 개념이 SQL에서 직접 나타납니다:

CREATE INDEX ON passages USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 1000);

SET ivfflat.probes = 10;

lists는 인덱스 구축 시 클러스터 수에 해당하고, probes는 query 시 nprobe에 해당합니다. 직접 k-means를 작성할 필요 없이 — 트레이드오프를 이해하고 적절한 수를 선택하기만 하면 됩니다.

4. 트레이드오프: recall vs. 속도

IVF는 approximate nearest neighbor (ANN)의 한 형태입니다. 속도를 얻기 위해 절대적 정확성을 포기합니다. 문제는: 클러스터는 수학적 거리로부터 형성되며, 사람이 문서를 분류하는 방식의 “깔끔한” 주제 경계로부터가 아닙니다.

RAG의 구체적인 예: ‘항공편 지연 시 환불’ 관련 조항은 ‘출장 비용 정책’ 클러스터보다 보험 문서의 벡터 클러스터에 더 가까울 수 있습니다 — 주제적으로는 직원이 출장 문서에서 찾을 것이지만. nprobe가 ‘비용 정책’ 클러스터만 스캔하면, 올바른 답변은 데이터에 존재함에도 불구하고 완전히 놓칩니다.

4.1. nprobe에 따른 recall 감소 테스트

class IvfIndexTest {

    @Test
    void nprobeThapCoTheLamMatKetQuaDung() {
        var passages = TestData.generatePassages(2000, 64, 42);
        var centroids = TestData.sampleCentroids(passages, 40, 42);
        var ivf = new IvfIndex(passages, centroids);
        var flat = new FlatVectorIndex(passages);

        float[] query = passages.get(1337).vector();

        var exact = flat.search(query, 5);
        var approxFewProbes = ivf.search(query, 5, 1);
        var approxManyProbes = ivf.search(query, 5, 40); // = 모두 스캔, flat과 동일

        assertThat(approxManyProbes).containsExactlyInAnyOrderElementsOf(exact);
        assertThat(approxFewProbes).isNotEqualTo(approxManyProbes);
    }
}

approxManyProbes는 40개 클러스터를 모두 스캔하므로 결과가 flat search와 정확히 일치합니다 — 이것이 IVF에 논리적 오류가 없음을 확인하는 기준입니다. approxFewProbes는 1개 클러스터만 스캔하고, 마지막 assertion은 결과가 정확한 경우와 다르다는 것을 확인합니다 — nprobe가 너무 낮을 때 recall 손실의 위험을 보여줍니다.

exact            = [p1337, p0892, p0456, p1890, p0023]
approxFewProbes  = [p1337, p0456, p0901, p0234]   // 4개 결과만, p0892, p1890 누락
approxManyProbes = [p1337, p0892, p0456, p1890, p0023]

nprobe가 낮으면, 인덱스는 단순히 더 적은 결과를 반환하는 것이 아니라, ’벗어난 클러스터’에 있는 중요한 passage를 놓칠 수 있습니다 — 위의 보험/출장 비용 예제와 동일합니다.

5. Flat을 언제 쓰고, IVF를 언제 쓸까

Flat search를 사용할 때: 데이터셋이 작을 때(수만 개 passage 이하), 또는 감사/컴플라이언스 목적으로 절대 정확성이 필요할 때, 또는 프로토타입 단계에서 추가 파라미터 튜닝을 아직 원하지 않을 때.
IVF(또는 HNSW)를 사용할 때: 데이터셋이 클 때(수십만에서 수백만 passage), 쿼리 지연이 중요할 때(챗봇, 실시간 검색), 그리고 속도를 위해 100% 미만의 recall을 수용할 준비가 되었을 때.

주의: 벤치마크 속도만 좋다고 nprobe를 너무 낮게 설정하지 마세요. RAG 시스템의 실제 질문 집합에서 recall을 측정하세요 — 중요한 컨텍스트가 없는 답변은 몇십 ms 느린 쿼리보다 더 나쁩니다.

프로덕션의 일반적인 패턴: IVF(또는 HNSW)를 사용하여 허용 가능한 recall로 상위 100개 후보를 빠르게 가져온 다음, reranking 단계(cross-encoder 또는 그 100개 후보 집합에 대한 flat search)를 사용하여 손실된 정확성을 보충합니다. 이 방식은 ANN의 속도를 유지하면서도 최종 결과 품질을 향상시킵니다.

6. 결론

Flat search는 완벽하게 정확하지만 비용이 passage 수에 따라 선형으로 증가합니다 — RAG가 수백만 문서를 제공해야 할 때 확장되지 않습니다. IVF는 클러스터링과 nprobe 파라미터로 이 문제를 해결하며, 일부 recall을 속도로 바꿉니다. 대가는 벡터 클러스터가 사람이 이해하는 주제 경계와 일치하지 않으므로, 중요한 passage가 스캔되지 않은 클러스터에 “떨어질” 수 있다는 것입니다. 이 트레이드오프를 명확히 이해하면 올바른 인덱스를 선택하고, 파라미터를 올바르게 튜닝하며, 정확성을 보충하기 위해 언제 reranking 단계를 추가해야 하는지 알 수 있습니다.