Figure 1

We can build automata from neural nets. And they do weird things, like learn languages, in a predictable way, which is wildly at odds with our traditional understanding of the difficulty of the task (Paging Doctor Chomsky). How can we analyse NNs in terms of computational complexity? What are the useful results in this domain?

Related: grammatical inference, memory machines, overparameterization, NN compression, learning automata, NN at scale, explainability

1 Computational cost of explaining complex reasoning

Intuitively, something might be, should be difficult, computationally about explaining the reasoning of a large neural network. Surely simpler things cannot explain more complex things?

As an extreme example, we might run into incompleteness results. (Prove the consistency of the following system of axioms…) I can believe such extreme esoterica would not be relevant in practice, but could problems close to those arise in practice? TBC.

2 Neural interactive proofs

The main theoretical challenges are to: i) represent a given protocol in the form of a prover-verifier game (Kirchner et al. 2024); and ii) train the models to approximate the right equilibria of this game. While the first challenge is reasonably straightforward, the power of different protocols can vary greatly depending on several subtle details such as the number of messages the agents can send to each other, their ability to randomise, and whether messages can be sent privately to different agents. By taking these subtleties into account, we can show an equivalence between the equilibria of the game and valid proof systems for a range of different protocols.

Table 1: (from Hammond and Adam-Day (2025)) A comparison of the various proof protocols we discuss in our work. The “Complexity” column denotes the corresponding complexity class of decision problems that can be solved when represented as a (generalised) prover-verifier game played between unbounded provers and probabilistic polynomial time verifiers.
Model Rounds Complexity Zero-knowledge
adp 2 NP
debate $T$ PSPACE
mac 2 MA
nip $T$ PSPACE
mnip $T$ NEXP
zk-nip $T$ PSPACE
zk-mnip $T$ NEXP

The second theoretical challenge arises because the equilibria that form this equivalence are (approximate) Stackelberg equilibria over the worst-case loss, which are difficult to optimise for using conventional machine learning algorithms. We discuss several approaches to overcoming this challenge, including the use of Stackelberg policy gradient and opponent-shaping algorithms to approximate Stackelberg equilibria, and the efficacy of average-case optimisation and adversarial training when it comes to minimising worst-case losses.

3 Incoming

4 References

Allen-Zhu, and Xu. 2025. DOGE: Reforming AI Conferences and Towards a Future Civilization of Fairness and Justice.” SSRN Scholarly Paper.
Blazek, and Lin. 2020. A Neural Network Model of Perception and Reasoning.” arXiv:2002.11319 [Cs, q-Bio].
———. 2021. Explainable Neural Networks That Simulate Reasoning.” Nature Computational Science.
Blazek, Venkatesh, and Lin. 2021. Deep Distilling: Automated Code Generation Using Explainable Deep Learning.” arXiv:2111.08275 [Cs].
Bölcskei, Grohs, Kutyniok, et al. 2019. Optimal Approximation with Sparsely Connected Deep Neural Networks.” SIAM Journal on Mathematics of Data Science.
Bubeck, Chandrasekaran, Eldan, et al. 2023. Sparks of Artificial General Intelligence: Early Experiments with GPT-4.”
Clark, Tafjord, and Richardson. 2020. Transformers as Soft Reasoners over Language.” In IJCAI 2020.
Dehghani, Gouws, Vinyals, et al. 2019. Universal Transformers.” In.
Delétang, Ruoss, Grau-Moya, et al. 2023. Neural Networks and the Chomsky Hierarchy.”
Duchnowski, Pavlick, and Koller. 2025. EHOP: A Dataset of Everyday NP-Hard Optimization Problems.”
Dziri, Lu, Sclar, et al. 2023. Faith and Fate: Limits of Transformers on Compositionality.”
Fiez, Chasnov, and Ratliff. 2019. Convergence of Learning Dynamics in Stackelberg Games.”
Frankle, and Carbin. 2019. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks.” arXiv:1803.03635 [Cs].
Garcez, and Lamb. 2020. Neurosymbolic AI: The 3rd Wave.”
Hammond, and Adam-Day. 2025. Neural Interactive Proofs.” In.
Kirchner, Chen, Edwards, et al. 2024. Prover-Verifier Games Improve Legibility of LLM Outputs.”
Kleinberg, and Mullainathan. 2024. Language Generation in the Limit.”
Minsky, and Papert. 1972. Perceptrons: an introduction to computational geometry.
Olazaran. 1993. A Sociological History of the Neural Network Controversy.” In Advances in Computers.
Peng, Narayanan, and Papadimitriou. 2024. On Limitations of the Transformer Architecture.”
Pereira. 2002. Formal Grammar and Information Theory: Together Again? In Current Issues in Linguistic Theory.
Russell, and Norvig. 2021. Artificial Intelligence: A Modern Approach. Pearson Series in Artificial Intelligence.
Schuurmans, Dai, and Zanini. 2024. Autoregressive Large Language Models Are Computationally Universal.”
Shi, Feng, and ZhifanZhu. 2016. Functional Hashing for Compressing Neural Networks.” arXiv:1605.06560 [Cs].
Shojaee, Mirzadeh, Alizadeh, et al. 2025. The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity.”
van Gelder, Wortsman, and Ehsani. 2020. Deconstructing the Structure of Sparse Neural Networks.” In.
Veličković, and Blundell. 2021. Neural Algorithmic Reasoning.” Patterns.
Wu, Tan, Wang, et al. 2024. Beyond Language Models: Byte Models Are Digital World Simulators.”
Zekri, Odonnat, Benechehab, et al. 2025. Large Language Models as Markov Chains.”
Zhang, Backurs, Bubeck, et al. 2022. Unveiling Transformers with LEGO: A Synthetic Reasoning Task.”