因子分解机与 LLM 路由：从 FM 理论到 MF 路由器

上一篇我们走完了 RouteLLM 的 MF Router 从训练到部署的完整流程。本篇向上追溯一层：RouteLLM 的 Matrix Factorization 路由器，本质上是 Rendle（2010）提出的 Factorization Machines（FM） 的一个特殊情况。理解 FM 的完整理论框架，不仅能帮助我们更深入地理解 MF 路由器为什么有效，还能看清一条明确的扩展路径——如何通过添加更多特征维度来增强路由能力。

1 问题：极端稀疏性下的预测

在很多真实场景中，数据被表示为高维特征向量，其中几乎所有元素都是零。当我们用 one-hot 编码处理大型分类变量（用户、物品、词语等）时，就会产生这种极端稀疏性。

假设有 10,000 个用户和 5,000 部电影。一个评分事件的特征向量需要 15,000 维（用户 one-hot + 电影 one-hot），但只有 2 维是非零的——99.987% 是零。更棘手的是：你想建模 Alice 和 Star Trek 之间的交互。如果 Alice 从未评过 Star Trek，传统模型只能看到零证据然后放弃。FM 不会。

形式化地，我们要学习 $\hat{y}: \mathbb{R}^n \to T$，将特征向量 $\mathbf{x} \in \mathbb{R}^n$ 映射到目标域 $T$（回归：$T = \mathbb{R}$；分类：$T = \{+,-\}$）。特征向量 $\mathbf{x}$ 高度稀疏：非零元素的平均数量 $\bar{m}_D \ll n$。

1.1 贯穿全文的示例：电影评分

Rendle 在论文中使用电影评分系统作为贯穿示例。用户 $U = \{\text{Alice}, \text{Bob}, \text{Charlie}\}$，电影 $I = \{\text{Titanic}, \text{Notting Hill}, \text{Star Wars}, \text{Star Trek}\}$：

用户	电影	评分
Alice	Titanic	5
Alice	Notting Hill	3
Alice	Star Wars	1
Bob	Star Wars	4
Bob	Star Trek	5
Charlie	Titanic	1
Charlie	Star Wars	5

每条记录被转换为包含多组 one-hot 特征的稀疏向量。总维度约 18，但每行仅约 6 个非零值。

核心问题：我们能预测 Alice 会如何评价 Star Trek 吗？训练数据中 $(x_\text{Alice}, x_\text{StarTrek})$ 的共现次数为零。传统模型（如带交互项的 SVM）会估计 $w_{\text{Alice},\text{StarTrek}} = 0$。FM 可以做得更好。

2 FM 模型方程

2.1 完整方程（度 d=2）

$\hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle \, x_i \, x_j$

参数：$w_0 \in \mathbb{R}$（全局偏置），$\mathbf{w} \in \mathbb{R}^n$（线性权重），$\mathbf{V} \in \mathbb{R}^{n \times k}$（因子矩阵），其中 $k$ 是因子分解维度。

等价矩阵形式：

$\hat{y}(\mathbf{x}) = w_0 + \mathbf{w}^T\mathbf{x} + \frac{1}{2}\mathbf{x}^T \tilde{\mathbf{W}}\, \mathbf{x}$

其中 $\tilde{\mathbf{W}} = \mathbf{V}\mathbf{V}^T - \text{diag}(\mathbf{V}\mathbf{V}^T)$ 是低秩因子化交互矩阵，对角线置零以排除自交互。

2.2 三个项的含义

参数	形状	含义	示例
$w_0$	标量	全局偏置/截距	”电影平均评分 = 3.5”
$w_i$	$\mathbb{R}^n$	一阶权重：特征 $i$ 单独对预测的影响	$w_\text{Alice} = +0.3$
$\mathbf{v}_i$	$\mathbb{R}^k$（$\mathbf{V}$ 的第 $i$ 行）	特征 $i$ 的隐因子向量	$\mathbf{v}_\text{Alice} = [0.8, -0.3, 0.1]$
$\langle \mathbf{v}_i, \mathbf{v}_j \rangle$	标量（派生）	特征 $i$ 和 $j$ 的交互强度	$\langle \mathbf{v}_\text{Alice}, \mathbf{v}_\text{SW} \rangle = -1.2$

关键创新：因子化的交互。传统方式为每对 $(i,j)$ 学一个独立参数 $w_{ij}$，共 $n^2/2$ 个参数。FM 方式将 $\hat{w}_{ij} = \langle \mathbf{v}_i, \mathbf{v}_j \rangle$ 因子化，只需 $n \cdot k$ 个参数。当 $k \ll n$ 时，参数量大幅减少且泛化更好。

2.3 超参数 $k$

$k$ 是因子分解维度，控制着表达能力与泛化之间的权衡。对于任意正定交互矩阵 $\mathbf{W}$，只要 $k$ 足够大，就存在 $\mathbf{V}$ 使得 $\mathbf{W} = \mathbf{V}\mathbf{V}^T$。但在稀疏场景下，小的 $k$（通常 8–64）泛化能力更好，因为它迫使模型发现共享的隐结构。

3 为什么因子分解有效——Alice 与 Star Trek

这是 Rendle 论文中最重要的洞察。让我们逐步追踪推理链：

问题：Alice 与 Star Trek 之间的交互 $\hat{w}_{\text{Alice},\text{ST}}$ 是什么？训练数据中两者从未共现，直接模型会设 $w_{\text{Alice},\text{ST}} = 0$。

FM 通过因子分解 $\hat{w}_{\text{Alice},\text{ST}} = \langle \mathbf{v}_\text{Alice}, \mathbf{v}_\text{ST} \rangle$，利用间接证据推断：

1. Bob 和 Charlie 都喜欢 Star Wars：训练迫使 $\mathbf{v}_B$ 和 $\mathbf{v}_C$ 以相似方式与 $\mathbf{v}_\text{SW}$ 对齐。
2. Alice 与 Charlie 对 Titanic 看法相反：Alice 给 5 分，Charlie 给 1 分，所以 $\mathbf{v}_A$ 和 $\mathbf{v}_C$ 在浪漫维度上不同。
3. Star Trek ≈ Star Wars（从 Bob 视角）：Bob 对两部都给高分（4 和 5），所以 $\mathbf{v}_\text{ST}$ 与 $\mathbf{v}_\text{SW}$ 相似。
4. Alice 不喜欢 Star Wars（评分 1），加上 $\mathbf{v}_\text{ST} \approx \mathbf{v}_\text{SW}$，得出 $\langle \mathbf{v}_A, \mathbf{v}_\text{ST} \rangle \approx$ 低值 → 预测 Alice 会给 Star Trek 低评分。

FM 不需要每对 (用户, 物品) 的直接证据。通过将交互因子化为隐向量，信息通过共享因子传播。如果 A 与 X 有交互，B 与 X 和 Y 都有交互，那么 A 的隐向量就间接携带了关于 Y 的信息。这就是 FM 在稀疏场景下仍然有效而 SVM 等模型失败的原因。

4 O(kn) 计算技巧

交互项的朴素计算需要 $O(kn^2)$——遍历所有 $\binom{n}{2}$ 对。Rendle 展示了一个优美的代数恒等式，将其降到 $O(kn)$。

4.1 推导

第一步：将 $i < j$ 的求和扩展为全量求和再减去对角项：

$\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j = \frac{1}{2} \left( \sum_{i=1}^{n} \sum_{j=1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j - \sum_{i=1}^{n} \langle \mathbf{v}_i, \mathbf{v}_i \rangle x_i^2 \right)$

第二步：展开点积，对每个因子维度 $f$ 分别处理：

$= \frac{1}{2}\left( \sum_{i}\sum_{j}\sum_{f} v_{i,f} v_{j,f} x_i x_j - \sum_{i}\sum_{f} v_{i,f}^2 x_i^2 \right)$

第三步（关键）：双重求和可分离为单重求和的乘积：

$\sum_{i}\sum_{j} v_{i,f} v_{j,f} x_i x_j = \left(\sum_{i} v_{i,f} x_i\right)^2$

因为 $v_{i,f} x_i$ 只依赖 $i$，$v_{j,f} x_j$ 只依赖 $j$。

最终结果：

$\boxed{\text{交互项} = \frac{1}{2}\sum_{f=1}^{k}\left[\left(\sum_{i=1}^{n} v_{i,f} x_i\right)^2 - \sum_{i=1}^{n} v_{i,f}^2 x_i^2\right]}$

复杂度从 $O(kn^2)$ 降到 $O(kn)$。在稀疏场景下，只需对非零 $x_i$ 计算，实际复杂度 $O(k\bar{m}_D)$。

用矩阵语言表达：定义 $\mathbf{s} = \mathbf{V}^T\mathbf{x} \in \mathbb{R}^k$，$\mathbf{r} = (\mathbf{V} \odot \mathbf{V})^T(\mathbf{x} \odot \mathbf{x}) \in \mathbb{R}^k$，则

$\text{交互项} = \frac{1}{2}(\|\mathbf{s}\|^2 - \mathbf{1}^T\mathbf{r})$

几何直觉：对每个隐维度 $f$，计算加权和 $s_f = \sum_i v_{i,f} x_i$。$s_f^2$ 包含所有成对乘积（包括自交互），减去自交互 $\sum_i v_{i,f}^2 x_i^2$ 就得到纯交叉交互。这和 $(a+b+c)^2 = a^2 + b^2 + c^2 + 2(ab+ac+bc)$ 是同一个思路。

4.2 一个具体计算例子

用 $k=2$ 计算 Alice 评价 Titanic 的 FM 预测值。假设训练后参数为：

变量	$w_i$	$v_{i,1}$	$v_{i,2}$
Alice	+0.3	0.8	1.2
Titanic	+0.5	0.9	1.0

$w_0 = 3.5$，仅 $x_\text{Alice} = 1$, $x_\text{Titanic} = 1$ 非零。

线性部分：$w_0 + w_A + w_{TI} = 3.5 + 0.3 + 0.5 = 4.3$

交互部分（使用高效公式）：

• $f=1$: $s_1 = 0.8 + 0.9 = 1.7$, $s_1^2 = 2.89$, 自交互 $= 0.64 + 0.81 = 1.45$
• $f=2$: $s_2 = 1.2 + 1.0 = 2.2$, $s_2^2 = 4.84$, 自交互 $= 1.44 + 1.00 = 2.44$

交互项 $= \frac{1}{2}[(2.89 - 1.45) + (4.84 - 2.44)] = \frac{1}{2}[1.44 + 2.40] = 1.92$

验证：$\langle \mathbf{v}_A, \mathbf{v}_{TI}\rangle = 0.8 \times 0.9 + 1.2 \times 1.0 = 0.72 + 1.20 = 1.92$ ✓

$\hat{y} = 4.3 + 1.92 = 6.22$，截断为评分上限 5。

5 梯度与训练

5.1 FM 的梯度

$\frac{\partial}{\partial \theta}\hat{y}(\mathbf{x}) = \begin{cases} 1, & \text{if } \theta = w_0 \\ x_i, & \text{if } \theta = w_i \\ x_i \sum_{j=1}^{n} v_{j,f} x_j - v_{i,f} x_i^2, & \text{if } \theta = v_{i,f} \end{cases}$

关键观察：$v_{i,f}$ 的梯度中，求和项 $\sum_{j} v_{j,f} x_j$ 与 $i$ 无关，且在前向传播时已经算过（就是 $s_f$）。因此每个梯度元素的计算成本是 $O(1)$，完整更新成本是 $O(kn)$，或稀疏场景下 $O(k\bar{m}_D)$。

矩阵形式：

$\frac{\partial \hat{y}}{\partial \mathbf{V}} = \mathbf{x}\,\mathbf{s}^T - (\mathbf{x}\odot\mathbf{x})\cdot\mathbf{V}$

其中 $\mathbf{s} = \mathbf{V}^T\mathbf{x}$ 是前向传播时缓存的向量。

5.2 SGD 训练流程

对每个训练样本 $(\mathbf{x}, y)$：

1. 前向传播：在 $O(k\bar{m}_D)$ 内计算 $\hat{y}(\mathbf{x})$，缓存 $s_f = \sum_i v_{i,f} x_i$
2. 计算损失（回归用 MSE，分类用 logit/hinge loss）
3. 反向传播：对每个非零 $x_i$，利用缓存的 $s_f$ 更新 $w_i$ 和所有 $v_{i,f}$
4. 应用 L2 正则化：$\theta \leftarrow \theta - \eta(\nabla_\theta L + \lambda \theta)$

每个样本的全部操作都是 $O(k\bar{m}_D)$——与计算预测值本身的复杂度相同。

6 FM vs SVM

多项式 SVM（度 $d=2$）和 FM 都建模了所有成对交互，区别在于如何参数化交互权重：

属性	多项式 SVM	FM
$(i,j)$ 的交互权重	$w_{i,j}$——独立自由参数	$\langle \mathbf{v}_i, \mathbf{v}_j \rangle$——因子化
交互参数数量	$n(n-1)/2$	$n \cdot k$
估计要求	需要直接的 $(i,j)$ 共现	间接证据即可
稀疏场景下	未观测对 → $w_{i,j} = 0$	能泛化到未观测对
优化方式	对偶形式（需支持向量）	原始形式（直接 SGD）
预测时间	取决于支持向量数量	$O(kn)$——固定

在 Netflix 数据（1 亿+评分）上，SVM 在 $k \approx 20$ 后开始退化（过拟合），而 FM 继续改善。在 $k = 128$ 时，FM 的 RMSE 约 0.906 vs SVM 约 0.981。

7 FM 统一了 MF、SVD++、PITF、FPMC

Rendle 的关键贡献之一：FM 能够模拟许多专用模型，只需选择正确的特征向量。

7.1 MF 是只有两组 one-hot 特征的 FM

如果特征向量 $\mathbf{x}$ 只包含用户 one-hot + 物品 one-hot（仅 2 个非零元素）：

$n = |U \cup I|, \quad x_j = \begin{cases} 1 & \text{if } j = u \text{ or } j = i \\ 0 & \text{otherwise}\end{cases}$

代入 FM 方程，线性项只剩 $w_u + w_i$，交互项只剩 $\langle \mathbf{v}_u, \mathbf{v}_i \rangle$：

$\hat{y}(\mathbf{x}) = w_0 + w_u + w_i + \langle \mathbf{v}_u, \mathbf{v}_i \rangle$

这恰好就是带偏置的标准 MF 模型：全局偏置 + 用户偏置 + 物品偏置 + 用户-物品隐交互。

同理，添加不同的特征组可以模拟：

• SVD++：加入用户隐式反馈特征
• PITF：加入标签 one-hot
• FPMC：加入购物篮特征

FM 不是”另一个模型”，它是一个统一框架。你不需要为每个任务推导新模型——只需改变特征向量。这正是 FM 适合扩展 LLM 路由器的原因。

8 RouteLLM MF 路由器：FM 视角

现在回到 LLM 路由。上一篇详细讲过 MF Router 的实现，这里从 FM 理论角度重新审视。

8.1 评分函数回顾

RouteLLM MF 路由器定义了隐评分函数：

$\delta(M, q) = \mathbf{w}_2^T \left(\mathbf{v}_m \odot \left(\mathbf{W}_1^T \mathbf{v}_q + \mathbf{b}\right)\right)$

其中 $\mathbf{v}_m \in \mathbb{R}^{d_m}$ 是可学习的模型嵌入，$\mathbf{v}_q \in \mathbb{R}^{1536}$ 是查询嵌入（来自 text-embedding-3-small），$\mathbf{W}_1$ 是投影矩阵，$\mathbf{w}_2$ 是输出权重，$\odot$ 是 Hadamard 积。

胜率通过评分差值计算：$P_\theta(\text{win}_s \mid q) = \sigma(\delta(M_s, q) - \delta(M_w, q))$。

8.2 逐层解读

查询投影：$\mathbf{h}_q = \mathbf{W}_1^T \mathbf{v}_q + \mathbf{b}$ 将 1536 维的通用文本嵌入投影到 $d_m$ 维的路由相关空间。直觉上，$\mathbf{W}_1$ 学习从通用语义空间中提取与路由相关的特征——放大区分”难数学”和”日常聊天”的维度，抑制无关细节。

Hadamard 积：$\mathbf{h}_q \odot \mathbf{v}_m$ 对每个维度做”供给 × 需求”的匹配。模型嵌入 $v_{m,f}$ 的每个维度代表一个模型能力轴，投影后查询 $h_{q,f}$ 代表该查询对该能力的需求程度。在模型恰好擅长查询所需之处产生高值。

线性读出：$\delta = \sum_f w_{2,f} \cdot h_{q,f} \cdot v_{m,f}$ 是加权聚合——学习哪些能力-需求匹配对预测质量最重要。

8.3 与标准 MF 的关系

标准 MF 评分是两个隐向量的纯点积：$\delta_\text{MF}(u, i) = \langle \mathbf{v}_u, \mathbf{v}_i \rangle$。

RouteLLM 的评分是扩展的 MF：

• 模型嵌入 $\mathbf{v}_m$ 扮演”用户”向量
• 投影后的查询 $\mathbf{W}_1^T\mathbf{v}_q + \mathbf{b}$ 扮演”物品”向量
• 权重 $\mathbf{w}_2$ 添加了非均匀的维度加权

两者都只使用两组特征：模型 ID 和查询。从 FM 的视角看，这就是只有两个 field 的 FM。

8.4 局限性

MF 路由器只看到模型身份和查询嵌入。它无法显式推理：

• 任务类型（数学、编程、创意写作）
• 复杂度级别（简单 vs 多步推理）
• Prompt 长度
• 语言
• 领域知识需求

所有这些信息必须被查询嵌入隐式捕获。路由器无法建模”GPT-4 在高复杂度数学任务上特别强”这样的显式交互，因为输入中没有 task_type 或 complexity 特征。

9 桥接：从 MF 到 FM 路由器

理解了 FM 和 RouteLLM MF 之后，一条清晰的扩展路径展现出来。

9.1 RouteLLM MF = 只有两组特征的 FM

9.2 公式对比

RouteLLM MF（2 组特征）：

$\hat{y} = w_0 + w_m + w_q + \langle \mathbf{v}_m, \text{proj}(\mathbf{v}_q)\rangle$

FM 路由器（N 组特征）：

$\hat{y} = w_0 + \sum_i w_i x_i + \sum_{i}\sum_{j>i} \langle \mathbf{v}_i, \mathbf{v}_j\rangle\, x_i x_j$

特征向量 $\mathbf{x}$ 可以包含：模型 ID（one-hot 或嵌入）、查询嵌入（稠密实值）、任务类型（one-hot）、复杂度（序数或分箱连续值）、Prompt 长度（归一化连续值）、语言（one-hot）等。FM 以 $O(kn)$ 时间自动建模所有二阶交互。

9.3 FM 能做到而 MF 做不到的

交互	MF (RouteLLM)	FM（扩展）
模型 × 查询	显式	显式
模型 × 任务类型	隐式（依赖嵌入）	显式
模型 × 复杂度	隐式	显式
任务类型 × 复杂度	无	显式
模型 × 语言	隐式	显式

这些交互为什么重要？“GPT-4 擅长数学”是一个已知事实，MF 只能从查询嵌入中隐式学到。“INT4 量化保留知识但降低推理能力”这样的模式，可以通过模型 × 量化配置 × 任务类型的交互直接建模。FM 让每组特征成为显式、可解释的一等公民。

9.4 核心要点

FM 的原始愿景是”只需指定输入数据，同一个算法就能模拟多种模型”。从 MF 到 FM 路由器的扩展完美体现了这一点：算法不变，变的只是特征向量。

10 总结

阶段	内容	核心公式
FM 理论 (Rendle 2010)	通用因子化交互框架，$O(kn)$ 计算	$\hat{y} = w_0 + \sum w_i x_i + \frac{1}{2}\sum_f [(\sum v_{i,f}x_i)^2 - \sum v_{i,f}^2 x_i^2]$
MF 路由器 (RouteLLM)	只用 (模型, 查询) 两组特征的 FM	$\delta(M,q) = \mathbf{w}_2^T(\mathbf{v}_m \odot (\mathbf{W}_1^T \mathbf{v}_q + \mathbf{b}))$
FM 路由器（扩展方向）	添加 task_type, complexity 等更多特征维度	同一 FM 公式，更丰富的 $\mathbf{x}$

FM 为 LLM 路由提供了一个既有理论保证又高效可行的扩展框架。从只看”模型+查询”到加入任务类型、复杂度、语言等多维特征，我们可以在不改变核心算法的情况下，让路由器做出更精细、更可解释的决策。