Fundamental Limits

Follow this topic Ask about this topic

Momentum

9 papers in the last four weeks, up 29% on the four weeks before. 0.1% of all new papers.

Jul 6Week of Sep 21

Latest papers 61

Oct 1, 2026cs.RO

Watch, Infer, Coordinate: Inferring Robot Partner Constraints for Zero-Shot Coordination

Robots operating in the physical world will increasingly need to coordinate with other robots, particularly in manipulation tasks where an object may be too large or heavy for a single robot to carry alone. Physical limitations caused by hardware degradation or actuator faults can restrict the actions a robot can reliably execute, yet these limitations may be unknown to its partner. We study whether a helper can infer a robot partner's physical constraints from observing it coordinate with another robot, then use the inferred capability to coordinate with the same partner on a new task. This is difficult because a demonstration shows what the constrained robot did, but not what it could have done. In physically coupled tasks, the other robot may also compensate for its limitations, making those limitations difficult to identify from the constrained robot's behavior alone. Our key insight is that these constraints shape the joint behavior of the team, making the actions of both robots informative about the constrained partner's capability. We introduce Watch, Infer, Coordinate, a benchmark spanning three physically coupled manipulation settings, together with an inference approach that scores candidate constraints using observed joint behavior. Across all three settings, our method substantially improves constraint inference and zero-shot coordination, approaching an oracle with access to the true constraints.

Suyu Ye, Zheyuan Zhang, Vaishnav Tadiparthi +5

Honda Research Institute USA · Johns Hopkins University

Human-Robot Collaboration Fundamental Limits Stance

Sep 30, 2026stat.ML

Target-Dependent Limits of Causal Repair: A Leading-Log Frontier in a Gaussian Model

Knowing how much a causal predictor could improve need not reveal the gain of the repair actually learned. We quantify this gap in a scalar Gaussian causal experiment with known intervention geometry: auxiliary data identify effect magnitude up to bounded contamination, while diagnostics identify direction. The target is the squared-loss gain of the realized trained repair relative to a fitted reference. Jointly optimizing the learner and assessor under uniform learning MSE

η

avoids the trivial solution of making no repair. At the usual

1/k

learning scale, every feasible learner incurs a

k^{-2}

assessment floor, even when oracle potential is estimable at a faster rate. In the magnitude-rich regime, we characterize a sharp leading-log frontier: the assessment exponent is

\min{\ell_k,2kη_k/U}

to first relative order, where

\ell_k=\log(1/(k^2E_k))

and

E_k

is auxiliary precision. A diagnostic-abstention rule attains this exponent with unknown nuisance parameters. We also bound the critical allowance window and transfer the frontier to adaptive sampling by exact Gaussian simulation. Finite-grid experiments distinguish sign-tail suppression from total MSE and expose conservative finite-budget behavior. The result isolates how the assessment target changes information requirements in this experiment; it is not a general causal identifiability claim.

Qinchuan Cheng, Jiaqi Liu, Ruixuan Xie

Xi’an Jiaotong University · Sichuan University · Southwestern University of Finance and Economics

Causal Inferences Repair Finite-Sample Fundamental Limits Gaussian Primitives Frontiers

Sep 30, 2026cs.CV

Structural Limits of the Information-Theoretic Uncertainty Decomposition

Uncertainty estimation in machine learning typically decomposes uncertainty into aleatoric uncertainty (AU) and epistemic uncertainty (EU) using the standard information-theoretic framework. However, in practice, two critical issues arise: entanglement (AU and EU are highly correlated) and epistemic collapse (EU magnitude shrinks with increasing model capacity). We analyze this framework on a functional level and discover that significant portions of the assumed AU, EU range are infeasible in finite settings, and cannot be attained with any class probabilities. We characterize how this infeasible region scales with the number of classes and Monte Carlo samples

N

(e.g., from ensembles with

N

members), revealing it is bounded by

\text{AU} \leq \log(2)/N

. Crucially, the infeasible region's boundary helps explain epistemic collapse: when model confidence is high,

\text{AU} > \text{EU}

is guaranteed by this fundamental structural limitation. Our findings show that increasing ensemble size mitigates epistemic collapse by reducing the infeasible area. Lastly, we caution against interpreting AU and EU as independent quantities in low AU regimes, since we show they are coupled when

\text{AU} \leq \log(2)/N

.

Jakob Lønborg Christensen, Christian F. Baumgartner, Morten Rieger Hannemose +2

DTU Compute Technical University of Denmark · Faculty of Health Sciences and Medicine University of Lucerne

Dynamic Epistemic Logic Uncertainty Fundamental Limits Entanglement Decomposition

Sep 30, 2026cs.RO

The Planning Limits of Latent World Models

World models offer a promising way to help robots understand how the physical world evolves and plan complex behaviours through imagination. Yet existing studies mainly demonstrate what these models can accomplish, leaving unclear when their predictions remain useful for planning and where they fail. We study this question using action-conditioned predictors built on five frozen self-supervised visual backbones: V-JEPA 2, V-JEPA 2.1, VideoMAEv2, VideoPrism, and DINOv2. We use frozen backbones to test representations intended to transfer across environments. We evaluate these models on diverse Meta-World manipulation tasks and real-robot interactions from BridgeData V2. We find that a world model guides action selection reliably only when the goal lies within, or slightly beyond, the trajectory it imagines during planning. With five-step rollouts, the length the predictor was trained on, the world model ranks actions reliably only for targets five to ten control steps ahead, whereas task goals lie 16 to 53 steps away. Neither an 81-fold larger predictor nor longer-rollout training extends this range; the encoder affects both range and closed-loop success, with V-JEPA 2.1 performing most consistently. More fundamentally, the limit persists under perfect prediction: using the real simulator, success falls from 92% to 41% as the target moves from five to twenty steps ahead of a five-step rollout. Planning therefore requires either longer imagined trajectories or closer subgoals. For distant goals, pure imagination succeeds in 23% of episodes, planning with feedback (MPC) raises success to 30%, imagining as far as the goal to 47%, and nearby expert subgoals to 76%. Used within its plannable range, a world model can also improve a vision-language-action (VLA) policy: choosing among eight actions the VLA proposes raises its success from 65% to 77% across 16 different tasks.

Ali Alrasheed, Basim Azam, Naveed Akhtar

The University of Melbourne, Australia

Latent World Models World Models Action Prediction World Planning Fundamental Limits+1

Sep 29, 2026cs.RO

Faster and Better? Benchmark Bugs and Design Limitations Distort the Evaluation of Vision-Language-Action Acceleration

Simulated manipulation benchmarks are the standard tool for evaluating vision-language-action (VLA) policies and the acceleration methods that reduce their inference latency for on-robot deployment. On these benchmarks, we observe that some training-free acceleration methods, which approximate the baseline policy's computation, achieve higher measured success rates than the baseline itself. Success rates alone cannot establish whether such gains come from better task execution or from evaluation flaws. We therefore investigate two kinds of benchmark flaws behind these gains: bugs, where the implementation does not match the intended task or evaluation protocol, and design limitations, where success criteria and simulation settings do not fully capture how acceleration affects task execution. Starting from tasks with anomalous gains, we localize root causes by plotting object trajectories against checker acceptance regions, and classify the resulting bugs into task consistency, initialization, and reproducibility. Extending this audit to seven benchmarks, including RoboTwin, LIBERO-Plus, and VLABench, we identify 22 bugs of these types and 4 design limitations. For the latter, we revise permissive success checkers, correct unrealistic object masses, and add a motion-aware score that favors smoother actions. Experiments show that bug fixes can reverse method rankings, moving the baseline from last to first on one task. Addressing design limitations can likewise remove anomalous gains: on another task, the baseline moves from 21 percentage points behind an accelerated method to 5 points ahead. Gains attributed to acceleration can therefore be artifacts of the benchmark rather than better task execution. We release our bug fixes and revised benchmark settings to support trustworthy evaluation of VLA acceleration.

Qiwei Chen, Kaijun Zhou, Nuohui Shi +3

Shanghai Jiao Tong University

Acceleration Fundamental Limits

Sep 29, 2026cs.CV

Why Cross-Skeleton Retargeting Is Non-Identifiable: Structural Limits of Generative Motion Models

Cross-skeleton motion generation trains generative models to carry action structure and motion intention from one body to another. Yet a target motion that shows the right action has two explanations that the training data cannot tell apart: the model transferred the source clip, or it recovered a typical motion for the requested action. We show that this ambiguity is structural rather than incidental: under standard generative objectives, the source-conditioned retargeting map is non-identifiable in sparse heterogeneous motion domains. Unpaired distribution matching yields gauge non-identifiability: the latent spaces of different skeletons can be transformed relative to one another without changing the training evidence, so different source-conditioned maps fit it equally well. Sparse paired supervision admits the complementary failure mode, \emph{conditional-mean degeneration}: when clips are paired only by action, squared-error training converges to an average target motion that ignores the source clip. To make the missing evidence observable, we introduce Source-Instance Fidelity (SIF), a diagnostic that tests whether outputs differ from one another the way their source clips do, with the target skeleton and action held fixed. Under this diagnostic, methods that succeed at the standard action-level test on animal motion data often sit at the source-blind floor, while the methods that rise above it retain only a partial relational signal. Retargeting therefore needs objectives and evaluations that can identify the source-conditioned map it claims to learn. Project page: https://cross-skeleton-retargeting.netlify.app/.

Zhiyuan Li, Wenyan Yang, Pekka Marttinen +1

Department of Electrical Engineering and Automation, Aalto University, Finland · Department of Computer Science, Aalto University, Finland

Cross-Embodiment Retargeting Skeleton Camera-Conditioned Video Generation Fundamental Limits

Sep 28, 2026cs.SE

MCP Error Messages Written for Developers Hurt the Most Capable Agents Most

Many Model Context Protocol (MCP) servers wrap web APIs built for human developers, and their error messages tell the reader to run a command, edit a configuration, open a web page or wait. Many agents that read them can only call the server's tools. In 150 widely used MCP servers, 949 of 3,001 error messages tell the caller what to do next, and half of these steps depend on something the server cannot see about the caller. On credential errors, 62 of 67 steps ask for a terminal command, a configuration change or a web page; on rate limits, 20 of 30 say to wait and retry without naming the call to repeat. We tested five OpenAI models that act only through the tools of Berkeley Function Calling Leaderboard tasks, and the agents did what the step said. On expired credentials, a terminal command in the step left 45% of tasks recovered, and the loss it caused grew from 18 points for GPT-5.5 to 69 for GPT-6 Astra. On a rate limit, GitHub's "Wait before retrying." left 6%. We tested two remedies. For MCP developers, naming a server tool in the step raised recovery on expired credentials to 84%, with the login tool in place of the command, and on a rate limit to 88%, with the call to repeat in place of the bare wait. For agent developers, deleting the step with a one-sentence prompt before the model reads it raised recovery on expired credentials to 82%.

Xiaonan Xu, Wenjing Wu

College of Computing, Georgia Institute of Technology, Atlanta, GA 30332, USA · Department of Computer Science, University of Colorado Boulder, Boulder, CO 80309, USA

Model Context Protocol Fundamental Limits

Sep 24, 2026cs.DC

Concurrent Split Learning Through Stable Client Clustering

Training with a fixed global batch limits how many distributed clients can provide examples in any one step. We examine a way to use additional server workers without increasing the batch processed by an individual workload. Global Clustered Parallel Split Learning (GCPSL) assigns clients to fixed clusters, executes a Parallel Split Learning with Global Sampling (GPSL) workload for each cluster concurrently, and periodically fuses the client and server model segments. In simulations with 256 logical clients, dividing the population across more workloads improves direct data participation, while smaller clusters can incur an accuracy cost. A four-H100 implementation of label-aware GCPSL reaches 85% CIFAR-10 validation accuracy in

6.13 \pm 0.15

minutes over three matched runs, versus

19.09 \pm 0.45

minutes when the same workloads are serialized. Within the four-GPU allocation, size-balanced and random fixed affiliations reach the target in similar mean times (5.70 and 5.66 minutes); size balancing increases direct participation by 3.25 percentage points. These measurements characterize a trade-off among execution concurrency, assignment information, participation, and accuracy for stable-client split learning.

Mohammad Kohankhaki, Valentin Rentschler, Anke Schmeink

Chair of Information Theory and Data Analytics, RWTH Aachen University, Aachen, Germany

Clients Fundamental Limits Fp8

Sep 24, 2026cs.AI

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of

M

tasks with

L

binary paths per task under the hard budget

(M+t)K

, where each path costs at most

K

responses or episodes. For fixed

L \ge 3

and

0 < α\le 1/12

, the optimal expected width on the worst pure cohort is

Θ_{α,L}([M(t+1)]^{-1/2})

when every task is observed and

Θ_{α,L}([M(t+\sqrt{M})]^{-1/2})

when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.

Yezhou Cheng, Runjia Du, Zeming Liu +5

Independent · Northwestern University · Pinterest, Inc.

Confidence Intervals Controlled Study Fundamental Limits Honesty

Sep 23, 2026cs.CV

What Looks Like a Capability Limit in Vision-Language Models Is a Readout Limit

Benchmarks for vision-language models offer their answer choices in some convention: a letter, a color name, a pixel coordinate. That convention is treated as neutral. We find it is not, and that the limits a benchmark reports can belong to the readout rather than to the model. On 200 COCO photographs, Qwen3-VL-4B picks the correct one of nine locations for a named object 68.5% of the time when the locations are given in English and 20.0% when the same locations are given as pixel coordinates. Chance is 11.1%. The cost arises when the answer options are coordinates; giving the model a coordinate in the question instead costs 3.5 points and is not significant. The gap holds on a 4x4 grid, under 8-bit rather than 4-bit quantization, and in every slice by object size, boundary distance and category. It also decides which model wins. Two models that tie under English names differ by 39 points in one coordinate system and by 54 in the other, in opposite directions. On the color task, three of the four open models capable of the task show the penalty; on photographs, two of three open models do, and so does Gemini, at 11.1 points on parseable answers (p = 1e-4). GPT-4o does not. To ask whether a model reads a coordinate at all, we attach the wrong name to each one and record which the model follows. Color options written as hue angles are followed below chance; a normalized pixel convention is followed at four times chance. This tells apart conventions a model can use from ones it cannot, though it did not predict accuracy on two untried conventions. Five models also name the same color wheel five different ways, so a fixed answer vocabulary is not neutral across models either. Five times during this work we measured a capable model as incapable because our scorer and the model disagreed about what an answer looks like. We report each case. They are the phenomenon in miniature.

Alfredo F. Frontera Del Valle

Columbia University

Readout Pixels Fundamental Limits

Sep 21, 2026cs.CV

High-resolution Nitrogen Dioxide Maps Reveal Exposure Limit Breaches across Europe

Nitrogen dioxide (NO2) is a common air pollutant, released into the atmosphere through the incomplete burning of fossil fuels, and associated with respiratory and cardiovascular diseases in humans. Ambient NO2 concentrations are regulated through air-quality limits assessed with a sparse network of fixed monitors. The revised EU Ambient Air Quality Directive (2024/2881) introduces a daily NO2 limit to be met from 2030. At present, neither the regulatory monitoring network nor existing coarse, annual-mean models can resolve NO2 concentrations at the spatio-temporal resolutions necessary to assess compliance. Here we map NO2 across Europe at hourly and 10m resolution with a machine-learning model that combines ground monitors with satellite, reanalysis, land-use, traffic and emission data and returns a calibrated predictive distribution at every location. Validated against held-out regulatory monitors and independent citizen-science campaigns, the maps resolve high-resolution spatiotemporal NO2 gradients for 110 metropolitan areas in Europe. We reconstruct the daily compliance statistic across those regions and find limit breaches in 91 EU air quality zones deemed compliant by the regulatory monitoring network, covering a population of approximately 135M. Beyond air quality zones and monitor locations, an estimated 9-9.4% (20M) of the population in mapped regions lives in areas where the daily NO2 limit is breached. The high-resolution maps offer a route to population-scale assessment of compliance with the 2030 limits.

Linus Scheibenreif, Konrad Schindler

Photogrammetry & Remote Sensing, ETH Zurich, Stefano-Franscini-Platz 5, Zurich, 8093, Switzerland.

Air Pollution Greenhouse Gas Fundamental Limits

Sep 17, 2026cs.DB

Resolution limits for process comparison from event data

One hospital runs bloods and imaging at the same time. Another runs them one after the other, in either order, equally often. Knowing which actually happened, and how it is recorded in data, is critical for all operational managers. In process mining, the standard approach is to construct an event log, and attempt to discover concurrent and sequential processes in a data-driven way. We show this standard approach, built on the stochastic language of an event log, reports only the assumptions of its discovery algorithm, because every such log is explained equally well by a model with no concurrency at all. Further, before any data is acquired, we characterise when data can and cannot distinguish concurrent behaviour. Where it cannot, the distinction is recoverable from evidence the stochastic language discards, such as the times at which activities start and end, or object-centric records that fix an order within an execution. The remedy is therefore a choice of what is recorded, rather than a larger sample. This impacts decision making, as planning resource for truly concurrent services is very different from sequential services.

Antony R. Lee, Peter Tiňo, Iain B. Styles

School of Computer Science, University of Birmingham, Birmingham, B15 2TT, United Kingdom · School of Electronics, Electrical Engineering and Computer Science, Queen’s University Belfast, Belfast, BT7 1NN, United Kingdom

Fundamental Limits Comparison Stochastic Object-Centric Representations

Sep 7, 2026cs.CY

An emancipatory vision for designing (generative) AI for learner flourishing

The hype around generative AI seems to promise unprecedented productivity (and learning) gains. However, these technologies' increasing agentic features seem to push learners towards individualism (or individual isolation), over-reliance, and dependence on them. Human-centered design approaches (e.g., value-sensitive design) assume that, by unearthing human needs, preferences, and values, technology researchers/designers may avoid such dangers, which are driven by wider systemic factors like economic incentives or inherent human limitations (e.g., our tendency to seek, in the moment, the easiest path of action). Yet, so far these efforts seem insufficient to guide our design of educational technology that avoids the aforementioned dependency and isolation dangers, while finding widespread adoption. This paper presents an alternative, more emancipatory vision for future educational AI technology, oriented towards learner flourishing while considering the wider complex systems they inhabit, including tentative design principles and an overall design methodology. Yet, many open questions remain before this vision can be realized.

Luis P. Prieto, Yannis Dimitriadis

GSIC-EMIC Research Group, Universidad de Valladolid, Paseo de Belén, 15, 47011 Valladolid, Spain

Artificial Intelligence Education Human-Centered Framework Generative Artificial Intelligence Agentic Fundamental Limits

Sep 7, 2026cs.IT

A Fundamental Limit in Decentralized Decision-Making

In decentralized decision-making, several agents connected according to a network graph aim at solving a classification problem by collecting streaming observations. Due to decentralization, they run an iterative algorithm where, at each iteration, they can only exchange information locally with their neighbors. While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making. Specifically, we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier. This result establishes a fundamental limit for the performance of any decentralized decision strategy. We obtain an analytical relation showing that this limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph, while the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem. By applying the derived closed-form relation to different network topologies and inference problems, we observe some interesting and perhaps unexpected behavior emerging. In particular, we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude; and we examine how performance is affected by the relative distance between informative and uninformative agents over the graph.

Marco Carpentiero, Felice Scala, Vincenzo Matta +1

Department of Information and Electrical Engineering and Applied Mathematics (DIEM), University of Salerno, I-84084 Fisciano (SA), Italy · Institute of Electrical and Micro Engineering, EPFL, CH-1015 Lausanne, Switzerland

Decentralized Autonomous Organization Network Science Decisions Equal Error Rate Fundamental Limits

Sep 7, 2026cs.RO

CALM: Configuration-Aware Human Intervention Boundaries During Robot Approach

How robot body configuration shapes human intervention during approach remains underexplored. We conducted a within-participants study with 41 participants, measuring final stopping distance, subjective comfort, and exploratory eye-tracking responses across four humanoid arm configurations and two spatial scales. Full forward arm extension increased stopping distance by approximately 31-36 cm relative to arms-down. Spatial scale primarily affected comfort and pupil responses without a detectable stopping-distance shift. We introduce the Configuration-Aware Limit Model (CALM), which translates stopping-distance distributions into configuration-dependent population-coverage boundaries. Estimated boundaries at 80% coverage ranged from 0.88 to 1.47 m. In an illustrative one-dimensional planning analysis, reconfiguration enabled a 1.10 m approach goal that was unreachable with arms remaining fully extended under the same nominal pointwise 20% intervention-probability constraint. These findings support treating body configuration as a planning variable while distinguishing physical safety, behavioral intervention, and subjective cost.

Xinting Gao, Sipu Zhu, Weimin Zhuang

School of Architecture, Tsinghua University, China · Architectural Design & Research Institute of Tsinghua University, China

Emergency Braking Intensity Prediction Human Agency Fundamental Limits Eye Tracking Boundaries

Sep 3, 2026cs.CR

A Non-Formulable Theorem: A Fundamental Limit of Finite Syntactic Systems and Its Consequences for Security and AI

For every coherent and sufficiently expressive finite syntactic system S, we prove the existence of at least one theorem that S cannot produce autonomously. The result is a metatheorem: it proves the existence of a theorem, and applies to every finite syntactic system - security mechanisms, AI systems, formal verifiers, legal systems, economic models, and the formal system in which it is itself proved.

Fabio F. G. Buono

Independent Researcher

Formal Verification Security Syntactic Structure Fundamental Limits Theory Economies

Aug 28, 2026cs.CL

A Formal Limitation on Learning Human Language From Textual Corpora

Can a listener recover what a speaker means from the form of an utterance alone? We answer this question information-theoretically, and for a listener given by any featurizer of text, including the hidden states of contemporary large language models. Modeling language use as a joint distribution over meanings, contexts, and utterances, we derive upper bounds on the probability that a decoder recovers a speaker's intended meaning from a representation of the utterance. The bounds are governed by the uncertainty that form leaves about meaning, which splits into an irreducible part and a part that only (extralinguistic) context, but never the utterance alone, can resolve. Because these quantities are intrinsic to language, no representation, however much text or supervision produced it, can surpass them. The bounds apply, moreover, to meaning spaces that are discrete or continuous. We provide empirical evidence in support of the theory through experiments on artificial languages, Mandarin zero-pronoun resolution, and color reference.

Emily Cheng, Ryan Cotterell

Universitat Pompeu Fabra · ETH Zürich

Linguistics Natural Language Processing Utterances Fundamental Limits Text Corpora Upper Bounds

Aug 21, 2026cs.CL

Tree-of-Concerns: Hierarchical Multi-Agent Debate for Unstated-Limitation Extraction in Scientific Critique

As scientific literature grows and papers increasingly under-report limitations, multi-agent LLMs offer a promising approach to systematically uncover these hidden failure modes. Here, we introduce Tree-of-Concerns, a multi-agent framework that deploys specialized skeptic personas, each operating through a category-specific analytical lens, as parallel debate trees to extract unstated limitations from scientific papers. Each persona conducts structured, evidence-grounded argumentation, while a Panel Review mechanism re-evaluates each surviving claim from all five perspectives to correct category drift and severity miscalibration. Through retrieval-free, single-paper experiments on ToC-Bench, our benchmark of 414 research papers with 1,905 unstated limitations, sourced from reviewer-reported weaknesses and follow-up citation critiques, we demonstrate that ToC improves precision by 79% and coverage by 11% relative to the strongest baseline, surfacing specific, evidence-grounded concerns that support reviewers in systematic evaluation.

Sahil Mishra, Niranjan Rajeev, Tanmoy Chakraborty

Department of Electrical Engineering, IIT Delhi

Scientific Discovery Multi-Agent Debate Reviewer Fundamental Limits Tree-Of-Thoughts Interpretive Layer+1

Aug 13, 2026math.ST

On the Structural Limits of Machine Learning Decision Systems: An Information-Theoretic, Interaction-Based, and Stochastic-Dynamical Perspective

Machine learning procedures are commonly evaluated in terms of predictive accuracy and computational efficiency. However, their achievable performance is fundamentally constrained by structural properties of the underlying data-generating process, which are formalized in terms of informational bounds. In this work we examine intrinsic limits of data-driven decision systems from an information-theoretic and interaction-based perspective. We analyze minimal achievable error in classification through Fano-type bounds and precision limits in parametric estimation via the Cramér-Rao inequality, emphasizing that such limits depend on the underlying model rather than on algorithmic sophistication alone. We further discuss how implicit assumptions, such as independence, ergodicity, and distributional stability, affect the validity of inferential procedures. Building on interaction-based modeling principles, we review typical frameworks such as Markov Random Fields and potential based representations for encoding dependence mechanisms. We also describe decision systems, including LLM-integrated agent architectures, as feedback-driven stochastic processes where state-dependent dynamics may induce emergent macroscopic behavior. This perspective highlights the importance of having adequate models for the data as a prerequi- site for expanding predictive capability, and situates algorithmic learning within the informational limits imposed by the models.

Nestor R. Barraza, Gabriel Pena

Universidad Nacional de Tres de Febrero. Departamento de Ciencia y Tecnología. · Universidad de Buenos Aires. Facultad de Ingeniería.

Fundamental Limits Probabilistic Inference Data-Driven Upper Bounds Stochastic Processes Emergence+1

Aug 13, 2026cs.AI

Numeracy in Large Language Models: Fundamental Limitations and Paths to Improvement

Large language models (LLMs) achieve strong results on mathematical reasoning benchmarks yet remain unreliable on elementary numerical tasks, including magnitude comparison, large-integer arithmetic, fractions, and scientific notation. This survey examines basic numerical understanding as a capability distinct from high-level mathematical reasoning. We propose the Numerical Grounding Framework (NGF), which decomposes numeracy into Representational Grounding (RG), mapping numeral forms to value, magnitude, and equivalent representations, and Procedural Grounding (PG), executing arithmetic operations in accordance with their mathematical definitions. Using NGF, we organize recent diagnostic benchmarks, failure modes, structural explanations, and mitigation strategies. We review evidence concerning tokenization, positional encoding, embedding geometry, and pretraining-data distribution. We also apply NGF in a coordinated evaluation of three frontier model families across Number Cookbook, NumericBench, and GSM-Symbolic, comparing atomic, contextual, and reasoning-assisted numeracy. Architectural interventions such as digit-aware tokenization and Abacus Embeddings can improve models trained from scratch but are generally unavailable to users of pretrained systems, for whom supervised fine-tuning, reasoning scaffolds, and external tools are more practical. We conclude with deployment recommendations and research directions for more reliable numerical behavior in foundation models.

Aoxin Ni

Department of Computer Science University of Chinese Academy of Sciences

Mathematical Reasoning Benchmarks Fundamental Limits Improvement Tokenizer Path

Aug 5, 2026physics.optics

Universal Function Approximation via Diffractive Optical Processors: Physical Limits, Error Bounds, and Learnability

We present a unified theoretical framework connecting classical universal approximation theory, Fourier-feature approximation, and diffractive optical processors. We show that phase-encoded diffractive processors implement finite Fourier-feature expansions whose mathematical completeness follows from Fourier/Stone-Weierstrass arguments, while their physical realizability is governed by finite coefficient synthesis through optimized spatially varying coherent point-spread functions (PSFs). Our analyses derive approximation-error bounds that separate Fourier truncation, PSF-synthesis, input phase error, optical hardware, readout, and noise contributions; establish scaling relationships linking approximation complexity to optical degrees of freedom and input/output space-bandwidth products; derive photon-budget and throughput limits imposed by photon statistics; formulate finite-class statistical learnability bounds for phase-quantized diffractive function approximators; and analyze the impact of spatially incoherent illumination. We further analyze coherent optical cascadability and show that quadratic feature expansion through coherent mixing and optical readout provides a mechanism for enhanced representation while remaining fundamentally distinct from the depth-separation results established for digital neural networks. Our analyses provide a rigorous theoretical foundation for diffractive nonlinear function approximation and establish quantitative relationships among mathematical expressivity, optical hardware resources, statistical learning, and physical performance limits, thereby offering general design principles for large-scale analog optical computing systems.

Md Sadman Sakib Rahman, Che-Yung Shen, Aydogan Ozcan

Electrical and Computer Engineering Department, University of California, Los Angeles, CA, 90095, USA · Bioengineering Department, University of California, Los Angeles, CA, 90095, USA · California NanoSystems Institute (CNSI), University of California, Los Angeles, CA, 90095, USA

Optical Fourier Fundamental Limits Learnability

Aug 5, 2026cs.CL

STRIVE: Probing Reasoning Limits in Graded Plausibility Generation and Evaluation

Event knowledge concerns who does what to whom. Psycholinguists use event-plausibility judgments to examine how this knowledge supports human language processing. To isolate plausibility effects, these studies require controlled event sets in which one event slot varies across plausibility levels while all other event features remain fixed. Constructing such sets manually is labor-intensive. We therefore introduce STRIVE, an LLM-based framework for jointly generating and evaluating controlled event sets crossing plausibility class (plausible vs. implausible) with intended classification difficulty (easy vs. hard). Given a verb, STRIVE constructs a shared event frame, then produces one event per condition by varying one slot while holding all others fixed. In experiments with six models across 60 verbs, GPT-5.1 produced high-quality sets only 16.7% of the time using the baseline generation prompt. Adding a global reasoning scratchpad and evaluator-guided refinement raised this rate to 75.0%. Greater reasoning effort also improved evaluator--human agreement. Nevertheless, events near the plausibility boundary remain most difficult. They elicit the greatest human disagreement, and the best evaluator reaches only 57% accuracy on the implausible-hard condition, indicating a need for human input. Overall, STRIVE offers a scalable approach to reducing manual effort by automating initial event-set generation and evaluation for psycholinguistic studies.

Bhiman Kumar Baghel, Anna Chrabaszcz, Tessa Warren +3

University of Pittsburgh, Pittsburgh, PA, USA · University of Wisconsin–Madison, Madison, WI, USA

Physical Plausibility Reasoning Skills Natural Language Processing Fundamental Limits

Aug 3, 2026stat.ML

The Label Defines the Timescale: Trait-State Limits of Temporal-Aggregate Learning

Machine-learning benchmarks often pair a label that aggregates a long temporal horizon with input observed through one or a few short windows. Their apparent performance ceiling may therefore be an acquisition-protocol ceiling rather than a model-capacity ceiling. We study labels of the form

Θ_{g,T}=T^{-1}\int_0^T g\{Z(t)\}\,\mathrm{d}t

when the latent Gaussian process contains both a stable individual trait and a correlated within-individual state. An exact protocol-conditioned Bayes-risk identity provides a common tool. First, we decompose label variance into an

O(1)

trait component and an

O(T^{-1})

state component, explaining why a snapshot can retain cross-sectional predictability while poorly tracking within-person change. Second, we derive task-dependent effective temporal spans: mean labels depend on the ordinary correlation time, whereas occupation-time labels depend on an entire spectrum of higher-order correlation times. Third, state-driven occupation-label variance is maximal when the stable trait lies at the threshold; window efficiency decays much more slowly away from that boundary. Under an equal segment budget, exact risks and Monte Carlo experiments show that repeated segments at one time rapidly saturate, whereas temporally dispersed observations continue to increase state explainability. The trait ceiling uses quantities available from ordinary test-retest data; only the state ceiling requires short-lag temporal calibration. The results distinguish architectural limits from protocol limits and show that the label, rather than duration or segment count alone, defines the relevant timescale.

Xizhe Zhang

Timescale Training Time State-Tracking Fundamental Limits Ceiling

Jul 31, 2026cs.AI

More Debate, Same Evidence: Structural Limits of Homogeneous Multi-Agent Groundedness

Large language model (LLM) judges are increasingly organized as multi-agent panels under the assumption that exchanging critiques improves judgment quality. We test this assumption for \emph{groundedness verification}, where a judge must determine whether a claim is supported by the supplied evidence. We evaluate a homogeneous three-agent panel on six public fact-verification and hallucination-detection benchmarks. Relative to a fixed single-agent reference, the panel's system-level accuracy difference ranges from

+8.5

to

-4.4

percentage points: two datasets show reliable gains, one shows a reliable loss, and three are statistically inconclusive. Because the reference and panel use different model variants, these differences characterize the complete systems rather than isolate a causal debate effect.

Yuelyu Ji

Multi-Agent Debate Citation Hallucination Detection Fundamental Limits

Jul 31, 2026cs.CL

PARALLEL: A Prefrontal-Aligned Reinforcement inspired Approach for Language-Model Learning under Explicit Limits

Recent language models achieve strong performance across a variety of tasks, but conventional adaptation applies updates uniformly across training samples regardless of their local update benefit. We propose PARALLEL, a prefrontal-aligned reinforcement inspired approach for language-model learning. Inspired by the complementary roles of goal-related and uncertainty-related control, PARALLEL represents these forms of information as separate controller signals and combines them with the current model representation. A reinforcement-inspired controller assigns sample-dependent update intensity using immediate utility-cost feedback. PARALLEL therefore learns when and how strongly to adapt to each sample, prioritizing beneficial updates while limiting unnecessary parameter changes. PARALLEL uses available updates more efficiently than selective baselines while retaining 94.1--99.2% of Full-adaptation performance. Beyond multiple-choice reasoning, experiments on XSum and CNN/DailyMail show that PARALLEL retains 96.9--98.6% of the ROUGE-1 and ROUGE-2 scores achieved by Full adaptation and 98.8--98.9% of the corresponding ROUGE-L scores. When compared at the same cumulative adaptation time or GPU energy, PARALLEL achieves higher ARC accuracy and exhibits a more stable late-stage adaptation trajectory than Full adaptation in the representative run. These results show that learning when and how strongly to update each sample supports stable and efficient post-deployment stream adaptation while avoiding unnecessary updates.

Namkyung Yoon, Sanghong Kim, Hwangnam Kim

School of Electrical Engineering, Korea University Seoul 02841, Republic of Korea

Large Language Model Adaptation Language Modeling Rapid Adaptation Reinforcement Learning Control Fundamental Limits

Jul 22, 2026physics.flu-dyn

Guarantees by Construction for Learned Finite Volume Schemes on Steady Supersonic Flow

A second order finite volume scheme rests on two local quantities: a gradient reconstructed in each cell, and a limiter which scales it down where the reconstruction would overshoot. Both are set by fixed formulas, and on coarse unstructured meshes a small network can supply better values. But a network is free to output anything, and the usual safeguard is a penalty in the training loss, which discourages inadmissible states without preventing them. We replace the penalty by a hard constraint. The network still sets both quantities, and every value it can produce lies inside safe bounds: its stencil weights cannot cancel a neighbour, and its limiter is capped by the local flow. The flux, the wall treatment and the time step are not learned and carry their own guarantees. Admissibility therefore holds for every value of the weights rather than as an outcome of training, and no negative density or pressure occurred in any computation reported here. Because the scheme is safe whatever the network does, we could ask what the network contributes. We test it on supersonic channel flow over an obstacle, including the forward facing step of Woodward and Colella. Learning lowers the error by 38% on an unseen geometry and 29% on an unseen obstacle topology, measured against the same scheme with the network switched off. The method aims at the accuracy of a fine mesh for the cost of a coarse one, and refining once improves the error fourfold while multiplying the run time by eight. Learning secures half of this improvement for a sixth of this time. All of this comes from one of the two quantities the network sets. The gradient reconstruction reproduces the full effect on its own, and the limiter accounts for about a tenth as much. This also explains why the gain fades beyond the Mach numbers the weights were trained on.

Denis Gueyffier

ONERA -- Institut Polytechnique de Paris · Direction Scientifique G´en´erale, ONERA · Institut Polytechnique de Paris, Palaiseau, France

Vortex Turbulent Flows Fundamental Limits Construction

Jul 21, 2026stat.ML

Fundamental limits of distributed multiclass classification from simple binary decisions

We consider the problem of constructing a

K

-class classifier from the combination of

O(\log K)

simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the

K

class centers are independent Gaussian points in

\mathbb R^d

and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.

Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh +2

School of Mathematics, University of Bristol · Department of Electrical Communication Engineering, Indian Institute of Science.

Multiclass Classification Gaussian Mixture Models Fundamental Limits Gaussian Primitives Decisions

Jul 19, 2026cs.IT

Rate-Distortion-Perception Theory: Redefining the Fundamental Limits of Information Representation

Classical rate-distortion (RD) theory has long established the fundamental limits of lossy compression by quantifying the minimum number of bits required to represent a source under a prescribed distortion constraint. However, widely used distortion measures such as mean-squared error often fail to capture perceptual quality or semantic validity, which are increasingly central in modern learning-driven applications. Rate-distortion-perception (RDP) theory extends the RD framework by introducing perception as a third fundamental axis, quantified via distributional similarity between the source and reconstructed signals, leading to the rate-distortion-perception function (RDPF). This tutorial provides a structured overview of the coding principles underlying perception-aware lossy compression and surveys recent achievability results under different randomness assumptions. It then presents a unifying optimization viewpoint for computing the RDPF as defined by Blau and Michaeli, for both discrete and continuous sources under broad families of perceptual constraints, including f-divergences, alpha-divergences, and Wasserstein-based metrics. Special attention is given to computational tools such as alternating minimization schemes, Newton-based methods, and convex optimization formulations, as well as to analytically tractable cases such as Gaussian sources and the perfect-realism regime. Unlike recent broad surveys that emphasize generative architectures and AI-empowered communication systems, this tutorial focuses on the coding-theoretic and computational machinery needed to characterize, compute, and interpret the RDP limits. Finally, the tutorial outlines promising research directions at the intersection of information theory, neural compression, robust source coding, and perception-aware networked control systems.

Photios A. Stavrou, Giuseppe Serra, Marios Kountouris

Rate-Distortion Theory Source-Channel Coding Information-Theoretic Limits Distortion Minimax Rate Fundamental Limits+1

Jul 17, 2026cs.LG

The Information Shadow: Measuring Structural Limits on What Language Models Can Learn

Some limits on what language models know are not gaps in data coverage but structural properties of learning from text. We introduce the information shadow: the region of phenomena that a text-trained learner cannot acquire regardless of scale, comprising (I) structures language cannot express, (II) functions that are statistically non-identifiable from the training distribution, and (III) functions that are representable but unreachable by gradient-based training. We give each type a probe that is decisive because the premise of the shadow is, in that setting, provable. For Type I, Language Compression Residuals compare a text learner, which sees only a lossy text-like encoding of the signal, against a full-signal learner, which sees the underlying signal directly. The text learner sits at a computable expressibility ceiling while the full-signal learner pulls away by a gap that stays flat across 300x more data, so the deficit is a property of the channel, not of training. For Type II, the Counterfactual Distinction Test trains models on data exactly consistent with two incompatible rules. Across a provable string task and a language-like agreement task, behavior on counterfactuals is set by the model's inductive bias, while 5% disambiguating data steers the learned rule bidirectionally to either target (r = +/-1.0, p < 1e-10). For Type III, Basin Escape Mapping exhibits a function that is representable at 100% (by hand construction) yet reached 0% of the time by standard training and instantly from a nearby initialization, with width scaling providing no help (p = 1.6 x 10^-14). Each effect is isolated by a control that rules out a capacity or modality artifact. We release the probe suite and discuss implications for benchmark design, capability auditing, and shadow-aware uncertainty.

Priyansh Srivastava, Romit Chatterjee

Sirena Ai · Independent Researcher

Fundamental Limits Language Modeling Large Language Models Fail Learnability Inductive Bias Counterfactual Generation

Jul 15, 2026cs.DC

The Cost and Network Limits of Space-Based AI Compute

This paper evaluates whether large-scale AI data centers deployed in low-Earth orbit (LEO) could become a cost-effective alternative to terrestrial facilities. The analysis compares orbital and ground-based systems across launch cost, power generation, cooling, radiation exposure, and atmospheric reentry, as well as compute-network performance. A key distinction is the shift from terrestrial Clos networks to space-based mesh networks using laser inter-satellite links. Using bisection bandwidth, bisection intensity, and roofline-style models, we show that while LEO-based inference may be feasible, training frontier-scale LLMs in orbit is unlikely to be competitive with terrestrial data centers.

Kees van Berkel

Technical University Eindhoven, Dept. of Math. & Computer Science P.O. Box 513, 5600 MB Eindhoven, The Netherlands

Artificial Intelligence Infrastructure Low Earth Orbit Satellite Networks Computational Cost Fundamental Limits

Jul 13, 2026cs.LG

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across

K

arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any

K\ge 3

and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most

\left(1 + \frac{\log(K)}{8}\right)^{-1}

times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Motti Goldberger

Yale University

Stochastic Multi-Armed Bandits Token Budget Allocation Fundamental Limits Exponential Family Ratio

Jul 12, 2026cs.LG

Learning to Fine-tune Foundation Models under Resource Limitations

We study the problem of optimal continual fine-tuning for a pre-trained Foundation Model deployed at a resource-limited device. At each time slot, a new batch of training data arrives, and the controller is faced with two options: either use the data to fine-tune the model and incur a compute cost, or do not fine-tune the model and discard the data. After the decision, the performance of the current model is measured in terms of an application-specific performance metric such as classification accuracy. Our objective is to learn an optimal policy that determines \emph{when to fine-tune the model} on a single task (e.g., sentiment analysis), under a finite compute budget. We formulate this online decision-making problem as a constrained Markov Decision Process, where the system state captures three essential aspects: (\textit{i}) model's performance, (\textit{ii}) computational budget, and (\textit{iii}) data distribution relevance to historic data encountered up to that point. The transition to the next state is stochastic and therefore, we propose a reinforcement learning-based method to solve this problem, namely the \emph{actor-critic} algorithm. We also consider the special case where the performance of fine-tuning for a given model can be predicted or estimated prior to decision; in this case the problem becomes a Dynamic Programming one. Experiments with a large pre-trained model on a widely-used text classification dataset demonstrate that our method consistently outperforms fine-tuning approaches with the same compute budget by more than

4\%

in terms of accuracy and achieves

97\%

of full-parameter fine-tuning accuracy while requiring only

25\%

of the fine-tuning steps.

Thomas Tsouparopoulos, Iordanis Koutsopoulos

Department of Informatics Athens University of Economics and Business Athens, Greece

Continual Fine-Tuning Wireless Foundation Models Parameter-Efficient Adaptation Foundation Model Fundamental Limits Optimal Policies+1

Jul 9, 2026cs.LG

Write-Protected Discrete Bottlenecks for Language-Grounded World Models: A Structural Limitation and Sufficient Fix

How should language interface with a world model's discrete symbol system? The dominant paradigm -- end-to-end injection of LLM/VLM features into robot world models (RT-2, Octo, PaLM-E) -- implicitly assumes that language gradients can directly shape physical symbol representations. We ask whether this assumption is safe, find that it is not, and characterize the minimal architectural constraint that prevents the failure. Any language gradient entering a Gumbel-softmax-based discrete symbol bottleneck forces a structural trade-off: the vanilla estimator collapses to 2.2/64 symbols (4/5 seeds), while five anti-collapse strategies maintain diversity but fail to learn semantic labels (all <= 9.2% accuracy). No tested GumbelBottleneck variant achieves both objectives simultaneously. Within this family of discrete bottlenecks, the failure is structural rather than a matter of optimization. We characterize a sufficient set of three constraints that prevent the failure: (1) cut the gradient chain (z.detach()), preventing language signals from reaching the symbol bottleneck; (2) provide a gradient-free semantic channel -- a non-parametric Memory Table (Dict[symbol -> Counter[label]], zero parameters, zero gradients) where co-occurrence counting replaces gradient-based binding; (3) handle symbol collisions via DP-Means streaming clustering for automatic sub-cluster splitting. All three layers together achieve 97.2% grounding accuracy vs. 22.2% without Layer 3. Across two experiments spanning 74 independent runs, we demonstrate zero symbol collapse in all 32 seeds, with the blackboard achieving 79-100% semantic binding across three encoder architectures (CNN, V-JEPA 300M, CLIP ViT-L), two environments, and three texture conditions. The fix trains fewer than 2M parameters and requires no LLM fine-tuning.

Jiayi Fang

Shanghai University of Finance and Economics

Latent World Models Large Language Model Fine-Tuning Bottlenecks Language Pairs Fundamental Limits

Jun 29, 2026cs.LG

The Fundamental Limits of Valid Transport Map Estimation

Many modern generative modeling methods, including diffusion models, normalizing flows, and flow matching, estimate transport maps or plans between distributions without explicitly targeting an optimal transport (OT) map. In applications like generative modeling, the transport cost itself is irrelevant, and this makes it natural to target maps which are more tractable from either a statistical or computational standpoint. In this short note, we formalize the task of estimating any valid transport map in a rigorous minimax framework. One consequence of this framing is that it yields sample complexity lower bounds for any method whose learned object is evaluated as a transport map or plan, including flow matching and diffusion-based generative models, in settings where direct analysis would be challenging due to the analytic complexity of the methods and their target maps. We observe that, under standard, though strong, stability assumptions from the OT literature, estimating any valid transport map is statistically as hard as estimating the OT map. We complement these results with some examples showing that when these stability assumptions fail, alternative transport maps can be learned substantially more accurately than the OT map. Our minimax framing provides a rigorous foundation for understanding the statistical limits of modern transport-based generative methods and clarifies when targeting sub-optimal maps can provide real statistical advantages.

Sivaraman Balakrishnan

Department of Statistics and Data Science† · Machine Learning Department‡

Generative Models Diffusion Models Normalizing Flows Fundamental Limits

Jun 26, 2026astro-ph.IM

Differentiable design of the PIAA-ZWFS: a flexible wavefront sensor that approaches the fundamental limit

Extreme adaptive optics (AO) is necessary for high contrast astronomy at scales of the habitable zone of nearby systems. We seek to evaluate wavefront sensors that approach fundamental limits of wavefront sensing, enabling adaptive optics systems to run faster or on fainter targets. We present the phase-induced amplitude apodisation Zernike wavefront sensor (PIAA-ZWFS): an adaptation of the conventional Zernike wavefront sensor (ZWFS) that leverages lossless apodisation of the pupil to concentrate the starlight in the focal plane. We optimise and evaluate the sensor with a differentiable modelling framework, drawing on concepts from Bayesian experimental design to minimise the variance of a maximum likelihood estimator that uses the system in the high Strehl regime. Our architecture shows state-of-the-art performance in simulation for different apertures, bandwidths, photon fluxes and source sizes, closing the gap to the fundamental limit by a factor 10 (2.5) compared to the conventional ZWFS (optimised ZWFS) in a typical photon-limited case. For extended sources, we show that even an ideal point source sensor rapidly becomes sub-optimal, and our system outperforms it for stellar diameters larger than 0.8λ/D. We verify that these gains do not come at the cost of dynamic range with either linear or non-linear reconstructors. Finally, we present a proof that there must be a trade-off between the information gained about amplitude and phase errors for any wavefront sensor. The PIAA-ZWFS is a viable wavefront sensor operating near the fundamental sensitivity limits.

A. K. Taras, S. Y. Haffert, L. Desdoigts

Leiden Observatory, Leiden University, PO Box 9513, 2300 RA Leiden, The Netherlands

Optical Differentiable Physics Fundamental Limits

Jun 16, 2026cs.LG

No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems

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.

Khoat Than

Hanoi University of Science and Technology

Algorithmic Fairness Learnability Subgroups Learning-Augmented Algorithms Biases Fundamental Limits+1

Jun 13, 2026cs.LG

LLMs on Tabular Data with Limited Semantics: Evidence from Industrial Car Retrofit Prediction

Industrial retrofit planning depends on structured operational data rather than free text: planners must estimate whether a newly registered prototype will require a retrofit, which retrofit package it will need, and how long the work will take. We study an industrial dataset linking a prototype-registration system (284,271 vehicles) with a retrofit-management system (48,716 cleaned visits), and compare strong tabular machine learning baselines with three LLM-based strategies on row-serialized inputs: embedding features (Amazon Titan), direct prompted classification (Claude Sonnet 4), and an ML+LLM stacking approach. Across binary occurrence prediction, 15-way retrofit-type classification, per-visit duration regression, and an aggregated monthly benchmark, classical tree ensembles remain the strongest standalone models. However, the LLM results reveal a consistent pattern: embeddings remain useful on tables (binary AUC = 0.982), direct prompting collapses once semantic signal is stripped by hashing (binary AUC = 0.500; multiclass weighted F1 = 0.018), and hybrid stacking yields the best manually built multiclass model (weighted F1 = 0.626). On the monthly benchmark, lag-based machine learning outperforms time-series foundation models, though Chronos-small remains competitive in zero-shot forecasting. The results suggest that on privacy-constrained industrial tables, LLMs are more effective as complementary components than as replacements for strong tabular baselines.

Aina Vila Pons, Ioannis Tzachristas, Constantinos Antoniou

Chair of Transportation Systems Engineering, Technical University of Munich, Germany · BMW Group, Munich, Germany

Tabular Data Predictive Maintenance Large Language Model Pipelines Fundamental Limits

Jun 11, 2026cs.LG

Can Machine Learning Forecast Rice Yields in Data-Constrained Settings? Satellite Climate Data, National Crop Statistics, and Lessons from Sierra Leone

Sierra Leone's agriculture operates with almost no data-driven decision support, and no published machine learning study has examined the country's crop yields. We ask whether rice yield can be forecast from data Sierra Leone currently has. Using 25 years of FAOSTAT production data (2000-2024) for nine major crops, we train XGBoost, Gradient Boosting, and Random Forest under a strict anti-leakage protocol with expanding-window walk-forward evaluation across seven held-out years, benchmarked against naive persistence. No model trained on crop statistics alone outperforms persistence. Augmenting with free satellite climate data (CHIRPS rainfall, NASA POWER temperature) reverses this result: a climate-only XGBoost reduces forecast error by one third (RMSE 284 vs 428 kg/ha), a gain that holds for a linear model and is robust to excluding the anomalous 2018 season. Early-season (May-June) rainfall is the dominant predictor, implying seasonal yield risk is observable months before harvest. No model anticipated the 2018 collapse, whose origins were institutional rather than climatic. We translate the findings into policy recommendations for Sierra Leone's Feed Salone Strategy, with a fully open-source pipeline.

Ibrahim Denis Fofanah

Seidenberg School of Computer Science & Information Systems, Pace University, New York, USA · RiseAfrica Foundation for STEM and Innovation, Sierra Leone, West Africa

Agricultural Prediction Sri Lanka Xgboost Model Fundamental Limits

Jun 8, 2026cs.CL

Generating in the Limit with Infinitely Many Hallucinations

The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner tasked with identifying that language. The recently introduced framework of language generation in the limit shifted the objective to better reflect modern language modeling, requiring the learner to produce valid, unseen strings from the target language. Related work highlighted a fundamental tension: a broad coverage of the target often comes at the cost of validity. We introduce a new notion of precision and recast this problem as the classic recall-precision trade-off. We analyze generation in the limit under varying constraints on enumeration, novelty, and validity, aimed at reflecting settings closer to those encountered by large language models. A key contribution is our analysis of learners that are not eventually valid: we allow infinitely many mistakes, provided their frequency tends to zero so that precision remains one. We show that this relaxation can strictly increase recall when the adversary permanently withholds a large portion of the target language. We also study a continuous relaxation of the novelty constraint that requires only a fixed fraction of outputs to be novel. Taken together, our results move toward a more realistic model of language generation where occasional errors and repetitions are unavoidable, but their rates are controlled.

Irene Strauss, Alexandra Butoi, Ryan Cotterell

ETH Zürich

Large Language Models Fail Fundamental Limits Data Generation Infinities Object Hallucination Factual Recall

Jun 2, 2026cs.LG

Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs

Graph Neural Networks (GNNs) have emerged as a powerful tool for wireless resource allocation that leverages the underlying graph structure of communication networks. Their transferability property enables models trained on small-scale graphs to generalize to large-scale deployments with little performance deterioration, a desirable property for currently growing networks. Wireless networks are sparse regimes, where a single node is connected to a small number of other users. This work establishes theoretical results for transferability of GNNs over graphs derived from sparse Random Geometric Graphs (RGGs). In particular, we focus on conflict graphs of RGGs used to model interference among links. Our approach considers the closeness between RGGs and Deterministic Grid Graphs (DGG) to establish bounds in the performance loss when a model is transferred across scales. We validate our theoretical findings through the problem of link scheduling, demonstrating that our learned policies consistently outperform existing benchmarks at scale. Finally, we examine the impact of our theoretical assumptions on empirical performance.

Romina Garcia Camargo, Zhiyang Wang, Alejandro Ribeiro

Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA · Halıcıoğlu Data Science Institute, UCSD, La Jolla, CA

Inhomogeneous Random Graphs Graph Neural Networks Power Allocation Fundamental Limits

May 30, 2026cs.CL

Revisiting Parameter-Based Knowledge Editing in Large Language Models: Theoretical Limits and Empirical Evidence

Parameter-based knowledge editing updates the internal knowledge of large language models (LLMs) via localized weight modifications and has attracted significant attention. However, most existing methods overlook fundamental theoretical limitations and are rarely evaluated under realistic, practice-oriented settings. In this paper, we first present a theoretical analysis based on the dimensional Collapse Hypothesis, explaining how localized parameter edits can propagate along fragile directions in the representation space, inducing global interference and ultimately causing reasoning collapse. Building on this insight, we conduct a comprehensive empirical evaluation by systematically varying knowledge complexity, number of edits, evaluation dimensions, and baseline methods. Our results show that parameter-based editing methods consistently damage core LLM capabilities. In contrast, a simple retrieval-based baseline achieves consistently stronger performance than all parameter-editing methods across all evaluated conditions. These findings highlight that preserving the fundamental capabilities of LLMs after knowledge editing should be a central concern for future research.

Wanying Ren, Xin Song, Futing Wang +2

East China Normal University, Shanghai, China · Westlake University, Hangzhou, China · Nanyang Technological University, Singapore

Multimodal Knowledge Editing Fundamental Limits Collapse

May 27, 2026cs.LG

The Routing Plateau: Understanding the Accuracy Limits of LLM Routers

LLM routing has become a popular approach to improve the cost-quality trade-off of LLM services by adaptively selecting a model for each query. Recent work has explored a broad range of routing methods, including clustering-based routers, learned classifiers, pairwise ranking, and confidence-based approaches. Our extensive study of 21 routing methods across five benchmarks reveals a consistent phenomenon that we call the routing plateau (Fig. 1): many methods, including kNN, achieve very similar accuracy and converge to a narrow performance range that remains far below the oracle router. Our analysis supports a correctness-prediction bottleneck hypothesis: current routers primarily learn global-average model performance trends rather than fine-grained, query-specific routing signals. As a result, they collectively fail on queries that require instance-specific routing decisions. Moreover, to understand whether the plateau can be alleviated with a better training setup, we construct a 300K-query benchmark (Nine-by-300k). More data, larger encoders, and end-to-end fine-tuning improve eight routers by 1.24 pp on average, but leave the plateau largely intact. These findings suggest that further progress may require inputs beyond the query itself, such as partial output trajectories that reveal how models attempt the task.

Yifan Lu, Qiyue Zhang, Shenrun Zhang +4

Rice University · Amazon

Large Language Model Routing Bottlenecks Fundamental Limits

May 26, 2026cs.LG

The Fundamental Limits of Fraud Detection in Card Payment Networks

Card payment fraud detection is usually framed as a supervised classification problem. Although this approach has generated practical progress, improvement has remained incremental despite major advances in model architecture. We argue that this is not mainly a failure of function approximation or optimization, but a consequence of structural information impairments inherent to the payment ecosystem. We formalize card authorization as a sequential decision problem with delayed, censored, corrupted, and counterfactually missing feedback. We derive a minimax regret lower bound showing that these impairments enter multiplicatively in the denominator of the achievable learning rate. The bound implies that improving issuer reporting quality or reducing censorship can yield larger reductions in the regret floor than increasing model complexity. We also show that heterogeneity across issuers worsens learnability beyond what average impairment rates suggest. The paper contributes a theory of why fraud detection in payment networks is fundamentally harder than in standard online learning settings, identifies ecosystem information quality as the key bottleneck, and provides a theoretical basis for prioritizing investments in reporting infrastructure, dispute process quality, and selective exploration. The paper is theory-first and does not rely on proprietary transaction data.

Gaurav Dhama

Mastercard

Fraud Detection Payment Networks Fundamental Limits Structural Complexity

May 23, 2026cs.AI

PRIMA: Operational Patterns for Resilient Multi-Agent Research with Verifiable Identity and Convergent Feedback

Operating LLMs as coordinated multi-agent research systems over multi-hour runs surfaces failure modes that single-shot evaluation cannot: upstream providers throttle without warning, sub-agents drift the task to fit accessible tools, narrate machinery instead of using it, open revision iterations with self-apology, or treat upstream context as executable directives. We present PRIMA, whose primary contributions are three operational patterns for surviving these failure modes: (1) a resilience-and-recovery layer that detects upstream rate-limit signals, persists a typed pause record to disk, and resumes long-running runs without re-executing converged work even across process restarts; (2) a sub-agent operating discipline encoding task-fidelity, tool-use, revision, and inter-step context-boundary norms as a structural prompt layer; (3) a multi-phase application pattern for structured engineering deliverables pairing orthogonal draft steps with an explicit cross-document harmonization pass before final synthesis. These sit atop a foundational protocol: a research-program specification language with explicit convergence criteria, a dual-metric scoring engine (LLM-judged rubric plus sandboxed code), an outer meta-optimization loop, event-driven persistence, hook-based middleware, context compaction, and a multi-provider LLM abstraction. Agent identities derive from prime powers, giving collision-free identifiers and trivially-verifiable cluster membership without a central registry. Theoretical guarantees include

O(k)

verification,

O(V+E)

DAG validation, and identity collision freedom by the Fundamental Theorem of Arithmetic. A Graph Isomorphism case study grounds the architectural claims in a generated artifact: a six-step protocol that produced a research paper proposing a new canonical-form algorithm with three theorems and five conjectures.

Sasank Annapureddy

Resilience Fundamental Limits Feedback

May 23, 2026cs.AI

Fundamental Limitation in Explaining AI

While large-scale models such as LLMs and diffusion models have achieved practical success, public institutions have emphasized the importance of explainability in AI. Existing methods for explaining AI, however, are not designed to provide completely faithful explanations of the behavior of large-scale AI systems. Although a completely faithful and interpretable explanation of the behavior of an AI system might be useful for AI governance, it has not been known whether providing such an explanation is theoretically possible. In this paper, we mathematically prove a fundamental quadrilemma in explaining AI, stating that AI and its explanation cannot satisfy the following four conditions simultaneously: 1) the complexity of the operation environment, 2) the goodness of the AI's performance, 3) the interpretability of the AI's explanation, and 4) the complete faithfulness of the AI's explanation. This quadrilemma suggests that, in most applications where we cannot change the environment or sacrifice good AI performance and an interpretable explanation, we should give up complete faithfulness of explanations and should instead aim to explain only the parts that are important for applications. As a consequence, the quadrilemma implies that AI governance should be designed on the premise that the faithfulness of AI explanations is always incomplete.

Atsushi Suzuki, Jing Wang

Department of Mathematics Faculty of Science The University of Hong Kong Hong Kong SAR · School of Computing and Mathematical Sciences Faculty of Engineering and Science University of Greenwich United Kingdom

Explainable Artificial Intelligence Artificial Intelligence Governance Fundamental Limits

May 19, 2026cs.HC

The Accessibility Capability Boundary: Operational Limits and Expansion Potential of AI-Generated Browser-Native Accessibility Systems

As large language models (LLMs) demonstrate increasing competence in synthesizing functional user interfaces, a fundamental question emerges in accessibility computing: \textit{how far can AI-driven accessibility systems go?} This paper introduces the \textit{Accessibility Capability Boundary} (ACB), a formal framework for reasoning about the operational limits and expansion potential of autonomous accessibility systems, and grounds this theory in a real-world systems artifact. We model accessibility not as a binary compliance property but as a dynamic, multidimensional capability space constrained by measurable variables including deployment latency, cognitive load, infrastructure dependency, offline persistence, interaction complexity, and adaptability. We argue that AI-generated, browser-native systems constructed as single-file HTML artifacts leveraging standard browser APIs may dramatically shift the ACB outward by reducing deployment friction to near-zero and enabling rapid, context-specific interface adaptation. We ground our theoretical framework in the analysis of two real-world exploratory prototypes. The first is an AI-generated browser-native accessibility interface deployed for a blind user in Nepal. The second is a fully functional, open-source webcam alignment assistant for visually impaired users, serving as a concrete systems artifact. Through formal definitions, propositions, and a comparative evaluation matrix, we characterize the regions of the accessibility capability space that such systems can and cannot reach. We further identify remaining computational, infrastructural, and verification constraints that constitute the hard boundaries of this paradigm. This work contributes a theoretical foundation for understanding the scalable limits of autonomous accessibility computing and proposes a research agenda for future work in accessibility-aware AI systems.

Rizwan Jahangir, Daisuke Ishii

NUST Business School, NUST, Islamabad, Pakistan · Kiara Inc., Tokyo, Japan

Accessibility Assistive Agents Browser Agent Fundamental Limits

May 13, 2026cs.LG

Mix, Don't Tune: Bilingual Pre-Training Outperforms Hyperparameter Search in Data-Constrained Settings

For most languages of the world, language model pre-training operates in a data-constrained regime where models must repeat their training data many times, degrading generalization. Two remedies exist: aggressive hyperparameter tuning such as high weight decay, and mixing in data from a high-resource auxiliary language to directly aid the low-resource target. While hyperparameter tuning regularizes the model by shrinking weights to restrict network capacity, auxiliary data mixing uses a tunable mixing ratio to expand the training distribution and diversify the training signal with new knowledge. Both offer a principled way to improve training in a data-constrained domain. We compare these levers systematically across four model scales from 150M to 1.43B parameters, using Arabic as the low-resource target and English as the auxiliary, over approximately 1000 pre-training runs. Three findings emerge. First, mixing yields larger improvements than hyperparameter tuning on both validation loss and downstream task accuracy, and the gap grows with model size. Second, we quantify how much mixing helps: it boosts performance by an amount equivalent to 2--3

\times

the unique target data on validation loss and 2--13

\times

on downstream task accuracy, with the gain scaling steeply with model size. Third, this divergence reveals that target-language validation loss systematically underestimates mixing's value. Mixing regularizes by diversifying the training signal and contributes knowledge the repeated target corpus cannot supply; validation loss captures only the first effect. Our practical recommendations are: mix in a high-resource language, prioritize the mixing ratio over hyperparameter tuning, and transfer hyperparameters from a small proxy model via

μ

P.

Paul Jeha, Anastasiia Sedova, Louis Béthune +4

1Apple · 2DTU

Multilingual Language Models Hyperparameter Mix Low-Resource Languages Tuning Loss Function+1

May 13, 2026stat.ML

On Hallucinations in Inverse Problems: Fundamental Limits and Provable Assessment Methods

Artificial intelligence (AI) has transformed imaging inverse problems, from medical diagnostics to Earth observation. Yet deep neural networks can produce hallucinations, realistic-looking but incorrect details, undermining their reliability, especially when ground truth data is unavailable. We develop a theoretical framework showing that such hallucinations are not merely artifacts of particular models, but can arise from the ill-posed nature of the inverse problem itself. We derive necessary and sufficient conditions for hallucinations, together with computable bounds on their magnitude that depend only on the forward model. Building on this theory, we introduce algorithms to: (1) estimate the minimum hallucination magnitude achievable by any reconstruction model for a given input; (2) assess the faithfulness of reconstructed details by a given reconstruction model. Experiments across three imaging tasks demonstrate that our approach applies broadly, including to modern generative models, and provides a principled way to quantify and evaluate AI hallucinations.

David Iagaru, Nina M. Gottschling, Anders C. Hansen +1

CMAP, Ecole polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France. · German Aerospace Center (DLR), Remote Sensing Technology Institute, Wessling, Germany. · Computing and Computational Sciences, Oak Ridge National Laboratory, Oak Ridge, Tennessee. +2

Hallucination Rate Inverse Problem Ai-Generated Image Detection Ground Truth Fundamental Limits Computerized Adaptive Testing

May 12, 2026cs.AI

NOVA: Fundamental Limits of Knowledge Discovery Through AI

Can AI systems discover genuinely new knowledge through iterative self improvement, and if so, at what cost? We introduce the NOVA framework, which models the common ``generate, verify, accumulate, retrain'' loop as an adaptive sampling process over a knowledge space. We identify sufficient conditions under which accumulated genuine knowledge eventually covers a finite domain, and show how their violations produce distinct failure modes: contamination, forgetting, exploration failure, and acceptance failure. We then analyze imperfect verification and identify a contamination trap: as easy-to-find knowledge is exhausted, the model mass assigned to new valid artifacts shrinks, so even small false-positive rates can cause invalid artifacts to enter the knowledge base faster than genuine discoveries. We clarify that Good--Turing estimation is a local batch-diversity diagnostic, not an estimator of the historically undiscovered valid mass that governs long-term discovery. Under a separate tail-equivalence assumption relating the model's effective discovery distribution to a Zipf law with exponent

α>1

, we prove that the cumulative generation cost required to obtain

D

distinct genuine discoveries satisfies

R_{\mathrm{cum}}(D)=Θ(c_{\mathrm{gen}}D^α)

, where

c_{\mathrm{gen}}

is the per-candidate generation cost. This scaling law quantifies asymptotic diminishing returns as the discovery frontier advances. Finally, we formalize human amplification through guidance, generation, and verification, explaining why expert input is most valuable near autonomous exploration barriers.

Salman Avestimehr, Ken Duffy, Muriel Médard

University of Southern California · Northeastern University · Massachusetts Institute of Technology

Fundamental Limits Recursive Self-Improvement

May 8, 2026cs.LG

Theoretical Limits of Language Model Alignment

Language model (LM) alignment improves model outputs to reflect human preferences while preserving the capabilities of the base model. The most common alignment approaches are (i) reinforcement learning, which maximizes the expected reward under a KL-divergence constraint, and (ii) best-of-

N

alignment, which selects the highest-reward output among

N

independent samples. Despite their widespread use, the fundamental limits of reward improvement under a KL budget remain poorly understood. We characterize the information-theoretic limits of KL-regularized alignment by deriving the maximum achievable expected reward gain for a fixed KL-divergence budget. Our first result provides a closed-form expression for the optimal reward improvement, governed by a Jeffreys divergence term rather than the

\sqrt{\texttt{KL}}

used in prior analyses. We further reformulate this expression as a covariance under the base model, yielding a practical estimator that predicts achievable alignment gains from base model samples alone. We extend our analysis to the proxy reward setting, showing that the gap between ideal and proxy alignment (reward hacking) grows with the magnitude of reward error and when the KL penalty factor decreases. We then prove that reward ensembling mitigates reward hacking, providing a theoretical justification for this technique used in practice. Empirically, we compute the KL-reward Pareto frontier for two tasks for LMs, safety and summarization, and show that best-of-

N

closely approaches the theoretical limit, while PPO and GRPO remain substantially suboptimal. Our theoretical results shed light on several empirically observed phenomena in the alignment literature and suggest that algorithmic improvements are needed to achieve optimal alignment without high inference costs.

Lucas Monteiro Paes, Natalie Mackraz, Barry-John Theobald +1

Apple

Large Language Model Alignment Fundamental Limits Divergence Pareto Frontier

May 3, 2026cs.RO

Lateral String Stability for Vehicle Platoons: Formulation, Definition, and Analysis

Platooning of connected and automated vehicles provides significant benefits in terms of energy efficiency, traffic throughput, and, most critically, safety. These safety benefits depend on string stability, which dictates how disturbances propagate along a vehicle string. Although longitudinal string stability has been extensively examined, lateral string stability, which governs the propagation of path-tracking errors that can lead to unsafe deviations from the desired path, remains underexplored. Its importance is growing as autonomous vehicles increasingly depend on onboard sensing and map-free navigation, where sensor occlusions and tight formations amplify safety risks. This paper presents a framework for lateral string stability that focuses directly on safety-critical, path-relative tracking errors and enables consistent comparison across vehicles that follow the same planned path. The key element of the framework is an arc-length (Eulerian) viewpoint, a departure from traditional analyses, that clarifies how tracking errors at a given point on the path propagate from one vehicle to the next. Building on this foundation, we propose the definition of L2 lateral string stability along with two control strategies: a feedback-feedforward strategy that relies solely on onboard sensing, and a novel learn-from-predecessor strategy that makes use of vehicle-to-vehicle communication. Both strategies are analyzed for lateral string stability with respect to two error measures: tracking error vector and lateral (cross-track) error. Our results show that onboard sensing alone cannot guarantee attenuation of path-tracking errors, imposing a fundamental safety limitation, while V2V communication enables true error attenuation. The analysis further identifies structural controller requirements, showing that nonzero feedback on specific measurements is essential for guaranteeing stability.

Sixu Li, Swaroop Darbha, Yang Zhou

Zachry Department of Civil & Environmental Engineering, Texas A&M University, College Station, TX 77843, USA · J. Mike Walker ’66 Department of Mechanical Engineering, Texas A&M University, College Station, TX 77843, USA

Vehicle Dynamics Lateral String Stability Safety Constraints Fundamental Limits

May 2, 2026cs.SE

Practical Limits of Autonomous Test Repair: A Multi-Agent Case Study with LLM-Driven Discovery and Self-Correction

Maintaining reliable UI test suites in large-scale enterprise applications is a persistent and costly challenge. We present an industrial case study of a multi-agent autonomous testing system evaluated using anonymized execution data from a production-like enterprise UI testing prototype. The application features several hundred dynamic UI elements per screen. Built on a large language model with LangGraph orchestration, Playwright execution, and a RAG knowledge base, the system evolves from human-directed testing toward High-autonomy feature discovery and test execution: given no explicit test targets, it discovers over 100 testable features across 10 UI screens, dynamically expands coverage by an additional 15--30 features through runtime DOM analysis, and iteratively repairs failing tests without human intervention. We analyzed 300 consecutive autonomous execution reports encompassing 636 individual test-case executions across 10 distinct scenario families. The system achieved a 70% repair convergence rate at the scenario-family level, with a mean of 3.4 repair iterations to convergence. However, only 10% of scenario families succeeded on first attempt, 38% of reports failed to produce any executable test artifact, and we documented concrete instances of assertion weakening and test-case deletion used as workaround mechanisms to achieve superficial convergence. Our findings show that unrestricted autonomy leads to unstable and often misleading outcomes, while constrained autonomy transforms such systems into operationally viable workflows. Rather than advocating full autonomy, our findings suggest that reliable autonomous testing in enterprise-scale settings requires explicit constraints, validation boundaries, and human oversight to preserve semantic correctness and operational trustworthiness.

Hyukjoo Lee

Independent Researcher Republic of Korea

Test Generation Automated Program Repair Autonomous Agents Penetration Testing Repair Multi-Agent Communication+1

Apr 30, 2026cs.CY

The Likelihood Ratio Wall: Structural Limits on Accurate Risk Assessment for Rare Violence

Pretrial risk assessment tools are used on over one million U.S. defendants each year, yet their use for predicting rare violent re-offense faces a basic statistical barrier. We derive a universal precision bound -- the Likelihood Ratio Wall -- showing that when violent re-arrest rates are low (2-5%), achieving even a 50% hit rate among people labeled "high risk" (positive predictive value, or PPV) would require tools far more discriminative than current instruments appear to be. For rare outcomes, a tool can have respectable-looking performance metrics and still be wrong most of the time it flags someone as "high risk for violence." We show that post-hoc score recalibration cannot solve this problem because it does not improve the tool's underlying ability to separate true positives from false positives. We further prove a Surveillance Ceiling: when over-policing inflates recorded "risk factors" among those who would not re-offend, the maximum achievable precision is structurally lower for over-policed groups, even at equal offense rates. We translate these results into the Number Needed to Detain (how many people must be detained to prevent one violent offense), and propose that risk reports should communicate this uncertainty explicitly. Our findings suggest that for rare violent outcomes, debates about fairness metrics alone are incomplete: under current data regimes, the available features may not support high-confidence individualized detention decisions.

Marco Pollanen

Trent University, Canada · Trent University, Peterborough, ON, Canada

Violence Detection Rare Events False-Negative Rate Fundamental Limits

Apr 29, 2026cs.AI

Evaluating TabPFN for Mild Cognitive Impairment to Alzheimer's Disease Conversion in Data Limited Settings

Accurate prediction of conversion from Mild Cognitive Impairment (MCI) to Alzheimers Diseases (AD) is essential for early intervention, however, developing reliable conversion predictive models is difficult to develop due to limited longitudinal data availability We evaluate TabPFN (Tabular Pre-Trained Foundation Network) against traditional machine learning methods for predicting 3 year MCI to AD conversion using the TADPOLE dataset derived from ADNI. Using multimodal biomarker features extracted from demographics, APOE4, MRI volumes, CSF markers, and PET imaging, we conducted an experimental comparison across varying training set sizes (N=50 to 1000) and models including XGBoost, Random Forest, LightGBM, and Logistic Regression. TabPFN achieved one the highest performance (AUC=0.892), outperforming LightGBM (AUC=0.860) and demonstrating advantages in low data settings. At N=50 training samples, TabPFN maintained strong AUC while the traditional machine learning models struggles at small training samples. These findings demonstrate that foundation models are promising for disease prediction in data limited scenarios, such as Alzheimers diseases.

Brad Ye, Bulent Soykan, Gulsah Hancerliogullari Koksalmis +2

Department of Medicine, University of Central Florida College of Medicine, Orlando, FL, USA · NIMBUS Lab, University of Central Florida · Department of Mechanical, Industrial & Manufacturing Eng., The University of Toledo, Toledo, OH, USA +3

Mild Cognitive Impairment Alzheimer Tabular Foundation Models Disease Longitudinal Data Fundamental Limits

Apr 27, 2026cs.LG

A Limit Theory of Foundation Models: A Mathematical Approach to Understanding Emergent Intelligence and Scaling Laws

Emergent intelligence have played a major role in the modern AI development. While existing studies primarily rely on empirical observations to characterize this phenomenon, a rigorous theoretical framework remains underexplored. This study attempts to develop a mathematical approach to formalize emergent intelligence from the perspective of limit theory. Specifically, we introduce a performance function E(N, P, K), dependent on data size N, model size P and training steps K, to quantify intelligence behavior. We posit that intelligence emerges as a transition from finite to effectively infinite knowledge, and thus recast emergent intelligence as existence of the limit

\lim_{N,P,K \to \infty} \mathcal{E}(N,P,K)

, with emergent abilities corresponding to the limiting behavior. This limit theory helps reveal that emergent intelligence originates from the existence of a parameter-limit architecture (referred to as the limit architecture), and that emergent intelligence rationally corresponds to the learning behavior of this limit system. By introducing tools from nonlinear Lipschitz operator theory, we prove that the necessary and sufficient conditions for existence of the limit architecture. Furthermore, we derive the scaling law of foundation models by leveraging tools of Lipschitz operator and covering number. Theoretical results show that: 1) emergent intelligence is governed by three key factors-training steps, data size and the model architecture, where the properties of basic blocks play a crucial role in constructing foundation models; 2) the critical condition Lip(T)=1 for emergent intelligence provides theoretical support for existing findings. 3) emergent intelligence is determined by an infinite-dimensional system, yet can be effectively realized in practice through a finite-dimensional architecture. Our empirical results corroborate these theoretical findings.

Jun Shu, Junxiong Jia, Deyu Meng +1

School of Mathematics and Statistics, Xi’an Jiaotong University.

General Intelligence Emergence Wireless Foundation Models Fundamental Limits Foundation Model Mathematics

Apr 16, 2026cs.IT

Exploiting Correlations in Federated Learning: Opportunities and Practical Limitations

The communication bottleneck in federated learning (FL) has spurred extensive research into techniques to reduce the volume of data exchanged between client devices and the central parameter server. In this paper, we systematically classify gradient and model compression schemes into three categories based on the type of correlations they exploit: structural, temporal, and spatial. We examine the sources of such correlations, propose quantitative metrics for measuring their magnitude, and reinterpret existing compression methods through this unified correlation-based framework. Our experimental studies demonstrate that the degrees of structural, temporal, and spatial correlations vary significantly depending on task complexity, model architecture, and algorithmic configurations. These findings suggest that algorithm designers should carefully evaluate correlation assumptions under specific deployment scenarios rather than assuming that they are always present. Motivated by these findings, we propose two adaptive compression designs that actively switch between different compression modes based on the measured correlation strength, and we evaluate their performance gains relative to conventional non-adaptive approaches. In summary, our unified taxonomy provides a clean and principled foundation for developing more effective and application-specific compression techniques for FL systems.

Adrian Edin, Michel Kieffer, Mikael Johansson +1

Department of Electrical Engineering (ISY), Linköping University, SE-581 83 Linköping, Sweden · CentraleSupélec, CNRS, L2S, Université Paris-Saclay, Gif-sur-Yvette, FR-91192, France · Division of Decision and Control Systems, School of EECS, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden

Federated Learning Generative Image Compression Spurious Correlations Gradient Bottlenecks Fundamental Limits

Apr 16, 2026cs.LG

On the Expressive Power and Limitations of Multi-Layer SSMs

We study how depth, finite precision, state dimension, and chain-of-thought (CoT) affect the expressive power of multi-layer state-space models (SSMs). For the explicit-table

K

-function-composition problem, a canonical benchmark for sequential information propagation, we prove that any

L

-layer SSM solving

(L+3)

-function composition must satisfy

d^2p=Ω(N/L^3)

, where

d

is the state dimension and

p

is the per-scalar precision. Conversely,

K

-function composition is solved exactly by a

(K+1)

-layer generalized SSM with

d=1

and

p=Θ(\log N)

. This gives a worst-case depth hierarchy for this formal problem family. We then distinguish post-input reasoning, in which all thought tokens are generated after the input, from input-interleaved reasoning, in which thought tokens may be inserted while the input stream is being read. Post-input reasoning does not circumvent our communication-based lower-bound pipeline, whereas input-interleaved reasoning admits bidirectional simulations with general deterministic one-pass streaming algorithms at the granularity of persistent memory. Finally, width and precision are not interchangeable under exact step-preserving simulation in the base affine-state model, but become interchangeable through the streaming-memory characterization once input-interleaved reasoning is allowed.

Nikola Zubić, Qian Li, Yuyi Wang +1

Robotics and Perception Group University of Zurich · Shenzhen International Center For Industrial And Applied Mathematics Shenzhen Research Institute of Big Data · Tengen Intelligence Institute2026 CRRC Zhuzhou Institute

State Space Models Expressivity Chain-of-Thought Reasoning Fundamental Limits

Mar 19, 2026math.OC

Fundamental Limits for Sensor-Based Control via the Gibbs Variational Principle

Fundamental limits on the performance of feedback controllers are essential for benchmarking algorithms, guiding sensor selection, and certifying task feasibility -- yet few general-purpose tools exist for computing them. Existing information-theoretic approaches overestimate the information a sensor must provide by evaluating it against the uncontrolled system, producing bounds that degrade precisely when feedback is most valuable. We derive a lower bound on the minimum expected cost of any causal feedback controller under partial observations by applying the Gibbs variational principle to the joint path measure over states and observations. The bound applies to nonlinear, nonholonomic, and hybrid dynamics with unbounded costs and admits a self-consistent refinement: any good controller concentrates the state, which limits the information the sensor can extract, which tightens the bound. The resulting fixed-point equation has a unique solution computable by bisection, and we provide conditions under which the free energy minimization is provably convex, yielding a certifiably correct numerical bound. On a scalar LQG problem the self-consistent bound captures over 80% of the known optimal cost at moderate sensor noise, and on a nonlinear Dubins car tracking problem it remains informative across all noise levels where a bound using the uncontrolled state distribution is vacuous.

Vincent Pacelli, Evangelos A. Theodorou

Daniel Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA, 30308

Robust Control Variational Fundamental Limits Free Energy Principle

Feb 15, 2026cs.LG

Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds

Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency, yet the distribution of the iterates is typically intractable. Classical asymptotics results give

X_k^{(α)} \approx X^{(α)} \approx x^\star+\sqrtαY

, where

X^{(α)}

is the steady state and

Y

is an appropriate Gaussian limit, by progressively taking the time

k\uparrow\infty

and stepsize

α\downarrow0

. Such limit results, however, do not quantify finite-time, finite-stepsize errors. We develop an explicit pre-limit characterization for SA with i.i.d.\ and Markovian noise. We establish existence and uniqueness of the stationary law, a geometric Wasserstein convergence to stationarity, and almost-sure and

L^3

convergence of the steady state to the root

x^\star

, identifying the scale

\sqrtα

as first-order fluctuation. At this scale, we derive a higher-order quantitative Gaussian approximation with a Wasserstein error, using Stein's method and Poisson equation techniques. We further obtain non-uniform Berry--Esseen-type tail bounds, incorporating both steady-state approximation and finite-time convergence errors. We instantiate the theory for strongly convex smooth SGD, linear SA, and nonlinear contractive SA. Beyond strong convexity, for general convex SGD, we identify a Gibbs limiting law and prove a pre-limit Wasserstein approximation error under stability and Stein-equation hypothesis, which are validated numerically.

Zedong Wang, Yuyang Wang, Ijay Narang +3

H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA · Department of Mathematics, Brown University, Providence, RI 02912, USA · School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA +2

Stochastic Approximation Finite Time Analysis Convergence Stationarity Wasserstein Distance Gaussian Primitives+1

Sep 2, 2025cs.CL

LLMs and their Limited Theory of Mind: Evaluating Mental State Annotations in Situated Dialogue

What if large language models could not only infer human mindsets but also expose every blind spot in team dialogue such as discrepancies in the team members' joint understanding? We present a novel, two-step framework that leverages large language models (LLMs) both as human-style annotators of team dialogues to track the team's shared mental models (SMMs) and as automated discrepancy detectors among individuals' mental states. In the first step, an LLM generates annotations by identifying SMM elements within task-oriented dialogues from the Cooperative Remote Search Task (CReST) corpus. Then, a secondary LLM compares these LLM-derived annotations and human annotations against gold-standard labels to detect and characterize divergences. We define an SMM coherence evaluation framework for this use case and apply it to six CReST dialogues, ultimately producing: (1) a dataset of human and LLM annotations; (2) a reproducible evaluation framework for SMM coherence; and (3) an empirical assessment of LLM-based discrepancy detection. Our results reveal that, although LLMs exhibit apparent coherence on straightforward natural-language annotation tasks, they systematically err in scenarios requiring spatial reasoning or disambiguation of prosodic cues.

Katharine Kowalyshyn, Matthias Scheutz

Department of Computer Science Tufts University

Large Language Model Annotations Dialogue Discrepancy Fundamental Limits