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

AI summary

Overview

Research area: Personalized LLM agents, data minimization, and combinatorial optimization (submodular maximization under matroid constraints, knowledge-graph compilation).

Technical level: Intermediate to Advanced. The paper is a theory-first contribution that assumes familiarity with submodular set functions, matroids, and strongly connected components. The intuition behind each piece is stated plainly enough for a motivated non-specialist, but the central result is a formal proof.

Scope in one sentence: The paper shows that common hierarchical and quota-based personalization constraints can be compiled into a laminar matroid, turning data-minimal LLM personalization into a well-studied submodular maximization problem that a simple greedy algorithm solves near-optimally.

What This Paper Is About

Personalizing an LLM agent means putting user-specific data into its context, but more data raises token costs and privacy exposure, so you want the smallest subset of user facts that still gets the job done. The trouble is that user data is not a loose bag of independent facts: some facts require others to be logically complete, and users impose nested quotas ("at most three hobbies, of which at most one is a water sport"). These constraints break the independence assumption that makes greedy selection provably near-optimal. The paper's goal is to reformulate constrained personalization so that greedy selection regains its performance guarantees.

Key Contributions

1. A compilation process from knowledge graphs to macro-facets. The paper defines a user's "chronicle" as a knowledge graph of facets with directed implication edges, and shows how to condense it using strongly connected components (SCCs) into "macro-facets" — logically inseparable bundles that act as atomic units of selection. Any valid selection then automatically satisfies logical dependencies via an expansion operator.

2. A proof that hierarchical quota constraints on macro-facets form a laminar matroid. The central theoretical result (Theorem 1) verifies the matroid axioms for the system (macro-facets, independent sets), using the standard augmentation argument for laminar systems. Nested "at-most-k" quotas such as "at most three social media preferences, at most one for a professional network" fit this structure.

3. A reduction to matroid-constrained submodular maximization. Because macro-facet utility preserves monotonicity and submodularity (Proposition 1), the problem becomes maximizing a monotone submodular function subject to a matroid constraint, inheriting a 1/2 guarantee for greedy and a (1 − 1/e) guarantee via continuous greedy with pipage or swap rounding. Simple categorical quotas are shown to be a special case (partition matroids, Corollary 1).

4. An efficient independence oracle and an empirical simulation. Feasibility checking is reduced to walking a root-to-leaf ancestor chain of height h, giving O(h) verification overhead. A simulation over 5,000 random instances compares greedy against brute-force optimal solutions.

Main Findings

• Macro-facets absorb dependencies without losing structure. Selecting a macro-facet implicitly selects its entire closure, so logical completeness is guaranteed by construction rather than checked after the fact. The explicit "Client Identities quota = 0" example shows why this matters: selecting '(User, led, ProjectApollo)' would otherwise drag in '(ProjectApollo, client_is, AcmeCorp)' and breach the prohibition.

• Hierarchical and quota-based rules are a laminar matroid. A laminar family requires that any two sets are nested or disjoint; with non-negative integer quotas, independent sets of macro-facets satisfy the matroid axioms (empty set, downward closure, augmentation). Mutual exclusivity within a category is expressed by a nested subset with quota q = 1.

• Quotas must be enforced pre-closure. Quotas apply only to the chosen macro-facets before expansion; elements introduced by expansion are never counted toward quotas, because each macro-facet already internalizes its dependents and counting post-expansion would double-count implied information rather than independent choices.

• Greedy retains a 1/2 guarantee; continuous greedy reaches (1 − 1/e). Greedy starts from an empty set and iteratively adds the element with the highest marginal utility while maintaining independence. Stronger guarantees come from continuous greedy with pipage or swap rounding.

• Constraint enforcement is cheap; utility evaluation is the bottleneck. Feasibility verification costs O(|P(m)|) = O(h), where h is the tree height. The paper notes that in practice this is mitigated via lazy greedy evaluation or lightweight proxy models.

• Simulated performance far exceeds the theoretical bound. Across 5,000 random instances using a weighted set cover utility (M = 14 macro-facets, each covering subsets of a 120-element universe with random positive weights) under partition matroid constraints (14 macro-facets randomly partitioned into 4 groups, each with a random integer quota, plus an overall budget), the mean approximation ratio was 0.996 (95% CI: 0.995, 0.996). The minimum across all 5,000 trials was 0.911 — described as over 82% better than the theoretical lower bound of 0.5 — and the 5th percentile was 0.975, meaning 95% of instances retained at least 97.5% of maximum utility.

• The simulation has stated limitations. It relies on a synthetic (though standard) submodular utility and randomly generated partition matroid constraints, and the brute-force comparison forced a small ground set (M = 14), so results may not generalize perfectly to much larger scale problems.

• Neuro-symbolic division of labor. The framework delegates semantic utility evaluation to the LLM while enforcing structural integrity symbolically through the matroid, avoiding "hallucinated compliance" where an LLM believes it satisfied a quota but did not.

• A worked example. In a writing-assistant scenario with five macro-facets (Formal Tone, Casual Tone, Uses Emojis, Cites Academic Sources, Succinct Phrasing) and laminar constraints (at most one tone; at most three style rules overall), greedy selects {Cites Academic Sources, Formal Tone, Succinct Phrasing}. In an end-to-end professional-networking example, dependencies condense into macro-facets M_A = {f1, f4}, M_B = {f3, f7}, and singletons M_C = {f2}, M_D = {f5}, M_E = {f6}, with laminar quotas A3 ⊂ A2 ⊂ A1; greedy selects {M_A, M_B, M_D}.

Methodology in Plain English

The authors treat the set of user facts as a graph. First, they define what "complete" means: a selection must include everything transitively implied by its members, a property called closure, modeled with a directed implication graph. Second, they collapse cycles in that graph — strongly connected components — because mutually implying facts cannot be separated anyway. Each collapsed component becomes a single "macro-facet," and the utility of a set of macro-facets is defined as the utility of the union of their closures. They then prove this redefined utility keeps the diminishing-returns property.

Third, they express user rules as nested quotas over categories, which mathematically form a laminar family, and prove (via the standard augmentation argument) that the resulting system is a matroid. Because of that, the selection problem becomes maximizing a monotone submodular function under a matroid constraint — a problem with known greedy guarantees. Fourth, they specify an independence oracle that stores counters on a rooted quota tree and checks a single ancestor chain per candidate, so constraint checking is cheap.

Finally, to check how the theory behaves in practice, they ran 5,000 randomly generated instances of weighted set cover under partition matroid constraints, compared greedy output against the brute-force optimum, and plotted the distribution of approximation ratios in Figure 1. Submodularity in LLMs is justified informally: early high-salience facts reduce generation uncertainty most, and later facts add less due to redundancy.

Why This Matters

Impact on research. The paper bridges two bodies of work that are usually kept separate: LLM personalization and data minimization on one side, and submodular optimization with matroid constraints on the other. It shows that a richer, more realistic class of personalization constraints (dependency closure plus nested quotas) still falls inside a regime with provable approximation guarantees, rather than requiring ad-hoc heuristics. It also warns that enforcing quotas post-closure generally induces non-matroidal packing variants for which the guarantees do not hold.

Real-world applications:

• Professional networking agents: honoring nested limits such as "at most two social media preferences, at most one professional network," as in the paper's end-to-end example.
• Writing assistants: enforcing "at most one tone" and an overall style-rule budget, as in the functional trace of Algorithm 1.
• Regulated or conflict-of-interest settings: the consultant example, where a zero quota on client identities must not be silently violated by transitively implied facts.
• Contextual relevance and policy limits: the paper notes the same structure can encode time-sensitivity, policy restrictions, and task-dependent relevance (e.g., a preferred writing tone matters for email generation but not summarization).

Industry relevance. The framing is directly operational for teams building personalized agents under token-cost and privacy budgets: it separates what the LLM is good at (judging semantic utility) from what it is bad at (strict counting and closure), and it keeps constraint-checking overhead small relative to utility evaluation.

Future Directions

1. Empirical validation on real tasks. The authors explicitly name validating the framework on real-world tasks as a key direction, since the current evidence is a synthetic simulation.
2. Beyond modular costs. Extending the framework to non-modular cost functions to model information leakage risk is left open.
3. The non-matroidal regime. When quotas are enforced post-closure, feasibility depends on the final expanded set, and the paper states its current guarantees do not apply; characterizing this case remains open.
4. Scale and generality. Because brute-force comparison required a small ground set (M = 14), whether the near-optimal average-case behavior of greedy persists at much larger scale, and on real utility landscapes, is untested here.

Target Audience

Researchers and practitioners in LLM personalization, privacy-preserving and data-minimal AI, and applied combinatorial optimization. It suits engineers designing context-selection or retrieval policies for personalized agents, and theorists interested in how identity constraints on knowledge graphs map onto matroid structures. Readers without a background in submodular optimization or matroid theory will need to lean on the worked examples in the appendix, which make the mechanics concrete.

Authors’ abstract

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.