Proportionality in Ranking Compression¶

会议: NeurIPS 2026
arXiv: 2610.23193
领域: 其他
关键词: 排序压缩、多元对齐、社会选择理论、比例代表制、网络流算法

一句话总结¶

本文针对多奖励模型集成与多元人类反馈对齐中海量评估者排序偏好的压缩难题，提出了排序压缩公理化框架，证明了位置比例性与坚实联盟比例性在任意输入下均可多项式时间求解，并揭示了成对比例性在一般情况下的不可能性边界与结构化偏好下的可达性。

研究背景与动机¶

在大语言模型的人类反馈强化学习（RLHF）中，主流范式通常假设评估者群体共享单一的潜在奖励函数，通过拟合统一的奖励模型来引导策略优化。然而，在面对涉及道德伦理、文化价值观以及主观偏好的复杂任务时，人类评估者之间天然存在广泛且合法的认知分歧。将异质性的多元偏好强行压缩进单一的标量奖励函数，不可避免地会导致少数群体视角的边缘化，并引发所谓“偏好坍缩（Preference Collapse）”现象，使得最终微调出的模型输出极度缺乏多样性。

为了解决这一困境，多元对齐（Pluralistic Alignment）提出了构建多奖励模型集成或“陪审团（Jury）”投票机制，力求在系统决策中覆盖广泛的信念体系。然而在现实场景中，为数以百万计的个人分别训练定制化奖励函数在计算和部署上极不现实，必须将庞大的评估者偏好剖面（Preference Profile）压缩为规模受限的代表性奖励模型集合。在抽象数学视角下，评估者反馈与奖励模型打分均体现为候选集合上的全排序，因此该问题本质上是将 \(n\) 个输入排序压缩为 \(k \le n\) 个输出排序，并使得原输入中的关键偏好模式获得成比例的代表。该问题恰好处于传统“排序聚合（Rank Aggregation）”与“多胜者投票（Multiwinner Voting）”两大社会选择理论分支的交叉口。

由于有损压缩不可避免地伴随信息损失，究竟什么样的压缩结果才算“公平且充分地代表了输入偏好”，此前缺乏严谨的理论界定。若直接要求代表性排序必须从原始输入中抽取，即使极小的实例也会导致所有代表性指标全盘失效。核心 idea：将多奖励模型集成中的偏好降维抽象为排序压缩公理化问题，系统提出位置比例性、成对比例性与坚实联盟比例性三大互不蕴含的正交准则，并利用组合匹配与网络流整数分解证明其可行性边界与多项式时间算法。

方法详解¶

整体框架¶

排序压缩问题 Formalize 如下：给定选民集合 \(N = [n]\)、候选对象集合 \(C = [m]\) 以及每位选民 \(i \in N\) 在 \(C\) 上的严格全排序 \(\pi_i = (c_{i,1}, \dots, c_{i,m})\)，目标是构造一个由 \(k\) 个排序构成的输出集合（排序间允许重复，且不必来自输入集合），以满足特定的比例代表性公理。论文针对这一目标建立了三套形式化公理： 1. 位置比例性（Positional Proportionality）：从候选对象角度出发，若某候选对象 \(c\) 在至少 \(t \cdot n / k\) 个输入排序中排在前 \(\ell\) 位，则在输出的 \(k\) 个排序中必须至少有 \(t\) 个将其排在前 \(\ell\) 位。 2. 坚实联盟比例性（Proportionality for Solid Coalitions, PSC）：从一致偏好选民群体角度出发，若至少 \(t \cdot n / k\) 个输入排序共同将候选子集 \(C' \subseteq C\) 放在其前 \(|C'|\) 位，则在输出的 \(k\) 个排序中至少有 \(t\) 个排序同样将 \(C'\) 完整置于前 \(|C'|\) 位。 3. 成对比例性（Pairwise Proportionality）：从局部相对优劣角度出发，若候选对象 \(c\) 在至少 \(t \cdot n / k\) 个输入排序中优于 \(c'\)，则在输出的 \(k\) 个排序中 \(c\) 必须在至少 \(t\) 个排序中优于 \(c'\)。

系统整体处理流程及不同公理对应的算法求解逻辑如下图所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入：n 个全量排序配置文件<br/>与目标压缩规模 k"] --> Split["公理化空间划分与路径选择"]
    Split --> D1["位置比例性构造<br/>行增量分配 + Hall 婚配定理二分匹配"]
    Split --> D2["坚实联盟比例性构造<br/>前缀子集 DAG + 顶点下界网络流分解"]
    Split --> D3["成对比例性判定<br/>强弱约束图分析与反例循环检验"]
    Split --> D4["结构偏好域联合求解<br/>单峰拓扑排序 / 单调跨越分位数抽样"]
    D1 --> Out["输出：k 个代表性排序集合<br/>保留多维偏好多样性"]
    D2 --> Out
    D3 -->|一般偏好域下无解| Imp["不可能性边界确认<br/>n ≥ k+2 时存在内在冲突"]
    D4 --> Out

关键设计¶

1. 位置比例性构造：行增量填充与二分匹配逐列置换 为了满足位置比例性，算法需要为每个候选对象 \(c \in C\) 和排位深度 \(\ell \in [m]\) 保证配额 \(t_{c,\ell} = \lfloor r_{c,\ell} \cdot k / n \rfloor\)，其中 \(r_{c,\ell}\) 为输入中 \(c\) 进入前 \(\ell\) 位的频次。痛点在于不同深度的前缀配额要求重叠，直接贪心构造各排序容易导致候选人出现冲突或同一排序内元素重复。算法设计了一个 \(m \times k\) 的网格矩阵，其中每一列对应一个最终的输出排序，每一行对应一个排位层级。首先计算每个候选人在深度增量上的分配需求 \(d_{c,\ell} = t_{c,\ell} - t_{c,\ell-1}\)（定义 \(t_{c,0} = 0\)）。由于所有候选人在前 \(\ell\) 位的总输入频次之和不超过 \(\ell n\)，容易证明配额总和满足 \(\sum_{c \in C} t_{c,\ell} \le \ell k\)。算法按层级 \(\ell = 1, \dots, m\) 从上到下、行内从左到右填充单元格，将 \(d_{c,\ell}\) 个元素 \(c\) 填入第 \(\ell\) 行及以上区域。填充完成后，每个候选对象 \(c\) 在表格中恰好出现 \(k\) 次，且在前 \(\ell\) 行出现的次数不少于 \(t_{c,\ell}\)。接下来，算法利用 Hall 婚配定理证明的关键引理：对于任意每个元素均出现 \(k\) 次的 \(m \times k\) 表格，均可通过在每一行内部独立置换元素，使得最终表格的每一列都是 \([m]\) 的合法全排列。具体实现上，算法构建 \(k\) 次二分图最大匹配：左部为候选对象集合，右部为 \(m\) 个行槽位，当行中包含该候选对象时连边。运行 Hopcroft-Karp 算法寻找完备匹配确定当前列的排列，随后扣减频次并归纳处理剩余列。该算法在 \(O(nm + m^{2.5}k)\) 时间复杂度内严格输出满足位置比例性的排序集。

2. 坚实联盟比例性构造：前缀子集 DAG 与顶点下界整数流分解 坚实联盟比例性要求充分大的选民群体对特定前缀子集的一致认同在输出中获得保留。局部贪心路径往往在早期消耗了配额，导致后继节点配额无法被单条路径覆盖。算法将所有排序的前缀建模为一个有向无环图（DAG）\(G^C = (V^C, E^C)\)。图的顶点为幂集 \(\mathcal{P}(C)\)，当且仅当 \(S \subset S'\) 且 \(|S'| = |S| + 1\) 时存在有向边 \((S, S')\)。任何从源点 \(\emptyset\) 到汇点 \(C\) 的有向路径均唯一对应一个候选对象的全排序。对于每个子集 \(S \subseteq C\)，定义输入选民计数 \(n_S = |\{i \in N \mid \mathrm{Top}_{|S|}(\pi_i) = S\}|\) 以及必须经过该顶点的输出路径配额下界 \(L(S) = q_S = \lfloor n_S \cdot k / n \rfloor\)。算法首先构造一个平凡的分数流 \(f\)：将每位输入选民的路径赋予 \(k/n\) 的流量，此流在所有顶点 \(S\) 上满足 \(f(S) = n_S \cdot k / n \ge L(S)\)，且总流量为 \(k\)。随后，通过顶点拆分技术（将顶点 \(v\) 拆为 \(v_{in}\) 与 \(v_{out}\)，引入容量为下界 \(L(v)\) 的超源超汇辅助边及反向循环边），将带顶点流量下界的流通问题规约为经典最大流问题。利用网络流整数性定理，算法在诱导子图（仅保留 \(n\) 条输入路径所经过的至多 \(n(m+1)\) 个顶点和 \(nm\) 条边）上求得流量为 \(k\) 的可行整数流 \(f^*\)，并在 \(O(nm^2 k)\) 时间内将其贪心分解为 \(k\) 条有向路径，每条路径即为一个输出排序。

3. 成对比例性判定：强弱约束图分析与不可能性反例构造 与前两者不同，成对比例性要求保留候选人之间的两两相对优劣关系。当 \(c\) 在至少 \(t \cdot n / k\) 个输入中排在 \(c'\) 前面时，输出中至少有 \(t\) 个排序满足 \(c \succ c'\)。针对 \(k=2\) 时的场景，论文将配额为 2 的成对关系定义为强约束 \(c \xrightarrow{\text{s}} c'\)（两个输出排序均须满足），配额为 1 的定义为弱约束 \(c \xrightarrow{\text{w}} c'\)（至少一个输出排序满足）。论文证明了关键引理：当 \(k=2\) 时，约束图可被两个输出排序满足的充分必要条件是，存在一个满足所有强约束的排序 \(\pi\)，使得图中每个有向环上至少有一条弱约束被 \(\pi\) 满足。基于该刻画，论文构造了一个精巧的反例系统：当 \(n=4, k=2\) 时，设置 \(m=24\) 个候选对象，分为 4 个长度为 6 的环 \(D_0, D_1, D_2, D_3\)。环内由强弱约束交替构成，且环间层级施加了全连接的强约束。任何试图满足所有强约束的排序 \(\pi\)，都会导致某个子环内的所有弱约束均被违反，从而在该环上形成未被覆盖的有向回路，导致拓扑排序失败。这一构造进一步推广到了任意 \(k \ge 2\) 且 \(n \ge k+2\) 的情形，确立了成对比例性在一般偏好域下的普遍不可满足性。

4. 结构偏好域联合求解：单峰拓扑排序与单调跨越分位数抽样 为了打破不可能性定理的壁垒，论文转向社会选择理论中广泛存在的结构化偏好域——单峰偏好（Single-peaked）与单调跨越偏好（Single-crossing）： - 单峰偏好域：针对以公共轴 \((1, 2, \dots, m)\) 为基准的单峰偏好，论文提出 Algorithm 1。针对每个输出位次 \(d \in [k]\) 动态构建有向约束图 \(G_d\)，根据候选人左右相对轴向位置决定保留哪些配额约束，并使用双指针算法从两端向中间剥离候选对象，构造出无环拓扑排序 \(\pi_d\)。该算法在 \(O(m^2(n+k))\) 时间内同时满足位置比例性、成对比例性与坚实联盟比例性，且严格保证每个输出排序继续保持单峰性质。 - 单调跨越偏好域：选民偏好沿某一顺序排列时任意候选对的偏好反转至多发生一次。算法设计了确定性分位数采样策略：直接抽取第 \(\lceil d \cdot n / k \rceil\)（\(d \in [k]\)）位选民的输入排序作为输出。借助区间交集引理，证明了该离散抽样能够在仅从输入排序中选择的前提下，同时满足成对比例性与坚实联盟比例性，算法运行时间仅需 \(O(mk)\)。

损失函数 / 训练策略¶

作为离散理论与组合优化算法研究，本方法不依赖梯度下降或连续损失函数，而是以多项式时间组合算法实现全局公理化约束的精确满足： 1. 位置比例性算法：输入预处理计算 \(r_{c,\ell}\) 耗时 \(O(nm + m^2)\)；随后求解 \(k\) 轮 Hopcroft-Karp 二分图匹配，每轮在 \(O(m^{2.5})\) 内完成，总复杂度为 \(O(nm + m^{2.5}k)\)。 2. 坚实联盟比例性算法：构建受限子集 DAG（节点数 \(\le n(m+1)\)，边数 \(\le nm\)），顶点下界总和 \(\sum L(S) \le k(m+1)\)；利用 Ford-Fulkerson 变体求解整数流并在 DAG 上沿正流量边回溯解包，总耗时 \(O(nm^2 k)\)。 3. 单峰拓扑求解策略：对 \(d \in [k]\) 分别在有向图 \(G_d\) 上执行双指针入度扫描，每次迭代在 \(O(m^2)\) 时间内输出排列，总耗时 \(O(m^2(n+k))\)。

实验关键数据¶

主实验¶

论文通过严格的数学证明与反例构造建立了排序压缩的核心理论图景。下表总结了三大比例性公理在一般偏好域及结构化偏好域下的存在性与计算复杂度边界：

公理 / 目标属性	一般偏好存在性	计算时间复杂度	单峰偏好域 (Single-peaked)	单调跨越偏好域 (Single-crossing)	仅从输入抽取 (From Input)
位置比例性 (Positional)	始终存在 (Always)	\(O(nm + m^{2.5}k)\)	满足且保单峰性质	满足 (不可仅取自输入)	不可满足 (反例见命题1)
坚实联盟比例性 (PSC)	始终存在 (Always)	\(O(nm^2 k)\)	满足且保单峰性质	满足且可直接取自输入	不可满足 (反例见命题1)
成对比例性 (Pairwise)	一般不可满足 (\(n \ge k+2\))	存在性反例 (NP-hard判定)	满足且保单峰性质	满足且可直接取自输入	不可满足 (反例见命题1)
三大公理同时满足	一般不存在	-	满足且 \(O(m^2(n+k))\) 求解	无法同时满足 (附录F)	不可能成立

消融实验¶

针对成对比例性不可满足性的参数边界以及各公理对“输出取自输入”限制的脆弱性，论文给出的参数敏感性与反例消融如下表所示：

配置 / 参数条件	候选集规模 \(m\)	成对比例性可行性	理论证明机制与边界剖析
\(k=1\)（单输出基线）	任意 \(m \ge 1\)	始终满足	所有输入完全一致时输出该排序，否则输出任意排序均平凡满足
\(n = k\)（无压缩全量保留）	任意 \(m \ge 1\)	始终满足	直接原样输出 \(n\) 个输入排序，配额完美守恒
\(n = k+1\)（压缩减少1位）	任意 \(m \ge 1\)	始终满足	任意抽取 \(k\) 个输入，阈值 \(\lceil t(k+1)/k \rceil \ge t+1\)，至多漏选 1 个必满足
\(k \ge 2, n \ge k+2\)（一般压缩）	\(m \ge 24\)（\(n=4,k=2\)）	不可满足	4 个 6 环构造强弱约束图，拓扑排序产生环路自相矛盾
小规模暴力搜索（\(n=4, k=2\)）	\(m \le 7\)	始终满足	穷举搜索验证，候选集过小时约束环路自由度不足以闭合矛盾
强制输出选自输入（命题1）	\(m \ge 6\)（\(n=4,k=2\)）	三大公理全灭	6 对输入分别垄断独立排位/成对/联盟条件，2 个代表无法覆盖 6 对

关键发现¶

输出自由度的关键价值：如果强制要求代表性排序必须选自原始评估者提交的输入排序（如 Metritocracy 设定），即使在 4 名选民、6 个候选对象的极简设置下，三大比例性公理均彻底失效（命题 1）。允许在排序空间内合成虚拟代表排序是实现比例代表制的数学前提。
全局约束对抗局部启发式：贪心路由启发式算法在 PSC 求解中必然失效。局部视角下看似合理的即时配额满足，会导致深层未满足顶点的配额无法被单条合法路径覆盖，必须依赖全局网络流规划。
结构偏好消除不可能性：现实场景中人类对政策或模型输出的评估往往沿着某种一维潜在空间展开（例如政治光谱、模型安全性程度）。一旦偏好呈现单峰或单调跨越结构，成对循环矛盾被天然消除，多项式时间内可同时兼顾多项强比例性保证。

亮点与洞察¶

将多元 RLHF 中海量奖励模型的降维问题精确转化为计算社会选择理论中的排序压缩，为长期依赖启发式聚类的对齐实践提供了严谨的公理化评判基准。
巧妙将位置比例性与坚实联盟比例性分别规约为经典的 Hall 婚配定理与网络流整数性定理，不仅证明了存在性，更给出了高效实用的强多项式时间构造算法。
确立了紧致的不可能性边界（\(n \ge k+2\) 且 \(k \ge 2\)），并通过约束图环路着色证明了成对一致性与全局排序传递性之间的内在数学张力。

局限与展望¶

完全排序假设与实际数据稀疏性的脱节：理论分析假设每位选民均能提供候选集上的完整严格全排序，而现实 RLHF 中标注者通常只能给出稀疏的成对比较或部分排序，扩展至带缺失值的偏好矩阵尚需更强的结构假设。
代表性排序到连续奖励函数的映射：算法产物是离散的置换排序，在下游集成部署时需要将其重新参数化并拟合为平滑的标量奖励神经网络，离散排序到连续参数空间的拟合保真度有待实证检验。
成对比例性的松弛界限未知：尽管证明了成对比例性一般不可达，乘法松弛可平凡取得 2-近似，但加法松弛（如允许误差为 1）是否存在普适求解算法仍是悬而未决的开放理论问题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出排序压缩的完整公理化体系，开辟了社会选择理论在多元对齐中的新交集。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论工作，存在性证明、不可能性边界、紧致性分析与结构化偏好拓展严密完备。
写作质量: ⭐⭐⭐⭐⭐ 数学符号清晰，引理推进层层深入，DAG 与二分图的建模直观优雅。
价值: ⭐⭐⭐⭐⭐ 为大模型多元价值对齐中的奖励模型集成设计奠定了坚实而重要的理论基石。