mlsanityData to 14 Oct 2026

Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval

arXiv 2201.12431 ↗First posted 28 Jan 2022cs.CL cs.LGcited by 60

Not on the map. Why?

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 .

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

33 of 47 references.

References · 33

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,824
  3. 2016Pointer Sentinel Mixture Modelscited by 3,096
  4. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,918
  5. 2017Billion-scale similarity search with GPUscited by 2,497
  6. 2020REALM: Retrieval-Augmented Language Model Pre-Trainingcited by 2,141
  7. 2021Improving language models by retrieving from trillions of tokenscited by 1,293
  8. 2019Generalization through Memorization: Nearest Neighbor Language Modelscited by 800
  9. 2021Learning To Retrieve Prompts for In-Context Learningcited by 648
  10. 2017Six Challenges for Neural Machine Translationcited by 335
  11. 2018Adaptive Input Representations for Neural Language Modelingcited by 226
  12. 2020Nearest Neighbor Machine Translationcited by 209
21 more
  1. 2019Facebook FAIR's WMT19 News Translation Task Submissioncited by 179
  2. 2020Unsupervised Domain Clusters in Pretrained Language Modelscited by 160
  3. 2021Efficient Nearest Neighbor Language Modelscited by 93
  4. 2017Generating Sentences by Editing Prototypescited by 88
  5. 2021Adaptive Semiparametric Language Modelscited by 83
  6. 2018A Retrieve-and-Edit Framework for Predicting Structured Outputscited by 73
  7. 2016Efficient softmax approximation for GPUscited by 67
  8. 2017Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamplescited by 66
  9. 2018Guiding Neural Machine Translation with Retrieved Translation Piecescited by 63
  10. 2021Learning to Retrieve Passages without Supervisioncited by 46
  11. 2018Retrieval-Based Neural Code Generationcited by 41
  12. 2017Unbounded cache model for online language modeling with open vocabularycited by 37
  13. 2021GNN-LM: Language Modeling based on Global Contexts via GNNcited by 27
  14. 2021Learning Kernel-Smoothed Machine Translation with Retrieved Examplescited by 25
  15. 2019Learning Deterministic Weighted Automata with Queries and Counterexamplescited by 22
  16. 2018Rational Recurrencescited by 18
  17. 2020Learning Sparse Prototypes for Text Generationcited by 15
  18. 2021Lexically Aware Semi-Supervised Learning for OCR Post-Correctioncited by 12
  19. 2016Generalizing and Hybridizing Count-based and Neural Language Modelscited by 11
  20. 2018SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machinescited by 8
  21. 2021Capturing Structural Locality in Non-parametric Language Modelscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 9; 2023: 21; 2024: 15; 2025: 11; 2026: 4.

60 papers.

Sort:

By area:

  1. 2023Retrieval-Augmented Generation for Large Language Models: A Surveycited by 2,212
  2. 2023In-Context Retrieval-Augmented Language Modelscited by 702
  3. 2024From Persona to Personalization: A Survey on Role-Playing Language Agentscited by 212
  4. 2023Unlimiformer: Long-Range Transformers with Unlimited Length Inputcited by 128
  5. 2023Test-Time Training on Nearest Neighbors for Large Language Modelscited by 88
  6. 2023Learning to Filter Context for Retrieval-Augmented Generationcited by 83
  7. 2022Efficient Methods for Natural Language Processing: A Surveycited by 78
  8. 2025PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Pathscited by 61
  9. 2024Instruction-tuned Language Models are Better Knowledge Learnerscited by 55
  10. 2022Nonparametric Masked Language Modelingcited by 40
  11. 2022Decoupling Knowledge from Memorization: Retrieval-augmented Prompt Learningcited by 36
  12. 2023Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databasescited by 35
38 more
  1. 2023How Do Large Language Models Capture the Ever-changing World Knowledge? A Review of Recent Advancescited by 33
  2. 2024Algorithmic progress in language modelscited by 31
  3. 2023Why do Nearest Neighbor Language Models Work?cited by 29
  4. 2023Copy Is All You Needcited by 27
  5. 2024RAG and RAU: A Survey on Retrieval-Augmented Language Model in Natural Language Processingcited by 25
  6. 2023Goodtriever: Adaptive Toxicity Mitigation with Retrieval-augmented Modelscited by 23
  7. 2023Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Modelscited by 23
  8. 2025LiMuon: Light and Fast Muon Optimizer for Large Modelscited by 22
  9. 2022Chunk-based Nearest Neighbor Machine Translationcited by 21
  10. 2024Accelerating Retrieval-Augmented Language Model Serving with Speculationcited by 20
  11. 2022You can't pick your neighbors, or can you? When and how to rely on retrieval in the kNN-LMcited by 18
  12. 2023What can we learn from Data Leakage and Unlearning for Law?cited by 15
  13. 2023kNN-Adapter: Efficient Domain Adaptation for Black-Box Language Modelscited by 14
  14. 2024On the Vulnerability of Applying Retrieval-Augmented Generation within Knowledge-Intensive Application Domainscited by 14
  15. 2022Relation Extraction as Open-book Examination: Retrieval-enhanced Prompt Tuningcited by 13
  16. 2024Retrieval-Enhanced Machine Learning: Synthesis and Opportunitiescited by 11
  17. 2023KNN-LM Does Not Improve Open-ended Text Generationcited by 10
  18. 2024Neuro-Symbolic AI: Explainability, Challenges, and Future Trendscited by 10
  19. 2024Vocabulary-Defined Semantics: Latent Space Clustering for Improving In-Context Learningcited by 8
  20. 2024Great Memory, Shallow Reasoning: Limits of kNN-LMscited by 8
  21. 2025Bring Your Own Knowledge: A Survey of Methods for LLM Knowledge Expansioncited by 8
  22. 2023Has It All Been Solved? Open NLP Research Questions Not Solved by Large Language Modelscited by 7
  23. 2025On the Predictive Power of Representation Dispersion in Language Modelscited by 7
  24. 2026Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guaranteescited by 7
  25. 2022Schema-aware Reference as Prompt Improves Data-Efficient Knowledge Graph Constructioncited by 6
  26. 2024Generation with Dynamic Vocabularycited by 6
  27. 2022EUREKA: EUphemism Recognition Enhanced through Knn-based methods and Augmentationcited by 5
  28. 2023LUNA: A Model-Based Universal Analysis Framework for Large Language Modelscited by 4
  29. 2024LIAR: Leveraging Inference Time Alignment (Best-of-N) to Jailbreak LLMs in Secondscited by 4
  30. 2024Vector Retrieval with Similarity and Diversity: How Hard Is It?cited by 3
  31. 2024Enhancing Conflict Resolution in Language Models via Abstract Argumentationcited by 3
  32. 2025Neuroplasticity and Corruption in Model Mechanisms: A Case Study Of Indirect Object Identificationcited by 3
  33. 2022Nearest Neighbor Language Models for Stylistic Controllable Generationcited by 2
  34. 2023BRENT: Bidirectional Retrieval Enhanced Norwegian Transformercited by 2
  35. 2025From Retrieval to Generation: Comparing Different Approachescited by 2
  36. 2023Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcscited by 1
  37. 2023N-Gram Nearest Neighbor Machine Translationcited by 1
  38. 2023knn-seq: Efficient, Extensible kNN-MT Frameworkcited by 1

50 most cited of 60 All 60 (JSON)