Position: The Complexity of Perfect AI Alignment – Formalizing the RLHF Trilemma

Subramanyam Sahoo, Aman Chadha, Vinija Jain, Divya Chaudhary · 2025

Read Position: The Complexity of Perfect AI Alignment – Formalizing the RLHF Trilemma by Subramanyam Sahoo, Aman Chadha, Vinija Jain, Divya Chaudhary (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-19504.txt.

Introduction

Subramanyam Sahoo, Aman Chadha, Vinija Jain, and Divya Chaudhary argue that perfect alignment of language models through human feedback faces a hard three-way trade-off. Practitioners notice that more safety can cut fairness, serving varied populations gets costly, and robustness can amplify majority bias. The authors formalize that tension as an Alignment Trilemma.

Their complexity analysis claims no feedback system can be fully representative of diverse values, cheap to run, and robust to attack all at once. Tight representativeness plus robustness would need a number of operations that grows exponentially with context size. Current systems, they argue, quietly sacrifice representativeness by sampling small, similar annotator pools.

Catalog record

CREATORSubramanyam Sahoo, Aman Chadha, Vinija Jain, Divya Chaudhary
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-19504

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Position: The Complexity of Perfect AI Alignment – Formalizing the RLHF Trilemma Subramanyam Sahoo, Aman Chadha, Vinija Jain, Divya Chaudhary Abstract Reinforcement Learning from Human Feedback (RLHF) has become the dominant approach for aligning large language models, yet practitioners face a persistent puzzle: improving safety often reduces fairness, scaling to diverse populations becomes computationally intractable, and making systems robust often amplifies majority biases. We formalize this tension as the Alignment Trilemma : no RLHF system can simultaneously achieve (i) ε \varepsilon -representativeness across diverse human values, (ii) polynomial tractability in sample and compute complexity, and (iii) δ \delta -robustness against adversarial perturbations and distribution shift. Through a complexity-theoretic analysis integrating statistical learning theory and robust optimization, we prove that achieving both representativeness ( ε ≤ 0.01 \varepsilon\leq 0.01 ) and robustness ( δ ≤ 0.001 \delta\leq 0.001 ) for global-scale populations requires Ω ⁡ ( 2 d context ) \Omega(2^{d_{\text{context}}}) operations—super-polynomial in the context dimensionality. We demonstrate that current RLHF implementations resolve this trilemma by sacrificing representativeness, collecting only 10 3 10^{3} – 10 4 10^{4} samples from homogeneous annotator pools while requiring 10 7 10^{7} – 10 8 10^{8} samples for true global representation. Our framework provides a unifying explanation for documented RLHF pathologies including preference collapse, sycophancy, and systematic bias amplification. We conclude with concrete directions for navigating these fundamental trade-offs through strategic relaxations of alignment requirements. \workshoptitle Socially Responsible and Trustworthy Foundation Models 1 Introduction Consider the challenge facing an AI lab deploying a language model globally: annotators in San Francisco rate a response as “helpful” because it is direct and assertive, while annotators in Tokyo rate the same response as “harmful” because it violates cultural norms around politeness. To capture both perspectives, the lab needs more diverse training data—but this introduces inconsistency that makes the reward model noisy. To maintain robustness against this noise, they increase regularization, which pulls the model back toward majority preferences, erasing the minority view entirely. They have encountered the Alignment Trilemma : representativeness, tractability, and robustness cannot be jointly optimized 7 . Reinforcement Learning from Human Feedback (RLHF) has become the dominant paradigm for aligning large language models with human preferences. By training reward models on human preference judgments and fine-tuning policies to maximize learned rewards, RLHF has enabled dramatic improvements in perceived helpfulness, truthfulness, and safety 1 . Yet despite this empirical success, RLHF systems exhibit systematic pathologies: they amplify majority viewpoints 9 , collapse diverse preferences into single modes 2 , become sycophantic rather than truthful and fail under distribution shift. These failures are not engineering accidents—they are computational necessities. This paper formalizes the Alignment Trilemma through three key contributions: 1. Formal Framework (§5): We define \varepsilon -representativeness, polynomial tractability, and \delta -robustness as precise mathematical properties, and prove that no alignment procedure can simultaneously satisfy all three. 2. Complexity Characterization : We derive lower bounds showing that joint (\varepsilon,\delta) -alignment requires \Omega(\kappa\cdot 2^{d_{\text{context}}}/(\varepsilon^{2}n\delta)) operations, which is super-polynomial when context dimensionality d_{\text{context}}=\omega(\log n) . 3. Practical Analysis (§5.2–§5.4): We map how current RLHF implementations navigate the trilemma, explaining why standard design choices (small annotator pools, KL penalties, scalar rewards) sacrifice representativeness for tractability and partial robustness. Our work shifts the discourse from “ How do we fix RLHF? ” to “ Which trade-offs are we willing to accept? ” This reframing is essential for responsible deployment: understanding fundamental limits enables principled choices about where to invest computational resources and which stakeholders to prioritize. 2 Why This Problem Matters Now RLHF is no longer a research curiosity—it’s production infrastructure. Frontier models all rely on RLHF variants, serving hundreds of millions of users daily across 180+ countries. Yet the preference data training these systems comes from 10³ annotators, predominantly WEIRD populations 4 ; 5 ; 6 . As deployment scales globally while training remains centralized, the gap between who the system serves and who the system learns from widens catastrophically. Recent failures illustrate the stakes. • Bias amplification: Recent study found RLHF models assign >99% probability to majority opinions, functionally erasing minority perspectives. • Sycophancy: Sharma et al. 8 showed RLHF-trained assistants sacrifice truthfulness to agree with users’ false beliefs. • Preference collapse: 3 proved single-reward RLHF cannot capture multimodal preferences even in theory. The Alignment Trilemma explains why these aren’t isolated bugs but symptoms of a deeper impossibility. Without this understanding, patches (fairness regularizers, adversarial training, post-hoc calibration) repeatedly hit the same fundamental ceiling, wasting resources on approaches that cannot overcome computational limits. 3 Background: RLHF in Three Steps Reinforcement Learning from Human Feedback (RLHF) aligns language models through a three-stage pipeline: Stage 1: Supervised Fine-Tuning (SFT). Pre-train the policy \pi_{\theta} on human-written demonstrations via next-token prediction. Stage 2: Reward Modeling (RM). Collect preference labels over output pairs (\tau_{a},\tau_{b}) and train a reward model r_{\phi} to predict preferences by minimizing \mathcal{L}(\phi)=-\sum_{(a,b)}\log\sigma\big(r_{\phi}(\tau_{a})-r_{\phi}(\tau_{b})\big), (1) where \sigma(\cdot) denotes the sigmoid function. This produces a scalar reward r_{\phi}(\tau) scoring how “good” an output \tau is according to human raters. Stage 3: Policy Optimization. Fine-tune the policy to maximize the learned reward while staying close to the reference policy \pi_{\text{ref}} : \theta^{*}=\arg\max_{\theta}\left\{\mathbb{E}_{\tau\sim\pi_{\theta}}[r_{\phi}(\tau)]-\beta\,D_{\mathrm{KL}}(\pi_{\theta}\,\|\,\pi_{\text{ref}})\right\}, (2) where \beta>0 controls the strength of the KL penalty, which prevents reward hacking and mode collapse. Critical Design Choices. Current implementations use m\approx 10^{3}\text{--}10^{4} preference pairs, aggregate judgments via majority voting or weighted averaging, and set \beta sufficiently large to keep \pi_{\theta} close to the reference policy \pi_{\text{ref}} . These design choices enable tractable training but, as we show in later Section, systematically sacrifice representativeness. 4 The Alignment Trilemma A central challenge in aligning large-scale AI systems is the impossibility of simultaneously satisfying three desiderata: (i) capturing the full diversity of human values, (ii) ensuring computational tractability, and (iii) guaranteeing robustness to manipulation. We refer to this tension as the Alignment Trilemma . Any alignment strategy, particularly those relying on RLHF, must necessarily sacrifice at least one of these axes. Figure 1: Current Alignment Paradigm 4.1 Formal Definitions We begin by formalizing the three properties that constitute the trilemma. Definition 1 ( \varepsilon -Representativeness) . Let \mathcal{H} denote a population of humans, where each individual h\in\mathcal{H} has a value function V_{h}:\Pi\rightarrow\mathbb{R} that assigns a utility score to policies. A policy \pi\in\Pi is \varepsilon -representative with respect to \mathcal{H} if \big|\mathbb{E}_{h\sim\mathcal{H}}[V_{h}(\pi)]-\hat{V}(\pi)\big|\leq\varepsilon, (3) where \hat{V}(\pi) is the empirical estimate derived from the learned reward model r_{\phi} . Intuitively, \varepsilon -representativeness requires that the alignment procedure faithfully captures preferences drawn from a broad and diverse set of humans, ideally reflecting pluralistic moral perspectives across cultures, demographics, and contexts. Smaller \varepsilon corresponds to higher fidelity in representing the population’s true values. Definition 2 (Polynomial Tractability) . An alignment procedure \mathcal{A} that produces a policy \pi from a dataset D=\{(x_{i},y_{i})\}_{i=1}^{m} is polynomially tractable if both of the following conditions hold: 1. Sample complexity: m=\mathrm{poly}(d,1/\varepsilon,\log(1/\delta)), (4) where d is the problem dimension, \varepsilon is the representativeness error, and \delta is the failure probability. 2. Computational complexity: \mathrm{Ops}(\pi\,|\,D)=\mathcal{O}(\mathrm{poly}(m,d)). (5) This definition captures the requirement that the alignment procedure should be computationally feasible—learnable via gradient-based optimization with polynomial time complexity in the problem parameters—thereby allowing scaling to modern large models with billions of parameters. Definition 3 ( \delta -Robustness) . Let \mathcal{A} denote an adversarial perturbation space (including distribution shifts,

Read the complete text