PCN-Rec: Agentic Proof-Carrying Negotiation for Reliable Governance-Constrained Recommendation
This addresses the need for reliable constraint satisfaction in recommendations, particularly for governance in domains like content moderation, though it is incremental as it builds on existing agent and verification methods.
The paper tackles the problem of LLM-based recommenders failing to reliably satisfy governance constraints like diversity, by introducing PCN-Rec, a proof-carrying negotiation pipeline that achieves a 98.55% pass rate on feasible users with only a 0.021 drop in NDCG@10 compared to a baseline.
Modern LLM-based recommenders can generate compelling ranked lists, but they struggle to reliably satisfy governance constraints such as minimum long-tail exposure or diversity requirements. We present PCN-Rec, a proof-carrying negotiation pipeline that separates natural-language reasoning from deterministic enforcement. A base recommender (MF/CF) produces a candidate window of size W, which is negotiated by two agents: a User Advocate optimizing relevance and a Policy Agent enforcing constraints. A mediator LLM synthesizes a top-N slate together with a structured certificate (JSON) describing the claimed constraint satisfaction. A deterministic verifier recomputes all constraints from the slate and accepts only verifier-checked certificates; if verification fails, a deterministic constrained-greedy repair produces a compliant slate for re-verification, yielding an auditable trace. On MovieLens-100K with governance constraints, PCN-Rec achieves a 98.55% pass rate on feasible users (n = 551, W = 80) versus a one-shot single-LLM baseline without verification/repair, while preserving utility with only a 0.021 absolute drop in NDCG@10 (0.403 vs. 0.424); differences are statistically significant (p < 0.05).