5D Library › Retrieval-Augmented Generation Geometry, Reciprocal Rank Fusion and Multi-Agent Error Cascades · 中文

Chapter 1. High-Dimensional Geometry: Concentration of Measure, Effective Dimension and Hub Chunks

Concentration of measure and the cost of corpus size

Calculation

Random directions are nearly orthogonal. The cosine between two independent random vectors on the dd-dimensional unit sphere has mean 0 and standard deviation 1/d1/\sqrt{d} — one of the simplest instances of the concentration of measure (Ledoux 2001; Vershynin 2018). The largest of MM such cosines is about 2ln⁡M/d\sqrt{2\ln M / d}. So if the truly relevant chunk has cosine ss with the question, distractors start to steal first place once 2ln⁡M/d\sqrt{2\ln M/d} approaches ss.

Calculation

# 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.

Part A confirms 1/d1/\sqrt{d}: the standard deviation of random cosines is 0.2524 in 16 dimensions and 0.0320 in 1024. Part B gives the relevant chunk a cosine of 0.30 and races it against MM pure-noise distractors for first place. In this isotropic model dimension does help: at 64 dimensions, 1,000 chunks already put the wrong chunk first with probability 0.7890, while at 768 dimensions even a million chunks do so only 0.0010 of the time. But at every dimension the error rate climbs steadily with MM: at 256 dimensions from 0.0730 (1,000 chunks) to 0.5030 (a million). Each tenfold growth of the corpus raises the strongest distractor’s cosine by a fixed step; the more chunks, the more similar the relevant chunk must be to the question.

Nominal and effective dimension

That conclusion rests on an assumption: that every direction matters equally. Real embeddings are not like that. Ethayarajh found contextual embeddings strongly anisotropic, with cosines between unrelated texts generally positive (Ethayarajh 2019); Mu and Viswanath found that a few dominant directions carry most of the variance (Mu and Viswanath 2018).

Calculation

The participation ratio. If the embedding coordinates have variances λ1,…,λd\lambda_1, \dots, \lambda_d, the effective dimension (participation ratio) is deff=(∑iλi)2∑iλi2,d_{\mathrm{eff}} = \frac{\big(\sum_i \lambda_i\big)^2}{\sum_i \lambda_i^2} , equal to dd when the embedding is isotropic and far smaller when the variance sits in a few directions. The spread of random cosines is set by deffd_{\mathrm{eff}}, not by dd.

Calculation

# 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.

All four spectra have 768 nominal dimensions. When the variance falls off as a power law (exponent a=1.0a = 1.0), only 31.7 effective dimensions remain; at a=1.5a = 1.5, only 5.4. Correspondingly, the spread of cosines between unrelated texts (after centring) rises from 0.0344 to 0.1587 and 0.3494, and the probability of putting the wrong chunk first among a hundred thousand rises from 0.0000 to 0.9875 and 0.9995 — a 768-dimensional embedding behaving like a space of a few dozen dimensions.

The shared direction also makes every raw cosine positive (means of about 0.264 to 0.304), so “a cosine of 0.304” by itself means almost nothing in absolute terms. Subtracting the mean (centring) removes the offset but cannot restore the missing dimensions. Hence the first correction to the outline: retrieval accuracy is governed by the effective dimension, not the nominal one; raising the nominal dimension need not help if the spectrum keeps its shape.

Hubs in high-dimensional space: the distribution of neighbour counts N_k grows right-skewed with dimension; a few chunks appear in very many neighbour lists and many in none.

Hub chunks: popularity by position

Calculation

# 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.

In three dimensions every chunk appears in other chunks’ neighbour lists about equally often (skewness −0.38), and the 1 % most frequent chunks reach a new question’s top ten with probability 9.0 %, about the 9.6 % of chance. In a hundred dimensions the distribution is strongly right-skewed (skewness 4.32): the most “popular” chunk appears in 177 lists, 18.8 % of chunks appear in no list at all, and the most frequent 5 % hold 33.8 % of all neighbour relations; the 1 % of hub chunks intrude on the top ten of 77.7 % of unrelated questions (Radovanović et al. 2010).

A hub’s popularity has nothing to do with its content and everything to do with its position: points near the centre of the data distribution are close to almost everything in high dimensions. In RAG, hub chunks keep turning up in off-target results; if one happens to contain wrong or outdated content, it contaminates many answers.

Note

These are models, not measurements. This chapter uses Gaussian random vectors and power-law spectra to show the mechanisms. The effective dimension and hubness of a real embedding model have to be measured on one’s own corpus: computing the participation ratio of the embedding covariance and the skewness of neighbour counts is far more reliable than reasoning from the nominal dimension.

Hypothesis · not established

The author’s hypothesis (not yet tested): in a real RAG corpus, the 1 % of chunks with the highest neighbour counts appear in answers that users flag as off-target significantly more often than in answers overall. What would show it wrong: under a labelling rule registered in advance, the 95 % confidence interval for the difference between the two shares contains zero, or hub chunks appear more often in well-rated answers.

Summary

Random directions are nearly orthogonal in high dimensions and cosines spread like 1/d1/\sqrt{d}, but every tenfold growth of the corpus strengthens the best distractor by a step, so top-1 errors rise with corpus size. Real embeddings concentrate their variance in a few directions, and 768 dimensions can behave like thirty; retrieval accuracy is governed by the effective dimension. High-dimensional space also produces hub chunks by itself: in a hundred dimensions, 1 % of chunks intrude on nearly eight in ten unrelated questions’ top ten.

References

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).