Non-Asymptotic Length Generalization

• URL: http://arxiv.org/abs/2506.03085v2
• Date: Fri, 06 Jun 2025 07:47:10 GMT
• Title: Non-Asymptotic Length Generalization
• Abstract summary: We provide provable guarantees of length generalization for various classes of functions in an idealized setting.<n>We show the Minimum-Complexity Interpolator learning algorithm achieves optimal length complexity.
• Score: 26.982645261213847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Length generalization is the ability of a learning algorithm to learn a hypothesis which generalizes to longer inputs than the inputs in the training set. In this paper, we provide provable guarantees of length generalization for various classes of functions in an idealized setting. First, we formalize the framework of non-asymptotic length generalization, which requires a computable upper bound for the minimum input length that guarantees length generalization, as a function of the complexity of ground-truth function under some given complexity measure. We refer to this minimum input length to length generalize as length complexity. We show the Minimum-Complexity Interpolator learning algorithm achieves optimal length complexity. We further show that whether a function class admits non-asymptotic length generalization is equivalent to the decidability of its language equivalence problem, which implies that there is no computable upper bound for the length complexity of Context-Free Grammars. On the positive side, we show that the length complexity of Deterministic Finite Automata is $2n - 2$ where $n$ is the number of states of the ground-truth automaton. Our main results are upper bounds of length complexity for a subset of a transformer-related function class called C-RASP (Yang & Chiang, 2024). We show that the length complexity of 1-layer C-RASP functions is $O(T^2)$ when the ground-truth function has precision $T$, and that the length complexity of 2-layer C-RASP functions is $O(T^{O(K)})$ when the ground-truth function has precision $T$ and $K$ heads.

Related papers

• The Head Complexity of Boolean Functions in Single-Layer Attention [2.2727733134290813]
  We study the minimum number of attention heads required to compute a function in a one-layer attention-only model.<n>We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity.<n>We also establish compactness bounds for embedding dimension and numerical precision.
  arXiv  Detail & Related papers  (2026-09-03T16:22:02Z)
• Fast Bounded-Independence Functions and Their Duals [21.031497777539332]
  Motivated by cryptographic applications, we generalize and improve on previous results in this area.<n>We demonstrate the usefulness of the above results to cryptography.<n>This includes the first nontrivial protocols for perfectly secure multiparty computation.
  arXiv  Detail & Related papers  (2026-06-05T07:53:04Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  We study the computational complexity of estimating the normalized trace $2-nTr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits.<n>This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.<n>We show that if $f(x)$ is a continuous function with approximate degree $(rm poly(n))$, then estimating $2-nTr[f(A)]$ up to constant additive error is
  arXiv  Detail & Related papers  (2026-04-02T01:15:12Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder.<n>We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Quantum computational complexity of matrix functions [2.7488316163114823]
  We study the computational complexity of two primitive problems.<n>We consider four functions -- monomials, Chebyshevs, the time evolution function, and the inverse function.<n>We identify BQP-complete forms of both problems for each function.
  arXiv  Detail & Related papers  (2024-10-17T18:00:03Z)
• Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
  Multiaccurate predictors satisfy a stronger condition: they are calibrated on each set in the collection. This complexity-theoretic Regularity Lemma is known to have implications in different areas. We show that every function (regardless of its hardness) has a small collection of disjoint hardcore sets.
  arXiv  Detail & Related papers  (2023-12-28T18:53:21Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  We propose a provably efficient reinforcement learning algorithm (both computationally and statistically) with general value function approximations. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting.
  arXiv  Detail & Related papers  (2023-02-22T20:21:25Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  Main algorithm is assembled from two components which may be of independent interest. A variant of LINEARSEQ is shown to have adaptive complexity of $O(log(n))$ smaller than that of any previous algorithm in the literature.
  arXiv  Detail & Related papers  (2021-11-15T17:10:40Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams [0.0]
  An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function.<n>This paper shows that a further speedup is possible with quantum computers by demonstrating the existence of a quantum algorithm that produces a minimum OBDD.
  arXiv  Detail & Related papers  (2019-09-27T12:52:07Z)

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

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