Recommendations With Receipts: When LLMs Have to Prove They Behaved

A recommendation list is rarely just a list.

On the surface, it says: “Here are ten movies, products, articles, songs, creators, or courses you may like.” Underneath, it often carries a second instruction: “Also do not bury long-tail items, do not over-concentrate exposure, do not violate diversity rules, do not create an audit nightmare, and please do all of this while still looking personalized.”

That second instruction is where many LLM-based recommenders start to look suspiciously charming. They can explain why a list sounds reasonable. They can balance user preference and policy language in fluent prose. They can even produce a beautifully formatted justification.

Then the list quietly violates the constraint.

The paper behind PCN-Rec, Agentic Proof-Carrying Negotiation for Reliable Governance-Constrained Recommendation, is useful because it does not try to solve that problem by making the LLM more sincere.¹ It changes the job description. The LLM is not the judge. It is not the compliance officer. It is not the source of truth. It is a proposer that must bring receipts.

That is the central mechanism of the paper: let agents negotiate a slate, require a structured certificate, verify the certificate with deterministic code, and repair the slate when verification fails. It is less “LLM recommender becomes responsible” and more “LLM recommender is no longer allowed to mark its own homework.” Progress, at last, through basic supervision. Revolutionary, apparently.

The real design move is to demote the LLM

PCN-Rec starts with a conventional recommender, such as matrix factorization or collaborative filtering, that produces a ranked candidate list for a user. The system then takes a bounded candidate window, denoted $C_W(u)$, from the top $W$ items. In the paper’s experiment, the selected operating point is $W=80$.

That window matters more than it first appears. It defines the universe within which every later step must operate. If a compliant recommendation slate cannot be formed from those 80 candidates, the failure is not an LLM reasoning failure. It is infeasibility under the chosen window and policy constraints.

Inside this window, PCN-Rec uses two agents with different incentives. A User Advocate argues for relevance to the user. A Policy Agent argues for constraints such as long-tail exposure, head-item limits, and genre diversity. A mediator LLM then synthesizes their arguments into a Top-$N$ slate and emits a structured JSON certificate.

The certificate is not a natural-language explanation. It is a proof object in a modest but operationally important sense: it contains the selected item IDs and fields needed for verification, such as which items count as tail items and which genres are covered.

Then comes the part that makes the architecture interesting. A deterministic verifier recomputes the constraints from the slate and item metadata. It does not trust the LLM’s explanation. It checks the slate.

If the slate passes, the system returns it with a logged certificate. If it fails, a deterministic constrained-greedy repair procedure attempts to construct a compliant slate from the same candidate window, then verifies the repaired slate again.

The pipeline can be summarized like this:

This is why the paper should not be read as another “LLMs improve recommendation” story. The LLM is useful because it can negotiate trade-offs and synthesize proposals. The reliability comes from the fact that its proposal is not trusted.

The constraints are simple, which is exactly the point

The paper evaluates PCN-Rec on MovieLens-100K under per-slate governance constraints. The constraints are not mystical. They are deliberately concrete.

First, the slate must satisfy head/tail exposure rules. Each item is marked as long-tail or head. The slate must contain at least a fraction $\tau$ of tail items and at most a fraction $\kappa$ of head items:

Second, the slate must satisfy genre diversity. If $G(i)$ is the set of genres for item $i$, the slate’s covered genres must meet a minimum threshold:

These are not the full universe of recommender governance. They do not capture every fairness problem, every content-quality concern, every creator-market objective, or every downstream user harm. But they are useful constraints because they are checkable.

That is the business lesson hiding in the technical setup. PCN-Rec works where governance can be translated into explicit predicates over items, users, slates, and metadata. “Show at least this much long-tail content” can be verified. “Be culturally appropriate” is not yet a verifier unless someone has done the hard work of defining the metric, validating the labels, and accepting the inevitable arguments.

The paper’s governance claim is therefore narrow but practical: if a policy can be expressed as deterministic checks over trusted metadata, the LLM can be placed inside a verified recommendation workflow without becoming the enforcement mechanism.

That is not a small claim. It is just a less glamorous one than “the model understands policy.” Glamour is cheap. Audit logs are better.

Feasibility is not failure, and this distinction saves the evaluation

One of the better parts of the paper is its separation between infeasibility and method failure.

For each user, PCN-Rec asks whether at least one compliant slate exists inside the candidate window. Formally, the user is feasible under $W$ if there exists some slate $S$ in the candidate window such that all policy constraints pass:

This matters because not every recommendation failure is the same kind of failure.

If the candidate window contains too few tail items, no mediator, no agent debate, no prompt engineering ceremony, and no “please think step by step” incantation will produce a compliant slate from that window. The correct diagnosis is not “the LLM failed.” The correct diagnosis is “the upstream candidate generator and window size made the policy impossible.”

The paper’s Figure 2 is best understood as a feasibility and operating-point analysis, not merely a chart decoration. As $W$ increases, more users admit at least one compliant slate, while tail shortage decreases. The authors choose $W=80$, where 551 out of 943 users are feasible, or about 58.4%.

That number is more important than it looks. It says that even before arguing about LLM behavior, roughly 41.6% of users are outside the paper’s feasible subset at that chosen window. For a production system, this would immediately raise product and infrastructure questions:

This is also where PCN-Rec becomes more useful than a standard benchmark comparison. A pass rate without feasibility analysis is easy to misread. A failed slate could mean the method is weak. Or it could mean the input window made success impossible. PCN-Rec forces that distinction into the evaluation.

For a business team, this is not academic neatness. It is root-cause analysis.

The main result: compliance rises, utility bends, and the bend is measurable

On the feasible subset at $W=80$ and $n=551$, the paper reports the central comparison: a one-shot Single LLM baseline without verification or repair versus PCN-Rec with verifier-checked certificates and deterministic repair.

The results are compact:

The headline is obvious: PCN-Rec reaches near-perfect governance compliance on feasible users, while the one-shot LLM baseline fails the verifier. The less obvious interpretation is that this is not magic from negotiation. It is the expected consequence of moving constraint enforcement into deterministic code and giving the system a repair path.

The Single LLM baseline has the higher NDCG@10 score, 0.424 versus PCN-Rec’s 0.403. The paper reports a utility drop of about $-0.022$ in NDCG@10, with statistical testing at $p<0.05$. This is the price of hard governance in this setup.

The deterministic greedy bound is also useful, but it should be read carefully. It is a reference point for achievable compliant utility under the same constraint setting, not a second thesis about agentic negotiation. Its NDCG@10 is 0.426, close to the Single LLM baseline’s 0.424 and above PCN-Rec’s 0.403. That suggests there remains room to improve the utility of the verifier-safe workflow. It does not invalidate the architecture. It says the current negotiation-plus-repair path is not utility-optimal.

The evidence structure is therefore:

This table is necessary because the paper’s most tempting misreading is also the easiest one: “The agentic LLM solved governance-constrained recommendation.” No. The architecture solved a narrower systems problem: how to prevent an LLM-generated slate from being served unless it passes explicit checks, and how to repair it when possible.

That is a better claim. It survives contact with engineering.

Why the certificate matters more than the explanation

Most consumer-facing recommendation explanations are not proof. They are vibes with bullet points.

“You may like this because you watched science fiction.” “This creator is popular among users like you.” “This playlist balances familiar and fresh content.”

Some of these explanations may be useful to users. They may also be incomplete, misleading, or entirely orthogonal to the actual ranking logic. PCN-Rec’s certificate serves a different function. It is not primarily a user-facing story. It is an operational artifact.

A certificate says: here is the slate, here are the fields needed to verify the policy constraints, and here is the machine-checkable structure that the verifier can parse. If the certificate claims three tail items but the metadata says there are only two, the verifier rejects it. If the certificate lists genres that do not correspond to the selected items, the verifier rejects it. If the slate violates a hard threshold, the verifier rejects it.

This is the architectural reason PCN-Rec has business relevance beyond MovieLens. Many companies already have recommender systems, policy rules, content metadata, and audit requirements. Their practical problem is not always “How do we make the LLM smarter?” It is often: “How do we prevent a plausible AI component from quietly bypassing a rule that legal, trust-and-safety, marketplace design, or partner contracts care about?”

The paper’s answer is a wrapper pattern:

1. Let the existing recommender generate candidates.
2. Let LLM agents negotiate the relevance-policy trade-off.
3. Require a structured certificate with every proposed slate.
4. Verify the slate in deterministic code.
5. Repair if possible.
6. Log the result.

That wrapper is not glamorous. It is deployable.

The business value is fewer silent violations, not free governance

For e-commerce, media, app stores, education platforms, creator feeds, and financial-content platforms, PCN-Rec points toward a realistic governance layer.

Suppose a marketplace wants to avoid showing only already-dominant sellers. A streaming platform wants genre variety. A learning platform wants recommendations to include both popular and under-discovered resources. A financial-content platform wants to ensure that certain categories of material are not overrepresented in a user’s feed. In each case, recommendation quality is no longer a single relevance score. It is relevance under policy.

PCN-Rec gives these organizations a way to separate three decisions that are often muddled together:

This separation is valuable because it makes failure diagnosable. If too many users are infeasible, the candidate generator or window size may be wrong. If certificates frequently fail, the LLM proposer is unreliable. If repaired slates lose too much utility, the repair method or constraint design needs work. If audits fail, the metadata or logging layer is suspect.

The ROI pathway is therefore not “LLMs recommend better.” It is more concrete: fewer silent policy violations, clearer audit artifacts, better diagnosis of infeasible policies, and safer integration of LLM flexibility into a recommender stack.

There is also a cost pathway. Larger candidate windows may increase computation. Metadata must be maintained. Constraint schemas must be designed. Repair logic must be tested. Logging must avoid exposing sensitive preference signals. Governance does not become free because someone put JSON near an LLM. It merely becomes inspectable.

Frankly, inspectable is already a promotion.

Where the paper’s boundaries matter

The paper is disciplined enough to state limitations that materially affect deployment. These limitations should not be sprinkled as generic caution confetti; they belong exactly where they change interpretation.

First, PCN-Rec guarantees compliance only when a compliant slate exists within the candidate window. This is a conditional guarantee. If the upstream candidate set is too narrow or too homogeneous, the verifier-safe workflow can return infeasible, not magic.

Second, the verifier only checks codified constraints. In the paper, those constraints are long-tail exposure, head-item limits, and genre diversity. A real platform may care about fairness across creator groups, content safety, regional regulation, age appropriateness, advertiser commitments, or multi-session exposure. PCN-Rec can inspire the interface, but each policy still has to be formalized.

Third, metadata quality becomes part of the trust boundary. If genre tags, head/tail labels, or other item attributes are wrong, the verifier can confidently verify the wrong thing. Deterministic enforcement is not truth. It is consistency with the available data and formal rules.

Fourth, the utility gap remains open. PCN-Rec’s NDCG@10 is lower than both the Single LLM baseline and the deterministic greedy reference in the reported experiment. This does not destroy the paper’s contribution, but it does suggest that future work should improve the utility of verifier-safe slate construction.

Finally, the experiment is on MovieLens-100K with specific governance constraints. It is a useful testbed, not a full simulation of modern recommendation platforms with billions of items, multi-stakeholder marketplaces, dynamic feedback loops, and adversarial content behavior. The mechanism is portable. The reported numbers are not.

What Cognaptus would take from this

The strongest practical reading of PCN-Rec is not that every company should replace its recommender with an agentic negotiation system tomorrow morning. That would be a very efficient way to create a meeting.

The better reading is that LLM-based recommendation should be designed around explicit contracts. A model may propose. It may negotiate. It may explain. It may help balance competing objectives. But when the output must satisfy hard platform rules, the final authority should be a verifier that executes the rules.

This architecture also clarifies how to build AI governance into business process automation more broadly. The same pattern appears in procurement approvals, financial document routing, customer-service escalation, compliance screening, and workflow recommendations:

• use AI to generate or rank candidate actions;
• require a structured proof object;
• verify hard constraints deterministically;
• repair or reject failed outputs;
• log the trace for audit.

PCN-Rec applies that pattern to recommendation. Its deeper value is the operating discipline: do not ask the model to be trustworthy when the system can be designed not to trust it.

That is the quiet upgrade. Not more fluent recommendations. Recommendations with receipts.

Cognaptus: Automate the Present, Incubate the Future.