{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T17:07:23Z","timestamp":1772644043745,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","funder":[{"name":"Hertz Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"David and Lucile Packard Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Office of Naval Research","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Microsoft","award":["Trustworthy AI Grant"],"award-info":[{"award-number":["Trustworthy AI Grant"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718220","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1755-1761","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Model Stealing for Any Low-Rank Language Model"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7987-5755","authenticated-orcid":false,"given":"Allen","family":"Liu","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7047-0495","authenticated-orcid":false,"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Conference on learning theory. 33\u20131.","author":"Anandkumar Animashree","year":"2012","unstructured":"Animashree Anandkumar, Daniel Hsu, and Sham M Kakade. 2012. A method of moments for mixture models and hidden Markov models. In Conference on learning theory. 33\u20131."},{"key":"e_1_3_2_1_2_1","volume-title":"Learning regular sets from queries and counterexamples. Information and computation, 75, 2","author":"Angluin Dana","year":"1987","unstructured":"Dana Angluin. 1987. Learning regular sets from queries and counterexamples. Information and computation, 75, 2 (1987), 87\u2013106."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585247"},{"key":"e_1_3_2_1_4_1","volume-title":"International Conference on Machine Learning. 1549\u20131563","author":"Bakshi Ainesh","year":"2023","unstructured":"Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau. 2023. Tensor decompositions meet control theory: learning general mixtures of linear dynamical systems. In International Conference on Machine Learning. 1549\u20131563."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00043"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241377"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945508"},{"key":"e_1_3_2_1_8_1","volume-title":"Thomas Steinke, Jonathan Hayase, A Feder Cooper, Katherine Lee, Matthew Jagielski, Milad Nasr, and Arthur Conmy.","author":"Carlini Nicholas","year":"2024","unstructured":"Nicholas Carlini, Daniel Paleka, Krishnamurthy Dj Dvijotham, Thomas Steinke, Jonathan Hayase, A Feder Cooper, Katherine Lee, Matthew Jagielski, Milad Nasr, and Arthur Conmy. 2024. Stealing part of a production language model. arXiv preprint arXiv:2403.06634."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422497"},{"key":"e_1_3_2_1_10_1","volume-title":"Conference on Learning Theory. 1060\u20131113","author":"Chen Xi","year":"2021","unstructured":"Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. 2021. Learning and testing junta distributions with sub cube conditioning. In Conference on Learning Theory. 1060\u20131113."},{"key":"e_1_3_2_1_11_1","volume-title":"International conference on machine learning. 3507\u20133557","author":"Chen Yanxi","year":"2022","unstructured":"Yanxi Chen and H Vincent Poor. 2022. Learning mixtures of linear dynamical systems. In International conference on machine learning. 3507\u20133557."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798342496"},{"key":"e_1_3_2_1_13_1","volume-title":"Conference on Learning Theory. 1514\u20131539","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. 2020. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. In Conference on Learning Theory. 1514\u20131539."},{"key":"e_1_3_2_1_14_1","unstructured":"Dylan J Foster Sham M Kakade Jian Qian and Alexander Rakhlin. 2021. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487."},{"key":"e_1_3_2_1_15_1","volume-title":"International Conference on Machine Learning. 3587\u20133596","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. 2020. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning. 3587\u20133596."},{"key":"e_1_3_2_1_16_1","first-page":"2147","article-title":"Statistical-query lower bounds via functional gradients","volume":"33","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel, Aravind Gollakota, and Adam Klivans. 2020. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33 (2020), 2147\u20132158.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585099"},{"key":"e_1_3_2_1_18_1","first-page":"1","article-title":"Gradient descent learns linear dynamical systems","volume":"19","author":"Hardt Moritz","year":"2018","unstructured":"Moritz Hardt, Tengyu Ma, and Benjamin Recht. 2018. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19, 29 (2018), 1\u201344.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_19_1","volume-title":"Neil Zhenqiang Gong, and Yang Zhang","author":"He Xinlei","year":"2021","unstructured":"Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. 2021. Stealing links from graph neural networks. In 30th USENIX security symposium (USENIX security 21). 2669\u20132686."},{"key":"e_1_3_2_1_20_1","unstructured":"Xuanli He Lingjuan Lyu Qiongkai Xu and Lichao Sun. 2021. Model extraction and adversarial transferability your BERT is vulnerable!. arXiv preprint arXiv:2103.10013."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.025"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2015.2510969"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"e_1_3_2_1_24_1","volume-title":"Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31","author":"Jacot Arthur","year":"2018","unstructured":"Arthur Jacot, Franck Gabriel, and Cl\u00e9ment Hongler. 2018. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31 (2018)."},{"key":"e_1_3_2_1_25_1","volume-title":"30th USENIX security symposium (USENIX Security 21). 1937\u20131954.","author":"Jia Hengrui","unstructured":"Hengrui Jia, Christopher A Choquette-Choo, Varun Chandrasekaran, and Nicolas Papernot. 2021. Entangled watermarks as a defense against model extraction. In 30th USENIX security symposium (USENIX Security 21). 1937\u20131954."},{"key":"e_1_3_2_1_26_1","volume-title":"International Conference on Machine Learning. 1704\u20131713","author":"Jiang Nan","year":"2017","unstructured":"Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. 2017. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning. 1704\u20131713."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP.2019.00044"},{"key":"e_1_3_2_1_28_1","unstructured":"Sham M. Kakade Akshay Krishnamurthy Gaurav Mahajan and Cyril Zhang. 2024. Learning Hidden Markov Models Using Conditional Samples. arxiv:2302.14753."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_3_2_1_30_1","volume-title":"International Conference on Machine Learning. 702\u2013710","author":"Kontorovich Aryeh","year":"2013","unstructured":"Aryeh Kontorovich, Boaz Nadler, and Roi Weiss. 2013. On learning parametric-output HMMs. In International Conference on Machine Learning. 702\u2013710."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i2.20036"},{"key":"e_1_3_2_1_32_1","volume-title":"Undistillable: Making a nasty teacher that cannot teach students. arXiv preprint arXiv:2105.07381.","author":"Ma Haoyu","year":"2021","unstructured":"Haoyu Ma, Tianlong Chen, Ting-Kuei Hu, Chenyu You, Xiaohui Xie, and Zhangyang Wang. 2021. Undistillable: Making a nasty teacher that cannot teach students. arXiv preprint arXiv:2105.07381."},{"key":"e_1_3_2_1_33_1","volume-title":"Conference on learning theory. 2388\u20132464","author":"Mei Song","year":"2019","unstructured":"Song Mei, Theodor Misiakiewicz, and Andrea Montanari. 2019. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on learning theory. 2388\u20132464."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060645"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3576915.3616652"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4171\/msl\/42"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3595292"},{"key":"e_1_3_2_1_38_1","unstructured":"Tribhuvanesh Orekondy Bernt Schiele and Mario Fritz. 2019. Prediction poisoning: Towards defenses against dnn model stealing attacks. arXiv preprint arXiv:1906.10908."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Samet Oymak and Necmiye Ozay. 2019. Non-asymptotic identification of lti systems from a single trajectory. In 2019 American control conference (ACC). 5655\u20135661.","DOI":"10.23919\/ACC.2019.8814438"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338498.3358646"},{"key":"e_1_3_2_1_41_1","unstructured":"Tuhin Sarkar Alexander Rakhlin and Munther A Dahleh. 2019. Nonparametric finite time LTI system identification. arXiv preprint arXiv:1902.01848."},{"key":"e_1_3_2_1_42_1","unstructured":"Zeyang Sha and Yang Zhang. 2024. Prompt stealing attacks against large language models. arXiv preprint arXiv:2402.12959."},{"key":"e_1_3_2_1_43_1","volume-title":"Prediction and entropy of printed English. Bell system technical journal, 30, 1","author":"Shannon Claude E","year":"1951","unstructured":"Claude E Shannon. 1951. Prediction and entropy of printed English. Bell system technical journal, 30, 1 (1951), 50\u201364."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188954"},{"key":"e_1_3_2_1_45_1","volume-title":"Learning overcomplete hmms. Advances in Neural Information Processing Systems, 30","author":"Sharan Vatsal","year":"2017","unstructured":"Vatsal Sharan, Sham M Kakade, Percy S Liang, and Gregory Valiant. 2017. Learning overcomplete hmms. Advances in Neural Information Processing Systems, 30 (2017)."},{"key":"e_1_3_2_1_46_1","volume-title":"Conference on Learning Theory. 2714\u20132802","author":"Simchowitz Max","year":"2019","unstructured":"Max Simchowitz, Ross Boczar, and Benjamin Recht. 2019. Learning linear dynamical systems with semi-parametric least squares. In Conference on Learning Theory. 2714\u20132802."},{"key":"e_1_3_2_1_47_1","volume-title":"25th USENIX security symposium (USENIX Security 16). 601\u2013618.","author":"Tram\u00e8r Florian","unstructured":"Florian Tram\u00e8r, Fan Zhang, Ari Juels, Michael K Reiter, and Thomas Ristenpart. 2016. Stealing machine learning models via prediction $APIs$. In 25th USENIX security symposium (USENIX Security 16). 601\u2013618."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC40024.2019.9029499"},{"key":"e_1_3_2_1_49_1","volume-title":"\u0141 ukasz Kaiser, and Illia Polosukhin","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, \u0141 ukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 30, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2017\/file\/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00038"},{"key":"e_1_3_2_1_51_1","unstructured":"Xinran Wang Yu Xiang Jun Gao and Jie Ding. 2020. Information laundering for model privacy. arXiv preprint arXiv:2009.06112."},{"key":"e_1_3_2_1_52_1","volume-title":"International Conference on Machine Learning. 42187\u201342199","author":"Zhao Xuandong","year":"2023","unstructured":"Xuandong Zhao, Yu-Xiang Wang, and Lei Li. 2023. Protecting language generation models via invisible watermarking. In International Conference on Machine Learning. 42187\u201342199."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:24Z","timestamp":1750693464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":52,"alternative-id":["10.1145\/3717823.3718220","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718220","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}