Meta:On the Theoretical Limitations of Embedding-Based Retrieval

基于嵌入检索的理论极限

问题背景

对于用户查询的向量嵌入问题，需要召回相关文档内容，尽管先前的研究指出了向量嵌入的理论局限性，但人们普遍认为这些困难是由于用户的不切实际的查询请求导致的，而对于那些切实的查询请求，通过更好的训练数据和更大的模型就能克服困难。这篇论文证明了在现实场景中，即便是极其简单的查询，也会遇到局限性，即：证明了对于给定的嵌入维度d，存在无法返回前k个文档组合————无论查询是什么，为了证明这一理论极限适用于任何检索模型或训练数据集，论文作者测试了一种场景：向量本身直接通过测试数据进行优化。这使我们能够通过实验证明嵌入维度如何助力解决检索任务。作者发现，对于每个嵌入维度((d))，都存在一个关键点，超过该点后，文档数量过多，导致嵌入维度无法对所有组合进行编码。随后，我们收集了不同维度d下的这些关键点，并证明这种关系可以通过多项式函数进行经验建模。

总结：虽然先前的一些研究已经指出了向量嵌入的一些理论限制，但通常假设这些困难仅仅来源于不切实际的用户查询问题，或者可以通过更好的训练数据集和更大参数量的模型来客服。这篇论文的动机就是挑战这一假设，并证明即使在现实且简单的查询设置中，这些理论限制也可能出现。

方法

在数学层面上，对于上面提到的问题进行一个证明：

参考论文3.3结论部分，简单的来说，3.3节提到的结论是关于向量嵌入模型表示能力的根本限制。它指出了：

• 存在无法被d维嵌入捕获的检索任务：对于任何固定的嵌入维度d，总会存在一些二进制相关性矩阵（你可以理解为一种用户的检索任务），是无法被d维嵌入模型精确表示的。这意味着，有些检索任务的难度太高，需要更高的嵌入维度才能被识别。

• 高签秩的检索任务更难：检索任务的相关性矩阵如果具有较高的签秩，那么对于嵌入模型来说，他就更难被精确捕获，应为它需要更高的维度。

• 签秩是衡量任务难度的指标：签秩为我们提供了一个衡量检索任务的难度的理论机制。我们可以通过优化自由嵌入表示的梯度下降方法，为矩阵的签秩确定一个上线。

用一个比喻来理解

• 嵌入维度： 就像你拥有的乐高积木的种类和数量
• 检索任务： 就像你想要搭建的各种复杂形状
• 签秩： 就像某个形状的复杂程度，想象你有一个表格，每个格子里只能填+1或-1（正号或负号）。矩阵签秩就是指：你至少需要多少个"简单模式"叠加起来，才能完美复现这个表格。
  • 低签秩：检索任务相对简单，查询和文档之间的相关性模式比较规律
  • 高签秩：检索任务复杂，需要捕获更多细微的语义关系和交互模式

如果你只有有限的乐高积木的种类和数量（就是有限的嵌入维度d），你就无法搭建所有可能的复杂形状（检索任务），某些非常复杂的形状（高签秩的检索任务）需要更多种类的乐高积木（维度d）才能搭建出来。而且，即使你用尽全力去尝试（就是优化嵌入模型），如果种类不够，也还是无法搭建出来某个形状。

核心结论：维度限制是根本性的

即使我们拥有最先进的优化算法、最大的训练数据集、最强的计算资源来训练嵌入模型，如果向量的维度不够高，某些复杂的检索任务就是无法被很好地解决的。

这个结论的重要性在于：

• 这不是工程问题，而是数学定理：不管你怎么优化模型架构或训练策略，维度不足就是一个无法突破的天花板
• 解释了为什么有些检索任务效果不佳：当我们发现某个检索系统表现不好时，可能不是模型设计的问题，而是维度本身就不够
• 为实际应用提供指导：在设计检索系统时，需要根据任务复杂度合理选择嵌入维度，而不是盲目追求模型优化

这也解释了为什么现代大模型的嵌入维度越高（从几百维到几千维甚至上万维），因为更高的维度能够处理更复杂的语义检索任务。

证明

见解析1部分的内容。

总结和实际意义

将所有不等式组合起来，我们就得到了：

$${\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})-1\le {\text{rank}}_{rop}A={\text{rank}}_{rt}A\le {\text{rank}}_{gt}A\le {\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})$$

实际意义：

1. 下限和上限： 这个链式不等式提供了嵌入模型表示能力的一个下限和上限。它告诉我们，要精确捕获相关性矩阵 $A$ 所定义的检索任务，至少需要 ${\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})-1$ 维的嵌入，并且最多只需要 ${\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})$ 维。
2. 嵌入维度 $d$ 的限制： 最重要的是，如果一个检索任务的“签秩”很高，那么它就无法被低维度的嵌入模型精确表示。这意味着，对于任何固定的嵌入维度 $d$，总存在一些任务，其内在复杂性（签秩）超出了 $d$ 维嵌入的表示能力，导致模型无法精确解决这些任务。
3. 解释模型失败的原因： 这解释了为什么在 LIMIT 这种数据集上，即使是先进的嵌入模型也会失败。不是因为模型不够大，或者训练数据不够好，而是因为任务本身的内在复杂性（高签秩）超出了单向量嵌入模型的理论表示能力。
4. 对未来研究的指导： 这个结论提示研究者，要解决更复杂的检索任务（特别是涉及任意组合或推理的任务），可能需要超越现有单向量嵌入范式的新方法，例如多向量模型或交叉编码器。

结果

• 嵌入模型存在理论上的限制：论文通过引入符号秩的概念，证明了在任何嵌入维度d下，都存在一些二进制相关性矩阵，这些矩阵无法通过d维嵌入来精确捕获。这就意味着检索任务中，如果用户的查询相关性矩阵的符号秩较高，那么使用嵌入模型精确捕获这些关系就越困难，需要更高的嵌入维度。
• 这些理论上的限制在实际情况中也会出现：论文作者发现，即使在最佳情况下，当文档数量超过某个临界值时（可以看原文的公式，这里只说结论），固定维度的嵌入也无法完全表示所有的top-k组合。这个临界值与嵌入维度呈多项式函数关系。
• 现有最先进的嵌入模型无法解决简单任务：论文中提到了LIMIT的简单自然语言数据集，这证实了理论上的限制，这表明，目前的单向量嵌入模型在处理需要返回不断增加的top-k相关文档组合的任务时，存在根本性的局限性，关于这一点，看过FusionANNS论文讲解章节的可以意识到，尽管FusionANNS架构在处理大批量召回的时候会有一个控制模型去检测是否需要继续进行召回，但是对于某些高秩的问题，也就是离谱的复杂用户问题，还是可能存在需要召回大批量数据的情况，这就说明，FusionANNS也是存在局限性的。
• 替代方案：论文还讨论了替代嵌入模型的方法，例如交叉编码器和多向量模型，他们发现，像 Gemini-2.5-Pro 这样的长上下文重排序器可以完美解决 LIMIT 小规模数据集上的任务，这表明这些模型不受与嵌入维度相关的相同限制。此外，稀疏模型由于其高维度也能够避免这些问题。

代码实践

论文作者已经开源了数据集和代码https://github.com/google-deepmind/limit/tree/main，我们在这里带着大家一步步的去看到嵌入模型的limit。 点击这里进入实践章节。查看代码实现

解析1

我们首先回顾一下Meta论文 3.3 节的最终结论：

$${\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})-1\le {\text{rank}}_{rop}A={\text{rank}}_{rt}A\le {\text{rank}}_{gt}A\le {\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})$$

这个式子包含了几个核心概念和它们之间的关系。让我们一个一个地来理解它们。

1. 相关性矩阵 $A\in \{0,1{\}}^{m\times n}$

• 含义： 这是一个二进制矩阵，表示查询和文档之间的真实相关性。
  • $m$ 是查询的数量。
  • $n$ 是文档的数量。
  • $A_{ij}=1$ 表示查询 $i$ 和文档 $j$ 是相关的。
  • $A_{ij}=0$ 表示查询 $i$ 和文档 $j$ 是不相关的。
• 例子： 假设我们有 2 个查询 ($Q_1,Q_2$) 和 3 个文档 ($D_1,D_2,D_3$)。
  • $Q_1$ 喜欢 $D_1$ 和 $D_2$，不喜欢 $D_3$。
  • $Q_2$ 喜欢 $D_2$ 和 $D_3$，不喜欢 $D_1$。 那么，相关性矩阵 $A$ 就是：
  $$A=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\end{array}\right)$$（第一行对应 $Q_1$，第二行对应 $Q_2$；第一列对应 $D_1$，第二列对应 $D_2$，第三列对应 $D_3$）

2. 得分矩阵 $B\in {\mathbb{R}}^{m\times n}$

• 含义： 这是一个实数矩阵，表示嵌入模型对查询和文档相关性的“预测得分”。通常，这个得分是通过查询向量 $u_i$ 和文档向量 $v_j$ 的点积计算出来的，即 $B_{ij}=u_i^T{v}_j$。
• 秩 (Rank)： 矩阵的秩是其线性独立行或列的最大数量。在嵌入模型的语境中，如果 $B$ 是由 $u_i\in {\mathbb{R}}^d$ 和 $v_j\in {\mathbb{R}}^d$ 生成的，那么 $B$ 的秩最多是 $d$。所以，矩阵 $B$ 的秩直接反映了嵌入模型的维度 $d$。我们的目标是找到一个足够小的 $d$（即 $B$ 的秩），使得 $B$ 能够正确反映 $A$ 的相关性。

3. 三种“秩”的概念（衡量模型正确表示 $A$ 的能力）

这些秩衡量的是最低需要多少维度（即 $B$ 的最小秩）才能让得分矩阵 $B$ 正确地反映相关性矩阵 $A$ 的信息。

• 行级顺序保持秩 (rank${}_{rop}$ A)

  • 定义： 最小的 $d$，使得存在一个秩为 $d$ 的矩阵 $B$，对于所有查询 $i$、文档 $j$ 和文档 $k$，如果 $A_{ij}>A_{ik}$（即 $D_j$ 相关，$D_k$ 不相关），那么 $B_{ij}>B_{ik}$（即模型给 $D_j$ 的得分高于 $D_k$）。
  • 例子： 对于 $Q_1$，我们知道 $A_{11}=1,A_{13}=0$，所以 $A_{11}>A_{13}$。那么模型必须满足 $B_{11}>B_{13}$。 对于 $Q_2$，我们知道 $A_{22}=1,A_{21}=0$，所以 $A_{22}>A_{21}$。那么模型必须满足 $B_{22}>B_{21}$。

• 行级阈值秩 (rank${}_{rt}$ A)

  • 定义： 最小的 $d$，使得存在一个秩为 $d$ 的矩阵 $B$，并且对于每个查询 $i$，存在一个特定的阈值 $t_i$，使得：
    • 如果 $A_{ij}=1$ (文档相关)，那么 $B_{ij}>t_i$ (得分高于阈值)。
    • 如果 $A_{ij}=0$ (文档不相关)，那么 $B_{ij}<t_i$ (得分低于阈值)。
  • 例子： 对于 $Q_1$，我们找到一个阈值 $t_1$，使得 $B_{11}>t_1$, $B_{12}>t_1$，而 $B_{13}<t_1$。 对于 $Q_2$，我们找到一个阈值 $t_2$，使得 $B_{22}>t_2$, $B_{23}>t_2$，而 $B_{21}<t_2$。 注意： 每个查询可以有自己的阈值。

• 全局阈值秩 (rank${}_{gt}$ A)

  • 定义： 最小的 $d$，使得存在一个秩为 $d$ 的矩阵 $B$，并且存在一个全局的阈值 $t$（对所有查询都一样），使得：
    • 如果 $A_{ij}=1$，那么 $B_{ij}>t$。
    • 如果 $A_{ij}=0$，那么 $B_{ij}<t$。
  • 例子： 我们找到一个唯一的阈值 $t$，使得所有相关的 $B_{ij}$ 都大于 $t$，所有不相关的 $B_{ij}$ 都小于 $t$。这个要求比行级阈值秩更严格。

4. 符号矩阵 $2A-{\mathbf{1}}_{m\times n}$ 和 签秩 (rank${}_{+}$)

• 符号矩阵 $M=2A-{\mathbf{1}}_{m\times n}$：

  • 含义： 这是一个将二进制相关性矩阵 $A$ 转换成一个只包含 $-1$ 和 $1$ 的矩阵。
    • 如果 $A_{ij}=1$ (相关)，那么 $M_{ij}=2\times 1-1=1$。
    • 如果 $A_{ij}=0$ (不相关)，那么 $M_{ij}=2\times 0-1=-1$。
  • 例子： 使用上面的 $A$ 矩阵：$$M=\left(\begin{array}{ccc}1& 1& -1\\ -1& 1& 1\end{array}\right)$$

• 签秩 (rank${}_{+}M$)

  • 定义： 最小的 $d$，使得存在一个秩为 $d$ 的实数矩阵 $B$，$B$ 的每个元素的符号都与 $M$ 的对应元素的符号相同。
    • 如果 $M_{ij}=1$，那么 $B_{ij}$ 必须是正数。
    • 如果 $M_{ij}=-1$，那么 $B_{ij}$ 必须是负数。
  • 重要性： 签秩是一个纯数学概念，用于衡量一个矩阵的“符号模式”的复杂性。如果一个 $\{-1,1\}$ 矩阵的签秩很高，这意味着它的符号模式非常复杂，需要一个高维度的线性模型才能复制这种模式。

证明的详细步骤（命题 1 和 命题 2）

现在，我们来一步步拆解证明过程。

命题 1：对于一个二进制矩阵 $A\in \{0,1{\}}^{m\times n}$，我们有 ${\text{rank}}_{rop}A={\text{rank}}_{rt}A$。

• 证明目标： 证明这两种“秩”是等价的，即如果一个 $d$ 维嵌入能满足一种条件，它也能满足另一种条件，反之亦然。

• 1. 证明 ${\text{rank}}_{rop}A\le {\text{rank}}_{rt}A$ (即：如果能做到阈值分离，就能做到顺序保持)

  • 在解释这个证明之前，先介绍几个关键名词和符号：
    • 二进制矩阵 $A$：$A\in \{0,1{\}}^{m\times n}$ 是一个 $m$ 行 $n$ 列的矩阵，通常用于表示检索任务中的相关性矩阵，其中 $m$ 表示查询的数量，$n$ 表示文档的数量。$A_{ij}$ 表示第 $i$ 个查询与第 $j$ 个文档是否相关，$A_{ij}=1$ 表示相关，$A_{ij}=0$ 表示不相关。
    • ${\text{rank}}_{rop}A$：表示实现行级顺序保持所需的矩阵 $A$ 的最小秩。行级顺序保持指的是，如果对于某个查询 $i$，文档 $j$ 比文档 $k$ 与该查询更相关（即 $A_{ij}>A_{ik}$），那么对应表示矩阵中的得分也应满足相应的顺序关系。
    • ${\text{rank}}_{rt}A$：表示实现行级阈值分离所需的矩阵 $A$ 的最小秩。行级阈值分离指的是，对于每个查询 $i$，存在一个阈值 $t_i$，可以根据这个阈值区分相关文档和不相关文档。
    • 矩阵的秩：矩阵的秩是矩阵中线性无关的行或列的最大数量，它反映了矩阵所包含的有效信息的维度。
    • 矩阵 $B$：一个用于表示查询 - 文档相关性得分的矩阵，其秩为 $d$。
    • 行级阈值 $\{t_i{\}}_{i=1}^m$：一组阈值，每个查询 $i$ 对应一个阈值 $t_i$，用于区分该查询下的相关文档和不相关文档。
  • 假设： 假设存在一个秩为 $d$ 的矩阵 $B$ 和一组行级阈值 $\{t_i{\}}_{i=1}^m$，使得 $B$ 满足行级阈值条件（即如果 $A_{ij}=1$ 表示第 $i$ 个查询与第 $j$ 个文档相关，则 $B_{ij}>t_i$；如果 $A_{ij}=0$ 表示第 $i$ 个查询与第 $j$ 个文档不相关，则 $B_{ij}<t_i$）。
  • 推导： 我们需要证明 $B$ 也满足行级顺序保持条件。
    • 考虑任意查询 $i$，以及文档 $j$ 和 $k$。这里的查询 $i$ 可以理解为一次检索请求，文档 $j$ 和 $k$ 是检索结果中的两个文档。
    • 如果 $A_{ij}>A_{ik}$，因为 $A$ 是二进制矩阵，元素只能取 0 或 1，所以这意味着 $A_{ij}=1$ （第 $i$ 个查询与第 $j$ 个文档相关）而 $A_{ik}=0$ （第 $i$ 个查询与第 $k$ 个文档不相关）。
    • 根据行级阈值条件，由于 $A_{ij}=1$ 则 $B_{ij}>t_i$，$A_{ik}=0$ 则 $B_{ik}<t_i$。也就是说，相关文档 $j$ 在矩阵 $B$ 中的得分大于阈值 $t_i$，不相关文档 $k$ 在矩阵 $B$ 中的得分小于阈值 $t_i$。
    • 因此，由 $B_{ij}>t_i$ 和 $B_{ik}<t_i$，可以直接得出 $B_{ij}>B_{ik}$。这表明在矩阵 $B$ 中，与查询 $i$ 更相关的文档 $j$ 的得分高于文档 $k$ 的得分。
  • 结论： 这正是行级顺序保持的条件，即当查询 $i$ 下文档 $j$ 比文档 $k$ 更相关时，矩阵 $B$ 中对应文档 $j$ 的得分高于文档 $k$ 的得分。所以，如果 $B$ 能满足行级阈值条件，它也能满足行级顺序保持条件。这意味着实现行级阈值分离所需的最小秩（${\text{rank}}_{rt}A$）至少不小于实现行级顺序保持所需的最小秩（${\text{rank}}_{rop}A$）。

• 2. 证明 ${\text{rank}}_{rt}A\le {\text{rank}}_{rop}A$ (即：如果能做到顺序保持，就能做到阈值分离)

  • 假设： 假设存在一个秩为 $d$ 的矩阵 $B$ 满足行级顺序保持条件（即如果 $A_{ij}>A_{ik}$ 则 $B_{ij}>B_{ik}$）。
  • 推导： 我们需要为每个查询 $i$ 找到一个阈值 $t_i$。
    • 对于每个查询 $i$，将文档分成两组：
      • $U_i=\{B_{ij}\mid A_{ij}=1\}$ (相关文档的得分集合)
      • $L_i=\{B_{ij}\mid A_{ij}=0\}$ (不相关文档的得分集合)
    • 根据行级顺序保持条件，对于任何 $B_{ij}\in U_i$ 和 $B_{ik}\in L_i$，我们总是有 $B_{ij}>B_{ik}$。这意味着相关文档的最低得分总是高于不相关文档的最高得分。
    • 因此，我们总是可以在 $max(L_i)$ 和 $min(U_i)$ 之间找到一个阈值 $t_i$。例如，可以取 $t_i=(max(L_i)+min(U_i))/2$。
  • 结论： 这样我们就为每个查询 $i$ 找到了一个阈值 $t_i$，使得 $B$ 满足行级阈值条件。这意味着实现行级顺序保持所需的最小秩（${\text{rank}}_{rop}A$）至少不小于实现行级阈值分离所需的最小秩（${\text{rank}}_{rt}A$）。

• 综合结论： 由于 ${\text{rank}}_{rop}A\le {\text{rank}}_{rt}A$ 和 ${\text{rank}}_{rt}A\le {\text{rank}}_{rop}A$ 同时成立，所以 ${\text{rank}}_{rop}A={\text{rank}}_{rt}A$。

命题 2：对于一个二进制矩阵 $A\in \{0,1{\}}^{m\times n}$：

$${\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})-1\le {\text{rank}}_{rop}A={\text{rank}}_{rt}A\le {\text{rank}}_{gt}A\le {\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})$$

这个命题可以分解成三个不等式来证明：

• 1. ${\text{rank}}_{rt}A\le {\text{rank}}_{gt}A$ (即：全局阈值分离比行级阈值分离更难，所以实现它所需的维度不会更少)

  • 证明思路： 这部分很简单，根据定义即可。
  • 假设： 假设存在一个秩为 $d$ 的矩阵 $B$ 和一个全局阈值 $t$，满足全局阈值条件。
  • 推导： 这个全局阈值 $t$ 自然可以作为每个查询的行级阈值 $t_i$。因此，如果能满足全局阈值条件，就能满足行级阈值条件。
  • 结论： 这意味着实现全局阈值分离所需的最小秩（${\text{rank}}_{gt}A$）至少不小于实现行级阈值分离所需的最小秩（${\text{rank}}_{rt}A$）。

• 2. ${\text{rank}}_{gt}A\le {\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})$ (即：符号模式能被低维表示，就能实现全局阈值分离)

  • 证明思路： 如果我们能找到一个低秩矩阵 $B^{\prime }$ 来匹配符号矩阵 $M$ 的符号，那么这个 $B^{\prime }$ 也可以用来实现全局阈值分离。
  • 令 $M=2A-{\mathbf{1}}_{m\times n}$。
  • 假设： 假设 ${\text{rank}}_{+}M=d_s$。这意味着存在一个秩为 $d_s$ 的矩阵 $B^{\prime }$，其符号与 $M$ 的符号相同。
    • 即，如果 $M_{ij}=1$，则 $B_{ij}^{\prime }>0$。
    • 如果 $M_{ij}=-1$，则 $B_{ij}^{\prime }<0$。
  • 推导： 我们需要证明这个 $B^{\prime }$ 可以实现全局阈值分离。
    • 通过 $M$ 的定义，我们知道 $M_{ij}=1⟺A_{ij}=1$。
    • 同时，通过 $B^{\prime }$ 的性质，我们知道 $B_{ij}^{\prime }>0⟺M_{ij}=1$。
    • 结合起来，我们得到 $B_{ij}^{\prime }>0⟺A_{ij}=1$。
    • 这意味着我们可以使用全局阈值 $t=0$。如果 $A_{ij}=1$，则 $B_{ij}^{\prime }>0$；如果 $A_{ij}=0$，则 $B_{ij}^{\prime }<0$。
  • 结论： 因此，矩阵 $B^{\prime }$ 可以实现全局阈值分离，并且它的秩就是 $d_s$。所以，${\text{rank}}_{gt}A\le d_s={\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})$。

• 3. ${\text{rank}}_{+}(2A-{\mathbf{1}}_{m\times n})-1\le {\text{rank}}_{rt}A$ (即：如果能实现行级阈值分离，那么符号模式的维度不会太高)

  • 证明思路： 这是最复杂的一步。我们从满足行级阈值条件的低秩矩阵 $B$ 出发，构造一个新矩阵 $B^{\ast }$，并证明 $B^{\ast }$ 的符号与 $M$ 的符号相同，且 $B^{\ast }$ 的秩只比 $B$ 的秩大 1。

  • 令 $M=2A-{\mathbf{1}}_{m\times n}$。

  • 假设： 假设 ${\text{rank}}_{rt}A=d_r$。这意味着存在一个秩为 $d_r$ 的矩阵 $B$ 和一组行级阈值 $\{t_i{\}}_{i=1}^m$，使得 $B$ 满足行级阈值条件。

    • 即，如果 $A_{ij}=1$ 则 $B_{ij}>t_i$。
    • 如果 $A_{ij}=0$ 则 $B_{ij}<t_i$。

  • 构造新矩阵 $B^{\ast }$： 考虑矩阵 $B^{\ast }=B-\tau {\mathbf{1}}_{m\times n}$，其中 $\tau$ 是一个列向量，其第 $i$ 个元素是 $t_i$。

    • 注意：这里原文写的是 $B-t{\mathbf{1}}^T$，如果 $t$ 是一个列向量，${\mathbf{1}}^T$ 是行向量，那么 $t{\mathbf{1}}^T$ 会生成一个秩为 1 的矩阵，其第 $i$ 行的所有元素都是 $t_i$。这正是我们想要的。

  • 推导 $B^{\ast }$ 的符号：

    • 情况一： 如果 $A_{ij}=1$。
      • 根据行级阈值条件，$B_{ij}>t_i$。
      • 所以 $B_{ij}-t_i>0$。
      • 同时，$M_{ij}=2A_{ij}-1=2(1)-1=1$。
      • 所以，当 $A_{ij}=1$ 时，$B_{ij}^{\ast }>0$ 且 $M_{ij}=1$，它们的符号相同。
    • 情况二： 如果 $A_{ij}=0$。
      • 根据行级阈值条件，$B_{ij}<t_i$。
      • 所以 $B_{ij}-t_i<0$。
      • 同时，$M_{ij}=2A_{ij}-1=2(0)-1=-1$。
      • 所以，当 $A_{ij}=0$ 时，$B_{ij}^{\ast }<0$ 且 $M_{ij}=-1$，它们的符号相同。
    • 结论： 矩阵 $B^{\ast }$ 的所有元素的符号都与 $M$ 的对应元素的符号相同。

  • 推导 $B^{\ast }$ 的秩：

    • 我们知道 $\text{rank}(B-\tau {\mathbf{1}}_{m\times n})$ 是 $B$ 的秩和秩为 1 的矩阵 $\tau {\mathbf{1}}_{m\times n}$ 的秩的和，或者更小（因为秩具有次可加性：$\text{rank}(X+Y)\le \text{rank}(X)+\text{rank}(Y)$）。
    • 具体来说，$\text{rank}(B-\tau {\mathbf{1}}_{m\times n})\le \text{rank}(B)+\text{rank}(\tau {\mathbf{1}}_{m\times n})$。
    • $\text{rank}(B)=d_r$ (根据假设)。
    • $\text{rank}(\tau {\mathbf{1}}_{m\times n})=1$ (这是一个由一个向量乘以一个全 1 向量的转置得到的矩阵，所以秩为 1)。
    • 因此，$\text{rank}(B^{\ast })\le d_r+1$。
    • 由于 $B^{\ast }$ 的符号与 $M$ 的符号相同，根据签秩的定义，${\text{rank}}_{+}M\le \text{rank}(B^{\ast })$。
    • 所以，${\text{rank}}_{+}M\le d_r+1$。
    • 重新整理得到 ${\text{rank}}_{+}M-1\le d_r={\text{rank}}_{rt}A$。

Reference

1. On the Theoretical Limitations of Embedding-Based Retrieval