The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems

• URL: http://arxiv.org/abs/2605.23024v1
• Date: Thu, 21 May 2026 20:48:35 GMT
• Title: The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems
• Abstract summary: This thesis turns impossibility results from curiosities into design rules.<n>Its flagship result proves an accuracy ceiling set by architecture alone.<n>The same argument recasts across subfields.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models now write software, draft legal documents, and produce clinical notes, yet fundamental limits, from Turing and Arrow to the No Free Lunch theorems, shape what computation can do. This thesis turns such impossibility results from curiosities into design rules. Its flagship result proves an accuracy ceiling set by architecture alone: past a critical reasoning depth, no amount of training moves it, at any adapter rank, sample size, or loss function. Computable before deployment from layer count and embedding width, this Deterministic Horizon is measured between nineteen and thirty-one across twelve transformer architectures, and fine-tuning on optimal-length traces recovers under four percentage points. The mechanism is a capacity invariant of the residual stream, and an information-theoretic conversion yields super-exponential accuracy decay past the horizon. An unconditional circuit-complexity lower bound for modular exponentiation against constant-depth prime-modulus circuits complements this result. The same argument recasts across subfields: preference learning under any misspecified model jumps discontinuously in sample complexity; multi-stage retrieval pipelines require at least as many independent metrics as stages; standard truthful auctions fail for agents with prompt-dependent valuations; and zero-knowledge verification of neural inference pays a measured overhead of one hundred ten to one hundred ninety times per non-linear activation. Together these form a catalogue of sixteen specifications, each pairing a computable boundary, a quantified violation cost, and a constructive design rule: two compositions are proved, one pairing is an honest obstruction, and four remain open. The impossibility-specification methodology is offered for the generative research programme that trustworthy AI may need. Every fundamental limit of AI is also a design rule.

Related papers

• Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate [47.36630149538994]
  In high-dimensional online prediction, the best predictor may depend on only a few features, so regret should scale with sparsity rather than the ambient dimension.<n>Warmuth and Amid asked at COLT 2023 whether any of three such rules admits a competitive online regret guarantee.<n>Our analysis identifies a common obstruction: cheap nuisance causes the refit to underweight the truly predictive coordinate.
  arXiv  Detail & Related papers  (2026-08-18T09:32:03Z)
• Reading Calibrated Uncertainty from Language Model Trajectories [46.663987199083245]
  Methods that probe the model's internal activations feed raw hidden states into opaque snapshots and leave implicit the layer-wise trajectory by which a representation is formed.<n>We extract eleven scale-invariant geometric features, tracing the cumulative path of per-layer updates, and feed them to a sparse linear probe.<n>The probe outperforms MSP under selective abstention, with baseline scaling with up to 21 AURC points.
  arXiv  Detail & Related papers  (2026-05-19T19:24:29Z)
• Forgetting That Sticks: Quantization-Permanent Unlearning via Circuit Attribution [3.6704226968275253]
  We show gradient-based methods that achieve meaningful forgetting lose it under compression, while methods that survive quantization barely change the model.<n>We present MANSU, which resolves both modes by combining causal circuit attribution to isolate the minimal forget-set subgraph.<n>We additionally introduce Circuit Attribution Divergence (CAD), a mechanistic verification metric distinguishing structural erasure from behavioral suppression.
  arXiv  Detail & Related papers  (2026-05-14T17:44:10Z)
• Tokens-per-Parameter Coverage Is Critical for Robust LLM Scaling Law Extrapolation [45.56738584872585]
  Neural scaling laws approximate a language model's loss as a power-law function of parameter count $N$ and token count $D$.<n>We show that a collinear design induces an inherent ill-conditioning in the Gauss-Newton least-squares problem.<n>We prove this for four scaling-law formalisms and derive a closed-form TPP-diversity threshold that is necessary and sufficient for well-conditioned estimation.
  arXiv  Detail & Related papers  (2026-05-08T23:00:17Z)
• INCRT: An Incremental Transformer That Determines Its Own Architecture [0.0]
  INCRT (Incremental Transformer) is an architecture that determines its own structure during training.<n>Each growth decision is driven by a single, online-computable geometric quantity.<n>Experiments on SARS-CoV-2 variant classification and SST-2 sentiment analysis confirm both results.
  arXiv  Detail & Related papers  (2026-04-12T15:56:47Z)
• JANUS: Structured Bidirectional Generation for Guaranteed Constraints and Analytical Uncertainty [0.0]
  JANUS (Joint Ancestral Network for Uncertainty and Synthesis) is a framework that unifies capabilities using a DAG of Bayesian Decision Trees.<n>Key innovation is Reverse-Topological Back-filling, an algorithm that propagates constraints backwards through the causal graph.<n>Janus achieves state-of-the-art fidelity (Detection Score 0.497), eliminates mode collapse on imbalanced data, and provides exact handling of complex inter-column constraints.
  arXiv  Detail & Related papers  (2026-03-04T05:36:11Z)
• Large Language Models Are Bad Dice Players: LLMs Struggle to Generate Random Numbers from Statistical Distributions [50.1404916337174]
  We present the first large-scale, statistically powered audit of native probabilistic sampling in large language models (LLMs)<n>We show that batch generation achieves only modest statistical validity, with a 13% median pass rate, while independent requests collapse almost entirely.<n>We conclude that current LLMs lack a functional internal sampler, necessitating the use of external tools for applications requiring statistical guarantees.
  arXiv  Detail & Related papers  (2026-01-08T22:33:12Z)
• On the Fundamental Limits of LLMs at Scale [15.459708840379975]
  Large Language Models (LLMs) have benefited enormously from scaling, yet these gains are bounded by five fundamental limitations.<n>This work presents a unified, proof-informed framework that formalizes the innate theoretical ceilings of LLM scaling.<n>We show how likelihood-based training favors pattern completion over inference, how retrieval under token limits suffers from semantic drift and coupling noise, and how multimodal scaling inherits shallow cross-modal alignment.
  arXiv  Detail & Related papers  (2025-11-17T01:55:33Z)
• Datarus-R1: An Adaptive Multi-Step Reasoning LLM for Automated Data Analysis [0.0]
  We present Datarus-R1-14B, a language model fine-tuned from Qwen 2.5-14B-Instruct to act as a virtual data analyst and graduate-level problem solver.<n>Datarus is trained not on isolated question-answer pairs but on full analytical trajectories including reasoning steps, code execution, error traces, self-corrections, and final conclusions.
  arXiv  Detail & Related papers  (2025-08-18T21:58:18Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• Neuro-Symbolic Entropy Regularization [78.16196949641079]
  In structured prediction, the goal is to jointly predict many output variables that together encode a structured object. One approach -- entropy regularization -- posits that decision boundaries should lie in low-probability regions. We propose a loss, neuro-symbolic entropy regularization, that encourages the model to confidently predict a valid object.
  arXiv  Detail & Related papers  (2022-01-25T06:23:10Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.