Neither Over- nor Under-Constrained: Evaluating LLM Personalization under a Constraint Qualification Audit

Introduction

LLMs demonstrate strong general-purpose capabilities across a wide range of tasks [11, 12]. Beyond generic performance, personalization has emerged as a crucial requirement for enhancing user satisfaction and enabling context-aware interactions. Specifically, personalization refers to tailoring LLM outputs to diverse user preferences, contextual signals, and implicit intents [21].

However, current evaluation paradigms fail to reliably evaluate LLM personalization, as they tend to either over-constrain or under-constrain the personalized response space, prematurely penalizing valid outputs or tolerating invalid ones (Figure 1). On one hand, reference-based metrics

(e.g., BLEU [13], ROUGE [3], BERTScore [20], MoverScore [23]) depend on proximity to rigid human references; they reject acceptable semantic variations while erroneously tolerating outputs with high surface overlap but critical personalization errors. On the other hand, LLM-as-a-judge frameworks (e.g., FactScore [10], GEMBA [7], PerSE [19]) can reason over flexible outputs, but they function as black-box evaluators that lack transparent and interpretable evaluation mechanisms. While recent constraint protocols (e.g., PREF [6], ExPerT [14]) enhance interpretability via a two-stage paradigm—extracting constraints from user profiles and assessing response adherence—they remain brittle: synthesized constraints often suffer from low fidelity, manifesting as redundancy, omissions, or hallucinated requirements.

To address both over- and under-constraining problems, we introduce ConQual-Audit, an audit-based framework that establishes calibrated, interpretable boundaries over the personalized response space via a principled constraint qualification mechanism (Figure 2). ConQual-Audit operates across three modular stages: First, it extracts original semantic constraints from both task-grounded reference and user preference. Second, it refines the extracted constraints through a counterexample-driven tripartite audit: (i) deduplicating redundant criteria; (ii) pruning unnecessary constraints by constructing personalized counterexamples that violate candidate criteria yet remain valid; and (iii) recovering missing constraints by synthesizing non-personalized counterexamples that satisfy all active criteria. Finally, it evaluates candidate responses against the audited constraint set via a premise–hypothesis inference formulation, and unifies constraint satisfaction and response attribution via their harmonic mean to jointly balance constraint coverage and response recall.

Empirical Verification. Extensive empirical evaluations across the PrefEval Zhao et al. [22] and LaMP (Salemi et al., [15]) benchmarks show the effectiveness of ConQual-Audit. Our framework establishes the highest evaluation performance, achieving top AUC scores (0.88 and 0.90) and the lowest overall false rates (FR = 0.21) while operating on the most compact constraint sets (2.36 and 2.97 per query). Crucially, we show that constraint qualification is model-agnostic and highly portable: integrating our audit module into existing evaluators (ExPerT and PREF) systematically remove unnecessary constraints, restore missing ones, and significantly reduce downstream evaluation errors at an amortized audit computational cost.

The primary contributions are three-fold:

• ConQual-Audit Framework: We propose a principled, three-stage audit-based framework for LLM personalization evaluation that overcomes both over- and under-constrained evaluation regimes through semantic constraint construction, qualification, and verification.

• Counterexample-Guided Qualification: We design a tripartite audit protocol that systematically deduplicates, prunes, and recovers constraints. This mechanism yields compact, calibrated constraint sets that attain top AUCs and the lowest overall false rates on LaMP and PrefEval.

• Modularity and Portability: We demonstrate that constraint qualification is model-agnostic: augmenting external constraint-based evaluators (ExPerT and PREF) with our audit module consistently improves constraint quality and lowers downstream false rates with minimal overhead.

Problem Formulation & Related Work

Problem formulation. We formalize LLM personalization evaluation (Salemi and Zamani, [16]; Kumar et al. [8]; Zhang et al. [21]; Dong et al. [5]) as a set-membership problem. Let $q$ be a query from a user with interaction history $H$, let $y^{\star}$ be a task reference for $q$, and let $\Omega$ be the set of all candidate responses to $q$. The user and the task determine the set of acceptable responses

where a response is acceptable if it follows the user’s preferences, as evidenced by $H$, and meets the task requirements specified by $y^{\star}$. Evaluating a response $y$ means deciding whether $y \in\mathcal{A}^{\star}$. Since $\mathcal{A}^{\star}$ is not observed, every evaluation method approximates it by an induced set $\widehat{\mathcal{A}}$; existing methods differ in how they construct it (Figure 1 and 2).

Reference-based evaluation (e.g., BLEU [13], ROUGE [3], BERTScore [20], MoverScore [23]) accepts responses that are similar to a set of human annotations $R \subset\mathcal{A}^{\star}$ via a similarity function $\operatorname{sim}$ and a threshold $\tau$:

Although annotations serve as effective anchors, they cannot encompass all forms of personalized responses. Consequently, they often reject valid responses that differ in wording from the annotations, while accepting invalid responses that happen to share similar vocabulary (such as negated answers).

LLM-as-a-judge (e.g., GEMBA [7], FActScore [10], PerSE [19]) asks an LLM $J$ [1, 4, 18, 17] to score a response given the user’s history:

LLM judges are not tied to references, but they score a response holistically, so the boundary of $\widehat{\mathcal{A}}_{\mathrm{llm}}$ is implicit in the judge and can be neither inspected nor audited.

Constraint evaluation (e.g., ExPerT [14], PREF [6]) describes $\mathcal{A}^{\star}$ by explicit constraints, such as rubric criteria in PREF or content aspects in ExPerT. They check responses against a constraint set $C$ and induce:

where $y \models c$ denotes that $y$ satisfies the constraint $c$; in practice, the conjunction is relaxed to a graded score. Since the constraints specify the required content of a response rather than the exact wording, this approach accepts a variety of valid responses, and evaluation results can be traced back to the underlying constraints.

However, the reliability of constraint-based evaluation depends on the quality of the constraints themselves; existing constraint-based evaluators often lack mechanisms to review these constraints during use, which can lead to the false acceptance of invalid responses or the false rejection of valid ones due to unqualified constraints.

Constraint Quality Analysis

A constraint evaluator errs when $\widehat{\mathcal{A}}(C)$ differs from $\mathcal{A}^{\star}$ (Figure 1). The difference consists of two error kinds: 1). False rejection $\operatorname{FR}(C)$ (i.e., the rejection of valid responses, constituting over-constraint); 2). False Acceptance $\operatorname{FA}(C)$ (i.e., the acceptance of invalid responses, constituting under-constraint).

Necessity and Sufficiency

$\widehat{\mathcal{A}}(C)$ is the intersection of all constraints, to reduce over-constraint and under-constraint problems, constraints should possess these two properties:

1. Individual necessity (no false rejections). $\operatorname{FR}(C) = \varnothing$ holds if and only if every constraint is satisfied by every valid response:

A constraint that some valid response violates is unnecessary; each unnecessary constraint adds its own false rejections.

2. Joint sufficiency (no false acceptances). $\operatorname{FA}(C) = \varnothing$ holds if and only if the constraints together admit only acceptable responses:

Unlike necessity, this property is for the whole set. A set that violates it is insufficient, because a necessary constraint that would exclude a falsely accepted response is missing.

Necessity gives $\mathcal{A}^{\star} \subseteq\widehat{\mathcal{A}}(C)$ and sufficiency the reverse inclusion, they together recover the acceptable set exactly.

Constraint Quality Impact on Evaluation

The constraint evaluators compute the satisfaction rate $s_C(y)$ and accept a response if $s_C(y) \ge\tau$:

Weighted criteria, as in PREF, follow an analogous continuous formulation. Let $n = |C|$ and $s = s_C(y)$. Modifying $C$ by adding a constraint $(+c)$ or removing one $(-c)$ perturbs the score by:

The direction and magnitude of this perturbation depend strictly on whether $y$ satisfies $c$ relative to its baseline score $s$. For a valid response $y^{+} \in\mathcal{A}^{\star}$ and an invalid response $y^{-} \notin\mathcal{A}^{\star}$, this establishes three theoretical links between constraint quality and evaluation error:

1. Unnecessary constraints inflate false rejections (FR$(\mathcal{C}) \uparrow$). When a constraint $c$ violates individual necessity (Eq. (6)), valid responses may violate it ($\mathbb{I}(y^{+} \models c) = 0$). Adding $c$ penalizes the valid response by $\Delta s_{+} = -s/(n+1) \leq0$. If $s-\Delta s_{+}<\tau$, this induces a false rejection. Conversely, pruning unnecessary constraints via qualification guarantees $\Delta s_{-}=s/(n-1)\geq0$, directly restoring valid responses above $\tau$.

2. Insufficient sets inflate false acceptances (FA$(\mathcal{C}) \uparrow$). If $\mathcal{C}$ violates joint sufficiency (Eq. (7)), a necessary constraint $c^{\star}$ that $y^{-}$ violates ($\mathbb{I}(y^{-}\models c^{\star})=0$) is omitted. The absence of $c^{\star}$ inflates the invalid response’s score by $\Delta s_{-}=s/(n-1)\geq0$. Omitting necessary constraint can decrease the threshold distance for invalid responses, leading to false acceptances.

Algorithm 1: ConQual-Audit

Input: $q$, $H$, $y^{\star}$, $\mathcal{Y}$; $G$, $J$, $V$

Output: Scores $\{(R_y,P_y,F1_y)\}_{y\in\mathcal{Y}}$

// 1. Construction

1 $\mathcal{C}^{p}\leftarrow G(q,H);\ \mathcal{C}^{a}\leftarrow G(q,y^{\star})$

// 2. Qualification (Alg. 2)

2 $\mathcal{C}\leftarrow\operatorname{QUALIFY}(\mathcal{C}^{p}\cup\mathcal{C}^{a})$

// 3. Verification

3 foreach $y\in\mathcal{Y}$ do

4 $\mathcal{C}^{E}_{y}\leftarrow\{c\in\mathcal{C}:V(y,c)=E\}$

5 $\{y^{E}_{c}\}_{c\in\mathcal{C}^{E}_{y}}\leftarrow V(S(y),\mathcal{C}^{E}_{y})$

6 $R_y\leftarrow|\mathcal{C}^{E}_{y}|/|\mathcal{C}|$

7 $P_y\leftarrow\operatorname{tok}(\bigcup_{c}y^{E}_{c})/\operatorname{tok}(S(y))$

8 $F1_y\leftarrow2P_yR_y/(P_y+R_y)$

9 return $\{(R_y,P_y,F1_y)\}_{y\in\mathcal{Y}}$

The ConQual-Audit Framework

A low-quality constraint set can lead to increased false rejections and false acceptances. Therefore, it is crucial to audit constraints before constraint validation. ConQual-Audit is proposed to evaluate LLM personalization under audited constraints. As shown in ALG. 1, ConQual-Audit proceeds in three stages: (1) construction (§ 4.1) derives original constraints from user preference and task reference; (2) qualification (§ 4.2) audits and improves necessity and sufficiency of the original constraints (§ 3.1); and (3) verification (§ 4.3) checks response against the audited constraints and computes evaluation result scores.

Constraint Construction

Each constraint is designed as a declarative proposition about the response, and $y \models c$ holds when $y$ entails $c$. A required $c$ is stated as a positive assertion (e.g., “The response recommends whole-food sources of protein.”), which is entailed only if the response provides the required content. A prohibited $c$ is stated as a negative assertion (e.g., “The response does not recommend protein powder.”), which is entailed when the response omits or explicitly rejects the corresponding content. Therefore, the constraints can be verified by natural language inference, during the constraint verification stage.

As shown in ALG. 1, preference constraints and answer constraints are constructed by a generator $G$ (line 1). Specifically, $G$ extracts the user’s interests from $H$, and derives one constraint for each thing the user prefers or avoids among the interests that apply to the query $q$. For the answer constraint, $G$ decomposes task-grounded reference $y^{\star}$ into atomic requirements, covering what a valid answer must provide and what it must avoid.

Constraint Qualification

Constraint qualification audits individual necessity (Eq. (6)) and joint sufficiency (Eq. (7)). Since $\mathcal{A}^{\star}$ is not observed, it tests them with counterexamples (ALG. 2): the generator $G$ produces a response $\tilde{y}$ subject to preset constraints; the verifier $V$ confirms that the constraints are satisfied; and the discriminator $J$ determines whether $\tilde{y}$ belongs to $\mathcal{A}^{\star}$ by verifying it against user preferences or task reference expectations. If no valid counterexample is found in $K$ attempts, the constraint is unchanged.

Specifically, Alg. 2 first applies a duplicated constraints check in line 1. If two constraints are duplicates, $c_i\equiv c_j$, the later one is removed. This does not change $\hat{\mathcal{A}}(\mathcal{C})$ but simplifies the constraints for following audits. Lines 2–4 audit unnecessary constraints (lines 2–4). For each $c$, $G$ generates a $\tilde{y}$ that satisfies every other constraint but violates $c$. If $J$ accepts it, then $\tilde{y}\in\mathcal{A}^{\star}$ and $\tilde{y}\not\models c$, so $c$ violates necessity and is removed. Each constraint is tested against those still kept. Finally, lines 5–8 imply missing constraints audit. For the task reference and user preference in turn, $G$ generates a $\tilde{y}$ that satisfies every constraint but breaks that exceptions. If $J$ rejects, then $\tilde{y}\in\mathrm{FA}(\mathcal{C})$, which violates sufficiency. $G$ then proposes new constraints from the broken requirements and $\tilde{y}$, and a proposal is added to exclude $\tilde{y}$ from other valid responses.

Constraint Verification and Metrics

Given the qualified set $C$, $V$ checks a response in two steps in ALG. 1. (1) Response verification (line 4). With $y$ as the premise and each constraint as a hypothesis, $V$ labels every constraint as ENTAILMENT, CONTRADICTION or NEUTRAL. The satisfied constraints are $C_y^E = \{c \in C : y \models c\}$. (2) Evidence attribution (line 5). For each $c \in C_y^E$, $V$ identifies the sentences $y_c^E \subseteq S(y)$ that support it, where $S(y)$ are the sentences of $y$. Then, lines 6–8 compute the evaluation results:

where $\operatorname{tok}(\cdot)$ counts word tokens.

The constraint recall $R_y$ is the score $s_C(y)$ of Eq. (8): it measures how many constraints the response meets, and a response is accepted if $R_y \ge\tau$. The response precision $P_y$ measures the share of the response devoted to these satisfied constraints and thus penalizes content that serves none of them. $F1_y$ is a balance between response precision and constraint recall. Further algorithm details about the counterexample generation and missing constraint update are referred to Appendix A.

Experimental Evaluation

We evaluate ConQual-Audit by addressing three core research questions:

RQ1 (Performance & Cost)(§ 5.2): Does ConQual-Audit minimize evaluation false rates more effectively than reference-based, prompt-based LLM judges, and constraint evaluation baselines, and what is its computational trade-off?

RQ2 (The Generalizability of Constraint Audit)(§ 5.3): Can ConQual’s qualification process be generalized as a model-agnostic filter to audit the constraints of other evaluators, and does it reduce their downstream decision errors?

RQ3 (Case Study)(§ 5.4): How does ConQual-Audit reshape decision boundaries to reflect both user preferences and task-grounded references?

Experimental Setup

Benchmarks. We evaluate on two benchmarks: (1) LaMP (Salemi et al., [15]) (tasks 1, 2, and 4; 3,000 responses per task), testing semantic discrimination against surface form by evaluating 10 paraphrased positive answers, 10 negated answers, and 10 incorrect answers per user across 100 users; and (2) PrefEval (Zhao et al., [22]) (200 responses across 100 users), testing explicit preference compliance via paired Qwen3-14B (Team, [18]) generations conditioned with and without the user’s preference.

Baselines. We compare against nine baselines across three families: (1) reference-based metrics on LaMP (BLEU-4 (Papineni et al., [13]), ROUGE-L (Lin, [9]), BERTScore (Zhang et al., [20]), MoverScore (Zhao et al., [23])); (2) LLM judges (GEMBA (Kocmi and Federmann, [7]), PerSE (Wang et al., [19]), FactScore (Min et al., [10])); and (3) constraint evaluators (ExPerT (Salemi et al., [14]), PREF (Fu et al., [6])). We also evaluate audited variants (ExPerT-Audit, PREF-Audit) via ConQual’s qualification stage (§ 4.2) to test constraint audit generalizability.

Metrics and Implementation. Responses are accepted at threshold $\tau\ge0.5$. We report False Rejection Rate (FRR), False Acceptance Rate (FAR), their mean False Rate (FR), AUC, mean score margins, number of evaluated constraints, and end-to-end token costs. To isolate methodological gains from model capability, all LLM judges and ConQual modules ($G$, $V$, $J$) use Qwen3-8B (Team, [18]). ConQual-Audit uses $K = 2$ counterexample attempts, one gap-repair round per constraints, and at most three new constraints per repair.

Algorithm 2: Constraint Qualification.
Input: Constraints C; q, H, y* and G, J, V
Output: Qualified constraints C
// Duplicated
1 foreach i < j with c_i ≡ c_j do
    C ← C \ {c_j}
// Unnecessary (necessity)
2 foreach c ∈ C, while |C| > 1 do
3   ỹ ← ADVERSE(C \ {c}, {c}, ·)
4   if ỹ ≠ ⊥ ∧ J(ỹ) = PASS then
      C ← C \ {c}
// Missing (sufficiency)
5 foreach r ∈ {REF, PREF} do
6   ỹ ← ADVERSE(C, ∅, r)
7   if ỹ ≠ ⊥ ∧ J(ỹ) = FAIL then
8      C ← C ∪ UPDATE(C, ỹ)
9 return C

ConQual-Audit: Minimizing False Rate

ConQual-Audit achieves the lowest overall false rate across both benchmarks. As shown in Table 1 and Table 2, ConQual-Audit reduces overall classification error to FR = 0.21 on both datasets—a 16% reduction over the strongest baseline on LaMP (PREF: 0.25) and a 28% reduction on PrefEval (PerSE: 0.29)—while dominating in AUC (0.90 and 0.88). This improvement stems from calibrated error control. On LaMP, ConQual-Audit halves the false rejection rate of PREF (FRR = 13% vs. 26%) at a comparable false acceptance rate (FAR = 29% vs. 25%), while evaluating roughly half as many constraints (2.97 vs. 5.43). On PrefEval, it reduces false acceptances (FAR = 28% vs. 45% for PerSE) without inflating false rejections (FRR = 15% vs. 13%). Crucially, ConQual-Audit widens the score margin between positive and negative responses to 0.57 on both benchmarks—nearly double any competing baseline ($\le0.30$ on LaMP, $\le0.32$ on PrefEval). Because audited constraints isolate necessary and sufficient conditions, valid paraphrases systematically satisfy them while invalid responses directly violate them.

Table 1: Results averaged over LaMP-1, LaMP-2 and LaMP-4. Best in bold, second underlined.

Method	Pos.$\uparrow$	Neg.$\downarrow$	AUC$\uparrow$	FRR$\downarrow$	FAR$\downarrow$	False Rate$\downarrow$	Tokens$\downarrow$	#Cons.
BLEU-4	0.35	0.16	0.79	0.65	0.14	0.39	0.0	–
ROUGE-L	0.65	0.46	0.70	0.22	0.46	0.34	0.0	–
BERTScore	0.95	0.92	0.74	0.00	1.00	0.50	28.3	–
MoverScore	0.65	0.57	0.76	0.08	0.79	0.44	29.0	–
GEMBA	0.52	0.30	0.67	0.47	0.26	0.36	198.3	–
PerSE	0.41	0.26	0.66	0.62	0.20	0.41	1,212.6	–
FActScore	0.48	0.53	0.48	0.52	0.53	0.53	1,506.6	–
ExPerT	0.07	0.00	0.54	0.92	0.01	0.46	3,027.0	3.47
PREF	0.61	0.31	<u>0.84</u>	0.26	0.25	<u>0.25</u>	649.1	5.43
ConQual-Audit	0.77	0.20	0.90	0.13	0.29	0.21	1,827.4	2.97

Method	Pos.$\uparrow$	Neg.$\downarrow$	AUC$\uparrow$	FRR$\downarrow$	FAR$\downarrow$	False Rate$\downarrow$	Tokens$\downarrow$	#Cons.
GEMBA	0.90	0.68	<u>0.82</u>	0.03	0.84	0.44	670.1	–
PerSE	0.87	0.55	0.81	0.13	0.45	<u>0.29</u>	1,889.2	–
FActScore	0.60	0.58	0.52	0.35	0.62	0.49	37,430.2	–
ExPerT	0.08	0.06	0.53	0.97	0.04	0.50	9,663.9	8.23
PREF	0.92	0.81	0.79	0.02	1.00	0.51	1,641.9	5.11
ExPerT-Audit	0.06	0.09	0.45	0.94	0.04	0.49	24,790.6	6.67
PREF-Audit	0.91	0.74	0.78	0.03	0.89	0.46	16,006.7	3.64
ConQual-Audit	0.80	0.23	0.88	0.15	0.28	0.21	12,628.5	2.36

Reference-based metrics confuses surface similarity with compliance. The acceptance sets $\hat{A}_{\mathrm{ref}}$ (Eq. (2)) exhibit severe failures: lexical metrics penalize benign stylistic rephrasing, falsely rejecting 65% of valid answers on LaMP (BLEU-4 FRR = 0.65), whereas semantic embedding metrics mistake embedding proximity for alignment, accepting 100% of negated or incorrect responses (BERTScore FAR = 1.00, MoverScore 0.79).

Prompt-based LLM judges misplace the decision boundary. Unconstrained LLM judges relying on implicit boundaries $\hat{A}_{\mathrm{llm}}$ (Eq. (3)) fail to calibrate across task distributions. While GEMBA and PerSE show reasonable ranking capability on PrefEval (AUC 0.81–0.82), they set overly permissive boundaries that accept 84% and 45% of non-compliant outputs (FAR). On LaMP, this behavior inverts into extreme conservatism, falsely rejecting 47% and 62% of correct answers (FRR). Decomposing responses into unweighted atomic facts (FActScore) fails entirely, hovering near chance on both benchmarks (AUC 0.48–0.52).

Constraint criteria violate necessity and sufficiency. Constraint baselines introduce high false rates by generating criteria that either over- or under-specify the solution space. ExPerT conditions constraints strictly on reference tokens; because gold references are often abstract criteria (PrefEval) or brief sentences (LaMP), valid candidate answers naturally omit arbitrary reference details. Its constraints set thus violate necessity (Eq. (6)), falsely rejecting 92% (LaMP) and 97% (PrefEval) of valid outputs (FRR). Conversely, PREF constructs generic rubric criteria easily satisfied by standard generation quality regardless of preference adherence (mean negative score 0.81); its constraints violate sufficiency (Eq. (7)), accepting every negative response on PrefEval (FAR = 1.00). Both evaluate more than twice as many constraints as ConQual-Audit (5.11–8.23 vs. 2.36), yet yield the highest false rates (FR $\ge0.50$).

Inference cost and amortized verification. On PrefEval, ConQual-Audit consumes 12.6k tokens per response end-to-end, higher than single-prompt judges (GEMBA: 0.7k, PerSE: 1.9k), but one-third of atomic-decomposition methods (FActScore: 37.4k) and substantially less than auditing unvetted external criteria (ExPerT-Audit: 24.8k, PREF-Audit: 16.0k). Over 80% of this compute ($\sim10.1$k tokens) is front-loaded into one-time constraint synthesis and qualification per instruction. The runtime verification step requires only 2.5k tokens per candidate response, readily amortizing across multiple model outputs ($N > 1$). On LaMP, end-to-end cost scales down to 1.8k tokens per response, falling between PREF (0.6k) and ExPerT (3.0k). This focused compute investment directly delivers the lowest (FR = 0.21 across both benchmarks.

Generalization of Constraint Audit

Because ConQual’s audit (§ 4.2) operates over the explicit constraints, it can function as a model-agnostic filter for other constraint-based evaluators. To test its portability, we apply the audit to the response aspects generated by ExPerT and the rubric criteria produced by PREF, re-scoring responses with each method’s native verifier under both original and audited constraints (Table 2). Table 3 details the resulting constraint reductions, classification AUC, and false rates.

	ExPerT		PREF
	Orig.	Audit	Orig.	Audit
#Cons.	8.23	6.67	5.11	3.64
Removed / added	1.78 / 0.22		1.51 / 0.05
AUC $\uparrow$	0.53	0.45	0.82	0.78
FRR $\downarrow$	0.96	0.94	0.02	0.03
FAR $\downarrow$	0.04	0.04	1.00	0.89
FR $\downarrow$	0.50	0.49	0.51	0.46
Reproduced	99.8%		77%

Eliminating false constraints can reduce the false rate. The audit systematically identifies and removes unnecessary or over-constraint constraints: it prunes 1.78 of ExPerT’s 8.23 aspects (−19%) and 1.51 of PREF’s 5.11 criteria (−29%), while rarely adding new ones (+0.22 and +0.05, respectively). Operating on these audited constraint sets reduces overall classification error: the false rate (FR) drops from 0.50 to 0.49 for ExPerT and from 0.51 to 0.46 for PREF. For PREF, this improvement directly addresses its primary failure mode identified in Table 2, reducing its false acceptance rate (FAR) down from 1.00 to 0.89 while keeping false rejections at a very low level (FRR: 0.02 → 0.03).

Decouple constraint quality from evaluation randomness. To isolate the intrinsic value of constraint pruning from downstream evaluator noise, we analyze a counterfactual setting where verifier decisions on unchanged constraints remain fixed. Under this controlled ablation, removing audited constraints strictly improves classification performance: PREF’s AUC increases from 0.82 to 0.84 (FR drops to 0.45), while ExPerT’s FR falls from 0.50 to 0.47 at a steady 0.53 AUC. In the end-to-end re-evaluation reported in Table 3, these gains are masked by test-retest instability in the underlying LLM judges: PREF’s verifier reproduces only 77% of its decisions on identical criteria across runs, introducing a baseline drift of $\pm$0.03 AUC that accounts for the nominal drop to 0.78. Thus, while the audit effectively cleans the constraint space, end-to-end performance remains constrained by the variance of third-party scoring backends.

Inference overhead and ConQual’s efficiency advantage. The primary trade-off of the audit process is computational cost. Because counterexample generation and verification consume 5–6k tokens per constraint, overhead scales linearly with the size of the unevetted constraint set. Auditing ExPerT (8.7 aspects per response) and PREF (5.1 criteria per prompt) inflates end-to-end inference to 24.8k and 16.0k tokens per response, respectively—overhead that is only marginally offset by downstream scoring speedups (8%–25% fewer verification tokens). By contrast, ConQual constructs and audits a compact set of only 3.9 global constraints once per question. Consequently, ConQual-Audit achieves higher accuracy (AUC 0.88, FR 0.21) at lower total compute (12.6k tokens). The audit thus functions as an effective off-the-shelf refiner for third-party criteria, but delivers its best cost-accuracy profile when integrated into ConQual’s unified pipeline.

ConQual-Audit: Case Study

Figure 3 illustrates a case study from PrefEval benchmark of ConQual-Audit. How it reshapes the decision boundary to jointly enforce user-specified preferences and task-grounded references.

The user specifies a negative preference against ’physical sports ’in team-building activities, while the gold reference suggests ’non-physical alternatives’, such as ’problem-solving exercises’ or ’creative collaborations’. The construction produces four candidate constraints: a user-specified preference against physical sports ($\mathrm{pc}_1$) with three task-grounded reference criteria ($\mathrm{ac}_1$–$\mathrm{ac}_3$).

Without constraint qualification, an invalid candidate proposal for a ’Team Sports Day’ satisfied two constraints ($\mathrm{ac}_2$, $\mathrm{ac}_3$) but violated two other sports-related constraints ($\mathrm{pc}_1$, $\mathrm{ac}_1$), and could be thus falsely accepted. This problem is resolved by ConQual-Audit qualification with counterexamples: because omitting creative collaborations ($\mathrm{ac}_3$) leaves a response fully acceptable, $\mathrm{ac}_3$ is pruned as unnecessary. Evaluated on the qualified three-constraint set ($\mathrm{pc}_1$, $\mathrm{ac}_1$, $\mathrm{ac}_2$), the invalid candidate is identified and rejected, while valid candidates are correctly accepted.

Conclusion

In this work, we presented ConQual-Audit, an audit-based framework for evaluating LLM personalization through semantic constraint construction, qualification, and verification. ConQual-Audit synthesizes candidate constraints grounded jointly in user preferences and task references, systematically auditing them for individual necessity and joint sufficiency, pruning unnecessary constraints to minimize false rejections while repairing missing constraints to prevent false acceptances. By evaluating candidate responses via the harmonic mean of constraint satisfaction and response attribution, ConQual-Audit establishes a calibrated decision boundary that resolves both over- and under-constrained failure modes.

Empirical evaluations across PrefEval and LaMP show that ConQual-Audit achieves state-of-the-art performance, attaining top AUC scores (0.88 and 0.90) and the lowest overall false rate (FR = 0.21 on both datasets) while operating on the most compact constraint sets (2.36 and 2.97 per query). Although constraint qualification requires an upfront token investment, this cost readily amortizes during runtime verification across multiple candidate generations. Furthermore, our case study demonstrates that qualification structurally realigns the decision boundary: pruning unqualified constraint details prevents auxiliary criteria from diluting core constraints and triggering false acceptances.

Finally, our findings confirm that constraint qualification is model-agnostic and portable: applying the audit to existing evaluators (ExPerT and PREF) systematically refines their constraint sets and consistently lowers downstream false rates. These results demonstrate that unvetted constraint extraction routinely dilutes explicit user preferences with superficial task artifacts, establishing systematic constraint auditing as a principled foundation for reliable personalization evaluation.

Acknowledgments

AI tools were used solely for language refinement. All scientific contributions are authors’ original work. This research is supported by the Technology Innovation Institute, Abu Dhabi, UAE.

Limitations

ConQual-Audit depends on the models that play the generator, the verifier and the judge. In our experiments a single Qwen3 model fills all three roles, so their errors are correlated. Qualification is also costly. It raises the cost per PrefEval response from 3.4k to 12.6k tokens end to end, and ConQual-Audit has the highest online time of the evaluators we compare (27 s per response). The framework needs a reference answer and an explicit preference to construct constraints, so it does not apply to open-ended requests that lack them. It scores a response by the share of satisfied constraints, all weighted equally, at a fixed threshold. Finally, our evaluation covers English benchmarks with constructed positive and negative responses. Results may differ for other domains, languages and response distributions.

LLM Instruction Templates

Algorithm 3: Functions of Algorithm 2. ADVERSE returns a response that satisfies every constraint in $A$ and violates every constraint in $B$ (or, with $B = \emptyset$, breaks requirement $r$), or $\perp$ after $K$ attempts. UPDATE asks $G$, given $J$’s explanation $J(\tilde{y})$, for at most three new constraints of the kind that $r$ calls for and returns those that exclude $\tilde{y}$ (and, for answer constraints, hold for $y^*$).

Input: $q$, $H$, $y^*$ and $G$, $J$, $V$ as in Algorithm 1; attempts $K$

1. Function ADVERSE$(A, B, r)$:

2. &nbsp;&nbsp;for $k = 1, \ldots, K$ do

3. &nbsp;&nbsp;&nbsp;&nbsp;$\tilde{y} \gets G(q, A, B, r)$ if &nbsp;&nbsp;&nbsp;&nbsp;$\forall c \in A : V(\tilde{y}, c) = \mathrm{E}$ and &nbsp;&nbsp;&nbsp;&nbsp;$\forall c \in B : V(\tilde{y}, c) \in\{\mathrm{C}, \mathrm{N}\}$ then &nbsp;&nbsp;&nbsp;&nbsp;return $\tilde{y}$

4. &nbsp;&nbsp;return $\perp$

5. Function UPDATE$(C, \tilde{y}, r)$:

6. &nbsp;&nbsp;$M \gets y^*$ if $r = y^*$ else $H$ &nbsp;&nbsp; // reference material of $r$

7. &nbsp;&nbsp;$C^+ \gets G(q, C, \tilde{y}, J(\tilde{y}), M)$ &nbsp;&nbsp; // $|C^+| \le3$, kind of $r$

8. &nbsp;&nbsp;$C^+ \gets\{c \in C^+ : V(\tilde{y}, c) \in\{\mathrm{C}, \mathrm{N}\}\}$

9. &nbsp;&nbsp;if $r = y^*$ then &nbsp;&nbsp;&nbsp;&nbsp;$C^+ \gets\{c \in C^+ : V(y^*, c) = \mathrm{E}\}$

10. &nbsp;&nbsp;return $C^+$

Adversarial generation. Both audits rest on counterexamples written by the generator $G$ (ADVERSE in Algorithm 3). $G$ receives the query $q$, a set $A$ of constraints the response must satisfy, and a target to break: either a set $B$ of constraints (over-constraint pruning, $B = \{c\}$) or an alignment requirement $r \in\{p, y^*\}$ (gap repair, $B = \emptyset$, where the response must break the stated preference or disagree with the reference). It writes a complete, plausible answer of at most 200 words. The verifier $V$ then checks the response against $A \cup B$, and it is used only if $V$ labels every constraint in $A$ as entailed and every constraint in $B$ as contradicted or neutral (a neutral label means the response omits the required content, so it does not satisfy the constraint). Otherwise $G$ tries again, up to $K = 2$ times; if no attempt passes, ADVERSE returns $\perp$ and the constraint set is left unchanged. A valid counterexample is then judged by $J$, which decides separately whether it is aligned with the preference and with the reference and explains each decision.

Constraint update. When $J$ finds that a gap-repair counterexample $\tilde{y}$ satisfies every current constraint yet breaks a requirement $r$, the constraint set admits a misaligned response, and UPDATE closes the gap for each broken requirement. $G$ receives $q$, the current constraints $C$, $\tilde{y}$, $J$’s explanation of the failure, and the material $r$ rests on: the reference $y^*$ when $\tilde{y}$ disagrees with it, or the user’s stated preferences $H$ when it breaks them. It proposes at most three new constraints of the matching kind (answer constraints from $y^*$, preference constraints from $H$) that $\tilde{y}$ violates, that every acceptable response would satisfy, and that do not restate a current constraint. A proposed constraint is added only if $V$ confirms that it excludes $\tilde{y}$ (contradicted or neutral); an answer constraint must also be entailed by $y^*$ itself, so that the repair never rejects the reference. Each requirement gets one repair round.