betaFeedback

WorksComputer Science

Differentiable Exact Learning

Abstract

We introduce a framework for differentiable exact learning that couples an unbounded external environment to a state-tracking neural controller, which we train on policy-trajectory observations (PTOs): expert behavior traces that expose observations and actions while hiding internal states. In addition to the learning framework, we introduce Differentiable Finite-State Transducers (DFSTs) which use multilinear updates, support log-parallel training, and emulate arbitrary finite-state controllers, yielding computational universality through environmental interaction. From tiny training datasets, compact DFSTs achieve extreme length generalization on arithmetic and universal-simulation tasks. We replicate the success of DFSTs on RNNs and GRUs, thereby supporting a broader learning recipe: State-Tracking Controller + Unbounded External Environment + PTOs = Extreme Length Generalization. Beyond length generalization, our metric-extraction protocol recovers interpretable discrete controllers from trained DFSTs, which we prove equivalent to the target arithmetic and universal-simulation algorithms. Furthermore, for our Softmax DFST models, simply taking argmax\mathrm{argmax} over the transition probabilities yields discrete controllers which provably exactly perform universal Turing-machine simulation and binary arithmetic. Proving exact learning for the neural controllers requires assumptions, which we empirically support. We make our code, training recipes, model weights, and proof checkers publicly available at https://github.com/fanagor/DEL.

Figure 1. Extreme Length Generalization from Small PTO Datasets and Compact Controllers. Length generalization by DFST models trained from scratch on arithmetic and universal-simulation tasks. Shading marks the length of inputs seen during training. Our models see computation traces of inputs with ≤3\le3 digits for addition and ≤5\le5 digits for multiplication. On the universal task, DFSTs see simulation traces of 5 Turing machines on inputs of up-to 5 symbols and generalize to 5 unseen Turing machines. Endpoints mark successful length-generalization reaching a pre-defined testing cap.

Introduction

For decades, researchers have sought to make neural networks learn algorithmic procedures from data, arguing that genuine machine intelligence requires exact recovery of underlying rules rather than matching surface-level statistics [57, 25].

Yet arithmetic, the canonical testbed for algorithmic learning, continues to expose a persistent gap. Transformers and RNNs trained on input-output data generalize only marginally to longer inputs [17]. Even an extensive arsenal of scratchpad protocols, positional-encoding schemes, and input-formatting tricks brings Transformer length generalization2 to 2–7× the training operand length, with exact-match accuracy swiftly decaying as inputs lengthen [27, 64, 12]. The Neural GPU [31] stands out by reaching 100× length generalization on random binary arithmetic instances, although later diagnostics expose long-carry and symmetric-input failures [50] (see Table 1). Such finite-test success leaves exactness on arbitrarily long inputs unresolved.

A relevant exception comes from the recursive Neural Programmer-Interpreter (NPI) [52, 10], which provably recovers decimal addition and several sorting algorithms. However, the training uses a stronger form of supervision through recursive call/return annotations that goes beyond merely observing expert actions in an external environment.

In contrast, real learners routinely succeed under exactly this restriction. Indeed, children acquire complex procedural skills by observing adults perform goal-directed actions, with no access to the adults’ internal neural processes. From such behavior traces alone, infants infer the underlying procedural structure and reproduce the target behavior through practice [37].

Motivated by the success of natural learners, this paper entertains the idea of gradient-based exact algorithmic learning from behavior observations and provides a simple recipe for achieving extreme length generalization with compact controllers trained from scratch on small datasets (see Figure 1). To our knowledge, this work provides the first differentiable exact recovery of a fixed universal interpreter with correctness proofs covering arbitrary simulations of Turing machines with unbounded input lengths and unbounded execution horizons. We similarly achieve exact differentiable recovery on addition and multiplication tasks. Our training withholds expert control states and the learned interpreter requires no retraining when exchanging input programs. We just need two ingredients: sufficiently informative observations and a sufficiently expressive learner.

Sufficiently Informative Observations. The choice of training data determines the possibility of exact learning. Gold [20] proved that no algorithm can identify the class of recursive functions in the limit from input–output examples alone Gold, [20]. Moreover, the impossibility persists in the active-learning setting Gold, [20]. Hence, supervised learning from (x,f(z))(x, f(z)) pairs and reinforcement learning rewarded only for correct output without a helpful curriculum cannot identify every recursive function in general. To navigate between this general identification barrier and the additional (strong and unrealistic) program-structure supervision of NPIs, we adopt policy-trajectory observations (PTOs) as our training signal. PTOs record how the environment evolves under the expert’s policy without exposing the expert’s internal state transitions.3 This middle ground carries two advantages: (i) PTOs avoid Gold’s impossibility barrier (Papazov and Flammarion, 2025, Theorem 16); (ii) PTOs admit a natural interpretation as behavior observations – the learner only observes how the world changes under the expert’s actions.

Sufficiently Expressive Learner. Since we target exact learning of arbitrary algorithms, the learner must belong to a Turing-complete model class. Prior work establishes Turing-completeness for Transformers and RNNs through assumptions that preclude effective optimization: unbounded arithmetic precision [56, 51], unbounded context windows [16, 7, 39], or non-differentiable environmental interaction [14] (Schürholt et al. 2024). We propose a simpler workaround that preserves finite precision and fixed-size contexts, allowing for effective gradient-based optimization. The key idea couples a state-tracking4 controller – such as an RNN, LSTM, or GRU – to a dynamically resizing external environment in which the controller can move, read, and write. Because the environment grows as needed, computation no longer bottlenecks on the controller’s fixed internal memory. Zaremba and Sutskever [65] explored a related architecture pairing an LSTM controller with external tapes, but trained via reinforcement learning on input–output rewards alone, which Gold’s theorem renders insufficient for exact learning in general. We hope to revive and strengthen this architectural idea through the richer PTO supervision.

Thus, our learning recipe distills into a simple equation:

State-Tracking Controller+Unbounded External Environment+PTOs=Extreme Length Generalization.\text{State-Tracking Controller} + \text{Unbounded External Environment} + \text{PTOs} = \text{Extreme Length Generalization}.

In fact, we go a step further and introduce a simple extraction procedure, which recovers discrete controllers from our trained neural models. We prove that the extracted controllers exactly follow the target behavior and hence certify the following method for differentiable exact learning of algorithms:

Method overview showing observation of PTOs, differentiable learning, and extraction of a discrete controller

Figure 1 (PDF p. 3).

Main Contributions.

  1. A Conceptual Framework for Differentiable Exact Learning. We revive the idea of achieving Turing-complete differentiable computation through a state-tracking neural controller coupled to an unbounded external environment. Training on a small number of PTOs yields extreme length generalization. Subsequent extraction establishes exact learning for the recovered discrete controllers across the studied tasks and for the neural controllers subject to stability assumptions.

  1. Differentiable Finite-State Transducers (DFSTs). We introduce a (i) minimalist, (ii) multilinear, (iii) differentiable, (iv) state-tracking, and (v) parallelizable model family whose members serve as controllers in our experiments. DFSTs use no nonlinear activations, admit log-parallel training via prefix scans (Blelloch, [8]), and offer a transparent structure for studying the loss landscape of algorithmic learning and the useful implicit bias of gradient descent.

  1. Extreme Generalization from Small PTO Datasets. We train on small PTO datasets (25 traces for add2, 100 for mult2, 250 for add10, and 10000 for mult10) and reach robust testing caps of 5000 digits for addition and 1000 digits for multiplication. The training operands contain at most 3 and 5 digits, respectively. We replicate the extreme length generalization on binary arithmetic using RNN and GRU controllers thereby supporting our generalization recipe.

  1. Exact Learning of a Universal Controller. A 4335-parameter DFST trained from scratch on just 75 PTOs from 5 program simulations over inputs of at most 5 symbols reaches the 500-symbol evaluation cap across 10 tasks, including 5 held-out programs. From trained DFST models, our extraction procedures recover controllers provably equivalent to the expert universal interpreter and capable of simulating arbitrary programs on any input lengths and execution horizons.

  1. Extraction and Verification of Exact Learning. A lightweight extraction procedure applied to trained DFSTs recovers compact FSTs. Eight proofs establish exact expert-policy equivalence across binary and decimal arithmetic and universal simulation. Additional empirically verified assumptions prove the equivalence of the trained neural controllers to the experts.

Remark. An earlier workshop version introduced DFSTs and reported considerable arithmetic length generalization ((Papazov et al., 2025)). The present work simplifies training; pushes length generalization to the extreme; and adds learned universal simulation, Softmax DFSTs, recurrent-controller comparisons, and exact-equivalence certificates for extracted controllers.

Paper Organization. Section 2 formalizes PTO-learning, DFSTs, and the studied algorithmic tasks. Section 3 expands on our arithmetic and universal experiments, with a short passage on the implicit bias of gradient descent. Section 4 explains FST extraction and verification of correctness. We refer the reader to Section A for a thorough discussion of related work.

Preliminaries

As discussed in the introduction, our recipe for exact learning couples a state-tracking controller to an unbounded external environment.

Policy-Trajectory Observations

We model the external environment as a symbolic grid.

Definition 2.1 (Symbolic Grid). Given a finite alphabet Σ\Sigma containing the empty symbol λ\lambda, a grid configuration w:Z2→Σw : \mathbb{Z}^{2} \to\Sigma assigns a symbol w(p)∈Σw(p) \in\Sigma to each cell p∈Z2p \in\mathbb{Z}^{2} such that only finitely many cells differ from λ\lambda. The symbolic grid G=G(Z2,Σ)\mathcal{G} = \mathcal{G}(\mathbb{Z}^{2}, \Sigma) denotes the set of all such configurations.

The finiteness requirement captures the idea that the environment grows as needed but never stores an infinite amount of information at any point in time. We now formalize the agents that inhabit the grid.

Definition 2.2 (Grid Agent). A grid agent over the symbolic grid G(Z2,Σ)\mathcal{G}(\mathbb{Z}^{2}, \Sigma) stands for a finite-state transducer T=(Q,Σ,Γ,δ,γ,q0,qf)T = (Q, \Sigma, \Gamma, \delta, \gamma, q_0, q_f), where QQ denotes a finite set of states, Σ\Sigma serves as both the read alphabet and the write alphabet, Γ=Σ×M\Gamma= \Sigma\times\mathcal{M} with M={L,R,U,D,S}\mathcal{M} = \{\mathrm{L}, \mathrm{R}, \mathrm{U}, \mathrm{D}, \mathrm{S}\} forms the output alphabet pairing a grid symbol with a motion direction, δ:Q×Σ→Q\delta: Q \times\Sigma\to Q specifies the state-transition function, γ:Q×Σ→Γ\gamma: Q \times\Sigma\to\Gamma specifies the output function, q0∈Qq_0 \in Q denotes the initial state, and qf∈Qq_f \in Q denotes the halting state. The agent always starts at p0=(0,0)p_0 = (0, 0).

The agent occupies a single cell pt∈Z2p_t \in\mathbb{Z}^{2} at each time step tt, reads the symbol xt+1=wt(pt)x_{t+1} = w_t(p_t), produces an output γ(qt,xt+1)=(st+1,mt+1)\gamma(q_t, x_{t+1}) = (s_{t+1}, m_{t+1}) that writes st+1s_{t+1} at position ptp_t and shifts the agent’s position by mt+1m_{t+1}, and transitions to state δ(qt,xt+1)\delta(q_t, x_{t+1}). We adopt the convention that every transition containing the stop motion S\mathrm{S} leads to the halting state qfq_f, and all transitions from qfq_f satisfy δ(qf,x)=qf\delta(q_f, x) = q_f and γ(qf,x)=(x,S)\gamma(q_f, x) = (x, \mathrm{S}) for every x∈Σx \in\Sigma, rendering qfq_f a dead state that leaves the grid unchanged.

Note that a grid agent perceives only one cell at a time. Future work could explore richer perception mechanisms encoding the contents of multiple cells and agents interacting with a larger motion vocabulary. Since standard Turing machines arise as a special case of grid agents restricted to a single row, the class A\mathcal{A} of all grid agents achieves computational universality when interacting with G\mathcal{G}.

PTOs. At each time step tt, an external learner observing agent TT perceives only the written symbol st∈Σs_t \in\Sigma, the motion mt∈Mm_t \in\mathcal{M}, and the observation xtx_t that triggered the action. Importantly, the internal state qtq_t remains hidden. The resulting sequence (xt,st,mt)t=1T(x_t, s_t, m_t)_{t=1}^{T} constitutes a policy-trajectory observation (PTO), matching the formalism of Papazov and Flammarion (2025). Crucially, Papazov and Flammarion (2025, Theorem 16) proved that PTOs enable exact identification of any computable function in the limit – a guarantee unachievable through input–output supervision alone [20].

Hardness. Each algorithmic task P\mathcal{P} comes with a set of valid inputs SP⊆Σ∗\mathcal{S}_{\mathcal{P}} \subseteq\Sigma^*. Because the motion token outputted at each step constrains the next observation, SP\mathcal{S}_{\mathcal{P}} may never cover all reachable transducer transitions, thereby making the learning problem fundamentally hard. Papazov and Flammarion (2025, Theorem 17) proved that no polynomial-mass characteristic set exists for this restricted-input regime, ruling out any algorithm that learns the policy of every grid agent from polynomially many polynomially long PTOs (see Section C.3 for details).

State-Tracking Differentiable Controllers

While Papazov and Flammarion (2025, Theorem 16) showed that a learning-by-enumeration strategy provably identifies any grid agent from PTOs, such an approach takes time and memory exponential in the size of the target expert agent. We instead pursue gradient-based learning by introducing a simple differentiable model that can serve as a grid-agent controller.

Definition 2.3 (DFST). A Differentiable Finite-State Transducer (DFST) of dimension dd over the symbolic grid G(Z2,Σ)\mathcal{G}(\mathbb{Z}^2,\Sigma) with motion vocabulary M\mathcal{M} comprises three trainable weight tensors

A∈R∣Σ∣×d×d,B∈R∣Σ∣×∣Σ∣×d,C∈R∣Σ∣×∣M∣×d,A \in\mathbb{R}^{|\Sigma|\times d\times d}, \qquad B \in\mathbb{R}^{|\Sigma|\times|\Sigma|\times d}, \qquad C \in\mathbb{R}^{|\Sigma|\times|\mathcal{M}|\times d},

and a trainable initial hidden state h0∈Rdh_0 \in\mathbb{R}^d. At each time step t≥1t \ge1, the controller reads the one-hot encoding xt∈R∣Σ∣x_t \in\mathbb{R}^{|\Sigma|} of the symbol at the current grid cell wt−1(pt−1)w_{t-1}(p_{t-1}) and computes

ht=A[xt]ht−1,s^t=B[xt]ht−1,m^t=C[xt]ht−1.h_t = A[x_t]h_{t-1}, \qquad\hat{s}_t = B[x_t]h_{t-1}, \qquad\hat{m}_t = C[x_t]h_{t-1}.

AA drives the hidden-state recurrence, BB produces scores over symbol tokens, and CC produces scores over motion tokens. At inference time, the controller emits σt=argmax⁡(s^t)∈Σ\sigma_t = \operatorname{argmax}(\hat{s}_t) \in\Sigma and μt=argmax⁡(m^t)∈M\mu_t = \operatorname{argmax}(\hat{m}_t) \in\mathcal{M}, writing σt\sigma_t at position pt−1p_{t-1} and moving μt\mu_t to ptp_t (see Figure 2).

One Step of the DFST Agent

Figure 2. One Step of the DFST Agent. Left: the grid wt−1w_{t-1} before the action; the agent at position pt−1p_{t-1} reads the symbol in the red cell as observation xtx_t. Center: the DFSTθ_\theta controller updates the hidden state via ht=A[xt]ht−1h_t = A[x_t] h_{t-1} and produces the discrete outputs σt=arg⁡max⁡(B[xt]ht−1)∈Σ\sigma_t = \arg\max(B[x_t] h_{t-1}) \in\Sigma (write) and μt=arg⁡max⁡(C[xt]ht−1)∈M\mu_t = \arg\max(C[x_t] h_{t-1}) \in\mathcal{M} (move). Right: the resulting grid wtw_t; the orange cell shows the symbol σt\sigma_t written at pt−1p_{t-1}, and the agent has shifted to ptp_t in the teal cell. We provide an interactive viewer that animates expert and trained neural controllers.

The DFST recurrence and readouts use only input-indexed matrix-vector products, without nonlinear activations. This multilinear structure enables log-parallel training via prefix scans (Blelloch, [8]) and yields a compact parametrization. A dd-dimensional DFST over an alphabet of size k=∣Σ∣k = |\Sigma| with r=∣M∣r = |\mathcal{M}| motion tokens carries kd(k+d+r)+dkd(k + d + r) + d trainable parameters, scaling as O(d2)O(d^2).

References

  1. [1]N. Alon, A. K. Dewdney, and T. J. Ott. Efficient simulation of finite automata by neural nets. Journal of the ACM (JACM), 38(2):495–514, 1991.DOI
  2. [2]M. Andrychowicz and K. Kurach. Learning efficient algorithms with hierarchical attentive memory. arXiv preprint arXiv:1602.03218, 2016.arxiv.org/abs/1602.03218
  3. [3]D. Angluin. Learning regular sets from queries and counterexamples. Information and computation, 75(2):87–106, 1987.
  4. [4]C. Anil, Y. Wu, A. Andreassen, A. Lewkowycz, V. Misra, V. Ramasesh, A. Slone, G. Gur-Ari, E. Dyer, and B. Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546–38556, 2022.arxiv.org/abs/2207.04901
  5. [5]B. D. Argall, S. Chernovа, M. Veloso, and B. Browning. A survey of robot learning from demonstration. Robotics and autonomous systems, 57(5):469–483, 2009.DOI
  6. [7]S. Bhattamishra, A. Patel, and N. Goyal. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286, 2020.arxiv.org/abs/2006.09286
  7. [8]G. E. Blelloch. Prefix sums and their applications. 1990.
  8. [9]M. Bošnjak, T. Rocktäschel, J. Naradowsky, and S. Riedel. Programming with a differentiable forth interpreter. In International conference on machine learning, pages 547–556. PMLR, 2017.arxiv.org/abs/1605.06640
  9. [10]J. Cai, R. Shin, and D. Song. Making neural programming architectures generalize via recursion. arXiv preprint arXiv:1704.06611, 2017.arxiv.org/abs/1704.06611
  10. [11]X. Chen, C. Liang, A. W. Yu, D. Song, and D. Zhou. Compositional generalization via neural-symbolic stack machines. Advances in Neural Information Processing Systems, 33:1690–1701, 2020.arxiv.org/abs/2008.06662
  11. [12]H. Cho, J. Cha, P. Awasthi, S. Bhojanapalli, A. Gupta, and C. Yun. Position coupling: Improving length generalization of arithmetic transformers using task structure. Advances in Neural Information Processing Systems, 37:22233–22315, 2024a.arxiv.org/abs/2405.20671
  12. [13]H. Cho, J. Cha, S. Bhojanapalli, and C. Yun. Arithmetic transformers can length-generalize in both operand length and count. arXiv preprint arXiv:2410.15787, 2024b.arxiv.org/abs/2410.15787
  13. [14]S. Chung and H. Siegelmann. Turing completeness of bounded-precision recurrent neural networks. Advances in neural information processing systems, 34:28431–28441, 2021.
  14. [15]C. De La Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, 27 (2):125–138, 1997.
  15. [16]M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and L. Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018.arxiv.org/abs/1807.03819
  16. [17]G. Delétang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, J. Veness, et al. Neural networks and the chomsky hierarchy. arXiv preprint arXiv:2207.02098, 2022.arxiv.org/abs/2207.02098
  17. [18]A. L. Gaunt, M. Brockschmidt, R. Singh, N. Kushman, P. Kohli, J. Taylor, and D. Tarlow. Terpret: A probabilistic programming language for program induction. arXiv preprint arXiv:1608.04428, 2016.arxiv.org/abs/1608.04428
  18. [19]C. Giles, G.-Z. Sun, H.-H. Chen, Y.-C. Lee, and D. Chen. Higher order recurrent networks and grammatical inference. Advances in neural information processing systems, 2, 1989.
  19. [20]E. M. Gold. Language identification in the limit. Information and control, 10(5):447–474, 1967.DOI
  20. [21]E. M. Gold. Complexity of automaton identification from given data. Information and control, 37(3):302–320, 1978.DOI
  21. [22]A. Graves, G. Wayne, and I. Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014.arxiv.org/abs/1410.5401
  22. [23]A. Graves, G. Wayne, M. Reynolds, T. Harley, I. Danihelka, A. Grabska-Barwińska, S. G. Colmenarejo, E. Grefenstette, T. Ramalho, J. Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471–476, 2016.DOI
  23. [24]E. Grefenstette, K. M. Hermann, M. Suleyman, and P. Blunsom. Learning to transduce with unbounded memory. Advances in neural information processing systems, 28, 2015.arxiv.org/abs/1506.02516
  24. [25]A. György, T. Lattimore, N. Lazić, and C. Szepesvári. Beyond statistical learning: Exact learning is essential for general intelligence. arXiv preprint arXiv:2506.23908, 2025.arxiv.org/abs/2506.23908
  25. [26]H. Zhou, A. Bradley, E. Littwin, N. Razin, O. Saremi, J. Susskind, S. Bengio, and P. Nakkiran. What algorithms can transformers learn? a study in length generalization. arXiv preprint arXiv:2310.16028, 2023.arxiv.org/abs/2310.16028
  26. [27]K. Hou, D. Brandfonbrener, S. M. Kakade, S. Jelassi, and E. Malach. Universal length generalization with Turing programs. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 23873–23893. PMLR, 2025. URL https://proceedings.mlr.press/v267/hou25a.html.arxiv.org/abs/2407.03310
  27. [28]P. Indyk. Optimal simulation of automata by neural nets. In Annual Symposium on Theoretical Aspects of Computer Science, pages 337–348. Springer, 1995.DOI
  28. [29]S. Jelassi, S. d’Ascoli, C. Domingo-Enrich, Y. Wu, Y. Li, and F. Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306.15400, 2023.arxiv.org/abs/2306.15400
  29. [30]A. Joulin and T. Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. Advances in neural information processing systems, 28, 2015.arxiv.org/abs/1503.01007
  30. [31]L. Kaiser and I. Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015.arxiv.org/abs/1511.08228
  31. [32]A. Kazemnejad, I. Padhi, K. Natesan Ramamurthy, P. Das, and S. Reddy. The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems, 36:24892–24928, 2023.arxiv.org/abs/2305.19466
  32. [33]D. P. Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.arxiv.org/abs/1412.6980
  33. [34]K. Kurach, M. Andrychowicz, and I. Sutskever. Neural random-access machines. arXiv preprint arXiv:1511.06392, 2015.arxiv.org/abs/1511.06392
  34. [35]N. Lee, K. Sreenivasan, J. D. Lee, K. Lee, and D. Papailiopoulos. Teaching arithmetic to small transformers. arXiv preprint arXiv:2307.03381, 2023.arxiv.org/abs/2307.03381
  35. [36]B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022.arxiv.org/abs/2210.10749
  36. [37]A. N. Meltzoff and M. K. Moore. Infants’ understanding of people and things: From body imitation to folk psychology. The body and the self, pages 43–69, 1995.DOI
  37. [38]W. Merrill. Sequential neural networks as automata. arXiv preprint arXiv:1906.01615, 2019.arxiv.org/abs/1906.01615
  38. [39]W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. CoRR, 2023a.arxiv.org/abs/2310.07923
  39. [40]W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545, 2023b.arxiv.org/abs/2207.00729
  40. [41]W. Merrill, J. Petty, and A. Sabharwal. The illusion of state in state-space models. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024.arxiv.org/abs/2404.08819
  41. [42]A. Neelakantan, Q. V. Le, and I. Sutskever. Neural programmer: Inducing latent programs with gradient descent. arXiv preprint arXiv:1511.04834, 2015.arxiv.org/abs/1511.04834
  42. [43]J. Oncina and P. Garcia. Identifying regular languages in polynomial time. In Advances in structural and syntactic pattern recognition, pages 99–108. World Scientific, 1992.DOI
  43. [46]R. Parekh and V. Honavar. Learning dfa from simple examples. Machine Learning, 44:9–35, 2001.
  44. [47]E. Parisotto, A.-r. Mohamed, R. Singh, L. Li, D. Zhou, and P. Kohli. Neuro-symbolic program synthesis. arXiv preprint arXiv:1611.01855, 2016.arxiv.org/abs/1611.01855
  45. [49]T. Pierrot, G. Ligner, S. E. Reed, O. Sigaud, N. Perrin, A. Laterre, D. Kas, K. Beguir, and N. de Freitas. Learning compositional neural programs with recursive tree search and planning. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1905.12941
  46. [50]E. Price, W. Zaremba, and I. Sutskever. Extensions and limitations of the neural gpu. arXiv preprint arXiv:1611.00736, 2016.arxiv.org/abs/1611.00736
  47. [51]J. Pérez, J. Marinković, and P. Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2019.arxiv.org/abs/1901.03429
  48. [52]S. Reed and N. De Freitas. Neural programmer-interpreters. arXiv preprint arXiv:1511.06279, 2015.arxiv.org/abs/1511.06279
  49. [53]D. Schuurmans, H. Dai, and F. Zanini. Autoregressive large language models are computationally universal. arXiv preprint arXiv:2410.03170, 2024.arxiv.org/abs/2410.03170
  50. [54]R. Shen, S. Bubeck, R. Eldan, Y. T. Lee, Y. Li, and Y. Zhang. Positional description matters for transformers arithmetic. arXiv preprint arXiv:2311.14737, 2023.arxiv.org/abs/2311.14737
  51. [55]H. T. Siegelmann. Recurrent neural networks and finite automata. Computational intelligence, 12(4):567–574, 1996.DOI
  52. [56]H. T. Siegelmann and E. D. Sontag. On the computational power of neural nets. In Proceedings of the fifth annual workshop on Computational learning theory, pages 440–449, 1992.
  53. [57]R. J. Solomonoff et al. Machine learning-past and future. Dartmouth, NH, July, 2006.
  54. [58]A. Svete and R. Cotterell. Recurrent neural language models as probabilistic finite-state automata. arXiv preprint arXiv:2310.05161, 2023.arxiv.org/abs/2310.05161
  55. [59]F. Vaandrager, B. Garhewal, J. Rot, and T. Wißmann. A new approach for active automata learning based on apartness. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 223–243. Springer, 2022.arxiv.org/abs/2107.05419
  56. [60]O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
  57. [61]C. Wei, Y. Chen, and T. Ma. Statistically meaningful approximation: a case study on approximating turning machines with transformers. Advances in Neural Information Processing Systems, 35: 12071–12083, 2022.arxiv.org/abs/2107.13163
  58. [62]G. Weiss, Y. Goldberg, and E. Yahav. On the practical computational power of finite precision rnns for language recognition. arXiv preprint arXiv:1805.04908, 2018.arxiv.org/abs/1805.04908
  59. [63]J. Weston, S. Chopra, and A. Bordes. Memory networks. arXiv preprint arXiv:1410.3916, 2014.arxiv.org/abs/1410.3916
  60. [64]Y. Zhou, U. Alon, X. Chen, X. Wang, R. Agarwal, and D. Zhou. Transformers can achieve length generalization but not robustly. arXiv preprint arXiv:2402.09371, 2024.arxiv.org/abs/2402.09371
  61. [65]W. Zaremba and I. Sutskever. Reinforcement learning neural turing machines-revised. arXiv preprint arXiv:1505.00521, 2015.arxiv.org/abs/1505.00521
  62. [66]W. Zaremba, T. Mikolov, A. Joulin, and R. Fergus. Learning simple algorithms from examples. In International conference on machine learning, pages 421–429. PMLR, 2016.arxiv.org/abs/1511.07275
  63. [67]H. Zhang, L. H. Li, T. Meng, K.-W. Chang, and G. V. d. Broeck. On the paradox of learning to reason from data. arXiv preprint arXiv:2205.11502, 2022.arxiv.org/abs/2205.11502

Paper details

vlnc:W_564fcrqy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

LLMs

View statement
Looking for related papers…
Contents