# Local Grammar-Based Coding Revisited

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 76 references that are in the map.
- First posted on arXiv 27 Sep 2022.

## Builds on (most cited first, 7 of 7)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Scaling Laws for Transfer](https://mlsanity.com/paper/2102.01293/) (2021)
- [Calibration, Entropy Rates, and Memory in Language Models](https://mlsanity.com/paper/1906.05664/) (2019)

## Abstract (arXiv)

In the setting of minimal local grammar-based coding, the input string is represented as a grammar with the minimal output length defined via simple symbol-by-symbol encoding. This paper discusses four contributions to this field. First, we invoke a simple harmonic bound on ranked probabilities, which reminds Zipf's law and simplifies universality proofs for minimal local grammar-based codes. Second, we refine known bounds on the vocabulary size, showing its partial power-law equivalence with mutual information and redundancy. These bounds are relevant for linking Zipf's law with the neural scaling law for large language models. Third, we develop a framework for universal codes with fixed infinite vocabularies, recasting universal coding as matching ranked patterns that are independent of empirical data. Finally, we analyze grammar-based codes with finite vocabularies being empirical rank lists, proving that that such codes are also universal. These results extend foundations of universal grammar-based coding and reaffirm previously stated connections to power laws for human language and language models.