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

This paper formalizes an Alignment Trilemma, proving that no RLHF-based alignment strategy can simultaneously achieve $\epsilon \backslash varepsilon$-representativeness, polynomial-time tractability, and $\delta \backslash delta$-robustness, with any two of these goals implying exponential cost in the third.

➡️ Key Highlights of the Alignment Trilemma Framework:
🧠 Formalization of Alignment Constraints: The paper rigorously defines $\epsilon \backslash varepsilon$-representativeness (alignment fidelity across diverse human values), polynomial tractability (sample and compute complexity), and $\delta \backslash delta$-robustness (resilience to adversarial perturbations). It proves that satisfying all three simultaneously is impossible for large populations and high-dimensional context spaces, i.e., achieving both small $\epsilon \backslash varepsilon$ and $\delta \backslash delta$ requires $\mathrm{\Omega }(2^{d_{\text{context}}})\backslash Omega(2^\{d\_\{\backslash text\{context\}\}\})$ operations.

📈 Complexity-Theoretic Lower Bounds on Scalability: The authors show that alignment requires operations scaling as $\mathrm{\Omega }(\kappa \cdot 2^{d_{\text{context}}}\mathrm{/}({\epsilon }^{2}n\delta ))\backslash Omega(\backslash kappa\; \backslash cdot\; 2^\{d\_\{\backslash text\{context\}\}\}\; /\; (\backslash varepsilon^2\; n\; \backslash delta))$, where $d_{\text{context}}\gg \log nd\_\{\backslash text\{context\}\}\; \backslash gg\; \backslash log\; n$. This implies that as model context spaces or population diversity grow, alignment becomes super-polynomial in cost, rendering naive scaling approaches ineffective for global representational alignment.

⚖️ Practical Trade-off Analysis in Current RLHF Pipelines: The study maps how existing RLHF systems navigate the trilemma: choosing small, homogeneous annotator pools (typically ${10}^{3}10^3$–\(10^4\) samples) and strong KL penalties to maintain tractability and partial robustness, at the cost of representativeness. This design leads directly to known pathologies such as sycophancy, reward hacking, and collapse of minority values—shown here to be inevitable outcomes of trilemma constraints.