5D Library › 检索增强生成几何、倒数秩融合与多智能体误差级联 · English

第一章 高维几何:测度集中、有效维度与枢纽块

一个流行的直觉

检索增强生成(RAG)的基本做法是:把知识库切成小块,每块编码成一个向量,用户提问时取出与问题向量最相似的几块,交给语言模型作答 (Lewis et al. 2020; Karpukhin et al. 2020)。一个流行的直觉是:嵌入的维度越高、塞进向量库的块越多,检索就越准。本章检查这个直觉的两半。第一半「维度越高越好」只在一个理想化的模型里成立,而真实嵌入的有效维度远低于名义维度;第二半「块越多越好」在任何维度下都有代价——语料越大,最强的干扰块越强。最后,高维空间还会自发地产生一类「枢纽块」,它们与大量无关问题都很近。

测度集中与语料规模的代价

推导

随机方向几乎正交。 dd 维单位球面上两个独立随机向量的余弦,均值为 0,标准差为 1/d1/\sqrt{d}——这是测度集中现象的一个最简单的例子 (Ledoux 2001; Vershynin 2018)。MM 个这样的余弦中最大的一个,大约是 2ln⁡M/d\sqrt{2\ln M / d}。所以,若真正相关的块与问题的余弦为 ss,当 2ln⁡M/d\sqrt{2\ln M/d} 接近 ss 时,第一名就开始被干扰块抢走。

推导

# Chapter 1. p01: Concentration of measure and the corpus-size penalty.
# A. Cosines between independent random unit vectors in d dimensions
#    have mean 0 and standard deviation 1/sqrt(d) (2,000 pairs each).
# B. Retrieval as an extreme-value race. The relevant chunk has cosine
#    s = 0.30 with the query plus noise; each of M irrelevant chunks has a
#    cosine that is pure noise of sd 1/sqrt(d) (isotropic model). Top-1 is
#    wrong when the largest of M noise cosines beats the relevant one.
#    The largest of M grows like sqrt(2 ln M / d). 1,000 queries per cell.
import math
import random

def unit(rng, d):
    v = [rng.gauss(0, 1) for _ in range(d)]
    n = math.sqrt(sum(x * x for x in v))
    return [x / n for x in v]

def erfinv(y):
    # Newton on erf(x) = y, from a good start
    x = 0.0 if abs(y) < 0.7 else math.copysign(
        math.sqrt(-math.log((1 - abs(y)) / 2)), y)
    for _ in range(60):
        err = math.erf(x) - y
        x -= err / (2 / math.sqrt(math.pi) * math.exp(-x * x))
    return x

if __name__ == "__main__":
    rng = random.Random(61001)
    print("A. cosine of random unit vectors")
    print("      d    sd (simulated)   1/sqrt(d)   largest |cos| of 2,000")
    for d in (16, 64, 256, 1024):
        cs = []
        for _ in range(2000):
            a, b = unit(rng, d), unit(rng, d)
            cs.append(sum(x * y for x, y in zip(a, b)))
        sd = math.sqrt(sum(c * c for c in cs) / len(cs))
        print("   {:4d}      {:.4f}          {:.4f}       {:.4f}".format(
            d, sd, 1 / math.sqrt(d), max(abs(c) for c in cs)))
    print("\nB. P(top-1 wrong), relevant cosine 0.30 (+ noise of same sd)")
    sizes = (1000, 10000, 100000, 1000000)
    print("      d   " + "".join("   M = {:<8d}".format(m) for m in sizes))
    for d in (64, 256, 768):
        sd = 1 / math.sqrt(d)
        cells = []
        for m in sizes:
            wrong = 0
            for _ in range(1000):
                rel = 0.30 + rng.gauss(0, sd)
                # max of m iid N(0, sd^2) by inverse CDF of the max
                u = rng.random() ** (1 / m)
                z = math.sqrt(2) * erfinv(2 * u - 1)
                wrong += z * sd > rel
            cells.append("   {:9.4f}  ".format(wrong / 1000))
        print("   {:4d}".format(d) + "".join(cells))
    for d in (64, 768):
        print("   d = {:3d}: sqrt(2 ln M / d) at M = 1e6 is {:.3f}".format(
            d, math.sqrt(2 * math.log(1e6) / d)))
    print("\nReading: in this isotropic model more dimensions help - noise")
    print("cosines shrink like 1/sqrt(d) - but every tenfold growth of the")
    print("corpus raises the best distractor by a fixed step, so top-1")
    print("errors climb with M at any d. The next program shows")
    print("why real embeddings behave as if d were far smaller.")
# A. cosine of random unit vectors
#       d    sd (simulated)   1/sqrt(d)   largest |cos| of 2,000
#      16      0.2524          0.2500       0.8060
#      64      0.1243          0.1250       0.4137
#     256      0.0623          0.0625       0.1969
#    1024      0.0320          0.0312       0.1029
#
# B. P(top-1 wrong), relevant cosine 0.30 (+ noise of same sd)
#       d      M = 1000       M = 10000      M = 100000     M = 1000000
#      64      0.7890        0.9270        0.9710        0.9850
#     256      0.0730        0.1740        0.3280        0.5030
#     768      0.0000        0.0000        0.0000        0.0010
#    d =  64: sqrt(2 ln M / d) at M = 1e6 is 0.657
#    d = 768: sqrt(2 ln M / d) at M = 1e6 is 0.190
#
# Reading: in this isotropic model more dimensions help - noise
# cosines shrink like 1/sqrt(d) - but every tenfold growth of the
# corpus raises the best distractor by a fixed step, so top-1
# errors climb with M at any d. The next program shows
# why real embeddings behave as if d were far smaller.

A 段验证了 1/d1/\sqrt{d}:16 维时随机余弦的标准差 0.2524,1024 维时 0.0320。B 段让相关块的余弦为 0.30,与 MM 个纯噪声干扰块竞争第一名。在这个各向同性的模型里,维度确实有帮助:64 维时,1,000 个块就有 0.7890 的概率排错,768 维时一百万个块也只有 0.0010。但对每一个维度,错误率都随 MM 单调上升:256 维时从 0.0730(1,000 块)升到 0.5030(一百万块)。语料每扩大十倍,最强干扰块的余弦就上升一个固定的台阶;块越多,越需要相关块与问题有更强的相似度。

名义维度与有效维度

上面的结论依赖一个假设:所有方向同样重要。真实的嵌入不是这样。Ethayarajh 发现上下文嵌入高度各向异性,无关文本之间的余弦普遍为正 (Ethayarajh 2019);Mu 与 Viswanath 发现少数主方向承载了大部分方差 (Mu and Viswanath 2018)。

推导

参与率。 若嵌入坐标的方差为 λ1,…,λd\lambda_1, \dots, \lambda_d,有效维度(参与率)为 deff=(∑iλi)2∑iλi2,d_{\mathrm{eff}} = \frac{\big(\sum_i \lambda_i\big)^2}{\sum_i \lambda_i^2} , 各向同性时等于 dd,方差集中于少数方向时远小于 dd。随机余弦的离散程度由 deffd_{\mathrm{eff}} 而不是 dd 决定。

推导

# Chapter 1. p02: Nominal dimension versus effective dimension.
# Embeddings with d = 768 coordinates whose variances fall off as a power
# law, lambda_i ~ i^(-a), plus a shared mean vector (the "common
# direction" that makes raw cosines between unrelated texts positive).
# Effective dimension (participation ratio) d_eff = (sum lambda)^2 /
# sum lambda^2. For 1,500 random pairs: mean and sd of raw cosines, and
# of cosines after centring (subtracting the mean vector). Then the
# top-1 race of p01 (relevant cosine 0.30 above the noise mean) is rerun
# with the centred noise sd, at M = 100,000 chunks.
import math
import random

D = 768

def erfinv(y):
    x = 0.0 if abs(y) < 0.7 else math.copysign(
        math.sqrt(-math.log((1 - abs(y)) / 2)), y)
    for _ in range(60):
        x -= (math.erf(x) - y) / (2 / math.sqrt(math.pi) * math.exp(-x * x))
    return x

def cos(a, b):
    na = math.sqrt(sum(x * x for x in a))
    nb = math.sqrt(sum(x * x for x in b))
    return sum(x * y for x, y in zip(a, b)) / (na * nb)

if __name__ == "__main__":
    rng = random.Random(61002)
    print("   a     d_eff   raw mean   raw sd   centred sd"
          "   P(top-1 wrong)")
    for a in (0.0, 0.5, 1.0, 1.5):
        lam = [(i + 1) ** (-a) for i in range(D)]
        tot = sum(lam)
        lam = [v * D / tot for v in lam]             # same total variance
        deff = sum(lam) ** 2 / sum(v * v for v in lam)
        sdv = [math.sqrt(v) for v in lam]
        mu = [0.0] * D
        mu[D - 1] = math.sqrt(D) * 0.6               # shared direction
        raw, cen = [], []
        for _ in range(1500):
            z1 = [rng.gauss(0, s) for s in sdv]
            z2 = [rng.gauss(0, s) for s in sdv]
            raw.append(cos([x + m for x, m in zip(z1, mu)],
                           [x + m for x, m in zip(z2, mu)]))
            cen.append(cos(z1, z2))
        m_raw = sum(raw) / len(raw)
        sd_raw = math.sqrt(sum((c - m_raw) ** 2 for c in raw) / len(raw))
        sd_cen = math.sqrt(sum(c * c for c in cen) / len(cen))
        wrong = 0
        for _ in range(2000):
            rel = 0.30 + rng.gauss(0, sd_cen)
            u = rng.random() ** (1 / 1e5)
            wrong += math.sqrt(2) * erfinv(2 * u - 1) * sd_cen > rel
        print("  {:3.1f}   {:6.1f}    {:6.3f}    {:.4f}    {:.4f}"
              "       {:.4f}".format(a, deff, m_raw, sd_raw, sd_cen,
                                     wrong / 2000))
    print("   (top-1 race at M = 100,000 chunks)")
    print("\nReading: with the same 768 coordinates, a power-law spectrum")
    print("leaves only tens of effective dimensions, so unrelated texts")
    print("scatter as widely as in a much smaller space and top-1 errors")
    print("return. The shared direction lifts every raw cosine, which is")
    print("why raw scores mean little in absolute terms; centring removes")
    print("that offset but cannot restore the missing dimensions.")
#    a     d_eff   raw mean   raw sd   centred sd   P(top-1 wrong)
#   0.0    768.0     0.264    0.0315    0.0344       0.0000
#   0.5    403.5     0.267    0.0399    0.0506       0.0675
#   1.0     31.7     0.270    0.1222    0.1587       0.9875
#   1.5      5.4     0.304    0.2676    0.3494       0.9995
#    (top-1 race at M = 100,000 chunks)
#
# Reading: with the same 768 coordinates, a power-law spectrum
# leaves only tens of effective dimensions, so unrelated texts
# scatter as widely as in a much smaller space and top-1 errors
# return. The shared direction lifts every raw cosine, which is
# why raw scores mean little in absolute terms; centring removes
# that offset but cannot restore the missing dimensions.

四种谱的名义维度都是 768。方差按幂律衰减(指数 a=1.0a = 1.0)时,有效维度只剩 31.7;a=1.5a = 1.5 时只剩 5.4。与此对应,无关文本之间余弦的离散程度(中心化后)从 0.0344 上升到 0.1587 与 0.3494,十万个块中把第一名排错的概率从 0.0000 上升到 0.9875 与 0.9995——768 维的嵌入,表现得像一个几十维的空间。

共享方向还让所有原始余弦都偏正(均值约 0.264 到 0.304),所以「余弦 0.304」本身几乎没有绝对意义。减去均值(中心化)可以去掉这个偏移,但不能恢复缺失的维度。所以对提纲的第一处修正是:决定检索精度的是有效维度,而不是名义维度;提高名义维度,若谱的形状不变,未必有帮助。

高维空间中的枢纽:近邻出现次数 N_k 的分布随维度增加而右偏;少数块出现在大量近邻列表中,许多块从不出现。

枢纽块:位置决定的「人缘」

推导

# Chapter 1. p03: Hubs: chunks that are everybody's nearest neighbour.
# 800 chunk vectors, i.i.d. Gaussian in d dimensions. For each chunk,
# its k = 10 nearest neighbours (Euclidean). N_k(x) counts how often x
# appears in other chunks' lists; its mean is exactly k. In low d, N_k
# is nearly symmetric; as d grows it becomes right-skewed: a few hubs
# appear in very many lists and many anti-hubs in none (Radovanovic,
# Nanopoulos and Ivanovic 2010). Then 300 fresh queries: how often does
# a top-1 % hub sit in a query's top 10?
import math
import random

N, K = 800, 10

def knn_counts(pts):
    n = len(pts)
    sq = [sum(x * x for x in p) for p in pts]
    counts = [0] * n
    for i in range(n):
        pi = pts[i]
        d = [(sq[i] + sq[j] - 2 * sum(a * b for a, b in zip(pi, pts[j])), j)
             for j in range(n) if j != i]
        d.sort()
        for _, j in d[:K]:
            counts[j] += 1
    return counts

def skew(v):
    m = sum(v) / len(v)
    s2 = sum((x - m) ** 2 for x in v) / len(v)
    return sum((x - m) ** 3 for x in v) / len(v) / s2 ** 1.5

if __name__ == "__main__":
    rng = random.Random(61003)
    print("     d   skew N_k   max N_k   anti-hubs   top 5 % hold"
          "   queries hit a hub")
    for d in (3, 20, 100):
        pts = [[rng.gauss(0, 1) for _ in range(d)] for _ in range(N)]
        c = knn_counts(pts)
        top = sorted(range(N), key=lambda i: -c[i])
        share = sum(c[i] for i in top[:N // 20]) / (N * K)
        hubs = set(top[:N // 100])
        hit = 0
        for _ in range(300):
            q = [rng.gauss(0, 1) for _ in range(d)]
            dd = sorted((sum((a - b) ** 2 for a, b in zip(q, p)), j)
                        for j, p in enumerate(pts))
            hit += any(j in hubs for _, j in dd[:K])
        print("   {:3d}    {:6.2f}     {:4d}     {:6.1%}      {:6.1%}"
              "          {:6.1%}".format(d, skew(c), max(c),
                                         sum(x == 0 for x in c) / N,
                                         share, hit / 300))
    chance = 1 - math.prod((N - N // 100 - i) / (N - i) for i in range(K))
    print("   chance that 8 given chunks of 800 meet a random top 10:"
          " {:.1%}".format(chance))
    print("\nReading: in three dimensions every chunk is someone's")
    print("neighbour about equally often. In a hundred, a handful of")
    print("hubs turns up in a large share of all neighbour lists and many")
    print("chunks are never retrieved at all; the top 1 % of chunks")
    print("intrudes on the top 10 of many unrelated queries. Nothing about")
    print("their content earns it - only their position in the space.")
#      d   skew N_k   max N_k   anti-hubs   top 5 % hold   queries hit a hub
#      3     -0.38       18       0.4%        7.8%            9.0%
#     20      2.27       83       6.4%       21.9%           46.0%
#    100      4.32      177      18.8%       33.8%           77.7%
#    chance that 8 given chunks of 800 meet a random top 10: 9.6%
#
# Reading: in three dimensions every chunk is someone's
# neighbour about equally often. In a hundred, a handful of
# hubs turns up in a large share of all neighbour lists and many
# chunks are never retrieved at all; the top 1 % of chunks
# intrudes on the top 10 of many unrelated queries. Nothing about
# their content earns it - only their position in the space.

三维时,每个块出现在别人近邻列表中的次数大致相同(偏度 −0.38),1% 最常出现的块落入一个新问题的前十名的概率是 9.0%,与随机的 9.6% 相当。到一百维,分布严重右偏(偏度 4.32):最「受欢迎」的块出现在 177 个列表中,18.8% 的块从未出现在任何列表里,最常出现的 5% 的块占据了全部近邻关系的 33.8%;1% 的枢纽块闯入 77.7% 的无关问题的前十名 (Radovanović et al. 2010)。

这类枢纽块的「人缘」与内容无关,只与它在空间中的位置有关:靠近数据分布中心的点,在高维中几乎与所有点都近。在 RAG 中,枢纽块会反复出现在答非所问的检索结果里;如果它恰好含有错误或过时的内容,就会污染大量回答。

注

这些是模型,不是测量。 本章用的是高斯随机向量与幂律谱,用来说明机制。真实嵌入模型的有效维度与枢纽程度需要在自己的语料上测量:计算嵌入协方差的参与率,统计近邻出现次数的偏度,比让结论依赖名义维度可靠得多。

假说 · 尚未验证

作者的假说(尚未验证): 在真实的 RAG 语料中,近邻出现次数最高的 1% 的块,在用户反馈为「答非所问」的回答中出现的比例,显著高于它们在全部回答中出现的比例。什么结果会证明它错:按事先登记的标注规则,两种比例之差的 95% 置信区间包含零,或枢纽块在好评回答中出现得更多。

小结

随机方向在高维中几乎正交,余弦的离散程度按 1/d1/\sqrt{d} 收缩,但语料每扩大十倍,最强干扰块就更强一级,第一名的错误率随语料规模上升。真实嵌入的方差集中在少数方向,768 维可以只相当于三十来维;决定检索精度的是有效维度。高维空间还会自发产生枢纽块:一百维时,1% 的块闯入近八成无关问题的前十名。

参考文献

Ethayarajh, Kawin. 2019. “How Contextual Are Contextualized Word Representations? Comparing the Geometry of BERT, ELMo, and GPT-2 Embeddings.” Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing (EMNLP-IJCNLP), 55–65.
Karpukhin, Vladimir, Barlas Oğuz, Sewon Min, et al. 2020. “Dense Passage Retrieval for Open-Domain Question Answering.” Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 6769–81.
Ledoux, Michel. 2001. The Concentration of Measure Phenomenon. Vol. 89. Mathematical Surveys and Monographs. American Mathematical Society.
Lewis, Patrick, Ethan Perez, Aleksandra Piktus, et al. 2020. “Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks.” Advances in Neural Information Processing Systems 33 (NeurIPS), 9459–74.
Mu, Jiaqi, and Pramod Viswanath. 2018. “All-but-the-Top: Simple and Effective Postprocessing for Word Representations.” International Conference on Learning Representations (ICLR).
Radovanović, Miloš, Alexandros Nanopoulos, and Mirjana Ivanović. 2010. “Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data.” Journal of Machine Learning Research 11: 2487–531.
Vershynin, Roman. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.

Fan, Y. (2026). Retrieval-Augmented Generation Geometry, Reciprocal Rank Fusion and Multi-Agent Error Cascades: High-Dimensional Concentration of Measure, Hybrid Lexical-Dense Retrieval Bounds and Verifier-Gated Fixed Points [检索增强生成几何、倒数秩融合与多智能体误差级联] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090170 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).