LR-ARC-PRIZE-2026 · Artificial Intelligence
OPENAI reasoning and fluid intelligence
ARC Prize 2026 is an open-source AI reasoning competition spanning ARC-AGI-2, ARC-AGI-3, and a paper prize, with a combined prize pool of $2 million.
Loading
Limits RegistryRegistry collection
Limits of Artificial Intelligence
Theoretical and empirical boundaries on learning systems, models, agents, and AI performance.
44 published records in this collectionLR-003601 · AI
PROVENAgnostic PAC sample complexity
Optimal distribution-free sample order for agnostic binary classification with VC dimension d.
LR-SOLAR-FILAMENT-2026 · Artificial Intelligence
OPENAutomated solar-filament segmentation
The Solar Filament Segmentation Challenge 2026 is a computer-vision competition with an advertised prize pool of up to $3,000.
LR-003626 · AI
PROVENAutoregressive cached-attention decoding work
Summing per-step attention over a growing cached context gives quadratic total interaction work.
LR-003627 · AI
PROVENAutoregressive transformer KV-cache size
Stored keys and values grow linearly in layers, context tokens, KV heads, and head width.
LR-003628 · AI
OPENChinchilla compute-optimal language-model frontier
Empirical compute-optimal parameter and token allocation for the model families and data regime studied in 2022.
LR-DRAFT-CHINCHILLA · AI
OPENCompute-optimal language-model scaling
Training a fixed compute budget into an ever-larger model isn't always the best use of that compute — the Chinchilla study found that model size and training-token count should scale together, not model size alone, to reach the best loss for a given budget.
LR-DRAFT-RETRIEVAL · AI
OPENContext-window retrieval reliability floor
Long-context language models don't retrieve information from anywhere in their context window with equal reliability — accuracy varies with where the relevant fact sits, how many distractors surround it, and which model and prompt are used, so no single model-independent floor can be asserted.
LR-003620 · AI
PROVENDense self-attention score computation complexity
Exact dense dot-product attention forms all n-by-n query-key interactions of width d.
LR-003634 · AI
PROVENDiscounted Bellman optimality contraction
The Bellman optimality operator is a gamma contraction for a discounted finite MDP.
LR-003635 · AI
PROVENDiscounted value-iteration error decay
Value iteration converges geometrically under the discounted Bellman contraction.
LR-003604 · AI
PROVENFinite-class agnostic uniform-convergence bound
Sample order sufficient for uniform convergence over a finite binary hypothesis class.
LR-003603 · AI
PROVENFinite-class consistent PAC sample bound
Sufficient realizable-case sample size for a consistent learner over a finite hypothesis class.
LR-003609 · AI
PROVENFinite-class minimax online mistake bound
Optimal deterministic realizable online mistake complexity equals the class Littlestone dimension.
LR-003623 · AI
PROVENFlashAttention HBM IO complexity
HBM traffic is asymptotically optimal over the SRAM-size range analyzed in the paper.
LR-003622 · AI
PROVENFlashAttention exact-attention memory
IO-aware tiling computes exact attention without materializing the quadratic score matrix.
LR-AIMO-PRIZE · Artificial Intelligence
OPENGold-medal-level mathematical reasoning by an AI model
The AIMO Prize is a $10 million program to accelerate open AI systems that can reason mathematically, including a $5 million grand prize and staged progress prizes.
LR-003631 · AI
PROVENGraph Isomorphism Network expressivity
With injective aggregation and sufficient capacity, GIN matches one-dimensional Weisfeiler-Leman distinguishing power.
LR-003625 · AI
PROVENGrouped-query-attention KV-cache scaling
G key/value groups interpolate cache size between multi-query and full multi-head attention.
LR-003605 · AI
PROVENHalving algorithm realizable mistake bound
Online halving makes at most logarithmically many mistakes when a finite class contains a perfect hypothesis.
LR-003629 · AI
OPENKaplan language-model scaling frontier
Empirical neural language-model loss scaling with model size, dataset size, and compute in the studied regime.
LR-003621 · AI
PROVENMaterialized dense-attention score memory
Explicit storage of the dense attention score or probability matrix grows quadratically with sequence length.
LR-003630 · AI
PROVENMessage-passing GNN expressivity ceiling
Standard permutation-invariant message-passing GNNs cannot distinguish graphs that one-dimensional Weisfeiler-Leman cannot distinguish.
LR-003632 · AI
PROVENMessage-passing receptive-field radius
A k-layer local message-passing network depends only on each node's k-hop computation neighborhood.
LR-003615 · AI
PROVENMinimum ReLU width for Lp universal approximation
Exact minimum hidden width for universal Lp approximation under the paper's ReLU architecture.
LR-003624 · AI
PROVENMulti-query-attention KV-cache scaling
A single shared key/value head makes per-layer KV cache linear in context length and head width, independent of query-head count.
LR-003610 · AI
PROVENNo-free-lunch learner superiority limit
Averaged uniformly over all objective functions, optimization algorithms have identical performance.
LR-003617 · AI
PROVENOne-neuron residual-block universality
Arbitrarily deep residual networks with one-neuron hidden layers are universal L1 approximators.
LR-003611 · AI
PROVENPAC-Bayes generalization bound
Posterior expected risk is controlled by empirical risk and divergence from a data-independent prior.
LR-003606 · AI
PROVENPerceptron margin mistake bound
Perceptron mistakes are bounded for linearly separable examples of norm at most R and margin gamma.
LR-003633 · AI
PROVENPermutation-invariant GNN graph representation requirement
Non-injective neighborhood aggregation loses distinctions available to the 1-WL test.
LR-003614 · AI
PROVENPiecewise-linear network pseudodimension bound
Tight parameter-unit capacity order for networks with W parameters and U nonlinear units.
LR-003616 · AI
PROVENReLU width-d universal-approximation impossibility
Fully connected ReLU networks no wider than the input dimension fail universal approximation.
LR-003613 · AI
PROVENReLU-network VC-dimension lower bound
Constructive lower capacity bound for piecewise-linear networks over the stated parameter range.
LR-003612 · AI
PROVENReLU-network VC-dimension upper bound
Upper capacity bound for piecewise-linear networks with W parameters and L layers.
LR-003600 · AI
PROVENRealizable PAC sample complexity
Minimum iid labeled examples for distribution-free realizable PAC learning of VC dimension d.
LR-003602 · AI
PROVENSauer–Shelah growth-function bound
A VC-dimension-d class cannot realize more labelings than the binomial growth bound.
LR-003619 · AI
PROVENSingle-layer ReLU linear-region upper bound
Maximum affine regions cut by n ReLU hyperplanes in d-dimensional general position.
LR-003636 · AI
PROVENTabular Q-learning convergence limit
Tabular Q-learning converges under finite MDP, sufficient exploration, bounded rewards, and Robbins-Monro step sizes.
LR-003618 · AI
PROVENThree-node threshold-network training complexity
Finding weights consistent with labeled examples is NP-complete even for the specified three-node network.
LR-DRAFT-ATTENTION · AI
OPENTransformer attention memory and IO scaling
Exact self-attention naively materializes a score matrix that grows quadratically with sequence length, which is what limits how long a context transformer models can practically handle. IO-aware kernels like FlashAttention avoid materializing that full matrix, trading a fixed compute cost for dramatically less memory traffic.
LR-003637 · AI
PROVENUCB1 stochastic-bandit regret bound
UCB1 has logarithmic instance-dependent expected regret for bounded iid arm rewards.
LR-003608 · AI
PROVENWeighted-majority expert regret bound
Weighted majority competes with the best of N experts under bounded losses.
LR-003607 · AI
PROVENWinnow sparse-disjunction mistake bound
Winnow learns a monotone disjunction with k relevant variables among n attributes with logarithmic dimension dependence.