Elamur Research⌕
☰
home / papers / 2026 / Prefix Parsing is Just Parsing

Prefix Parsing is Just Parsing

Paper · 2026 · Clemente Pasti, Andreas Opedal, Timothy J. O'Donnell et al.

Summary

Prefix parsing asks whether the beginning of a string can still be completed into a sentence of a context-free grammar. In the weighted case it yields prefix probabilities, which are used in CFG language modeling, surprisal-based psycholinguistics, and grammar-constrained decoding from LLMs. Earlier prefix parsers needed intricate, algorithm-specific changes to CKY or Earley (e.g., Stolcke's method). The authors instead transform the grammar. From any weighted CFG over a commutative semiring, they build a "prefix grammar" whose language is exactly the original's weighted prefix language. Any standard parser can then serve as a prefix parser without modification, including subcubic, GPU, or optimized CPU parsers. Its dependence on input length is unchanged, and the overhead appears only as a constant-factor growth in grammar size, kept small by binarizing first. For next-token prediction, they parse a lattice that encodes all one-symbol extensions and apply reverse-mode algorithmic differentiation. This yields every next-token weight at a bounded constant cost instead of a vocabulary-sized factor. Experiments with Earley's algorithm on a large WSJ grammar confirm these predictions.

Key points

  • Evaluation setup: the grammar is WSJ 5000 from EarleyX (Luong et al., 2013), with 35,016 rules, 448 nonterminals and total size 116,667. Runtimes were measured over every prefix of 500 strings.
  • Scaling: the fitted complexity exponents are nearly identical for parsing (1.99), prefix parsing (2) and next-token computation (2.12).
  • Overhead: prefix parsing runs about 2.9× slower than ordinary parsing. This closely matches the ≈2.86× growth in grammar size after binarization plus the prefix transformation.
  • Next-token cost: computing the next-token weight vector costs only ≈1.2× a prefix parse. The theoretical bound (Theorem 3) is 4×, versus a naïve |Σ|-fold cost.
  • Practical comparison and code: Earley's algorithm on the prefix grammar performs comparably to Luong et al.'s Stolcke implementation. The code is released as genlm/prefix-acl-26. Experiments cover only CKY and Earley.

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

🎓McGill UniversityMontreal · Canada87 works · 11,027 citations🎓ETH ZurichZurich · Switzerland72 works · 5,176 citations🔬Canadian Institute for Advanced ResearchToronto · Canada28 works · 16,725 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

Cite

Cite as Clemente Pasti, Andreas Opedal, Timothy J. O'Donnell, Ryan Cotterell and Tim Vieira. 2026. Prefix Parsing is Just Parsing. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-short.25

@inproceedings{pasti2026prefix,
  title = {{Prefix Parsing is Just Parsing}},
  author = {Clemente Pasti, Andreas Opedal, Timothy J. O'Donnell, Ryan Cotterell and Tim Vieira},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-short.25},
  url = {https://doi.org/10.18653/v1/2026.acl-short.25}
}

References

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

  1. Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yua… — TensorFlow: A system for large-scale machine learning
  2. John Canny, David Hall, and Dan Klein. 2013. A multi-teraflop constituency parser using GPUs. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. find
  3. Zhiyi Chi. 1999. Statistical properties of probabilistic context-free grammars. Computational Linguistics, 25(1).
  4. John Cocke and Jacob T. Schwartz. 1970. Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University. find
  5. Manfred Droste, Werner Kuich, and Heiko Vogler. 2009. Handbook of Weighted Automata. Springer. find
  6. Aaron Joseph Dunlop. 2014. Efficient Latent-Variable Grammars: Learning and Inference. Ph.D. thesis, Oregon Health & Science University. find
  7. Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the Association for Computing Machinery, 13(2). find
  8. Jason Eisner. 2016. Inside-outside and forward-backward algorithms are just backprop (tutorial paper). In Proceedings of the Workshop on Structured Prediction for NLP. find
  9. Jason Eisner and John Blatz. 2007. Program transformations for optimization of parsing algorithms and other weighted logic programs. In Proceedings of the Conference on Formal Grammar. find
  10. Jason Eisner, Eric Goldlust, and Noah A. Smith. 2005. Compiling comp ling: Weighted dynamic programming and the Dyna language. In Proceedings of the Human Language Technology Conference and the Conference on Empirical Methods in Natural Language Processing. find
  11. J. K. Baker. 1979. Trainable grammars for speech recognition. In Speech Communication Papers for the Meeting of the Acoustical Society of America. find
  12. Javier Esparza, Stefan Kiefer, and Michael Luttenberger. 2007. An extension of Newton’s method to ω-continuous semirings. In Developments in Language Theory. find
  13. Yehoshua Bar-Hillel, Micha Asher Perles, and Eli Shamir. 1961. On formal properties of simple phrase-structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14. find
  14. Javier Esparza, Stefan Kiefer, and Michael Luttenberger. 2008. Newton’s method for ω-continuous semirings. In Automata, Languages and Programming. find
  15. Shalev Ben-David. 2022. Lecture 10: Closure properties for context-free languages (CS 360, Winter 2022). find
  16. Taylor L. Booth and Richard A. Thompson. 1973. Applying probability measures to abstract languages. IEEE Transactions on Computers, 22(5). find
  17. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018. JAX: Composable transformations of Python+NumPy programs. find
  18. Joshua Goodman. 1999. Semiring parsing. Computational Linguistics, 25(4). find
  19. Andreas Griewank and Andrea Walther. 2008. Evaluating Derivatives. SIAM. find
  20. John Hale. 2001. A probabilistic Earley parser as a psycholinguistic model. In Proceedings of the Meeting of the North American Chapter of the Association for Computational Linguistics on Language Technologies.
  21. Keith B. Hall. 2005. Best-first Word-lattice Parsing: Techniques for Integrated Syntactic Language Modeling. Ph.D. thesis, Brown University. find
  22. Laurent Hascoët and Valérie Pascual. 2013. The Tapenade automatic differentiation tool: Principles, model, and specification. Association for Computing Machinery Transactions on Mathematical Software, 39(3). find
  23. Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017. Automatic differentiation in PyTorch. In Proceedings of the NeurIPS Autodiff Workshop. find
  24. Frederick Jelinek and John D. Lafferty. 1991. Computation of the probability of initial substring generation by stochastic context-free grammars. Computational Linguistics, 17(3).
  25. Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Synchromesh: Reliable code generation from pre-trained language models. In Proceedings of the International Conference on Learning Representations. find
  26. Tadao Kasami. 1965. An efficient recognition and syntax algorithm for context-free languages. Technical Report AF-CRL-65-758, Air Force Cambridge Research Laboratory. find
  27. Jeffrey Kegler. 2023. Marpa, a practical general parser: the recognizer. find
  28. Alexander Rush. 2020. Torch-Struct: Deep structured prediction library. In Proceedings of the Annual Meeting of the Association for Computational Linguistics: System Demonstrations. find
  29. Martin Lange and Hans Leiß. 2009. To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica, 8. find
  30. Yves Schabes and Aravind K. Joshi. 1988. An Earley-type parsing algorithm for tree adjoining grammars. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. find
  31. João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O’Donnell. 2025. Syntactic and semantic control of large language models via sequen… find
  32. Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021. Constrained language models yield few-shot semantic parsers. In Proceedings of the Conference on Empirical Methods in Natural Languag… find
  33. Minh-Thang Luong, Michael C. Frank, and Mark Johnson. 2013. Parsing entire discourses as very long strings: Capturing topic continuity in grounded language learning. Transactions of the Association for Computational Linguistics, 1.
  34. Mark-Jan Nederhof. 1999. The computational complexity of the correct-prefix property for TAGs. Computational Linguistics, 25(3). find
  35. Miloš Stanojević and Laurent Sartran. 2023. SynJax: Structured probability distributions for JAX. In Proceedings of the Conference on Empirical Methods in Natural Language Processing: System Demonstrations. find
  36. Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2).
  37. Mark-Jan Nederhof and Giorgio Satta. 2008. Probabilistic Parsing, chapter 7. Springer. find
  38. Leslie G. Valiant. 1975. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10(2). find
  39. Franz Nowak and Ryan Cotterell. 2023. A fast algorithm for computing prefix probabilities. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. find
  40. Youngmin Yi, Chao-Yue Lai, Slav Petrov, and Kurt Keutzer. 2011. Efficient parallel CKY parsing on GPUs. In Proceedings of the International Conference on Parsing Technologies. find
  41. Andreas Opedal, Anej Svete, Alexandra Butoi, Franz Nowak, and Ryan Cotterell. 2022. Lecture 7: Grammar transformations. find
  42. Daniel H. Younger. 1967. Recognition and parsing of context-free languages in time n 3 . Information and Control, 10(2). find
  43. Andreas Opedal, Ran Zmigrod, Tim Vieira, Ryan Cotterell, and Jason Eisner. 2023. Efficient semiring-weighted Earley parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. find
  44. Clemente Pasti, Andreas Opedal, Tiago Pimentel, Tim Vieira, Jason Eisner, and Ryan Cotterell. 2023. On the intersection of context-free and regular languages. In Proceedings of the Conference of the European Chapter of the Association for Computational Linguistics. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/pasti-2026-prefix-parsing-is-just-parsing/