This post discusses a CAP-theorem-style conjecture for large language models, based on the paper *A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination* by Vinu Ellampallil Venugopal (arXiv:2605.11672, May 2026, cs.AI / cs.DB).
Background: The CAP Theorem
In 2000, Eric Brewer proposed the CAP theorem: in a distributed system, when a network partition (P) occurs, you must choose between consistency (C) and availability (A). The theorem was later formally proven and became foundational to distributed systems design—it is a structural limitation, not a bug.
The paper conjectures that LLMs face an analogous trilemma: under semantic underdetermination, an LLM cannot simultaneously guarantee correctness, strict non-bias, and utility.
What Is Semantic Underdetermination?
A prompt is semantically underdetermined when its premises are insufficient to uniquely determine an answer. For example: "Should I choose career A or career B?"—without information about interests, abilities, finances, or constraints.
To give a meaningful (useful) answer, the model must introduce a selection criterion—e.g., "pick the higher-paying one." Such criteria are not derived from the premises; they come from the model's internal priors or patterns in its training data.
Once the model introduces a selection criterion that the user did not specify and the premises do not justify—bias is introduced.
The Trilemma, Formalized
| Property | Meaning | Failure mode when lost | |---|---|---| | Correctness | Logically sound, factually accurate answers | Hallucinations, logical errors | | Strict Non-bias | No preference introduced beyond the premises | Leaning toward specific answers, implicit values | | Utility | Helpful, direct, actionable answers | Refusals, vagueness, "it depends" |
Conceptual proof sketch: 1. A useful answer requires choosing among multiple plausible answers. 2. Multiple plausible answers means the premises do not determine a unique one. 3. Choosing requires a criterion (preference/prior/value ordering). 4. The user did not provide the criterion → it comes from the model's internal bias. 5. Therefore the answer carries an unsupported preference → biased. 6. If the model refuses to choose (staying non-biased) → it must be vague or refuse → loses utility.
The CAP Analogy
| CAP | LLM Trilemma | |---|---| | Network partition (P) | Semantic underdetermination | | Consistency (C) | Correctness | | Availability (A) | Utility | | — | Non-bias | | Choose C: exact but possibly incomplete data | Choose Correct + Non-bias: accurate but non-committal ("there are multiple reasonable answers") | | Choose A: responsive but possibly inconsistent | Choose Correct + Utility: direct advice with implicit preferences | | — | Choose Non-bias + Utility: present all options fairly without guaranteeing optimality |
Implications
- For AI ethics: The goal of "unbiased AI" conflicts with usefulness in underdetermined scenarios. A model that never makes choices is technically unbiased but unhelpful.
- For AI evaluation: Current safety evaluations assess correctness, fairness, and helpfulness separately, ignoring their inherent conflict. A low score on one axis may reflect a deliberate trade-off favoring the other two, not lack of capability.
- For AI design: System designers should explicitly choose a trade-off rather than pretend all three are achievable—just as database designers explicitly pick between C and A. Deployers might state, e.g., "this model favors safety and compliance in underdetermined scenarios" or "this model never decides on the user's behalf."
- Title: A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination
- Author: Vinu Ellampallil Venugopal
- arXiv: 2605.11672
- Published: May 12, 2026
- Categories: cs.AI, cs.DB
Closing Thought (Feynman-style)
Like CAP, this is not a yellow card saying "you could do better"—it is a red card saying "the rules of the game make it impossible." If widely accepted, the trilemma could spawn a design philosophy for LLMs akin to CAP-inspired database design: stop blaming models for bias, and instead declare their trade-off policies openly.
---
Paper details