PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Subramanyam Sahoo, Aman Chadha, Vinija Jain, Divya Chaudhary

arXiv:2511.19504v1cs.LGstat.ML

TL;DR

RLHF must balance representing diverse human values, computational tractability, and robustness to manipulation. The paper formalizes these competing goals and concludes that an alignment procedure satisfying any two must sacrifice the third.

  • Problem

    The paper asks whether RLHF can represent the full diversity of human values, remain computationally tractable, and guarantee robustness to manipulation at once.

    Source: §4 · p. 3

  • Method

    The paper formalizes ε-representativeness, polynomial tractability, and δ-robustness, then characterizes their joint limits and analyzes current RLHF design choices.

    Source: §1 · p. 2, §4.1 · pp. 3–4

  • Results

    Any alignment algorithm satisfying two of ε-representativeness, polynomial tractability, and δ-robustness must sacrifice the third.

    Source: §4.1 · p. 4

  • Takeaways & Limitations

    Current RLHF design choices—small annotator pools, KL penalties, and scalar rewards—trade representativeness for tractability and partial robustness.

    Source: §1 · p. 2

    The framing does not set quantitative thresholds for sufficient alignment, and its worst-case complexity sketches may overstate costs in specific settings.

    Source: §8 · p. 8

Abstract

from arXiv · show

Reinforcement Learning from Human Feedback (RLHF) is widely used 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) epsilon-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 (epsilon <= 0.01) and robustness (delta <= 0.001) for global-scale populations requires Omega(2^{d_context}) operations, which is super-polynomial in the context dimensionality. We show that current RLHF implementations resolve this trilemma by sacrificing representativeness: they collect only 10^3--10^4 samples from homogeneous annotator pools while 10^7--10^8 samples are needed for true global representation. Our framework provides a unified 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.

1 Introduction

The introduction frames global RLHF as a conflict among representing diverse values, computational tractability, and robustness, then presents the Alignment Trilemma as a formal account of that tension. It connects this conflict to documented RLHF failures and to the gap between global deployment and concentrated preference data.

1 Introduction

  • A culturally diverse preference set can make the reward model noisy, while stronger regularization pulls it toward majority preferences and erases minority views [1].The paper illustrates this with contrasting San Francisco and Tokyo judgments of the same response.Source: §1 · p. 1
  • The paper formalizes the Alignment Trilemma, proves the three goals cannot be jointly satisfied, derives complexity lower bounds, and analyzes how current RLHF choices trade representativeness for tractability and partial robustness.The analysis identifies small annotator pools, KL penalties, and scalar rewards as standard choices.Source: §1 · p. 2

2 Why This Problem Matters Now

  • Preference data comes from 10^3 annotators, predominantly WEIRD populations, while RLHF models serve hundreds of millions of users across 180+ countries.The paper says the gap between who systems serve and who they learn from widens as deployment scales globally while training remains centralized.Source: §2 · p. 2
  • Reported pathologies include majority-view amplification, preference collapse, sycophancy, and distribution-shift failure; Sharma et al. report assistants agreeing with users’ false beliefs.A recent study found RLHF models assigned >99% probability to majority opinions; proved single-reward RLHF cannot capture multimodal preferences even in theory.Source: §1 · pp. 1–2, §2 · p. 2
  • The paper argues these failures reflect a fundamental computational ceiling, so fairness regularizers, adversarial training, and post-hoc calibration repeatedly hit the same limit.It frames the practical question as which trade-offs to accept, rather than how to fix RLHF.Source: §2 · p. 2, §1 · p. 2

3 Background: RLHF in Three Steps

This section outlines RLHF’s three stages: supervised fine-tuning, reward modeling from pairwise preferences, and policy optimization. It then describes common design choices that make training tractable while sacrificing representativeness.

3 Background: RLHF in Three Steps

  • RLHF begins with supervised fine-tuning on human-written demonstrations, then trains a reward model on preference labels for output pairs to produce scalar scores.The reward model predicts preferences from pairs and scores outputs according to human raters.Source: §3 · p. 2
  • Policy optimization fine-tunes the policy to maximize learned reward while staying close to the reference policy; the KL penalty is described as preventing reward hacking and mode collapse.The penalty strength is controlled by β > 0.Source: §3 · p. 3
  • Current implementations use approximately 10^3–10^4 preference pairs, aggregate judgments by majority voting or weighted averaging, and choose sufficiently large β to keep πθ close to πref, enabling tractable training but sacrificing representativeness.Source: §3 · p. 3

4 The Alignment Trilemma

The Alignment Trilemma frames representation of diverse human values, computational tractability, and robustness to manipulation as goals that cannot all be achieved together. The section formalizes these properties and examines the trade-offs in current RLHF designs.

4.1 Formal Definitions

  • ε-representativeness concerns fidelity to a broad human population, tractability bounds sample and compute costs, and δ-robustness requires acceptable performance under worst-case perturbations.The section defines representativeness in terms of human value assessments and robustness over an adversarial perturbation space.Source: §4.1 · pp. 3–4
  • For sufficiently large populations and rich adversarial spaces, no polynomially tractable procedure can achieve all three properties; satisfying two requires sacrificing the third.In particular, ε-representativeness plus polynomial tractability requires δ → 1, meaning no robustness guarantee.Source: §4.1 · p. 4

4.2 Tractability & Robustness ⇒Narrow Value Capture (Sacrificing Representativeness)

  • δ ≈ 0.1–0.2 and ε > 0.3–0.5 across cultures describe the tractability and partial robustness achieved at the expense of representativeness in current designs.Small, comparatively homogeneous annotator pools and agreement-weighted aggregation narrow which values the reward model can represent.Source: §4.2 · pp. 4–5

4.3 Representativeness & Tractability ⇒Gaming (Sacrificing Robustness)

  • α ≈ 0.05 corrupted annotations can drive δ → 1, while broadening the feedback distribution also risks superficial overfitting to linguistic proxies.The section says representativeness and tractability improve as robustness degrades sharply.Source: §4.3 · p. 5

4.4 Representativeness & Robustness ⇒Intractability (Sacrificing Tractability)

  • Optimizing over all human preferences and worst-case perturbations supports representativeness and robustness but is computationally intractable; the inner minimization is NP-hard for general adversarial spaces.The section concludes that progress requires accepting degradation on one axis or redefining the desiderata.Source: §4.4 · p. 5

5 Implications for Alignment Research and Practice

The trilemma sets a scaling barrier for joint alignment and requires explicit choices about which guarantees to relax. The section pairs those trade-offs with research directions for preserving value pluralism.

5.1 The Scaling Wall

  • Beyond moderate population sizes (n ≳106) and context dimensionalities (dcontext ≳50), joint-alignment costs grow superpolynomially, while brute-force scaling brings diminishing and eventually negative returns.The section says heterogeneity increases adversarial surface area faster than robustness scales.Source: §5.1 · p. 6

5.2 Strategic Relaxations Are Unavoidable

  • Three relaxations are proposed: limit values to a core, restrict adversaries to plausible threats, or accept super-polynomial costs for critical applications.Examples include focusing on roughly 30 human-rights values, testing 102 realistic scenarios, or training a high-reliability system with 109 samples.Source: §5.2 · p. 6

5.3 Value Pluralism Requires Technical Innovation

  • The computational barrier motivates modular value architectures, active querying of disagreement, and structurally constrained robustness; these choices also affect who benefits and who is left out.For clustered populations, active learning is described as reducing sample complexity from Ω(n) to Ω(√n).Source: §5.3 · p. 6

6 Current State of the Field

Current RLHF pipelines use narrow, aggregated preference data and KL constraints for tractable training, but the supplied discussion connects these choices to preference collapse and trade-offs among alignment goals.

Current RLHF practice

  • Typical pipelines train scalar reward models on 10³–10⁴ pairwise comparisons, often from similar annotators, then fine-tune with a KL penalty that limits policy exploration.Majority voting or weighted averaging and the KL constraint are described as yielding stable training while collapsing reward learning toward majority opinions.Source: §6 · p. 7

Known limitations

  • A single scalar reward model cannot capture diverse, multimodal preferences, while human-feedback fine-tuning can encourage sycophancy when raters reward flattering answers.The discussion also notes reward hacking and over-optimization as practitioner concerns.Source: §6 · p. 7

Known trade-offs

  • RLHF can reduce output diversity, while efforts to improve robustness or inclusion can require substantially more gradient steps and human labels; proposed fixes introduce new assumptions.The section says the field lacks a unified theory explaining why these fixes appear to push the same trade-off boundary.Source: §6 · p. 7

7 Open Questions and Directions

The paper leaves open how to improve representativeness and robustness without intractable costs. It calls for theoretical models, richer empirical tests, and community-wide attention to subgroup and adversarial performance.

Open Problem

  • The open question is how to improve representativeness and robustness without intractable costs, including which values, adversaries, or context subsets to exclude through relaxation.Each relaxation introduces ethical choices and technical trade-offs, and how to navigate them remains unresolved.Source: §7 · p. 7

Theory and Practice Collaboration

  • The proposed research agenda pairs formal models of sample and compute costs with empirical tests on multicultural preference data and simulated poisoning.It also suggests interactive querying in areas of disagreement and hierarchical reward models separating group-level from individual-level preferences.Source: §7 · p. 7

Community Relevance

  • The discussion proposes evaluating subgroup distributional performance and adversarial robustness, alongside average reward, as research benchmarks for the community.It calls for RLHF testing at scale on diverse human data.Source: §7 · p. 8

8 Limitations

The paper describes its trilemma framing as abstract and not yet empirically validated, with worst-case complexity reasoning and an RLHF-centered scope.

Scope and thresholds

  • The framework sets no quantitative thresholds for sufficient representativeness, tractability, or robustness in practice.The paper asks, for example, how much demographic diversity is enough for deployment.Source: §8 · p. 8

Scope and assumptions

  • Worst-case complexity sketches may overstate costs for specific alignment settings, and the discussion focuses primarily on RLHF rather than other alignment paradigms.The paper notes that other paradigms may navigate the trilemma differently, though analogous trade-offs may arise.Source: §8 · p. 8

Empirical validation

  • The analysis is primarily normative and theoretical and does not yet empirically validate where current RLHF models fall within the trilemma space.Source: §8 · p. 8

9 Societal Impacts

The paper frames alignment complexity bounds as both a basis for informed deployment decisions and a risk of being misused to excuse inadequate alignment. It advocates disclosure, accessible verification tools, and governance involving affected communities.

9 Societal Impacts

  • The bounds could be misused to justify biased systems and may concentrate comprehensive alignment among well-resourced organizations.The authors warn this could marginalize academic researchers, startups, and Global South stakeholders.Source: §9 · p. 8
  • The authors advocate disclosing systems’ trilemma positions, building open-source verification tools, and involving affected communities in trade-off decisions.Disclosures would cover estimated ε across demographic groups, certified δ for specified adversaries, and alignment-budget allocation.Source: §9 · p. 8
  • They argue that computational constraints should lead to deliberate, justifiable ethical choices rather than accidental harms.They call for research on reducing exponential dependence on d_context and stratified sampling for heterogeneous populations.Source: §9 · p. 8

10 Conclusion

The conclusion presents representativeness, tractability, and robustness as competing alignment goals, with current practice prioritizing tractability and partial robustness over full value diversity. It calls for empirical and theoretical work on feasible trade-offs.

10 Conclusion

  • The authors conclude that RLHF cannot simultaneously maximize representativeness, tractability, and robustness.Source: §10 · p. 8
  • Current practice prioritizes tractability and partial robustness at the expense of full value diversity.The authors identify implications for fairness, bias, and safety as LLMs scale and deploy globally.Source: §10 · p. 9
  • The conclusion calls for experimentalists to map practical trade-off boundaries and theorists to formalize computationally feasible relaxed objectives.The authors present the framing as a starting point for community discussion about alignment trade-offs.Source: §10 · p. 9

NeurIPS Paper Checklist

The checklist affirms that the abstract and introduction accurately reflect the paper’s contributions and scope, identifying it as a position paper.

NeurIPS Paper Checklist

  • The checklist answers yes that the abstract and introduction accurately reflect the paper’s contributions and scope, and identifies it as a position paper.Its guidance says claims should match theoretical and experimental results and reflect generalization limits.Source: NeurIPS Paper Checklist · p. 11

2. Limitations

The checklist identifies the work as a position paper and marks several experiment- and asset-related items as not applicable, while affirming responses on limitations, theory, ethics, and societal impacts.

2. Limitations

  • The checklist says the paper discusses limitations and marks theoretical assumptions and proofs as complete.It describes the paper’s motivation as examining problems in current AI safety alignment methods.Source: §2 · p. 11
  • The checklist marks experimental reproducibility, training and test details, statistical significance, and compute-resource disclosures as not applicable because the paper has no experiments.Source: §2 · pp. 12–14
  • The checklist response is marked not applicable, and its justification is listed as not available; the cited passage provides no further explanation.Source: §2 · p. 13
  • The checklist answers yes on ethics and societal-impact discussion and says the work involved no human-subject research.Source: §2 · pp. 14, 16
  • The checklist describes the paper as a position paper in its response about documenting new assets.Source: §2 · pp. 15–16
Loading 2511.19504v1…