Fetching the paper…
Reading the bibliography…
The performance of modern language models (LMs) has been improved by chain-of-thought (CoT) reasoning, i.e., the process of generating intermediate results that guide the model towards a final answer.
On the computational power of RNNs
Samuel A. Korsky and Robert C. Berwick. 2019 · 1906
Earlier work this paper cites.
A logical calculus of the ideas immanent in nervous activity
Warren S. McCulloch and Walter Pitts. 1943 · 1943
Earlier work this paper cites.
Neural Nets and the Brain Model Problem
Marvin Lee Minsky. 1954 · 1954
Earlier work this paper cites.
Representation of events in nerve nets and finite automata
S. C. Kleene. 1956 · 1956
Earlier work this paper cites.
On formal properties of simple phrase structure grammars
Y. Bar-Hillel, M. Perles, and E. Shamir. 1961 · 1961
Earlier work this paper cites.
Finding structure in time
Jeffrey L. Elman. 1990 · 1990
Earlier work this paper cites.
On the computational power of neural nets
Hava T. Siegelmann and Eduardo D. Sontag. 1992 · 1992
Earlier work this paper cites.
Computational Complexity
C.H. Papadimitriou. 1994 · 1994
Earlier work this paper cites.
Long short-term memory
Sepp Hochreiter and Jürgen Schmidhuber. 1997 · 1997
Earlier work this paper cites.
Finite-state transducers in language and speech processing
Mehryar Mohri. 1997 · 1997
Earlier work this paper cites.
Speech recognition by composition of weighted finite automata
Fernando C. N. Pereira and Michael D. Riley. 1997 · 1997
Earlier work this paper cites.
Relating probabilistic grammars and automata
Steven Abney, David McAllester, and Fernando Pereira. 1999 · 1999
Earlier work this paper cites.
On the determinization of weighted finite automata
Adam L. Buchsbaum, Raffaele Giancarlo, and Jeffery R. Westbrook. 2000 · 2000
Earlier work this paper cites.
Introduction to Automata Theory, Languages, and Computation , 3 edition
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001 · 2001
Earlier work this paper cites.
An Introduction to Kolmogorov Complexity and Its Applications , 3 edition
Ming Li and Paul M.B. Vitányi. 2008 · 2008
Earlier work this paper cites.
Speech Recognition with Weighted Finite-State Transducers , pages 559–584. Springer Berlin Heidelberg, Berlin, Heidelberg
Mehryar Mohri, Fernando Pereira, and Michael Riley. 2008 · 2008
Earlier work this paper cites.
Weighted Automata Algorithms , pages 213–254. Springer Berlin Heidelberg, Berlin, Heidelberg
Mehryar Mohri. 2009 · 2009
Earlier work this paper cites.
RNNs can generate bounded hierarchical languages with optimal memory
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. 2020 · 2010
Earlier work this paper cites.
Upper semicomputable sumtests for lower semicomputable semimeasures
Bruno Bauwens. 2013 · 2013
Cited alongside, same era.
Introduction to the Theory of Computation , 3 edition
Michael Sipser. 2013 · 2013
Cited alongside, same era.
On the properties of neural machine translation: Encoder–decoder approaches
Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014 · 2014
Cited alongside, same era.
From softmax to sparsemax: A sparse model of attention and multi-label classification
André F. T. Martins and Ramón F. Astudillo. 2016 · 2016
Cited alongside, same era.
Context-free transductions with neural stacks
Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. 2018 · 2018
Cited alongside, same era.
Saturated transformers are constant-depth threshold circuits
William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022 · 2022
Later among the works it cites.
Extracting finite automata from RNNs using state merging
William Merrill and Nikolaos Tsilivis. 2022 · 2022
Later among the works it cites.
Challenging BIG-Bench tasks and whether chain-of-thought can solve them
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V. Le, Ed H. Chi, Denny Zhou, and Jason Wei. 2022 · 2022
Later among the works it cites.
A measure-theoretic characterization of tight language models
Li Du, Lucas Torroba Hennigen, Tiago Pimentel, Clara Meister, Jason Eisner, and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
Towards revealing the mystery behind chain of thought: A theoretical perspective
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018 · 2018
Cited alongside, same era.
Sequential neural networks as automata
William Merrill. 2019 · 2019
Cited alongside, same era.
On the computational power of transformers and its implications in sequence modeling
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020 · 2020
Cited alongside, same era.
Theoretical limitations of self-attention in neural sequence models
Michael Hahn. 2020 · 2020
Cited alongside, same era.
Calibrating generative models: The probabilistic Chomsky–Schützenberger hierarchy
Thomas F. Icard. 2020 · 2020
Cited alongside, same era.
A formal hierarchy of RNN architectures
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020 · 2020
Cited alongside, same era.
Turing completeness of bounded-precision recurrent neural networks
Stephen Chung and Hava Siegelmann. 2021 · 2021
Cited alongside, same era.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2023 · 2023
Later among the works it cites.
Large language models are zero-shot reasoners
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2023 · 2023
Later among the works it cites.
The parallelism tradeoff: Limitations of log-precision transformers
William Merrill and Ashish Sabharwal. 2023 · 2023
Later among the works it cites.
On the representational capacity of recurrent neural language models
Franz Nowak, Anej Svete, Li Du, and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
On the intersection of context-free and regular languages
Clemente Pasti, Andreas Opedal, Tiago Pimentel, Tim Vieira, Jason Eisner, and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
Recurrent neural language models as probabilistic finite-state automata
Anej Svete and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
Transformers learn in-context by gradient descent
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. 2023 · 2023
Later among the works it cites.
Sub-task decomposition enables learning in sequence to sequence tasks
Noam Wies, Yoav Levine, and Amnon Shashua. 2023 · 2023
Later among the works it cites.
On affine homotopy between language encoders
Robin Chan, Reda Boumasmoud, Anej Svete, Yuxin Ren, Qipeng Guo, Zhijing Jin, Shauli Ravfogel, Mrinmaya Sachan, Bernhard Schölkopf, Mennatallah El-Assady, and Ryan Cotterell. 2024 · 2024
Closest in time.
The expressive power of transformers with chain of thought
William Merrill and Ashish Sabharwal. 2024 · 2024
Closest in time.
Transformers can represent n n -gram language models
Anej Svete and Ryan Cotterell. 2024 · 2024
Closest in time.
Lower bounds on the expressivity of recurrent neural language models
Anej Svete, Franz Nowak, Anisha Mohamed Sahabdeen, and Ryan Cotterell. 2024 · 2024
Closest in time.
Chain-of-thought reasoning without prompting
Xuezhi Wang and Denny Zhou. 2024 · 2024
Closest in time.