Sao so hết lại quá tốn?: giải thích chi tiết kèm ví dụ (RAG)

1. Tổng quan

Trong pipeline RAG (Retrieval-Augmented Generation), bước retrieval thường là so khớp vector câu hỏi với vector của hàng trăm nghìn passage. Cách đơn giản nhất — so sánh tuần tự từng vector — luôn cho kết quả đúng nhưng chi phí tăng tuyến tính theo kích thước dữ liệu. Bài này giải thích vì sao “so hết” lại tốn, cách Inverted-File Index (IVF) giảm chi phí bằng clustering, và cái giá bạn phải trả khi chấp nhận kết quả xấp xỉ. Đọc xong, bạn sẽ tự viết được một flat index và một IVF index đơn giản bằng Java, đo được sự đánh đổi giữa tốc độ và recall, và biết khi nào nên — hoặc không nên — dùng approximate search.

2. Vấn đề: Flat Index và độ phức tạp O(n)

2.1. Flat search hoạt động thế nào

Flat index (hay brute-force search) so sánh query với toàn bộ vector trong tập dữ liệu, rồi chọn ra những vector có điểm số (thường là cosine similarity hoặc dot product) cao nhất. Không có bước lọc trung gian nào cả.

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));
    }
}

Mỗi lần gọi search, vòng lặp ẩn trong stream() phải tính cosine với tất cả passages. Nếu tập dữ liệu có n vector và mỗi vector có d chiều, chi phí mỗi query là O(n × d). Gấp đôi số passage, gấp đôi số phép so sánh — đây chính là ý nghĩa của “O(n)”.

Lưu ý: Flat search cho kết quả “exact” — nghĩa là đúng tuyệt đối theo công thức khoảng cách bạn chọn. Nhưng “exact” không có nghĩa là passage đó chứa câu trả lời đúng về mặt ngữ nghĩa. Độ chính xác hình học và độ chính xác ngữ nghĩa là hai thứ khác nhau.

2.2. Đo chi phí tăng theo kích thước dữ liệu

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);
    }
}

Kết quả minh họa trên máy phát triển (số liệu thật phụ thuộc phần cứng, nhưng xu hướng luôn giữ nguyên):

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

Dữ liệu tăng 10 lần, thời gian tăng gần 10 lần — đúng với dự đoán O(n). Với một triệu passage và nhiều query mỗi giây, chi phí này cộng dồn rất nhanh. Đây là lý do flat index không scale tốt cho hệ thống RAG production.

3. Giải pháp: Inverted-File Index (IVF)

3.1. Ý tưởng clustering

IVF giảm chi phí bằng cách không so sánh với mọi vector. Thay vào đó:

1. Khi xây index, chạy clustering (thường là k-means) để tìm ra các “centroid” đại diện cho từng nhóm vector gần nhau.
2. Mỗi vector trong tập dữ liệu được gán vào nhóm có centroid gần nhất.
3. Khi tìm kiếm, chỉ chọn một số nhóm có centroid gần query nhất, rồi chỉ so sánh với vector trong các nhóm đó.

Tưởng tượng một triệu passage được chia vào 1000 nhóm. Nếu chỉ quét 10 nhóm, bạn so sánh khoảng 10.000 passage thay vì cả triệu — giảm chi phí gần 100 lần.

3.2. Tham số nprobe

Số nhóm được quét gọi là nprobe. Quét nhiều nhóm hơn thường cải thiện recall (tỷ lệ tìm được kết quả đúng) nhưng cũng làm tăng chi phí. Đây là tham số bạn sẽ tune trực tiếp trong production.

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 tìm k centroid gần query nhất — đây chính là nơi nprobe phát huy tác dụng khi gọi search(query, topK, nprobe). Phần build index (constructor) chạy một lần, phần search chạy mỗi query — đó là lý do IVF nhanh hơn nhiều ở thời điểm truy vấn.

Lưu ý: Ví dụ trên dùng centroid cho sẵn (lấy mẫu từ dữ liệu) để giữ code ngắn. Trong thực tế, bạn cần chạy k-means thật (nhiều vòng lặp cập nhật centroid) để nhóm có chất lượng tốt — các thư viện như FAISS, Milvus hay pgvector đã làm việc này cho bạn.

3.3. Wiring thực tế với pgvector

Nếu bạn đang dùng PostgreSQL với extension pgvector, khái niệm IVF và nprobe xuất hiện trực tiếp trong SQL:

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

SET ivfflat.probes = 10;

lists tương đương số cluster khi xây index, probes tương đương nprobe khi query. Bạn không cần tự viết k-means — chỉ cần hiểu đánh đổi để chọn số hợp lý.

4. Đánh đổi: recall vs. tốc độ

IVF là một dạng approximate nearest neighbor (ANN). Nó đổi độ chính xác tuyệt đối để lấy tốc độ. Vấn đề là: các cluster được hình thành từ khoảng cách toán học, không phải từ ranh giới chủ đề “gọn gàng” theo cách con người phân loại tài liệu.

Ví dụ cụ thể trong RAG: một điều khoản về “hoàn tiền khi chuyến bay bị hoãn” có thể nằm gần cụm vector của tài liệu bảo hiểm hơn là cụm “chính sách chi phí công tác” — dù về mặt chủ đề, nhân viên sẽ tra cứu nó trong tài liệu công tác. Nếu nprobe chỉ quét cụm “chính sách chi phí”, câu trả lời đúng bị bỏ lỡ hoàn toàn, dù nó tồn tại trong dữ liệu.

4.1. Test kiểm tra recall giảm theo nprobe

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); // = quét hết, tương đương flat

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

approxManyProbes quét toàn bộ 40 cluster nên kết quả trùng khớp hoàn toàn với flat search — đây là baseline để xác nhận IVF không có lỗi logic. approxFewProbes chỉ quét 1 cluster, và assertion cuối xác nhận rằng kết quả khác với trường hợp chính xác — minh họa rủi ro mất recall khi nprobe quá thấp.

exact            = [p1337, p0892, p0456, p1890, p0023]
approxFewProbes  = [p1337, p0456, p0901, p0234]   // chỉ 4 kết quả, thiếu p0892, p1890
approxManyProbes = [p1337, p0892, p0456, p1890, p0023]

Khi nprobe thấp, index không chỉ trả về ít kết quả hơn đúng, mà còn có thể bỏ lỡ passage quan trọng nằm “lệch cụm” — đúng với ví dụ bảo hiểm/chi phí công tác ở trên.

5. Khi nào dùng flat, khi nào dùng IVF

• Dùng flat search khi: tập dữ liệu nhỏ (vài chục nghìn passage trở xuống), hoặc bạn cần độ chính xác tuyệt đối cho mục đích audit/compliance, hoặc đang ở giai đoạn prototype và chưa muốn tune thêm tham số.
• Dùng IVF (hoặc HNSW) khi: tập dữ liệu lớn (hàng trăm nghìn đến hàng triệu passage), độ trễ query là yếu tố sống còn (chatbot, search real-time), và bạn chấp nhận recall dưới 100% để đổi lấy tốc độ.

Lưu ý: Đừng chọn nprobe quá thấp chỉ vì benchmark tốc độ đẹp. Hãy đo recall trên tập câu hỏi thật của hệ thống RAG — một câu trả lời bị thiếu context quan trọng còn tệ hơn một query chậm vài chục ms.

Một pattern phổ biến trong production: dùng IVF (hoặc HNSW) để lấy nhanh top-100 candidate với recall chấp nhận được, sau đó dùng một bước rerank (cross-encoder hoặc flat search trên tập nhỏ 100 candidate đó) để bù lại phần chính xác đã mất. Cách này giữ được tốc độ của ANN mà vẫn nâng chất lượng kết quả cuối.

6. Kết luận

Flat search đúng tuyệt đối nhưng chi phí tăng tuyến tính theo số lượng passage — không scale khi RAG của bạn phải phục vụ hàng triệu document. IVF giải quyết vấn đề này bằng clustering và tham số nprobe, đổi một phần recall để lấy tốc độ. Cái giá phải trả là các cụm vector không trùng khớp với ranh giới chủ đề theo cách con người hiểu, nên passage quan trọng đôi khi nằm “lạc” ở cụm không được quét. Hiểu rõ đánh đổi này giúp bạn chọn đúng index, tune đúng tham số, và biết khi nào cần thêm bước rerank để bù lại độ chính xác.