# An Exact Poly-Time Membership-Queries Algorithm for Extraction a three-Layer ReLU Network

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 20 May 2021.

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

- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Secret Revealer: Generative Model-Inversion Attacks Against Deep Neural Networks](https://mlsanity.com/paper/1911.07135/) (2019)
- [High Accuracy and High Fidelity Extraction of Neural Networks](https://mlsanity.com/paper/1909.01838/) (2019)
- [Model Reconstruction from Model Explanations](https://mlsanity.com/paper/1807.05185/) (2018)
- [Reverse-Engineering Deep ReLU Networks](https://mlsanity.com/paper/1910.00744/) (2019)
- [Cryptanalytic Extraction of Neural Network Models](https://mlsanity.com/paper/2003.04884/) (2020)
- [Robust and Resource Efficient Identification of Two Hidden Layer Neural Networks](https://mlsanity.com/paper/1907.00485/) (2019)

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

- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Polynomial Time Cryptanalytic Extraction of Neural Network Models](https://mlsanity.com/paper/2310.08708/) (2023)
- [Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting](https://mlsanity.com/paper/2410.05750/) (2024)
- [Efficiently Learning Any One Hidden Layer ReLU Network From Queries](https://mlsanity.com/paper/2111.04727/) (2021)
- [Navigating the Deep: End-to-End Extraction on Deep Neural Networks](https://mlsanity.com/paper/2506.17047/) (2025)
- [Is the Hard-Label Cryptanalytic Model Extraction Really Polynomial?](https://mlsanity.com/paper/2510.06692/) (2025)
- [Provably Learning Multi-Head Attention with Queries](https://mlsanity.com/paper/2608.03294/) (2026)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)
- [Provably Learning Attention with Queries](https://mlsanity.com/paper/2601.16873/) (2026)
- [Sequencing the Neurome: Towards Scalable Exact Parameter Reconstruction of Black-Box Neural Networks](https://mlsanity.com/paper/2409.19138/) (2024)
- [End-to-End Hard-Label Cryptanalytic Model Extraction Using Efficient Sign Recovery](https://mlsanity.com/paper/2609.21941/) (2026)

## Abstract (arXiv)

We consider the natural problem of learning a ReLU network from queries, which was recently remotivated by model extraction attacks. In this work, we present a polynomial-time algorithm that can learn a depth-two ReLU network from queries under mild general position assumptions. We also present a polynomial-time algorithm that, under mild general position assumptions, can learn a rich class of depth-three ReLU networks from queries. For instance, it can learn most networks where the number of first layer neurons is smaller than the dimension and the number of second layer neurons. These two results substantially improve state-of-the-art: Until our work, polynomial-time algorithms were only shown to learn from queries depth-two networks under the assumption that either the underlying distribution is Gaussian (Chen et al. (2021)) or that the weights matrix rows are linearly independent (Milli et al. (2019)). For depth three or more, there were no known poly-time results.