# Model Stealing for Any Low-Rank Language Model

arXiv: https://arxiv.org/abs/2411.07536 · HTML: https://mlsanity.com/paper/2411.07536/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 50 references that are in the map.
- First posted on arXiv 12 Nov 2024.

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Stealing Part of a Production Language Model](https://mlsanity.com/paper/2403.06634/) (2024)
- [Stealing Hyperparameters in Machine Learning](https://mlsanity.com/paper/1802.05351/) (2018)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Protecting Language Generation Models via Invisible Watermarking](https://mlsanity.com/paper/2302.03162/) (2023)
- [Prediction Poisoning: Towards Defenses Against DNN Model Stealing Attacks](https://mlsanity.com/paper/1906.10908/) (2019)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defences](https://mlsanity.com/paper/2206.08451/) (2022)
- [A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks](https://mlsanity.com/paper/2001.11443/) (2020)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Model Extraction and Adversarial Transferability, Your BERT is Vulnerable!](https://mlsanity.com/paper/2103.10013/) (2021)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Defending against Model Stealing via Verifying Embedded External Features](https://mlsanity.com/paper/2112.03476/) (2021)
- [Undistillable: Making A Nasty Teacher That CANNOT teach students](https://mlsanity.com/paper/2105.07381/) (2021)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Stealing the Decoding Algorithms of Language Models](https://mlsanity.com/paper/2303.04729/) (2023)
- [Prediction with a Short Memory](https://mlsanity.com/paper/1612.02526/) (2016)
- [Learning and Testing Junta Distributions with Subcube Conditioning](https://mlsanity.com/paper/2004.12496/) (2020)
- [Information Laundering for Model Privacy](https://mlsanity.com/paper/2009.06112/) (2020)
- [Learning Hidden Markov Models Using Conditional Samples](https://mlsanity.com/paper/2302.14753/) (2023)
- [Nonparametric Finite Time LTI System Identification](https://mlsanity.com/paper/1902.01848/) (2019)
- [Learning Overcomplete HMMs](https://mlsanity.com/paper/1711.02309/) (2017)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [Minimal Realization Problems for Hidden Markov Models](https://mlsanity.com/paper/1411.3698/) (2014)
- [On learning parametric-output HMMs](https://mlsanity.com/paper/1302.6009/) (2013)

## Built on by (most cited first, 9 of 9)

- [A Comprehensive Survey in LLM(-Agent) Full Stack Safety: Data, Training and Deployment](https://mlsanity.com/paper/2504.15585/) (2025)
- [SoK: Large Language Model Copyright Auditing via Fingerprinting](https://mlsanity.com/paper/2508.19843/) (2025)
- [Sequences of Logits Reveal the Low Rank Structure of Language Models](https://mlsanity.com/paper/2510.24966/) (2025)
- [Clone What You Can't Steal: Black-Box LLM Replication via Logit Leakage and Distillation](https://mlsanity.com/paper/2509.00973/) (2025)
- [Provably Learning from Modern Language Models via Low Logit Rank](https://mlsanity.com/paper/2512.09892/) (2025)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)
- [CryptoTensors: A Light-Weight Large Language Model File Format for Highly-Secure Model Distribution](https://mlsanity.com/paper/2512.04580/) (2025)
- [The Role of Generator Access in Autoregressive Post-Training](https://mlsanity.com/paper/2604.04855/) (2026)
- [Proofs of Ownership for Machine Learning Models](https://mlsanity.com/paper/2606.30423/) (2026)

## Abstract (arXiv)

Model stealing, where a learner tries to recover an unknown model via carefully chosen queries, is a critical problem in machine learning, as it threatens the security of proprietary models and the privacy of data they are trained on. In recent years, there has been particular interest in stealing large language models (LLMs). In this paper, we aim to build a theoretical understanding of stealing language models by studying a simple and mathematically tractable setting. We study model stealing for Hidden Markov Models (HMMs), and more generally low-rank language models. We assume that the learner works in the conditional query model, introduced by Kakade, Krishnamurthy, Mahajan and Zhang. Our main result is an efficient algorithm in the conditional query model, for learning any low-rank distribution. In other words, our algorithm succeeds at stealing any language model whose output distribution is low-rank. This improves upon the previous result by Kakade, Krishnamurthy, Mahajan and Zhang, which also requires the unknown distribution to have high "fidelity", a property that holds only in restricted cases. There are two key insights behind our algorithm: First, we represent the conditional distributions at each timestep by constructing barycentric spanners among a collection of vectors of exponentially large dimension. Second, for sampling from our representation, we iteratively solve a sequence of convex optimization problems that involve projection in relative entropy to prevent compounding of errors over the length of the sequence. This is an interesting example where, at least theoretically, allowing a machine learning model to solve more complex problems at inference time can lead to drastic improvements in its performance.