---
title: "Zoology — paper by Rudra; and Re (2023) — summary and ideas"
description: "To expose it, the authors propose multi-query associative recall (Mqar). 2.1 perplexity. 77 references, cited by 54 papers here."
authors: ["Simran Arora; Sabri Eyuboglu; Aman Timalsina; Isys Johnson; Michael Poli; James Zou; Atri Rudra;", "Christopher Re"]
year: 2023
venue: "arXiv:2312.04927"
source: "https://arxiv.org/abs/2312.04927"
doi: "10.48550/arxiv.2312.04927"
arxiv: "2312.04927"
licence: "CC0 1.0 (arXiv)"
licence_url: "http://creativecommons.org/publicdomain/zero/1.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/arora-2023-zoology-measuring-improving-recall-efficient/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/arora-2023-zoology-measuring-improving-recall-efficient/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2023](https://md.research.elamur.ai/free/en/papers/2023/page/10/) / Zoology: Measuring and Improving Recall in Efficient Language Models

# Zoology: Measuring and Improving Recall in Efficient Language Models

**Authors:** Simran Arora; Sabri Eyuboglu; Aman Timalsina; Isys Johnson; Michael Poli; James Zou; Atri Rudra; and [Christopher Re](https://md.research.elamur.ai/free/en/authors/christopher-re/) · **Year:** 2023 · **Venue:** arXiv:2312.04927 · **Licence:** [CC0 1.0 (arXiv)](http://creativecommons.org/publicdomain/zero/1.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2312.04927) · [PDF](https://arxiv.org/pdf/2312.04927) · [DOI 10.48550/arxiv.2312.04927](https://doi.org/10.48550/arxiv.2312.04927) · [arXiv 2312.04927](https://arxiv.org/abs/2312.04927) · [OpenAlex](https://openalex.org/W4389599535)

**Citations:** 1 citations (OpenAlex, 2026-10-14) · [54](https://md.research.elamur.ai/free/en/papers/arora-2023-zoology-measuring-improving-recall-efficient/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Gated-convolution language models such as H3, Hyena and RWKV are attractive because they scale sub-quadratically with sequence length. This paper asks whether they truly match Transformers. The authors trained 17 models with 5 architectures at sizes from 70M to 1.4B parameters, all on the same Pile data and setup. Attention still won by up to 2.1 perplexity points. Most of that gap came from associative recall: predicting a token by retrieving an association that appeared earlier in the same context.

Earlier synthetic recall benchmarks hid this weakness. To expose it, the authors propose multi-query associative recall (Mqar). In Mqar, many lookups happen at varied positions and draw on a large vocabulary. They also introduce BaseConv, an operator that can simulate gated-convolution architectures. Using it, they prove that solving Mqar requires model width that grows with sequence length, whereas attention needs no such growth.

The key fix is input-dependent mixing. Adding sparse attention at only a few layers, aimed at likely recall positions, nearly closes the gap while keeping costs sub-quadratic. This makes Mqar a useful design tool for efficient architectures.

## Key points
- **Recall explains most of the gap.** Tokens that require recall make up only 6.4% of Pile tokens, yet they account for about 82% of the perplexity gap. On these tokens, a 70M attention model beats a 1.4B Hyena model. The same gap appears at 7B scale when comparing RWKV with Llama-2.
- **Theory.** BaseConv provably covers H3, Hyena, RWKV and RetNet. For these models, the dimension needed to solve Mqar scales with input length, while attention's does not.
- **Full-attention hybrid.** At 360M parameters, BaseConv with only 3 attention layers beats the Transformer by 0.85 perplexity points while using about 18% fewer FLOPs.
- **Sparse-attention hybrids.** Placing sparse attention on repeated-bigram positions closes 85% of the recall gap. A learned selector using k = 256 positions closes 72%. According to the abstract, input-dependent sparse hybrids recover 97.4% of the overall gap.
- **Code:** https://github.com/HazyResearch/zoology

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Stanford University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 506 works · 330,053 citations
- [Purdue University West Lafayette](https://md.research.elamur.ai/free/en/universities/purdue-university-west-lafayette/) — University, West Lafayette, United States · 26 works · 2,076 citations
- [University at Buffalo, State University of New York](https://md.research.elamur.ai/free/en/universities/university-at-buffalo-state-university-of-new-york/) — University, Buffalo, United States · 13 works · 3,945 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works · [👁️ Computer Vision and Pattern Recognition](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-vision-and-pattern-recognition/) · 3,486 works

🧭 Topics (1): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,894 works

## Cite

Cite as: Simran Arora; Sabri Eyuboglu; Aman Timalsina; Isys Johnson; Michael Poli; James Zou; Atri Rudra; and Christopher Re. 2023. Zoology: Measuring and Improving Recall in Efficient Language Models. arXiv:2312.04927.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{rudra2023zoology,
  title = {{Zoology: Measuring and Improving Recall in Efficient Language Models}},
  author = {Simran Arora; Sabri Eyuboglu; Aman Timalsina; Isys Johnson; Michael Poli; James Zou; Atri Rudra; and Christopher Re},
  year = {2023},
  doi = {10.48550/arxiv.2312.04927},
  eprint = {2312.04927},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2312.04927}
}
```

- [← previous DERA: Enhancing Large Language Model Completions with Dialog-Enabled Resolving Agents](https://md.research.elamur.ai/free/en/papers/nair-2023-dera-enhancing-large-language-model/)
- [next → CMB: A Comprehensive Medical Benchmark in Chinese](https://md.research.elamur.ai/free/en/papers/wang-2023-cmb-comprehensive-medical-benchmark/)
- [↑ back to papers of 2023](https://md.research.elamur.ai/free/en/papers/2023/page/10/)

## References

77 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Daniel Y. Fu, Tri Dao, Khaled K. Saab, Armin W. Thomas, Atri Rudra, and Christopher Ré. Hungry Hungry Hippos: Towards language modeling with state space models. In International Conference on Learning Representations, 2023a. 1, 1, 2, 3.1, 3.2, 4.3, 5, 5, A.3, A.3, C.2, E.1 [find](https://scholar.google.com/scholar?q=Daniel+Y%2E+Fu%2C+Tri+Dao%2C+Khaled+K%2E+Saab%2C+Armin+W%2E+Thomas%2C+Atri+Rudra%2C+and+Christopher+Re%CC%81%2E+Hungry+Hungry+Hippos%3A+Towards+language+modeling+with+state+space+models%2E+In+International+Conference+on+Learnin)
2. Xuezhe Ma, Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Zettlemoyer Luke. Mega: Moving average equipped gated attention. arXiv preprint arXiv:2209.10655, 2022. 1, A.3, A.3 [find](https://scholar.google.com/scholar?q=Xuezhe+Ma%2C+Chunting+Zhou%2C+Xiang+Kong%2C+Junxian+He%2C+Liangke+Gui%2C+Graham+Neubig%2C+Jonathan+May%2C+and+Zettlemoyer+Luke%2E+Mega%3A+Moving+average+equipped+gated+attention%2E+arXiv+preprint+arXiv%3A2209%2E10655%2C+2022%2E+)
3. Junxiong Wang, Jing Nathan Yan, Albert Gu, and Alexander M Rush. Pretraining without attention. arXiv preprint arXiv:2212.10544, 2022. 1, 2 [find](https://scholar.google.com/scholar?q=Junxiong+Wang%2C+Jing+Nathan+Yan%2C+Albert+Gu%2C+and+Alexander+M+Rush%2E+Pretraining+without+attention%2E+arXiv+preprint+arXiv%3A2212%2E10544%2C+2022%2E+1%2C+2)
4. Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. arXiv preprint arXiv:2302.10866, 2023a. 1, 1, 2, 3.1, 3.2, 4.3, A.2, A.3, B, C.2, E.1, 2, H.2, 8 [find](https://scholar.google.com/scholar?q=Michael+Poli%2C+Stefano+Massaroli%2C+Eric+Nguyen%2C+Daniel+Y+Fu%2C+Tri+Dao%2C+Stephen+Baccus%2C+Yoshua+Bengio%2C+Stefano+Ermon%2C+and+Christopher+Re%CC%81%2E+Hyena+hierarchy%3A+Towards+larger+convolutional+language+models%2E+ar)
5. Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. [Language modeling with gated convolutional networks](https://md.research.elamur.ai/free/en/papers/dauphin-2016-language-modeling-gated-convolutional-networks/). In International conference on machine learning, pages 933–941. PMLR, 2017. 1, 2
6. Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021. 1, 2, A.2, A.3, 3, H.2.2 [find](https://scholar.google.com/scholar?q=Albert+Gu%2C+Karan+Goel%2C+and+Christopher+Re%CC%81%2E+Efficiently+modeling+long+sequences+with+structured+state+spaces%2E+arXiv+preprint+arXiv%3A2111%2E00396%2C+2021%2E+1%2C+2%2C+A%2E2%2C+A%2E3%2C+3%2C+H%2E2%2E2)
7. Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, and Jiaming et al. Kong. Rwkv: Reinventing rnns for the transformer era. arXiv:2305.13048, 2023. 1, 2… [find](https://scholar.google.com/scholar?q=Bo+Peng%2C+Eric+Alcaide%2C+Quentin+Anthony%2C+Alon+Albalak%2C+Samuel+Arcadinho%2C+Huanqi+Cao%2C+Xin+Cheng%2C+Michael+Chung%2C+Matteo+Grella%2C+Kranthi+Kiran+GV%2C+Xuzheng+He%2C+Haowen+Hou%2C+Przemyslaw+Kazienko%2C+Jan+Kocon%2C+a)
8. Daniel Y. Fu, Simran Arora, Jessica Grogan, Isys Johnson, Sabri Eyuboglu, Armin W. Thomas, Benjamin Spector, Michael Poli, Atri Rudra, and Christopher Ré. Monarch mixer: A simple sub-quadratic gemm-based architecture, 2023b. 1, 2, A.3 [find](https://scholar.google.com/scholar?q=Daniel+Y%2E+Fu%2C+Simran+Arora%2C+Jessica+Grogan%2C+Isys+Johnson%2C+Sabri+Eyuboglu%2C+Armin+W%2E+Thomas%2C+Benjamin+Spector%2C+Michael+Poli%2C+Atri+Rudra%2C+and+Christopher+Re%CC%81%2E+Monarch+mixer%3A+A+simple+sub%2Dquadratic+gemm%2Db)
9. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014. 1, A.1 [find](https://scholar.google.com/scholar?q=Alex+Graves%2C+Greg+Wayne%2C+and+Ivo+Danihelka%2E+Neural+turing+machines%2E+arXiv+preprint+arXiv%3A1410%2E5401%2C+2014%2E+1%2C+A%2E1)
10. Jimmy Ba, Geoffrey E Hinton, Volodymyr Mnih, Joel Z Leibo, and Catalin Ionescu. Using fast weights to attend to the recent past. Advances in neural information processing systems, 29, 2016. 1, A.1, H.7.1 [find](https://scholar.google.com/scholar?q=Jimmy+Ba%2C+Geoffrey+E+Hinton%2C+Volodymyr+Mnih%2C+Joel+Z+Leibo%2C+and+Catalin+Ionescu%2E+Using+fast+weights+to+attend+to+the+recent+past%2E+Advances+in+neural+information+processing+systems%2C+29%2C+2016%2E+1%2C+A%2E1%2C+H%2E)
11. Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 1, 2021. 1, A.1 [find](https://scholar.google.com/scholar?q=Nelson+Elhage%2C+Neel+Nanda%2C+Catherine+Olsson%2C+Tom+Henighan%2C+Nicholas+Joseph%2C+Ben+Mann%2C+Amanda+Askell%2C+Yuntao+Bai%2C+Anna+Chen%2C+Tom+Conerly%2C+et+al%2E+A+mathematical+framework+for+transformer+circuits%2E+Trans)
12. Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. [In-context learning and induction heads](https://md.research.elamur.ai/free/en/papers/olsson-2022-context-learning-induction-heads/). arXiv preprint arXiv:2209.11895, 2022. 1, 3.2, 4.3, A.1, E.1
13. Shahar Lutati, Itamar Zimerman, and Lior Wolf. Focus your attention (with adaptive iir filters), 2023. 1 [find](https://scholar.google.com/scholar?q=Shahar+Lutati%2C+Itamar+Zimerman%2C+and+Lior+Wolf%2E+Focus+your+attention+%28with+adaptive+iir+filters%29%2C+2023%2E+1)
14. Michael Hahn. Theoretical limitations of self-attention in neural sequence models. In Transactions of the Association for Computational Linguistics, volume 8, 2020. 1, 6 [find](https://scholar.google.com/scholar?q=Michael+Hahn%2E+Theoretical+limitations+of+self%2Dattention+in+neural+sequence+models%2E+In+Transactions+of+the+Association+for+Computational+Linguistics%2C+volume+8%2C+2020%2E+1%2C+6)
15. William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. In Transactions of the Association for Computational Linguistics, volume 10, 2022. 1, 6 [find](https://scholar.google.com/scholar?q=William+Merrill%2C+Ashish+Sabharwal%2C+and+Noah+A%2E+Smith%2E+Saturated+transformers+are+constant%2Ddepth+threshold+circuits%2E+In+Transactions+of+the+Association+for+Computational+Linguistics%2C+volume+10%2C+2022%2E+1)
16. Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computational complexity of self-attention. In 34th International Conference on Algorithmic Learning Theory, volume 201, page 1–23, 2023. 1, 6 [find](https://scholar.google.com/scholar?q=Feyza+Duman+Keles%2C+Pruthuvi+Mahesakya+Wijewardena%2C+and+Chinmay+Hegde%2E+On+the+computational+complexity+of+self%2Dattention%2E+In+34th+International+Conference+on+Algorithmic+Learning+Theory%2C+volume+201%2C+pa)
17. Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The Pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.00027, 2020. 2, 3.1, D, D.1 [find](https://scholar.google.com/scholar?q=Leo+Gao%2C+Stella+Biderman%2C+Sid+Black%2C+Laurence+Golding%2C+Travis+Hoppe%2C+Charles+Foster%2C+Jason+Phang%2C+Horace+He%2C+Anish+Thite%2C+Noa+Nabeshima%2C+Shawn+Presser%2C+and+Connor+Leahy%2E+The+Pile%3A+An+800gb+dataset+of+)
18. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, and Shruti Bhosale. [Llama 2: Open foundation and fine-tuned chat models](https://md.research.elamur.ai/free/en/papers/touvron-2023-llama-2-open-foundation-fine/). arXiv:2307.09288, 2023. 2, 3.1, C.2, G Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob…
19. James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297–301, 1965. 2, A.2 [find](https://scholar.google.com/scholar?q=James+W+Cooley+and+John+W+Tukey%2E+An+algorithm+for+the+machine+calculation+of+complex+fourier+series%2E+Mathematics+of+computation%2C+19%2890%29%3A297%E2%80%93301%2C+1965%2E+2%2C+A%2E2)
20. Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. [Efficient transformers: A survey](https://md.research.elamur.ai/free/en/papers/tay-2020-efficient-transformers-survey/). ACM Computing Surveys, 55(6):1–28, 2022. 2, 4
21. Karan Goel, Albert Gu, Chris Donahue, and Christopher Ré. It’s raw! audio generation with state-space models. Proceedings of the 39 th International Conference on Machine Learning,, 2022. 2 [find](https://scholar.google.com/scholar?q=Karan+Goel%2C+Albert+Gu%2C+Chris+Donahue%2C+and+Christopher+Re%CC%81%2E+It%E2%80%99s+raw%21+audio+generation+with+state%2Dspace+models%2E+Proceedings+of+the+39+th+International+Conference+on+Machine+Learning%2C%2C+2022%2E+2)
22. Michael Zhang, Khaled Saab, Michael Poli, Tri Dao, Karan Goel, and Christopher Ré. Effectively modeling time series with simple discrete state spaces. International Conference on Learning Representations, 2023. 2 [find](https://scholar.google.com/scholar?q=Michael+Zhang%2C+Khaled+Saab%2C+Michael+Poli%2C+Tri+Dao%2C+Karan+Goel%2C+and+Christopher+Re%CC%81%2E+Effectively+modeling+time+series+with+simple+discrete+state+spaces%2E+International+Conference+on+Learning+Representat)
23. Shuangfei Zhai, Walter Talbott, Nitish Srivastava, Chen Huang, Hanlin Goh, Ruixiang Zhang, and Josh Susskind. An attention free transformer. arXiv preprint arXiv:2105.14103, 2021. 2 — [arXiv:2105.14103](https://arxiv.org/abs/2105.14103) [find](https://scholar.google.com/scholar?q=Shuangfei+Zhai%2C+Walter+Talbott%2C+Nitish+Srivastava%2C+Chen+Huang%2C+Hanlin+Goh%2C+Ruixiang+Zhang%2C+and+Josh+Susskind%2E+An+attention+free+transformer%2E+arXiv+preprint+arXiv%3A2105%2E14103%2C+2021%2E+2+%E2%80%94+%5BarXiv%3A2105%2E1410)
24. Alex Andonian, Quentin Anthony, Stella Biderman, Sid Black, Preetham Gali, Leo Gao, Eric Hallahan, Josh Levy-Kramer, Connor Leahy, Lucas Nestler, Kip Parker, Michael Pieler, Jason Phang, Shivanshu Purohit, Hailey Schoelkopf, Dashiell Stander, Tri Songz, Curt Tigges, Benjamin Thérien, Phil Wang, and… [find](https://scholar.google.com/scholar?q=Alex+Andonian%2C+Quentin+Anthony%2C+Stella+Biderman%2C+Sid+Black%2C+Preetham+Gali%2C+Leo+Gao%2C+Eric+Hallahan%2C+Josh+Levy%2DKramer%2C+Connor+Leahy%2C+Lucas+Nestler%2C+Kip+Parker%2C+Michael+Pieler%2C+Jason+Phang%2C+Shivanshu+Pur)
25. Ramin Hasani, Mathias Lechner, Tsun-Huang Wang, Makram Chahine, Alexander Amini, and Daniela Rus. Liquid structural state-space models. arXiv preprint arXiv:2209.12951, 2022. 3.1, A.3 — [arXiv:2209.12951](https://arxiv.org/abs/2209.12951) [find](https://scholar.google.com/scholar?q=Ramin+Hasani%2C+Mathias+Lechner%2C+Tsun%2DHuang+Wang%2C+Makram+Chahine%2C+Alexander+Amini%2C+and+Daniela+Rus%2E+Liquid+structural+state%2Dspace+models%2E+arXiv+preprint+arXiv%3A2209%2E12951%2C+2022%2E+3%2E1%2C+A%2E3+%E2%80%94+%5BarXiv%3A2209%2E12)
26. Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. [Retentive network: A successor to transformer for large language models](https://md.research.elamur.ai/free/en/papers/sun-2023-retentive-network-successor-transformer-large/), 2023. 3.1, A.3, D.1.2, 3, 6, H.2, H.2.3, 12
27. Sabri Eyuboglu, Maya Varma, Khaled Saab, Jean-Benoit Delbrouck, Christopher Lee-Messer, Jared Dunnmon, James Zou, and Christopher Ré. Domino: Discovering systematic errors with cross-modal embeddings. In International Conference on Learning Representations, March 2022. 3.1 [find](https://scholar.google.com/scholar?q=Sabri+Eyuboglu%2C+Maya+Varma%2C+Khaled+Saab%2C+Jean%2DBenoit+Delbrouck%2C+Christopher+Lee%2DMesser%2C+Jared+Dunnmon%2C+James+Zou%2C+and+Christopher+Re%CC%81%2E+Domino%3A+Discovering+systematic+errors+with+cross%2Dmodal+embeddings)
28. David J Willshaw, O Peter Buneman, and Hugh Christopher Longuet-Higgins. Non-holographic associative memory. Nature, 222(5197):960–962, 1969. 3.1, A.1 [find](https://scholar.google.com/scholar?q=David+J+Willshaw%2C+O+Peter+Buneman%2C+and+Hugh+Christopher+Longuet%2DHiggins%2E+Non%2Dholographic+associative+memory%2E+Nature%2C+222%285197%29%3A960%E2%80%93962%2C+1969%2E+3%2E1%2C+A%2E1)
29. John J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8):2554–2558, 1982. 3.1, A.1 [find](https://scholar.google.com/scholar?q=John+J+Hopfield%2E+Neural+networks+and+physical+systems+with+emergent+collective+computational+abilities%2E+Proceedings+of+the+national+academy+of+sciences%2C+79%288%29%3A2554%E2%80%932558%2C+1982%2E+3%2E1%2C+A%2E1)
30. P. Bürgisser, T. Lickteig, M. Clausen, and A. Shokrollahi. Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 1996. ISBN 9783540605829. URL [https://books.google.com/books?id=dYcgjfXsYk8C](https://books.google.com/books?id=dYcgjfXsYk8C). 4.1, H.13 [↗](https://books.google.com/books?id=dYcgjfXsYk8C)
31. Tri Dao, Nimit S Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszczynski, Atri Rudra, and Christopher Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. arXiv preprint arXiv:2012.14966, 2020. 4.1, H.3, H.4, H.14, H.17, H.4, H.19 — [arXiv:2012.14966](https://arxiv.org/abs/2012.14966) [find](https://scholar.google.com/scholar?q=Tri+Dao%2C+Nimit+S+Sohoni%2C+Albert+Gu%2C+Matthew+Eichhorn%2C+Amit+Blonder%2C+Megan+Leszczynski%2C+Atri+Rudra%2C+and+Christopher+Re%CC%81%2E+Kaleidoscope%3A+An+efficient%2C+learnable+representation+for+all+structured+linear+m)
32. Daniel Y. Fu, Elliot L. Epstein, Eric Nguyen, Armin W. Thomas, Michael Zhang, Tri Dao, Atri Rudra, and Christopher Ré. Simple hardware-efficient long convolutions for sequence modeling. arXiv preprint arXiv:2302.06646, 2023c. 4.3, A.3, C.2, 10, 13 [find](https://scholar.google.com/scholar?q=Daniel+Y%2E+Fu%2C+Elliot+L%2E+Epstein%2C+Eric+Nguyen%2C+Armin+W%2E+Thomas%2C+Michael+Zhang%2C+Tri+Dao%2C+Atri+Rudra%2C+and+Christopher+Re%CC%81%2E+Simple+hardware%2Defficient+long+convolutions+for+sequence+modeling%2E+arXiv+preprin)
33. Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and et al. [Big bird: Transformers for longer sequences](https://md.research.elamur.ai/free/en/papers/zaheer-2020-big-bird-transformers-longer-sequences/). Proceedings of NeurIPS, 2020. 5, 4
34. Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. [Generating long sequences with sparse transformers](https://md.research.elamur.ai/free/en/papers/child-2019-generating-long-sequences-sparse-transformers/). arXiv preprint arXiv:1904.10509, 2019a. 5
35. Iz Beltagy, Matthew E Peters, and Arman Cohan. [Longformer: The long-document transformer](https://md.research.elamur.ai/free/en/papers/beltagy-2020-longformer-long-document-transformer/). arXiv preprint arXiv:2004.05150, 2020. 5, D.1.2, 4
36. Liliang Ren, Yang Liu, Shuohang Wang, Yichong Xu, Chenguang Zhu, and ChengXiang Zhai. Sparse modular activation for efficient sequence modeling. Sparse Modular Activation for Efficient Sequence Modeling, 2023. 5, A.3 [find](https://scholar.google.com/scholar?q=Liliang+Ren%2C+Yang+Liu%2C+Shuohang+Wang%2C+Yichong+Xu%2C+Chenguang+Zhu%2C+and+ChengXiang+Zhai%2E+Sparse+modular+activation+for+efficient+sequence+modeling%2E+Sparse+Modular+Activation+for+Efficient+Sequence+Modeli)
37. Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Processing Systems, 2022. 6 [find](https://scholar.google.com/scholar?q=Tri+Dao%2C+Daniel+Y%2E+Fu%2C+Stefano+Ermon%2C+Atri+Rudra%2C+and+Christopher+Re%CC%81%2E+FlashAttention%3A+Fast+and+memory%2Defficient+exact+attention+with+IO%2Dawareness%2E+In+Advances+in+Neural+Information+Processing+Systems)
38. Tri Dao. [FlashAttention-2: Faster attention with better parallelism and work partitioning](https://md.research.elamur.ai/free/en/papers/dao-2023-flashattention-2-faster-attention-better/). 2023. 6
39. A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In Proceedings of the International Conference on Machine Learning (ICML), 2020a. URL https://arxiv.org/abs/2006.16236. 6 [↗](https://arxiv.org/abs/2006.16236)
40. Chris Olah. Mechanistic interpretability, variables, and the importance of interpretable bases: An informal note on some intuitions related to mechanistic interpretability, 2022. URL [https://transformer-circuits.pub/2022/mech-interp-essay/index.html](https://transformer-circuits.pub/2022/mech-interp-essay/index.html). A.1, A.3 [↗](https://transformer-circuits.pub/2022/mech-interp-essay/index.html)
41. Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. [Grokking: Generalization beyond overfitting on small algorithmic datasets](https://md.research.elamur.ai/free/en/papers/power-2022-grokking-generalization-overfitting-small-algorithmic/). arXiv:2201.02177, 2022. A.1
42. Nick Cammarata, Shan Carter, Gabriel Goh, Chris Olah, Michael Petrov, Ludwig Schubert, Chelsea Voss, Ben Egan, and Swee Kiat Lim. Thread: circuits. Distill, 5(3):e24, 2020. A.1 [find](https://scholar.google.com/scholar?q=Nick+Cammarata%2C+Shan+Carter%2C+Gabriel+Goh%2C+Chris+Olah%2C+Michael+Petrov%2C+Ludwig+Schubert%2C+Chelsea+Voss%2C+Ben+Egan%2C+and+Swee+Kiat+Lim%2E+Thread%3A+circuits%2E+Distill%2C+5%283%29%3Ae24%2C+2020%2E+A%2E1)
43. Dingquan Wang and Jason Eisner. [The galactic dependencies treebanks: Getting more data by synthesizing new languages](https://md.research.elamur.ai/free/en/papers/wang-2016-galactic-dependencies-treebanks-getting-more/). Transactions of the Association for Computational Linguistics, 4:491–505, 2016. A.1
44. Jennifer C White and Ryan Cotterell. Examining the inductive bias of neural language models with artificial languages. arXiv preprint arXiv:2106.01044, 2021. A.1 [find](https://scholar.google.com/scholar?q=Jennifer+C+White+and+Ryan+Cotterell%2E+Examining+the+inductive+bias+of+neural+language+models+with+artificial+languages%2E+arXiv+preprint+arXiv%3A2106%2E01044%2C+2021%2E+A%2E1)
45. Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 1, context-free grammar. arXiv preprint arXiv:2305.13673, 2023. A.1 [find](https://scholar.google.com/scholar?q=Zeyuan+Allen%2DZhu+and+Yuanzhi+Li%2E+Physics+of+language+models%3A+Part+1%2C+context%2Dfree+grammar%2E+arXiv+preprint+arXiv%3A2305%2E13673%2C+2023%2E+A%2E1)
46. Shauli Ravfogel, Yoav Goldberg, and Tal Linzen. [Studying the inductive biases of rnns with synthetic variations of natural languages](https://md.research.elamur.ai/free/en/papers/ravfogel-2019-studying-inductive-biases-rnns-synthetic/). arXiv preprint arXiv:1903.06400, 2019. A.1
47. Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. [An explanation of in-context learning as implicit bayesian inference](https://md.research.elamur.ai/free/en/papers/xie-2021-explanation-context-learning-implicit-bayesian/). arXiv preprint arXiv:2111.02080, 2021. A.1, G Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451…
48. JA Feldman, GE Hinton, and JA Anderson. Parallel models of associative memory, 1981. A.1 [find](https://scholar.google.com/scholar?q=JA+Feldman%2C+GE+Hinton%2C+and+JA+Anderson%2E+Parallel+models+of+associative+memory%2C+1981%2E+A%2E1)
49. Wei Zhang and Bowen Zhou. Learning to update auto-associative memory in recurrent neural networks for improving sequence memorization. arXiv preprint arXiv:1709.06493, 2017. A.1 — [arXiv:1709.06493](https://arxiv.org/abs/1709.06493) [find](https://scholar.google.com/scholar?q=Wei+Zhang+and+Bowen+Zhou%2E+Learning+to+update+auto%2Dassociative+memory+in+recurrent+neural+networks+for+improving+sequence+memorization%2E+arXiv+preprint+arXiv%3A1709%2E06493%2C+2017%2E+A%2E1+%E2%80%94+%5BarXiv%3A1709%2E06493%5D%28h)
50. Stefano Massaroli, Michael Poli, Daniel Y Fu, Hermann Kumbong, David Romero, Rom Parnichukun, Aman Timalsina, Quinn McIntyre, Beidi Chen, Atri Rudra, Ce Zhang, Christopher Ré, Stefano Ermon, and Yoshua Bengio. Laughing hyena distillery: Extracting compact recurrences from convolutions. 2023. A.2 [find](https://scholar.google.com/scholar?q=Stefano+Massaroli%2C+Michael+Poli%2C+Daniel+Y+Fu%2C+Hermann+Kumbong%2C+David+Romero%2C+Rom+Parnichukun%2C+Aman+Timalsina%2C+Quinn+McIntyre%2C+Beidi+Chen%2C+Atri+Rudra%2C+Ce+Zhang%2C+Christopher+Re%CC%81%2C+Stefano+Ermon%2C+and+Yosh)
51. David W. Romero, Anna Kuzina, Erik J. Bekkers, Jakub M. Tomczak, and Mark Hoogendoorn. Ckconv: Continuous kernel convolution for sequential data. 2022. A.3 [find](https://scholar.google.com/scholar?q=David+W%2E+Romero%2C+Anna+Kuzina%2C+Erik+J%2E+Bekkers%2C+Jakub+M%2E+Tomczak%2C+and+Mark+Hoogendoorn%2E+Ckconv%3A+Continuous+kernel+convolution+for+sequential+data%2E+2022%2E+A%2E3)
52. Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces, 2022. A.3 [find](https://scholar.google.com/scholar?q=Ankit+Gupta%2C+Albert+Gu%2C+and+Jonathan+Berant%2E+Diagonal+state+spaces+are+as+effective+as+structured+state+spaces%2C+2022%2E+A%2E3)
53. Albert Gu, Ankit Gupta, Karan Goel, and Christopher Ré. On the parameterization and initialization of diagonal state space models, 2022. A.3 [find](https://scholar.google.com/scholar?q=Albert+Gu%2C+Ankit+Gupta%2C+Karan+Goel%2C+and+Christopher+Re%CC%81%2E+On+the+parameterization+and+initialization+of+diagonal+state+space+models%2C+2022%2E+A%2E3)
54. Harsh Mehta, Ankit Gupta, Ashok Cutkosky, and Behnam Neyshabur. Long range language modeling via gated state spaces, 2022. A.3 [find](https://scholar.google.com/scholar?q=Harsh+Mehta%2C+Ankit+Gupta%2C+Ashok+Cutkosky%2C+and+Behnam+Neyshabur%2E+Long+range+language+modeling+via+gated+state+spaces%2C+2022%2E+A%2E3)
55. Jimmy T. H. Smith, Andrew Warrington, and Scott W. Linderman. Simplified state space layers for sequence modeling, 2023. A.3 [find](https://scholar.google.com/scholar?q=Jimmy+T%2E+H%2E+Smith%2C+Andrew+Warrington%2C+and+Scott+W%2E+Linderman%2E+Simplified+state+space+layers+for+sequence+modeling%2C+2023%2E+A%2E3)
56. Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Callum Birch-Sykes, Michael Wornow, Aman Patel, Clayton Rabideau, Stefano Massaroli, Yoshua Bengio, Stefano Ermon, Stephen A. Baccus, and Chris Ré. Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution, 2023. A.3 [find](https://scholar.google.com/scholar?q=Eric+Nguyen%2C+Michael+Poli%2C+Marjan+Faizi%2C+Armin+Thomas%2C+Callum+Birch%2DSykes%2C+Michael+Wornow%2C+Aman+Patel%2C+Clayton+Rabideau%2C+Stefano+Massaroli%2C+Yoshua+Bengio%2C+Stefano+Ermon%2C+Stephen+A%2E+Baccus%2C+and+Chris+R)
57. Transformers revolutionized ai. what will replace them?, 2023. URL [https://www.forbes.com/](https://www.forbes.com/) sites/robtoews/2023/09/03/transformers-revolutionized-ai-what-will-replace-them/?sh= 6ed698269c1f. A.3 [↗](https://www.forbes.com/)
58. Jue Wang, Wentao Zhu, Pichao Wang, Xiang Yu, Linda Liu, Mohamed Omar, and Raffay Hamid. Selective structured state-spaces for long-form video understanding. In CVPR, 2023. A.3 [find](https://scholar.google.com/scholar?q=Jue+Wang%2C+Wentao+Zhu%2C+Pichao+Wang%2C+Xiang+Yu%2C+Linda+Liu%2C+Mohamed+Omar%2C+and+Raffay+Hamid%2E+Selective+structured+state%2Dspaces+for+long%2Dform+video+understanding%2E+In+CVPR%2C+2023%2E+A%2E3)
59. Brandon Yang, Gabriel Bender, Quoc V. Le, and Jiquan Ngiam. Condconv: Conditionally parametrized convolutions for efficient inference. In 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), 2020. A.3 [find](https://scholar.google.com/scholar?q=Brandon+Yang%2C+Gabriel+Bender%2C+Quoc+V%2E+Le%2C+and+Jiquan+Ngiam%2E+Condconv%3A+Conditionally+parametrized+convolutions+for+efficient+inference%2E+In+33rd+Conference+on+Neural+Information+Processing+Systems+%28Neur)
60. Chrysoula Kosma, Giannis Nikolentzos, and Michalis Vazirgiannis. Time-parameterized convolutional neural networks for irregularly sampled time series. 2023. A.3 [find](https://scholar.google.com/scholar?q=Chrysoula+Kosma%2C+Giannis+Nikolentzos%2C+and+Michalis+Vazirgiannis%2E+Time%2Dparameterized+convolutional+neural+networks+for+irregularly+sampled+time+series%2E+2023%2E+A%2E3)
61. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention, 2020b. A.3 [find](https://scholar.google.com/scholar?q=Angelos+Katharopoulos%2C+Apoorv+Vyas%2C+Nikolaos+Pappas%2C+and+Franc%CC%A7ois+Fleuret%2E+Transformers+are+rnns%3A+Fast+autoregressive+transformers+with+linear+attention%2C+2020b%2E+A%2E3)
62. Together. Redpajama: An open source recipe to reproduce llama training dataset, 2023. URL [https://github.com/togethercomputer/RedPajama-Data](https://github.com/togethercomputer/RedPajama-Data). D, D.2, 4 [↗](https://github.com/togethercomputer/RedPajama-Data)
63. Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. [Adaptive attention span in transformers](https://md.research.elamur.ai/free/en/papers/sukhbaatar-2019-adaptive-attention-span-transformers/). Association of Computational Linguistics, 2019. D.1.2
64. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. [Language models are few-shot learners](https://md.research.elamur.ai/free/en/papers/brown-2020-language-models-few-shot-learners/). Advances in neural information processing systems, 33:1877–1901, 2020. 1
65. Anonymous. Mamba: Linear-time sequence modeling with selective state spaces. 2023a. URL [https://openreview.net/forum?id=AL1fq05o7H](https://openreview.net/forum?id=AL1fq05o7H). 3, F.1 [↗](https://openreview.net/forum?id=AL1fq05o7H)
66. Anonymous. Gateloop: Fully data-controlled linear recurrence for sequence modeling. 2023b. URL [https://openreview.net/pdf?id=02Ug9N8DCI](https://openreview.net/pdf?id=02Ug9N8DCI). 3, F.1 [↗](https://openreview.net/pdf?id=02Ug9N8DCI)
67. Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. [Generating long sequences with sparse transformers](https://md.research.elamur.ai/free/en/papers/child-2019-generating-long-sequences-sparse-transformers/). arXiv preprint arXiv:1904.10509, 2019b. 4
68. Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint arXiv:1911.02972, 2019. 4 [find](https://scholar.google.com/scholar?q=Jiezhong+Qiu%2C+Hao+Ma%2C+Omer+Levy%2C+Scott+Wen+tau+Yih%2C+Sinong+Wang%2C+and+Jie+Tang%2E+Blockwise+self%2Dattention+for+long+document+understanding%2E+arXiv+preprint+arXiv%3A1911%2E02972%2C+2019%2E+4)
69. Michael T Heideman and C Sidney Burrus. Multiplicative complexity, convolution, and the DFT. Springer, 1988. H.1.1 [find](https://scholar.google.com/scholar?q=Michael+T+Heideman+and+C+Sidney+Burrus%2E+Multiplicative+complexity%2C+convolution%2C+and+the+DFT%2E+Springer%2C+1988%2E+H%2E1%2E1)
70. Ilya Volkovich. A guide to learning arithmetic circuits. In Conference on Learning Theory, pages 1540–1561. PMLR, 2016. H.1.1 [find](https://scholar.google.com/scholar?q=Ilya+Volkovich%2E+A+guide+to+learning+arithmetic+circuits%2E+In+Conference+on+Learning+Theory%2C+pages+1540%E2%80%931561%2E+PMLR%2C+2016%2E+H%2E1%2E1)
71. Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. Proceedings of the 40th International Conference on Machine Learning, 2023b. H.2.1 [find](https://scholar.google.com/scholar?q=Michael+Poli%2C+Stefano+Massaroli%2C+Eric+Nguyen%2C+Daniel+Y+Fu%2C+Tri+Dao%2C+Stephen+Baccus%2C+Yoshua+Bengio%2C+Stefano+Ermon%2C+and+Christopher+Re%CC%81%2E+Hyena+hierarchy%3A+Towards+larger+convolutional+language+models%2E+Pr)
72. Thathachar S Jayram, Ravi Kumar, and Dandapani Sivakumar. The one-way communication complexity of hamming distance. Theory of Computing, 4(1):129–135, 2008. H.23 [find](https://scholar.google.com/scholar?q=Thathachar+S+Jayram%2C+Ravi+Kumar%2C+and+Dandapani+Sivakumar%2E+The+one%2Dway+communication+complexity+of+hamming+distance%2E+Theory+of+Computing%2C+4%281%29%3A129%E2%80%93135%2C+2008%2E+H%2E23)
73. Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108.12409, 2021. H.7.2 [find](https://scholar.google.com/scholar?q=Ofir+Press%2C+Noah+A+Smith%2C+and+Mike+Lewis%2E+Train+short%2C+test+long%3A+Attention+with+linear+biases+enables+input+length+extrapolation%2E+arXiv+preprint+arXiv%3A2108%2E12409%2C+2021%2E+H%2E7%2E2)
74. Selim G Akl and Henk Meijer. Parallel binary search. IEEE Transactions on Parallel & Distributed Systems, 1(02):247–250, 1990. H.7.4, H.7.4 [find](https://scholar.google.com/scholar?q=Selim+G+Akl+and+Henk+Meijer%2E+Parallel+binary+search%2E+IEEE+Transactions+on+Parallel+%26+Distributed+Systems%2C+1%2802%29%3A247%E2%80%93250%2C+1990%2E+H%2E7%2E4%2C+H%2E7%2E4)
75. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022. H.32 [find](https://scholar.google.com/scholar?q=Thomas+H+Cormen%2C+Charles+E+Leiserson%2C+Ronald+L+Rivest%2C+and+Clifford+Stein%2E+Introduction+to+algorithms%2E+MIT+press%2C+2022%2E+H%2E32)
76. Miklós Ajtai, János Komlós, and Endre Szemerédi. An 0 (n log n) sorting network. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 1–9, 1983. H.35 [find](https://scholar.google.com/scholar?q=Miklo%CC%81s+Ajtai%2C+Ja%CC%81nos+Komlo%CC%81s%2C+and+Endre+Szemere%CC%81di%2E+An+0+%28n+log+n%29+sorting+network%2E+In+Proceedings+of+the+fifteenth+annual+ACM+symposium+on+Theory+of+computing%2C+pages+1%E2%80%939%2C+1983%2E+H%2E35)
77. Chris Chatfield. The analysis of time series: An introduction, fifth edition. 1995. H.8.1 [find](https://scholar.google.com/scholar?q=Chris+Chatfield%2E+The+analysis+of+time+series%3A+An+introduction%2C+fifth+edition%2E+1995%2E+H%2E8%2E1)

*Updated 2 November 2026*