Local Grammar-Based Coding Revisited
This work provides incremental theoretical extensions to universal grammar-based coding, relevant for understanding power laws in human language and language models.
The paper tackles the problem of minimal local grammar-based coding by developing theoretical bounds and frameworks, resulting in simplified universality proofs, refined vocabulary size bounds linked to power laws, and universal codes with fixed or finite vocabularies.
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.