CoChat
Sign Up
PreprintCited by 32Topic ModelingNatural Language Processing TechniquesInformation Retrieval and Search Behavior

Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval

Open access
Alon, Uri, Xu, Frank F., He, Junxian, Sengupta, Sudipta, Roth, Dan, Neubig, Graham·2022·arXiv
DOI 10.48550/arxiv.2201.12431arXiv 2201.12431
Open this paper in CoChat — free accountOpen PDF

Abstract

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 $k$NN-LM (Khandelwal et al., 2020) without hurting perplexity. Our code and trained models are available at https://github.com/neulab/retomaton .

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2201.12431

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Scaling approaches for alleviating the kNN-LM storage issue to large corpora remains an open challenge.

    “Although numerous approaches have been suggested for alleviating this issue (He et al., 2021;Alon et al., 2022), scaling any of them to large corpora remains an open challenge.”

    From In-Context Retrieval-Augmented Language Models (2023) · cites this paper as Alon et al., 2022

    The Introduction (p. 1) and Abstract (p. 1) identify costly, frequent datastore searches as the problem RETOMATON addresses, not datastore storage. The Experimental Setup (p. 4) describes datastores of 103 million and 19 million entries, but neither it nor the passages on memory and larger datastores in Appendix C (p. 12) says that scaling storage-alleviation approaches to large corpora remains an open challenge. Searched for storage, memory, and scaling limitations. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 40

  1. Aharoni, R. and Goldberg, Y. Unsupervised domain clusters in pretrained language models. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics , pp. 7747-7763, 2020.
  2. Baevski, A. and Auli, M. Adaptive input representations for neural language modeling. In International Conference on Learning Representations , 2019.
  3. Barrault, L., Bojar, O., Costa-jussà, M. R., Federmann, C., Fishel, M., Graham, Y., Haddow, B., Huck, M., Koehn, P., Malmasi, S., Monz, C., Müller, M., Pal, S., Post, M., and Zampieri, M. Findings of the 2019 conference on machine translation (WMT19). In Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1) , pp. 1-61, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10.18653/v1/W19-5301. URL https://aclanthology.org/W19-5301 . · DOI
  4. Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford, E., Millican, K., Driessche, G. v. d., Lespiau, J.-B., Damoc, B., Clark, A., et al. Improving language models by retrieving from trillions of tokens. arXiv preprint arXiv:2112.04426 , 2021. · arXiv
  5. Giles, C. L., Miller, C. B., Chen, D., Chen, H.-H., Sun, G.-Z., and Lee, Y.-C. Learning and extracting finite state automata with second-order recurrent neural networks. Neural Computation , 4(3):393-405, 1992.
  6. Grave, E., Cisse, M. M., and Joulin, A. Unbounded cache model for online language modeling with open vocabulary. Advances in neural information processing systems , 30, 2017.
  7. Gu, J., Wang, Y., Cho, K., and Li, V. O. Search engine guided neural machine translation. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 32, 2018.
  8. Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., and Kumar, S. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning , pp. 3887-3896. PMLR, 2020.
  9. Guu, K., Hashimoto, T. B., Oren, Y., and Liang, P. Generating sentences by editing prototypes. Transactions of the Association for Computational Linguistics , 6:437-450, 2018.
  10. Guu, K., Lee, K., Tung, Z., Pasupat, P., and Chang, M.W. REALM: Retrieval-augmented language model pretraining. arXiv preprint arXiv:2002.08909 , 2020. · arXiv
  11. Hashimoto, T. B., Guu, K., Oren, Y., and Liang, P. A retrieve-and-edit framework for predicting structured outputs. In Proceedings of the 32nd International Conference on Neural Information Processing Systems , pp. 10073-10083, 2018.
  12. Hayati, S. A., Olivier, R., Avvaru, P., Yin, P., Tomasic, A., and Neubig, G. Retrieval-based neural code generation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing , pp. 925-930, 2018.
  13. He, J., Berg-Kirkpatrick, T., and Neubig, G. Learning sparse prototypes for text generation. Advances in Neural Information Processing Systems , 33, 2020.
  14. He, J., Neubig, G., and Berg-Kirkpatrick, T. Efficient nearest neighbor language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing , pp. 5703-5714, 2021.
  15. Jiang, Q., Wang, M., Cao, J., Cheng, S., Huang, S., and Li, L. Learning kernel-smoothed machine translation with retrieved examples. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing , pp. 7280-7290, 2021.
  16. Johnson, J., Douze, M., and Jégou, H. Billion-scale similarity search with gpus. IEEE Transactions on Big Data , 2019.
  17. Joulin, A., Cissé, M., Grangier, D., Jégou, H., et al. Efficient softmax approximation for gpus. In International conference on machine learning , pp. 1302-1310. PMLR, 2017.
  18. Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pp. 6769-6781, 2020.
  19. Khandelwal, U., Levy, O., Jurafsky, D., Zettlemoyer, L., and Lewis, M. Generalization through memorization: Nearest neighbor language models. In International Conference on Learning Representations , 2020. URL https:// openreview.net/forum?id=HklBjCEKvH .
  20. Khandelwal, U., Fan, A., Jurafsky, D., Zettlemoyer, L., and Lewis, M. Nearest neighbor machine translation. In International Conference on Learning Representations , 2021. URL https://openreview.net/forum? id=7wCBOfJ8hJM .
  21. Koehn, P. and Knowles, R. Six challenges for neural machine translation. In Proceedings of the First Workshop on Neural Machine Translation , pp. 28-39, 2017.
  22. Lin, C.-C., Zhu, H., Gormley, M. R., and Eisner, J. Neural finite-state transducers: Beyond rational relations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) , pp. 272-283, 2019.
  23. Meng, Y., Zong, S., Li, X., Sun, X., Zhang, T., Wu, F., and Li, J. GNN-LM: Language modeling based on global contexts via GNN. In International Conference on Learning Representations , 2022. URL https: //openreview.net/forum?id=BS49l-B5Bql .
  24. Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. In International Conference on Learning Representations , 2017.
  25. Neubig, G. and Dyer, C. Generalizing and hybridizing count-based and neural language models. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing , pp. 1163-1172, 2016.
  26. Ng, N., Yee, K., Baevski, A., Ott, M., Auli, M., and Edunov, S. Facebook fair's wmt19 news translation task submission. In Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1) , pp. 314-319, 2019.
  27. Omlin, C. W. and Giles, C. L. Extraction of rules from discrete-time recurrent neural networks. Neural networks , 9(1):41-52, 1996.
  28. Peng, H., Schwartz, R., Thomson, S., and Smith, N. A. Rational recurrences. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing , pp. 1203-1214, 2018.
  29. Ram, O., Shachaf, G., Levy, O., Berant, J., and Globerson, A. Learning to retrieve passages without supervision. arXiv preprint arXiv:2112.07708 , 2021. · arXiv
  30. Rastogi, P., Cotterell, R., and Eisner, J. Weighting finitestate transductions with neural context. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies , pp. 623-633, 2016.
  31. Rijhwani, S., Rosenblum, D., Anastasopoulos, A., and Neubig, G. Lexically-aware semi-supervised learning for ocr post-correction. Transactions of the Association for Computational Linguistics , 9:1285-1302, 2021.
  32. Rubin, O., Herzig, J., and Berant, J. Learning to retrieve prompts for in-context learning. arXiv preprint arXiv:2112.08633 , 2021. · arXiv
  33. Schwartz, R., Thomson, S., and Smith, N. A. Bridging cnns, rnns, and weighted finite-state machines. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pp. 295-305, 2018.
  34. Sennrich, R., Haddow, B., and Birch, A. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pp. 1715-1725, 2016.
  35. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. In Advances in Neural Information Processing Systems , pp. 6000-6010, 2017.
  36. Weiss, G., Goldberg, Y., and Yahav, E. Extracting automata from recurrent neural networks using queries and counterexamples. In International Conference on Machine Learning , pp. 5247-5256. PMLR, 2018.
  37. Weiss, G., Goldberg, Y., and Yahav, E. Learning deterministic weighted automata with queries and counterexamples. Advances in Neural Information Processing Systems , 32: 8560-8571, 2019.
  38. Xu, F. F., He, J., Neubig, G., and Hellendoorn, V. J. Capturing structural locality in non-parametric language models. arXiv preprint arXiv:2110.02870 , 2021. · arXiv
  39. Yogatama, D., de Masson d'Autume, C., and Kong, L. Adaptive semiparametric language models. Transactions of the Association for Computational Linguistics , 9:362-373, 2021.
  40. Zhang, J., Utiyama, M., Sumita, E., Neubig, G., and Nakamura, S. Guiding neural machine translation with retrieved translation pieces. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) , pp. 1325-1335, 2018.

Cited by

Sorted by citations

Authors
Alon, U., Xu, F. F., He, J., Sengupta, S., Roth, D., & Neubig, G.
Affiliations
  • Carnegie Mellon University (US)
  • Amazon (United States) (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2022
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2201.12431
arXiv
2201.12431
OpenAlex
W4221155916
Cited by
32
References
0
Citations by year
2026: 1 · 2025: 3 · 2024: 7 · 2023: 13 · 2022: 8
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • Rare & Special e-Zone (The Hong Kong University of Science and Technology) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
Keywords
unsupervised clustering, perplexity reduction

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review