Structured Personalization: Modeling Constraints as Matroids for Data-Minimal LLM Agents¶

会议: AAAI 2026
arXiv: 2512.11907
代码: 无
领域: LLM Agent / 个性化优化
关键词: 个性化数据选择、子模优化、拟阵约束、知识图谱编译、数据最小化

一句话总结¶

将 LLM Agent 个性化中的结构化约束（逻辑依赖 + 层级配额）形式化为层叠拟阵（laminar matroid），证明贪心算法在此约束下仍具有常数因子近似保证，解决了有依赖关系和层级限制的数据最小化选择问题。

研究背景与动机¶

领域现状：LLM Agent 的个性化通常通过在上下文中注入用户特定数据来实现。数据越多通常任务效果越好，但也带来更高的 token 成本和隐私泄露风险。
现有痛点：在理想情况下，个性化效用具有子模性（diminishing returns），简单的贪心选择就能获得近优解。然而现实中用户数据存在两类结构化约束：(a) 逻辑依赖——选择事实 A 可能必须同时选择事实 B（如选"用户负责 ProjectPinnacle"就必须选"ProjectPinnacle 是遗留系统迁移项目"，否则 Agent 可能产生错误推断）；(b) 层级配额——嵌套的数量限制（如最多选 3 个兴趣爱好，其中最多 1 个水上运动）。
核心矛盾：这些结构化约束违反了标准子集选择算法的独立性假设，使得贪心算法的近优性保证失效。但现有个性化方法要么忽略这些约束，要么用临时启发式处理。
本文要解决什么：提供一个数学上严格的框架来建模这些复杂约束，使得有保证的优化算法可以应用于现实世界的个性化场景。
切入角度：从组合优化理论出发，利用拟阵（matroid）这一代数结构来刻画可行解空间的性质。
核心idea：两步编译过程——先用强连通分量（SCC）将有逻辑依赖的 facet 压缩为 macro-facet（消解依赖），再证明在 macro-facet 上的层级配额约束构成层叠拟阵，从而将问题归约为经典的"拟阵约束下子模函数最大化"问题。

方法详解¶

整体框架¶

整体流程分三步：(1) 建模——将用户身份表示为知识图谱（chronicle），facet 间存在逻辑蕴含关系；(2) 编译——通过 SCC 凝聚将有依赖的 facet 压缩为 macro-facet，消解依赖结构；(3) 约束建模——证明 macro-facet 上的层级配额约束形成层叠拟阵，应用贪心算法获得 1/2 近似解（或连续贪心获得 \((1-1/e)\) 近似解）。

关键设计¶

模块一：Chronicle 与 Facet 依赖编译

做什么：将用户身份知识图谱中逻辑不可分的 facet 组合编译为 "macro-facet"。
核心思路：用户身份 \(\mathcal{C}_u = \{e_1, \dots, e_n\}\) 中的 facet 通过有向蕴含图 \(G = (\mathcal{C}_u, E)\) 连接，边 \((e_i, e_j)\) 表示选择 \(e_i\) 逻辑上要求 \(e_j\)。任何有效的个性化过滤器必须是闭集（包含所有传递蕴含的 facet）。关键操作：计算蕴含图 \(G\) 的强连通分量（SCC），每个 SCC 构成一个 macro-facet。选择某个 macro-facet 即自动包含其整个闭包 \(\text{cl}_G(m)\)，自动满足所有逻辑依赖。效用函数在新基集上重定义为 \(U'(S_\mathcal{M}) \triangleq U(\text{Exp}(S_\mathcal{M}))\)。
设计动机：将"约束满足"问题编码进基集本身，使得选择操作天然满足依赖关系，简化后续优化。

模块二：层叠拟阵约束证明

做什么：证明在 macro-facet 集合上的层级配额约束构成层叠拟阵（laminar matroid）。
核心思路：层叠族 \(\mathcal{F} \subseteq 2^\mathcal{M}\) 中任意两个集合要么嵌套要么不交。对每个集合 \(A \in \mathcal{F}\) 施加配额 \(q_A\)，独立集定义为对所有 \(A\)，\(|S_\mathcal{M} \cap A| \leq q_A\)。通过验证拟阵三公理（空集、遗传性、增广性）来证明 \((\mathcal{M}, \mathcal{I})\) 是拟阵。增广性证明的关键利用了层叠族的嵌套/不交性质：若不存在可增广元素，则紧约束集的嵌套结构会导致 \(|A| \geq |B|\)，矛盾。重要约定：配额仅在选择的 macro-facet 集合上检查（pre-closure），展开后的元素不计入配额。
设计动机：拟阵结构是使贪心算法具有近优保证的关键代数条件。partition matroid（简单分类配额）是其特例。

模块三：贪心选择算法与独立性 Oracle

做什么：实现高效的贪心选择算法，迭代选择边际效用最大且保持独立的 macro-facet。
核心思路：算法初始化 \(S = \emptyset\)，每步找到 \(m^* = \arg\max_{m \in C} [U'(S \cup \{m\}) - U'(S)]\)，若 \(S \cup \{m^*\} \in \mathcal{I}\) 则加入。独立性 Oracle 实现：将层叠族表示为有根森林，为每个 macro-facet 预计算其祖先链 \(P(m)\)（由于层叠性，这是一条根到叶路径），检查 \(\text{cnt}[A] < q_A\) 对所有 \(A \in P(m)\) 是否成立。复杂度仅 \(O(h)\)（\(h\) 为树高），约束检查开销可忽略。
设计动机：贪心算法获得 1/2 近似保证（Fisher et al.），连续贪心可达 \((1-1/e)\)（Calinescu et al.）。体现了"神经-符号分工"——LLM 估计效用（语义），拟阵保证可行性（符号）。

损失函数 / 训练策略¶

效用函数 \(U: 2^{\mathcal{C}_u} \to \mathbb{R}_{\geq 0}\) 需满足归一化（\(U(\emptyset)=0\)）、单调性和子模性。实践中可通过 LLM-as-Judge 在 benchmark 上测量下游任务性能来经验性估计。仿真中使用加权集合覆盖函数作为标准子模函数。

实验关键数据¶

主实验¶

5000 个随机问题实例的仿真实验（14 个 macro-facet，4 组 partition matroid）：

指标	值
贪心近似比均值	0.996 (95% CI: 0.995, 0.996)
最低近似比	0.911
第 5 百分位	0.975
理论下界	0.5

消融实验¶

贪心算法在 95% 的实例上保持了至少 97.5% 的最优效用。
观测到的最差情况（0.911）比理论下界（0.5）好 82% 以上。
分布高度左偏，绝大多数结果集中在 1.0 附近。

关键发现¶

贪心算法在实践中表现远超理论保证：平均近似比 0.996，几乎等同于暴力搜索的最优解。
层叠拟阵建模有效：证明了常见的层级约束和互斥规则可以被优雅地统一到拟阵框架中。
Partition matroid 是重要特例：简单的分类配额（"每类选 k 个"）自动涵盖在层叠拟阵框架内。
神经-符号分工的必要性：LLM 在语义评估上擅长但在严格逻辑约束上不可靠（可能"幻觉式合规"），将硬约束委托给符号层是正确的设计。

亮点与洞察¶

理论优雅：从 SCC 凝聚→层叠拟阵→子模最大化的推导链条清晰完整，每一步都有明确的数学保证。
实际落地意义：为 LLM 个性化中的数据最小化提供了有保证的解决方案——在满足隐私和配额约束的前提下最大化个性化效果。
"逻辑依赖"的处理方式非常巧妙：通过编译把约束吸收进基集，使后续优化完全在"干净"的空间上进行。
Pre-closure vs. Post-closure 的区分具有实用价值：明确指出 post-closure 模式下拟阵结构不再成立，划清了方法的适用边界。

局限性 / 可改进方向¶

纯理论工作：仅有合成仿真实验，缺乏在真实 LLM 个性化任务上的端到端验证。
基集规模小：仿真中仅 14 个 macro-facet，暴力搜索可行；大规模场景下的可扩展性未验证。
效用函数假设较强：子模性和单调性在 LLM 场景下是否严格成立需要更多实证支持。
Post-closure 配额留为未来工作：当配额需要在展开后的实际 facet 数上检查时，当前框架不适用。
静态模型：未考虑用户兴趣随时间变化、上下文依赖的动态个性化场景。

评分¶

⭐⭐⭐⭐

理论贡献扎实——将 LLM 个性化中的实际约束形式化为拟阵是很好的创新点，证明清晰完整。但实验仅为合成仿真，缺乏真实场景验证是主要不足。论文的理论-实践鸿沟较大，需要后续工作填补。