ZH
EspañolPortuguêsFrançaisTiếng ViệtDeutschEnglish한국어日本語简体中文
首页 / AI 与机器学习 / RAG

为什么遍历搜索这么贵？: 详细解释及示例 (RAG)

Cris The Dev · 2026/10/06 · 8 分钟阅读 · 105
本文有一个短视频：YouTubeTikTok

1. 概述

在 RAG (Retrieval-Augmented Generation) 管道中，检索步骤通常是将问题向量与数十万篇段落的向量匹配。最简单的方法——逐个向量地顺序比较——总是给出正确结果，但成本随着数据大小线性增长。本文解释为什么“遍历搜索”这么昂贵，Inverted-File Index (IVF) 如何通过聚类降低成本，以及当你接受近似结果时需要付出的代价。读完之后，你将能够用 Java 自己编写一个简单的 flat index 和 IVF index，测量速度和 recall 之间的权衡，并了解何时应该——或不应该——使用近似搜索。

2. 问题：Flat Index 与 O(n) 复杂度

2.1. Flat search 如何工作

Flat index（或 brute-force search）将查询与数据集中的所有向量进行比较，然后选出得分最高的向量（通常是 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 的余弦相似度。如果数据集有 n 个向量，每个向量有 d 维，则每个查询的成本是 O(n × d)。段落数量加倍，比较次数也加倍——这正是“O(n)“的含义。

注意： Flat search 给出“精确”结果——即根据你选择的距离公式完全正确。但“精确”并不意味着这个段落在语义上包含正确答案。几何精度和语义精度是两码事。

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) 预测一致。对于一百万个段落和每秒许多查询，这种成本会迅速累加。这就是为什么 flat index 不能很好地扩展到生产 RAG 系统。

3. 解决方案：倒排文件索引 (IVF)

3.1. 聚类思想

IVF 通过不与每个向量比较来降低成本。相反：

  1. 当构建索引时，运行聚类（通常是 k-means）来找到代表每组相近向量的“质心”。
  2. 数据集中的每个向量被分配到最近的质心所在的组。
  3. 在搜索时，只选择质心最接近查询的几个组，然后只比较这些组中的向量。

想象一百万个段落被分成 1000 个组。如果只扫描 10 个组，你比较大约 10,000 个段落，而不是全部一百万个——成本降低近 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 找到最接近查询的 k 个质心——这正是 nprobe 在调用 search(query, topK, nprobe) 时发挥作用的地方。构建索引部分（构造函数）运行一次，搜索部分每个查询运行一次——这就是为什么 IVF 在查询时快得多。

注意： 上面的示例使用预先给定的质心（从数据中采样）来保持代码简洁。在实践中，你需要运行真正的 k-means（多次迭代更新质心）以获得高质量的聚类——FAISS、Milvus 或 pgvector 等库已经为你完成了这项工作。

3.3. 使用 pgvector 的实际连接

如果你正在使用带有 pgvector 扩展的 PostgreSQL，IVF 和 nprobe 概念直接出现在 SQL 中：

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

SET ivfflat.probes = 10;

lists 等同于构建索引时的聚类数，probes 等同于查询时的 nprobe。你不需要自己编写 k-means——只需理解权衡以选择合理的数字。

4. 权衡：recall 与速度

IVF 是一种近似最近邻（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 较低时，索引不仅返回的结果比正确数量少，还可能错过重要的“偏离聚类”的段落——正如上面保险/差旅费示例所示。

5. 何时使用 flat，何时使用 IVF

  • 使用 flat search 时： 数据集较小（数万个段落或更少），或者你需要绝对精度用于审计/合规目的，或者你还在原型阶段，不想调优更多参数。
  • 使用 IVF（或 HNSW）时： 数据集很大（数十万到数百万个段落），查询延迟是关键因素（聊天机器人、实时搜索），并且你愿意接受低于 100% 的 recall 来换取速度。

注意： 不要只因为速度基准测试看起来不错就选择过低的 nprobe。在你的 RAG 系统的真实问题集上测量 recall——缺少重要上下文的答案比晚了几十毫秒的查询更糟。

生产中的常见做法是：使用 IVF（或 HNSW）快速获取可接受 recall 的前 100 个候选项，然后使用重新排序步骤（cross-encoder 或在这 100 个候选项的小集合上进行 flat search）来弥补损失的精度。这种方法保持了 ANN 的速度，同时提高了最终结果的质量。

6. 结论

Flat search 精度绝对但成本随段落数量线性增长——当你的 RAG 必须服务数百万文档时无法扩展。IVF 通过聚类和 nprobe 参数解决了这个问题，用部分 recall 换取速度。代价是向量聚类与人类理解的主题边界不相符，所以重要的段落有时会“迷失”在未被扫描的聚类中。清楚地理解这种权衡可以帮助你选择正确的索引、调优正确的参数，并了解何时需要添加重新排序步骤来弥补精度损失。

rag向量搜索ivfjavaembedding
作者的应用HoanTien.proCashback on Shopee, TikTok Shop and Lazada (Vietnam)iOS · Android · Web

同主题文章

RAG · 2026/10/13 · 10 分钟阅读 · 110

RAG 从 A 到 Z：先获取文档再回答

用 Spring AI 构建完整的 RAG 管道：切分文档、生成嵌入、向量搜索、构建带引用的提示词并为每个步骤编写测试。

RAG · 2026/10/05 · 8 分钟阅读 · 112 · 有视频

从找到段落到有证据的答案在 RAG 中

找到相关段落并不意味着有答案。本文介绍了 rerank、混合搜索和 grounding 管道，使 LLM 能够提供有证据的答案，并在数据不足时拒绝回答。