Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms

• URL: http://arxiv.org/abs/2508.18526v2
• Date: Tue, 16 Sep 2025 14:10:46 GMT
• Title: Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
• Authors: Anastasis Kratsios, Dennis Zvigelsky, Bradd Hart,
• Abstract summary: We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN)<n>We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks.
• Score: 10.292476979020522
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A main open question in contemporary AI research is quantifying the forms of reasoning neural networks can perform when perfectly trained. This paper answers this by interpreting reasoning tasks as circuit emulation, where the gates define the type of reasoning; e.g. Boolean gates for predicate logic, tropical circuits for dynamic programming, arithmetic and analytic gates for symbolic mathematical representation, and hybrids thereof for deeper reasoning; e.g. higher-order logic. We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN) with ReLU activations by iteratively replacing each gate with a canonical ReLU MLP emulator. We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks. The number of neurons in the resulting network (parametric complexity) scales with the circuit's complexity, and the network's computational graph (structure) mirrors that of the emulated circuit. This formalizes the folklore that NNs networks trade algorithmic run-time (circuit runtime) for space complexity (number of neurons). We derive a range of applications of our main result, from emulating shortest-path algorithms on graphs with cubic--size NNs, to simulating stopped Turing machines with roughly quadratically--large NNs, and even the emulation of randomized Boolean circuits. Lastly, we demonstrate that our result is strictly more powerful than a classical universal approximation theorem: any universal function approximator can be encoded as a circuit and directly emulated by a NN.

Related papers

• Recurrent Graph Neural Networks and Arithmetic Circuits [3.996231905922229]
  We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers.<n>We introduce the model of recurrent arithmetic circuits, which can be seen as arithmetic analogues of sequential or logical circuits.
  arXiv  Detail & Related papers  (2026-03-05T13:10:27Z)
• Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem [0.0]
  Neural networks are capable of superposition -- representing more features than there are dimensions.<n>Recent work considers the analogous concept for computation instead of storage, proposing theoretical constructions.<n>We investigate a toy model for the Universal-AND problem which computes the AND of all $mchoose 2$ pairs of $m$ sparse inputs.
  arXiv  Detail & Related papers  (2025-07-13T22:18:15Z)
• Challenges and opportunities in the supervised learning of quantum circuit outputs [0.0]
  Deep neural networks have proven capable of predicting some output properties of relevant random quantum circuits. We investigate if and to what extent neural networks can learn to predict the output expectation values of circuits often employed in variational quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-07T16:10:13Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• Pretraining Graph Neural Networks for few-shot Analog Circuit Modeling and Design [68.1682448368636]
  We present a supervised pretraining approach to learn circuit representations that can be adapted to new unseen topologies or unseen prediction tasks. To cope with the variable topological structure of different circuits we describe each circuit as a graph and use graph neural networks (GNNs) to learn node embeddings. We show that pretraining GNNs on prediction of output node voltages can encourage learning representations that can be adapted to new unseen topologies or prediction of new circuit level properties.
  arXiv  Detail & Related papers  (2022-03-29T21:18:47Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  We study the potential gains in sample efficiency that can bring in the principle of minimum description length. We use Turing machines to represent universal models and circuits. We highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.
  arXiv  Detail & Related papers  (2021-03-23T17:03:10Z)
• Artificial Neural Networks generated by Low Discrepancy Sequences [59.51653996175648]
  We generate artificial neural networks as random walks on a dense network graph. Such networks can be trained sparse from scratch, avoiding the expensive procedure of training a dense network and compressing it afterwards. We demonstrate that the artificial neural networks generated by low discrepancy sequences can achieve an accuracy within reach of their dense counterparts at a much lower computational complexity.
  arXiv  Detail & Related papers  (2021-03-05T08:45:43Z)
• Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks [1.4902915966744057]
  We describe a programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit.
  arXiv  Detail & Related papers  (2020-06-06T11:08:06Z)
• LogicNets: Co-Designed Neural Networks and Circuits for Extreme-Throughput Applications [6.9276012494882835]
  We present a novel method for designing neural network topologies that directly map to a highly efficient FPGA implementation. We show that the combination of sparsity and low-bit activation quantization results in high-speed circuits with small logic depth and low LUT cost.
  arXiv  Detail & Related papers  (2020-04-06T22:15:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.