Abstract
Large Language Models (LLMs) have achieved remarkable success but remain theoretical "black boxes." This work provides the first end-to-end provable learning guarantee for a generative model that captures the behavior of modern LLMs. By exploiting the empirical observation that LLMs exhibit "low logit rank," the authors develop a polynomial-time algorithm capable of learning an LLM's underlying probability distribution using logit queries.
Introduction: The Black Box Problem
Despite their ubiquity, LLMs lack a robust theoretical framework. Existing models like Hidden Markov Models (HMMs) or single attention layers are either too simplistic to represent natural language or too complex to offer provable guarantees. Furthermore, learning these distributions from raw samples is computationally hard due to the potential encoding of "noisy parities," a classic hard problem in computer science. To circumvent this, the authors propose a query learning model: if we have access to a model's logits (the raw scores before the final softmax layer), can we efficiently reconstruct its behavior?
The Low Logit Rank Abstraction
The core of this approach is the Low Logit Rank hypothesis. If one constructs a matrix where rows represent "histories" (prompts) and columns represent "futures" (responses), the entries—representing log-probabilities—form an approximately low-rank matrix. This structure is more manageable than the probability space, which often lacks linear structure.
Algorithmic Framework
The proposed algorithm avoids reconstructing the exact neural architecture (like a Transformer), instead learning a mathematically equivalent but simpler structure called an Input-Switched Affine Network (ISAN). Key components include:
- Adaptive Future Selection: Using an "elliptical potential" argument, the algorithm adaptively chooses futures that reveal new dimensions of the model's internal state.
- Barycentric Spanners: The algorithm identifies a small set of "basis histories" that can represent any other history through linear combinations in logit space.
- Linear Programming for Stability: To prevent exponential coefficient growth during recursive learning, a global linear program ensures the learned distribution remains stable.
Key Results and Theoretical Significance
The authors prove that for a distribution $M$ with $\epsilon_{avg}$-approximate logit rank $d$, their algorithm outputs a distribution $\hat{M}$ such that the Total Variation (TV) distance $D_{TV}(M, \hat{M}) \leq \epsilon$. Crucially, both query complexity and computational time are polynomial in sequence length $T$, rank $d$, alphabet size $|\Sigma|$, and $1/\epsilon$. This framework also generalizes the celebrated Kushilevitz-Mansour theorem for learning sparse Boolean functions, suggesting it is a powerful generalization of classical query learning.
Empirical Validation
The "low logit rank" property was verified using OLMo2-1b, where approximation error followed a power law relative to rank. Additionally, experiments with Tinystories-8M demonstrated that a simplified version of the algorithm could generate coherent, albeit surreal, narratives, demonstrating the practical potential of the theoretical framework.
Limitations and Future Work
While theoretically sound, the current polynomial exponents are high (e.g., requiring $\epsilon \approx d^{-9.5}$ in some proofs), though empirical evidence suggests a much more favorable dependence (closer to $d^{-0.1}$). Future research will focus on bridging the gap between full logit access and top-K token access, as well as overcoming the "noisy parity" barrier for sample-only learning without query access.
Summary updated