A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination

Technical Summary: A CAP-like Trilemma for Large Language Models

Problem Statement
This paper identifies a structural tension in Large Language Model (LLM) response generation analogous to the CAP theorem in distributed systems. While the CAP theorem posits that consistency, availability, and partition tolerance cannot be simultaneously guaranteed during network partitions, this work argues that LLMs face a similar impossibility under semantic underdetermination.

A prompt is defined as semantically underdetermined when the available facts, assumptions, and premises ($F_x$) are insufficient to logically entail a unique answer. In such scenarios, user queries (e.g., "Which candidate should be selected?" or "Which city is better?") request a singleton decision, yet the premises do not specify the decision criterion required to justify that choice. The paper posits that an LLM cannot simultaneously guarantee three desirable properties in these contexts:

1. Strong Correctness ($C_{strong}$): The output is strictly entailed by the available premises ($F_x \models y$).
2. Strict Non-bias ($NB_{strict}$): The model does not privilege one candidate over another unless that preference is explicitly justified by $F_x$. Bias is defined broadly here as any unsupported selection preference, prior, or normative criterion.
3. Decisive Utility ($U_{decisive}$): The response provides a concrete, actionable answer rather than refusing, hedging, or asking for clarification.

Methodology
The paper employs a formal logical framework to articulate this trilemma, drawing a direct analogy to the Gilbert-Lynch formalization of the CAP theorem.

• Formal Definitions: The authors define the set of premise-compatible answers $S_x = \{a \in A \mid a \text{ is compatible with } F_x\}$. A prompt is underdetermined if $|S_x| > 1$.
• Logical Formulation: The core conjecture is formalized as $D(x) \Rightarrow \neg(C_{strong} \land NB_{strict} \land U_{decisive})$. This implies that if a prompt is underdetermined, it is impossible to satisfy all three conditions simultaneously.
• Pairwise Analysis: The paper analyzes the pairwise trade-offs:
  • $C_{strong} \land NB_{strict} \Rightarrow \neg U_{decisive}$: To remain correct and unbiased, the model must refuse or ask for clarification, reducing utility.
  • $NB_{strict} \land U_{decisive} \Rightarrow \neg C_{strong}$: To be useful and decisive while remaining neutral, the model may present unsupported equivalences that weaken correctness.
  • $C_{strong} \land U_{decisive} \Rightarrow \neg NB_{strict}$: To provide a correct, decisive answer, the model must introduce a selection criterion; if this criterion is not supplied by the user, it functions as an unsupported bias.
• Case Studies: The methodology is illustrated through three examples:
  1. Scholarship Selection: Choosing between students based on GPA and financial need without a specified weighting rule.
  2. Subjective Recommendation: Ranking cities based on unstated user priorities (e.g., job market vs. safety).
  3. Normative Decision: Prioritizing profit vs. employee well-being without a defined ethical framework.

Key Contributions

1. The CAP-like Conjecture: The primary contribution is the formulation of the "Correctness–Non-bias–Utility Trilemma." This shifts the focus from viewing LLM failures solely as model limitations (e.g., hallucination or training data bias) to recognizing them as structural consequences of underdetermined decision requests.
2. Redefinition of Bias: The paper expands the definition of bias beyond demographic or social prejudice to include "selection-theoretic bias." In underdetermined settings, any mechanism that selects a single answer from multiple valid options without explicit user justification constitutes a bias.
3. Formalizing Refusal: The work reframes model refusal or clarification requests not as failures of helpfulness, but as consistency-preserving strategies analogous to a distributed system refusing a request during a network partition to avoid inconsistency.
4. Design Policy Proposal: The authors propose a practical policy $\pi(x)$ for managing these trade-offs, suggesting that models should:
   • Answer directly if $|S_x| = 1$.
   • Ask for clarification if $|S_x| > 1$ and no criterion is supplied.
   • Provide conditional answers if multiple criteria are plausible.
   • Recommend with stated assumptions if utility strictly requires a decision.

Results and Claims
The paper does not present empirical experimental results but offers a theoretical proof by contradiction. It demonstrates that for any underdetermined prompt with multiple valid answers, satisfying all three properties leads to a logical contradiction.

• Theoretical Result: A decisive answer ($y \in S_x$) requires the introduction of a value function or criterion $\theta$. If $\theta$ is not in $F_x$, the answer is not strongly correct ($F_x \not\models y$). If $\theta$ is hidden, the answer is biased. If $\theta$ is explicit but the model refuses to choose, utility is reduced.
• Implication for Alignment: The paper argues that current alignment efforts, which often treat truthfulness, harmlessness, and helpfulness as independently maximizable goals, may be fundamentally flawed in underdetermined contexts. A "useful" answer often necessitates a preference, and a "neutral" answer often necessitates a refusal.

Significance
The paper claims that understanding this trilemma is critical for the next generation of LLM alignment and deployment.

• Reframing Failures: It suggests that many perceived model failures are structurally induced by the nature of the prompt rather than model incompetence.
• Transparency over Neutrality: It argues that the goal should not be to eliminate the trade-off but to make it explicit. Models should prioritize "conditional correctness" and "transparent non-bias" (disclosing the assumptions used) over "decisive utility" when premises are insufficient.
• Systemic Impact: As foundation models are deployed in high-stakes downstream tasks, recognizing that a "balanced" answer may actually be an unsupported equality claim is vital for preventing the propagation of hidden normative frameworks.

In conclusion, the paper asserts that alignment strategies must evolve to study how correctness, non-bias, and utility trade off under semantic underdetermination, rather than attempting to maximize them independently.