No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems
Khoat Than
Abstract
In this paper, we establish a set of theoretical impossibility results, termed the No-Free-Fairness theorems, that identify three fundamental sources of disparity in learning systems. First, we show that when a task exhibits irreducible cost on a subgroup, any decision rule must trade off overall performance with disparity, yielding an inherent fairness--cost frontier. Second, we prove that even in ideal, noise-free settings where a perfectly fair and accurate solution exists, finite-sample learning alone induces nontrivial subgroup disparity, ruling out distribution-free fairness guarantees. More seriously, enforcing strict relative fairness creates a statistical bottleneck: achieving low cost may require exponentially many samples. Third, we show that limitations of the model class can independently induce disparity: if the model cannot represent accurate solutions for a subgroup, fairness remains unattainable regardless of data or training procedure. Overall, these results demonstrate that unfairness is not solely a consequence of biased data or suboptimal optimization, but arises from the intrinsic structure of decision problems, the constraints of finite data, and the expressivity of models. Our framework applies broadly beyond standard supervised learning, and suggests that achieving fairness requires explicit trade-offs and should be treated as a core design consideration.
AI Impact Assessments
(1 models)Scientific Impact Assessment: "No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems"
1. Core Contribution
The paper establishes three "No-Free-Fairness" theorems identifying fundamental sources of disparity in learning systems: (1) task-inherent irreducible cost creates fairness-cost frontiers, (2) finite-sample learning induces disparity even in realizable settings, and (3) model class limitations independently cause disparity. The key distinguishing feature is the use of the risk ratio (relative fairness) rather than absolute disparity, which the authors argue better captures proportional harm in low-risk regimes and aligns with regulatory standards like the EEOC's Four-Fifths Rule.
2. Methodological Rigor
The mathematical rigor varies significantly across the three results:
Theorems 1 and 3 are mathematically straightforward—almost tautological. The proofs consist of decomposing expected cost as a(h) = p_b·a_b(h) + (1-p_b)·ε·a_b(h) and applying elementary bounds. The author acknowledges Theorem 1 has a "surprisingly simple proof." The core insight—that if a subgroup has irreducible cost, total cost is bounded below as a function of disparity—follows immediately from the definition of population risk. Theorem 3 is structurally identical, replacing the Bayes-optimal subgroup cost with the best-in-class cost. While the statements are correct, their depth is limited.
Theorem 2 is the most technically substantive contribution. The minimax construction—partitioning X into m ≥ 2n regions, randomly labeling unseen partitions—follows a standard technique in learning theory lower bounds but is applied effectively to the fairness setting. The resulting bound E[ε_S] ≥ 1/4 even under realizability is non-trivial.
Corollary 1 (exponential sample complexity under strict relative fairness) is the most interesting derived result, showing that maintaining c(n) = 1/log(n) forces n ≥ e^{Ω(1/ν)} to achieve E[a(h_S)] ≤ ν. However, this exponential complexity arises partly from the parameterization choice of the floor c(n), making the practical significance somewhat ambiguous.
3. Potential Impact
The paper addresses an important conceptual question—whether unfairness is eliminable through better data or algorithms—and provides a negative answer under specific formalizations. The unified three-axis framing (data, algorithm, architecture) is pedagogically useful and could influence how practitioners think about fairness as a design constraint rather than a post-hoc fix.
However, practical impact may be limited for several reasons:
4. Timeliness & Relevance
Fairness in ML remains a high-priority research area, especially as LLMs and generative AI proliferate. The paper is timely in arguing that fairness limitations are structural rather than merely data-driven. The risk ratio perspective is well-motivated given regulatory trends. However, the impossibility result literature in fairness is already substantial (Chouldechova 2017; Kleinberg et al. 2017; Pinzón et al. 2022), and the marginal contribution over these works is modest.
5. Strengths & Limitations
Strengths:
Limitations:
Additional Observations
The paper would benefit from: (1) concrete examples showing the bounds are approximately tight, (2) discussion of when the bounds are vacuous, and (3) comparison of the risk ratio framework's implications against known polynomial convergence results for absolute disparity to clarify whether the exponential bottleneck is a genuine phenomenon or an artifact of the metric choice. The single-author nature limits the breadth of perspectives, and some claims (e.g., regarding LLMs) would benefit from more rigorous formalization.
Generated Jun 17, 2026
Comparison History (22)
Paper 2 likely has higher scientific impact: it offers broadly applicable theoretical impossibility results (“No-Free-Fairness”) that formalize inherent trade-offs among accuracy, finite-sample effects, and model expressivity. Such limits can reshape how multiple fields (ML, statistics, policy, algorithmic fairness, and law) frame and evaluate fairness interventions, and are timely given widespread deployment of decision systems. Paper 1 is innovative and potentially valuable for scientific discovery in PDE analysis, but its impact is narrower (primarily applied math/physics) and depends more on empirical success and adoption of a new tooling paradigm.
Paper 2 likely has higher impact due to strong real-world and clinical applicability (precision oncology), a timely intersection of foundation models and spatial transcriptomics, and the creation of a large multi-organ dataset (HumanST-1k) that could become a community resource. The ST-guided, pathway-informed alignment is a concrete methodological innovation with broad potential across computational pathology, bioinformatics, and multimodal ML. Paper 1 is conceptually important and broadly relevant, but as theory-focused impossibility results it may have more indirect downstream uptake compared to an enabling dataset+framework with clear translational pathways.
Paper 2 establishes foundational theoretical limits ('No-Free-Fairness') for algorithmic fairness, analogous to the famous 'No Free Lunch' theorems. Its mathematical formalization of the intrinsic trade-offs between accuracy, sample size, model capacity, and fairness addresses a critical, timely issue in AI. Because algorithmic fairness impacts cross-disciplinary fields including machine learning, ethics, law, and public policy, Paper 2 has a significantly broader scope and higher potential for foundational scientific impact compared to the algorithmic advancements in blind inverse problems presented in Paper 1.
Paper 1 establishes fundamental impossibility theorems (No-Free-Fairness) for learning systems, demonstrating intrinsic limits and trade-offs across all models and data sizes. Such foundational theoretical limits typically have profound, long-lasting, and broad scientific impact across multiple disciplines within and beyond ML. While Paper 2 is highly timely and relevant to current LLM paradigms, Paper 1's results dictate theoretical boundaries for any learning system, offering wider and more enduring scientific significance.
Paper 1 (TRACE) presents a novel and practical framework that bridges autoregressive language models with causal discovery, establishing a theoretical duality between next-token prediction and causal identification. It addresses a concrete, unsolved problem at scale (vocabularies up to 29,100), demonstrates strong empirical results (20+ F1 improvement), and has immediate real-world applications in diagnostics and manufacturing. Paper 2 provides valuable impossibility theorems for fairness but is primarily theoretical and confirmatory of intuitions already present in the fairness literature. TRACE's methodological innovation and practical scalability suggest broader and more transformative impact.
Paper 1 addresses a critical, highly timely issue in AI (fairness) by establishing fundamental mathematical limits and trade-offs. Its theoretical rigor and broad applicability across all learning systems give it a foundational quality likely to influence a wide range of future research and policy. In contrast, Paper 2 presents a more niche methodological contribution focused specifically on meta-classifying one-class classification models, which has a narrower scope and lower potential for widespread, cross-disciplinary impact.
Paper 1 establishes fundamental theoretical impossibility results for fairness in learning systems, analogous to classic no-free-lunch theorems. It identifies three irreducible sources of disparity (irreducible cost, finite samples, model expressivity) with broad implications across all of machine learning and AI policy. This kind of foundational theoretical contribution tends to have lasting, wide-ranging impact by shaping how the field conceptualizes fairness trade-offs. Paper 2 makes a solid empirical contribution to understanding LLM belief coherence, but addresses a narrower problem with more incremental methodological advances.
Paper 2 establishes fundamental theoretical limits on fairness in machine learning, offering foundational insights akin to the No-Free-Lunch theorems. While Paper 1 provides a highly practical and timely engineering contribution for efficient model deployment, Paper 2's broad applicability across all learning systems and its establishment of intrinsic trade-offs give it a more profound and enduring scientific impact across multiple disciplines.
Paper 1 establishes fundamental impossibility theorems for fairness in learning systems, identifying three irreducible sources of disparity (irreducible cost, finite-sample constraints, model expressivity). These results have broad implications across all of machine learning and AI policy, providing theoretical foundations similar in spirit to no-free-lunch theorems. The breadth of applicability, combined with the timeliness of fairness concerns in AI deployment, gives it higher impact potential. Paper 2 makes a solid contribution to understanding modularity in continual learning but addresses a narrower question with more limited cross-field relevance.
Paper 1 establishes fundamental theoretical limits (impossibility theorems) for algorithmic fairness, akin to the foundational 'No Free Lunch' theorems. Its conclusions about intrinsic structural, data, and expressivity constraints apply broadly across all machine learning disciplines, fundamentally shaping future research in AI ethics and model design. In contrast, Paper 2 presents incremental enhancements and a regional case study for weather forecasting. While practically useful for meteorology, Paper 2 lacks the broad, cross-disciplinary foundational impact and sweeping novelty of Paper 1's theoretical framework.