Research shelf / AI & machine learning / USG
Written Updated
Statistical language models that compose, and prove that they do
Classical statistical generation died of one problem. For vocabulary V and context length n the state space grows as Vⁿ, so n > 5 was infeasible and the field ceded the ground to neural models. The Universal Statistical Generator replaces the explicit state table with a fixed hash table, which trades exactness for a bounded memory footprint and buys a thousand-token context.
Experiments were run and the numbers are reported here.
Generators shown to form a mathematical category under composition, with hash-based context compression that breaks the state-explosion ceiling that capped n-gram and HMM methods at three to five tokens.
The framework synthesises three established bodies of mathematics: category theory for composition, Lévy process theory for the generative dynamics, and information-theoretic filtration for parameter selection. The central formal contribution is a proof that statistical generators form a valid category under a naturally defined composition operator — so a complex generator can be assembled from verified simple ones and inherit their guarantees.
The engineering contribution is hash-based context compression. Arbitrary-length context histories are mapped through SHA-256 into a fixed table of M = 2³² entries, making memory O(M) rather than O(Vⁿ) — independent of both vocabulary and context length. Effective context goes from 3–5 tokens to 1,000+, a 200× extension, at roughly 4 GB.
Parameter reduction runs through a two-stage information-theoretic pipeline: Minimum Description Length scoring followed by Marchenko–Pastur spectral thresholding, which separates signal eigenvalues from the random-matrix bulk. The paper reports the result as provably noise-optimal under its stated assumptions, and validates every theoretical claim computationally against a Python reference implementation.
Every number, and what stands behind it
A claim is only worth the evidence attached to it. Each row below carries its basis: measured on the author’s own hardware, derived from the construction, measured on synthetic data, projected from literature, or simply cited.
| Claim | Figure | Basis | Context |
|---|---|---|---|
| Context length vs classical methods | 1,000+ tokens (200×) | Derived | Property of the hash construction, not a benchmark |
| Memory footprint | O(M), M = 2³² (~4 GB) | Derived | Independent of vocabulary size and context length |
| Perplexity vs state-of-the-art neural | within ~10% | Measured | Held-out comparison, author-run |
| Convergence rate | O(1/√n) | Derived | From the Lévy-process formulation |
| Training time | O(N) | Derived | Linear in corpus size |
| Composability | generators form a category | Derived | Proved for the stated composition operator |
| Classical ceiling being replaced | n = 3–5 tokens | Cited | n-gram, HMM and PPM literature, 1980s–2000s |
Measured — author-run experiment on the stated setup. Synthetic — measured, but on synthetic rather than real data. Derived — follows from the stated construction or proof. Projected — paper-stated projection, not an author-run benchmark. Cited — taken from external literature.
How it works
- Categorical composition. Objects are generators, morphisms are composition operations; associativity and identity are proved, so modular assembly is sound.
- Lévy-process dynamics. Generation is modelled as an increment process, which supplies the O(1/√n) convergence rate.
- SHA-256 context hashing. Arbitrary history → fixed table index. Collisions are the price; bounded memory is the purchase.
- MDL + Marchenko–Pastur filtration. Two-stage parameter reduction: description-length scoring, then spectral thresholding against the random-matrix bulk.
What it does not do
Taken from the folder’s own README. Nothing here has been softened.
- Hash collisions merge distinct contexts. The paper bounds the effect but the mapping is lossy by construction.
- "Within 10% of neural perplexity" is author-run on the author’s corpus. No third-party benchmark.
- The determinism and composability guarantees are real; they are also the reason the model cannot do what a large neural model does.
- The paper itself names the cases where classical methods still win: very constrained environments, structured parsing, maximum-compression applications.
- M = 2³² is a design constant. Behaviour at other table sizes is not characterised.
Free under AGPL-3.0+ for almost everyone
Personal use, charities, education and organisations under AUD 50,000 a year pay nothing. A tiered commercial licence covers everyone else.