CAP Theorem Meets LLMs: Correctness, Non-bias, and Utility Cannot Coexist

Forum topic · 二一 · 2026-05-13

Summary

A forum post discusses a proposed CAP-theorem-style trilemma for large language models, based on a paper by Vinu Ellampallil Venugopal titled 'A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination' (arXiv:2605.11672). The central claim: when a prompt is semantically underdetermined—meaning the given premises do not uniquely determine an answer—an LLM cannot simultaneously guarantee correctness, strict non-bias, and utility. To produce a useful answer, the model must introduce an unstated selection criterion, which constitutes unsupported bias; refusing to choose preserves non-bias but sacrifices usefulness. The post draws a detailed analogy with Eric Brewer's CAP theorem, mapping network partition to semantic underdetermination and consistency/availability to correctness/utility. It discusses implications for AI ethics, evaluation methodology, and system design: developers should make explicit trade-offs rather than assume all three properties can be achieved, much as database designers explicitly choose between consistency and availability.

CAP Theorem Meets LLMs: A Trilemma of Correctness, Non-bias, and Utility

The post opens with a nod to Feynman's lectures on quantum mechanics: problems arise when people apply a logic that doesn't belong to a domain. Here, ironically, a classic distributed-systems logic—the CAP theorem—turns out to map surprisingly well onto large language models.

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 proven and became a cornerstone of distributed systems design—an inherent structural limitation, not a bug.

A recent single-author paper proposes a bold conjecture: LLMs face a CAP-like trilemma. Under a condition called *semantic underdetermination*, an LLM cannot simultaneously guarantee correctness, strict non-bias, and utility—any two, but never all three.

What Is Semantic Underdetermination?

A prompt is *semantically underdetermined* when its premises are insufficient to uniquely determine an answer. Example: "Should I choose career A or career B?" Without knowing your interests, skills, finances, or family constraints, the model cannot answer meaningfully without introducing 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 training data.

Once the model introduces a criterion not specified by the user or supported by the premises, bias has been introduced.

The Formal Trilemma

| Property | Meaning | Failure mode | |---|---|---| | Correctness | Logically sound, factually accurate answers | Hallucinations, logical errors | | Strict Non-bias | No preference unsupported by premises | Tilted answers, implicit values | | Utility | Useful, direct, actionable answers | Refusals, vagueness, "it depends" |

Claim: under semantically underdetermined prompts, an LLM cannot satisfy all three. The conceptual proof:

1. A useful answer requires choosing among multiple plausible answers. 2. Multiple plausible answers mean the premises do not determine a unique one. 3. Choosing requires a criterion (preference, prior, value ordering). 4. The criterion is not user-supplied → it comes from the model's internal biases. 5. Therefore the answer contains an unsupported preference → it is biased. 6. If the model refuses to introduce a criterion (staying non-biased) → it must decline to choose → losing utility.

From CAP to LLMs

| CAP | LLM Trilemma | |---|---| | Network partition (P) | Semantic underdetermination | | Consistency (C) | Correctness | | Availability (A) | Utility | | — | Non-bias | | Choose C: return exact but possibly incomplete data | Choose Correct + Non-bias: answer correctly but make no choice ("there are multiple reasonable answers") | | Choose A: return data but possibly inconsistent | Choose Correct + Utility: give direct advice with implicit preferences | | — | Choose Non-bias + Utility: present multiple options fairly without guaranteeing optimality |

Why It Matters

For AI ethics: demanding absolute non-bias means sacrificing utility. A model that always says "it depends on your situation" is technically unbiased but useless.
For evaluation: current AI safety benchmarks assess correctness, fairness, and helpfulness separately, ignoring their inherent conflict. A low score on one axis may reflect a deliberate trade-off, not incompetence.
For design: like database engineers explicitly choosing C or A, LLM deployers must explicitly choose between "helpful but possibly implicitly biased" and "strictly unbiased but largely unhelpful"—and state that choice.

Closing Thought (Feynman-style)

The post ends by noting that CAP spawned an entire design philosophy: instead of blaming systems for imperfection, engineers state their trade-offs explicitly ("we chose consistency, so we may be unavailable during partitions"). If this trilemma is widely accepted, LLM discourse could shift similarly: no longer accusing models of bias, but declaring their policies—"this model favors safety and compliance under underdetermination" or "this model never decides for the user."

> "When you deceive yourself that you can have it all, you get nothing. When you admit you must choose, you begin to design something real."

---

Paper info

Title: A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination
Author: Vinu Ellampallil Venugopal
arXiv ID: 2605.11672
Published: May 12, 2026
Categories: cs.AI, cs.DB