# Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval

arXiv: https://arxiv.org/abs/2201.12431 · HTML: https://mlsanity.com/paper/2201.12431/

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 47 references that are in the map.
- First posted on arXiv 28 Jan 2022.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2010.00710/) (2020)
- [Facebook FAIR's WMT19 News Translation Task Submission](https://mlsanity.com/paper/1907.06616/) (2019)
- [Unsupervised Domain Clusters in Pretrained Language Models](https://mlsanity.com/paper/2004.02105/) (2020)
- [Efficient Nearest Neighbor Language Models](https://mlsanity.com/paper/2109.04212/) (2021)
- [Generating Sentences by Editing Prototypes](https://mlsanity.com/paper/1709.08878/) (2017)
- [Adaptive Semiparametric Language Models](https://mlsanity.com/paper/2102.02557/) (2021)
- [A Retrieve-and-Edit Framework for Predicting Structured Outputs](https://mlsanity.com/paper/1812.01194/) (2018)
- [Efficient softmax approximation for GPUs](https://mlsanity.com/paper/1609.04309/) (2016)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Guiding Neural Machine Translation with Retrieved Translation Pieces](https://mlsanity.com/paper/1804.02559/) (2018)
- [Learning to Retrieve Passages without Supervision](https://mlsanity.com/paper/2112.07708/) (2021)
- [Retrieval-Based Neural Code Generation](https://mlsanity.com/paper/1808.10025/) (2018)
- [Unbounded cache model for online language modeling with open vocabulary](https://mlsanity.com/paper/1711.02604/) (2017)
- [GNN-LM: Language Modeling based on Global Contexts via GNN](https://mlsanity.com/paper/2110.08743/) (2021)
- [Learning Kernel-Smoothed Machine Translation with Retrieved Examples](https://mlsanity.com/paper/2109.09991/) (2021)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)
- [Learning Sparse Prototypes for Text Generation](https://mlsanity.com/paper/2006.16336/) (2020)
- [Lexically Aware Semi-Supervised Learning for OCR Post-Correction](https://mlsanity.com/paper/2111.02622/) (2021)

## Built on by (most cited first, 30 of 60)

- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [In-Context Retrieval-Augmented Language Models](https://mlsanity.com/paper/2302.00083/) (2023)
- [From Persona to Personalization: A Survey on Role-Playing Language Agents](https://mlsanity.com/paper/2404.18231/) (2024)
- [Unlimiformer: Long-Range Transformers with Unlimited Length Input](https://mlsanity.com/paper/2305.01625/) (2023)
- [Test-Time Training on Nearest Neighbors for Large Language Models](https://mlsanity.com/paper/2305.18466/) (2023)
- [Learning to Filter Context for Retrieval-Augmented Generation](https://mlsanity.com/paper/2311.08377/) (2023)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Paths](https://mlsanity.com/paper/2502.14902/) (2025)
- [Instruction-tuned Language Models are Better Knowledge Learners](https://mlsanity.com/paper/2402.12847/) (2024)
- [Nonparametric Masked Language Modeling](https://mlsanity.com/paper/2212.01349/) (2022)
- [Decoupling Knowledge from Memorization: Retrieval-augmented Prompt Learning](https://mlsanity.com/paper/2205.14704/) (2022)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [How Do Large Language Models Capture the Ever-changing World Knowledge? A Review of Recent Advances](https://mlsanity.com/paper/2310.07343/) (2023)
- [Algorithmic progress in language models](https://mlsanity.com/paper/2403.05812/) (2024)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [Copy Is All You Need](https://mlsanity.com/paper/2307.06962/) (2023)
- [RAG and RAU: A Survey on Retrieval-Augmented Language Model in Natural Language Processing](https://mlsanity.com/paper/2404.19543/) (2024)
- [Goodtriever: Adaptive Toxicity Mitigation with Retrieval-augmented Models](https://mlsanity.com/paper/2310.07589/) (2023)
- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [LiMuon: Light and Fast Muon Optimizer for Large Models](https://mlsanity.com/paper/2509.14562/) (2025)
- [Chunk-based Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2205.12230/) (2022)
- [Accelerating Retrieval-Augmented Language Model Serving with Speculation](https://mlsanity.com/paper/2401.14021/) (2024)
- [You can't pick your neighbors, or can you? When and how to rely on retrieval in the kNN-LM](https://mlsanity.com/paper/2210.15859/) (2022)
- [What can we learn from Data Leakage and Unlearning for Law?](https://mlsanity.com/paper/2307.10476/) (2023)
- [kNN-Adapter: Efficient Domain Adaptation for Black-Box Language Models](https://mlsanity.com/paper/2302.10879/) (2023)
- [On the Vulnerability of Applying Retrieval-Augmented Generation within Knowledge-Intensive Application Domains](https://mlsanity.com/paper/2409.17275/) (2024)
- [Relation Extraction as Open-book Examination: Retrieval-enhanced Prompt Tuning](https://mlsanity.com/paper/2205.02355/) (2022)
- [Retrieval-Enhanced Machine Learning: Synthesis and Opportunities](https://mlsanity.com/paper/2407.12982/) (2024)
- [KNN-LM Does Not Improve Open-ended Text Generation](https://mlsanity.com/paper/2305.14625/) (2023)
- [Neuro-Symbolic AI: Explainability, Challenges, and Future Trends](https://mlsanity.com/paper/2411.04383/) (2024)

## Abstract (arXiv)

Retrieval-based language models (R-LM) model the probability of natural language text by combining a standard language model (LM) with examples retrieved from an external datastore at test time. While effective, a major bottleneck of using these models in practice is the computationally costly datastore search, which can be performed as frequently as every time step. In this paper, we present RetoMaton - retrieval automaton - which approximates the datastore search, based on (1) saving pointers between consecutive datastore entries, and (2) clustering of entries into "states". This effectively results in a weighted finite automaton built on top of the datastore, instead of representing the datastore as a flat list. The creation of the automaton is unsupervised, and a RetoMaton can be constructed from any text collection: either the original training corpus or from another domain. Traversing this automaton at inference time, in parallel to the LM inference, reduces its perplexity by up to 1.85, or alternatively saves up to 83% of the nearest neighbor searches over kNN-LM (Khandelwal et al., 2020) without hurting perplexity. Our code and trained models are available at https://github.com/neulab/retomaton .