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

🕒 Published (v1): 2025-12-10 20:22 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Personalizing LLM agents by selecting user data subsets faces structural constraints (logical dependencies, hierarchical quotas) that break standard greedy algorithms. This paper compiles a user's knowledge graph into "macro-facets" via SCC condensation, then proves that hierarchical quota constraints over these macro-facets form a laminar matroid, reducing the problem to matroid-constrained submodular maximization with provable approximation guarantees. The greedy algorithm achieves a 1/2-approximation (continuous greedy: 1−1/e), and empirically averages 0.996 of optimal across 5,000 simulated trials.

Problem¶

LLM agent personalization requires injecting user-specific data into context, but naïvely selecting data subsets faces two compounding challenges: (1) logical dependencies in the user's knowledge graph (selecting fact A requires fact B for contextual integrity), and (2) hierarchical quota constraints (e.g., "at most 3 preferences, of which at most 1 is a professional network"). Standard submodular greedy assumes an independence oracle over a flat ground set; these structural constraints violate that assumption, rendering performance guarantees void.

Method¶

Knowledge graph representation: Model the user's facts (facets) as nodes in a directed implication graph G where edge (eᵢ, eⱼ) means selecting eᵢ requires eⱼ.
Macro-facet compilation: Compute strongly connected components (SCCs) of G via Tarjan's algorithm. Each SCC becomes one atomic macro-facet m; selecting m implicitly includes its full transitive closure clG(m) (the expansion). This absorbs all logical dependencies into the new ground set M.
Laminar matroid construction: Apply hierarchical quota constraints (nested "at-most-k" bounds over categories of macro-facets) pre-closure — i.e., quotas count chosen macro-facets SM, not expanded raw facets. The paper proves this family of feasible sets (M, I) satisfies all three matroid axioms (empty set, downward closure, augmentation), constituting a laminar matroid.
Greedy selection: Run standard greedy — iteratively pick the macro-facet with highest marginal utility U'(SM ∪ {m}) − U'(SM) subject to the independence oracle, which checks cnt[A] < qA along each root-to-leaf path in the laminar tree in O(h) time.
Utility function: U' over M is defined via expansion: U'(SM) = U(Exp(SM)); Proposition 1 proves monotonicity and submodularity are preserved under expansion.

Key Contributions¶

Proof that SCC condensation of a user's implication graph yields macro-facets whose utility function inherits monotonicity and submodularity (Proposition 1).
Proof that hierarchical quota constraints enforced pre-closure over macro-facets form a valid laminar matroid (Theorem 1), enabling matroid-constrained submodular maximization with classical guarantees.
Identification of a neuro-symbolic division of labor: LLM evaluates semantic utility; the matroid layer enforces hard structural constraints symbolically, preventing hallucinated constraint compliance.
Simulation validating practical near-optimality of greedy on 5,000 random instances (mean approximation ratio 0.996, minimum 0.911).

Results¶

Mean greedy approximation ratio: 0.996 (95% CI: 0.995–0.996) vs. brute-force optimal over 5,000 random instances.
Minimum observed approximation ratio: 0.911 (vs. theoretical worst-case bound of 0.5).
5th percentile approximation ratio: 0.975 — greedy retained ≥97.5% of optimal utility in 95% of trials.
Experimental setup: M=14 macro-facets, 120-element weighted set cover utility, partition matroid with 4 groups + budget constraint; brute-force optimal computed exhaustively.

Limitations¶

Simulation uses synthetic weighted set cover utility and partition matroids; real-world utility landscapes and constraint topologies may differ.
Ground set limited to M=14 macro-facets for tractability of brute-force comparison; scalability to large chronicles is unverified empirically.
No real-world end-to-end evaluation on actual LLM personalization tasks; utility function assumed submodular without empirical validation of this assumption for LLMs.
Post-closure quota enforcement (where quotas apply to expanded sets) is explicitly outside the framework's guarantees and left as future work.
Cost/privacy modeling (non-modular disclosure cost functions) is not yet integrated.

Relevance to Agentic AI / LLM Agents¶

This paper directly addresses a core challenge in deploying LLM agents in personal or enterprise settings: how to select context-window content from a user's knowledge graph in a principled, data-minimal way while respecting complex policy constraints. The laminar matroid framing provides a mathematically grounded alternative to ad-hoc context stuffing or probabilistic LLM-driven filtering, with formal approximation guarantees. The neuro-symbolic architecture — LLM as semantic oracle, matroid as constraint enforcer — is a reusable pattern applicable to any agentic system where hard feasibility constraints must coexist with learned utility. For researchers tracking agentic personalization, retrieval-augmented generation, and tool-use under policy constraints, this offers a combinatorial optimization lens that complements current embedding-based approaches.