用集合拟阵建模用户数据约束,实现小数据下大模型代理的高效个性化。
Structured Personalization: Modeling Constraints as Matroids for Data-Minimal LLM Agents
- 将用户知识图谱转化为抽象宏特征,用拟阵形式表达复杂约束
- 证明层级与配额约束构成层状拟阵,支持近似最优贪心选择
- 适用于数据极少但需满足逻辑规则的个性化场景,如写作风格、社交偏好
个性化大型语言模型代理需依赖用户特定数据,面临任务效用与数据披露之间的权衡。尽管增加用户数据的效用常呈现递减趋势(即子模性),可实现近似最优的贪心选择,但现实中的个性化受结构约束干扰。这些约束包括逻辑依赖(如选事实A需同时选事实B)、类别配额(如最多选一种写作风格)和层级规则(如最多选两个社交媒体偏好,其中仅一个可为职业网络)。此类约束破坏了标准子集选择算法的假设。本文提出一种形式化建模方法:将用户知识图谱中的依赖关系编译为一组抽象宏特征。核心结果是证明:在这些宏特征上常见的层级与配额约束构成有效层状拟阵。该理论特性使结构化个性化问题可被建模为带拟阵约束的子模最大化问题,从而支持具有常数因子保证的贪心算法,以及通过连续贪心实现(1-1/e)近似率,适用于更广泛且更贴近现实的个性化问题。
原文摘要 · Abstract (English)
Personalizing Large Language Model (LLM) agents requires conditioning them on user-specific data, creating a critical trade-off between task utility and data disclosure. While the utility of adding user data often exhibits diminishing returns (i.e., submodularity), enabling near-optimal greedy selection, real-world personalization is complicated by structural constraints. These include logical dependencies (e.g., selecting fact A requires fact B), categorical quotas (e.g., select at most one writing style), and hierarchical rules (e.g., select at most two social media preferences, of which at most one can be for a professional network). These constraints violate the assumptions of standard subset selection algorithms. We propose a principled method to formally model such constraints. We introduce a compilation process that transforms a user's knowledge graph with dependencies into a set of abstract macro-facets. Our central result is a proof that common hierarchical and quota-based constraints over these macro-facets form a valid laminar matroid. This theoretical characterization lets us cast structured personalization as submodular maximization under a matroid constraint, enabling greedy with constant-factor guarantees (and (1-1/e) via continuous greedy) for a much richer and more realistic class of problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。