Unverified 2026

Straight-Line Grammar Tokenizer

Implementation & benchmark of arXiv:2608.19228 — Assembly Theory and the Smallest Grammar Problem

Usefulness6/10

Difficulty6/10

Novelty6/10

Architecture Speedup Memory Scalability Tokenizer Transformer Attention Inference speedup Combinatorics Graph theory Optimization Information theory

Source paper: Assembly Theory and the Smallest Grammar Problem arXiv:2608.19228 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace repeated substrings in long sequences with nonterminal symbols from an acyclic straight-line grammar, then run the transformer on the compressed sequence. Unlike ordinary fixed tokenization, the compression objective explicitly minimizes the number of reusable binary productions, allowing repeated document-specific or corpus-level motifs to become single units. An expansion map lets the model recover token-level outputs for selected positions.

Formulas

$$\mathrm{ASI}(w)=\mathrm{SLP}(w).$$

$$A_p\to x\,y,\qquad p^* = \arg\max_{(x,y)} f_s(x,y),\qquad s\leftarrow \operatorname{Replace}_{\mathrm{nonoverlap}}(s,p^*\mapsto A_{p^*}).$$

$$h_{A_p}=W_2\,\sigma\!\left(W_1\,[h_x\|h_y]+b_1\right)+b_2,\qquad \ell_{\mathrm{attn}}=L\ll L_0=n.$$$

$$\mathrm{cost}_{\mathrm{attention}}(L)=O(L^2)\quad\text{instead of}\quad O(n^2).$$

Mathematical statement

A straight-line program (SLP) for a string w is an acyclic set of rules A -> B C, where A, B, and C are terminals or nonterminals and every nonterminal A has exactly one rule; the grammar generates one unique string. Its size SLP(w) is the number of production rules, and the paper states the exact identity ASI(w) = SLP(w), where ASI(w) is the assembly index. Use the constructive Re-Pair operation: for a current symbol sequence s, choose a digram p = (x,y) with maximal non-overlapping occurrence count f_s(x,y), introduce a fresh nonterminal A_p with rule A_p -> x y, and replace every selected non-overlapping occurrence xy by A_p. Iterate until no pair has sufficient reuse or a budget is reached. The resulting grammar has R rules and compressed sequence length L; its approximate compression ratio is (n-L)/n for original length n, while R is an explicit upper bound on the minimum grammar size. The neural adaptation assigns each nonterminal a representation by composing its children: h_{A_p} = W_2 sigma(W_1[h_x || h_y] + b_1) + b_2, where h_x and h_y are child representations, || denotes concatenation, sigma is a pointwise nonlinearity, and W_1, W_2, b_1, b_2 are learned parameters. Attention then operates on the compressed sequence of terminals and nonterminals rather than all n original symbols.

Implementation notes

1. Integration point: insert a grammar-compression tokenizer before the transformer embedding layer. The input is a token sequence w of length n. Build a corpus-level dictionary of frequent digrams offline, or run bounded document-level Re-Pair at inference time for long contexts. Keep both the compressed sequence s and an expansion table mapping every compressed symbol to either a terminal or an ordered pair of child symbols. 2. Pseudocode: initialize s = w and an empty rule set G; while |G| < R_max: count all non-overlapping digrams (x,y) in s; choose p* with largest count, breaking ties deterministically by earliest occurrence or lexicographic order; if count(p*) < m_min, stop; create A -> x y; replace selected occurrences by A; append A to G. Embed terminals normally. For each nonterminal, recursively compute h_A using the displayed composition formula, memoizing each node exactly once. Feed the resulting compressed sequence into the transformer. For token-level language-model loss, either expand logits only at requested positions or train an auxiliary expansion head that predicts the two children of each nonterminal. 3. Compute from the paper's mathematics: the grammar rules, rule count R, occurrence counts, compressed length L, and expansion DAG. Estimate empirically: validation perplexity, wall-clock latency, peak memory, and the fraction of positions requiring expansion. Use a fixed maximum grammar size and cache grammar construction for repeated documents. 4. First experiment: train a small 6-layer causal transformer on enwik8 or WikiText-103, comparing standard BPE against greedy Re-Pair compression at matched embedding vocabulary and matched training FLOPs. Evaluate ordinary text, duplicated passages, source code, and synthetic strings with controllable repetition. The expected signal is lower attention memory and faster tokens/sec at equal perplexity, especially when L/n is small; reject the method if perplexity rises substantially on non-repetitive text or grammar construction cancels the attention savings.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.