N-gram Language Models

Phony uses N-gram Markov chains for generating realistic, locale-specific text. This document describes the model architecture, training process, the .ngram file format, and the generation algorithms — all verified against the built engine (ngram-core).

Implementation status (ngram-core)

Built: char/word/text training (single-order 2–5), the streaming/parallel ModelBuilder, the portable binary .ngram format v3 (PHNYNG03), all generation modes (word/words/sentence/sentences/text/paragraph/poem/acrostic/real_word), constraints (starts_with/ends_with/contains/min_length/max_length/exclude_originals), min_count pruning, the verbatim-run privacy guard, sampling policy (temperature/top_k/top_p/no_repeat), unique and keyed generation, and sentence/paragraph positional openings.

Roadmap (not built): CSV/JSON training inputs (--column/--path), per-locale automatic n-gram-order defaults, multi-level prefix-shortening fallback, and an uncompressed mmap-able format variant.

Core Concepts

What is a Character-Level N-gram?

Unlike word-level N-grams (which model word sequences), Phony's default char models use character-level N-grams to model character sequences within words:

Word: "sphinx" (n=4)
─────────────────────────
s p h i n x
└───┘         → "sphi" (first n-gram)
  └───┘       → "phin" (middle n-gram)
    └───┘     → "hinx" (last n-gram)

This approach enables:

• Infinite vocabulary: Generate words never seen in training
• Locale characteristics: Model learns "Turkish-sounding" or "English-sounding" patterns
• Compact storage: Model file much smaller than word lists

Markov Chain Graph

Each N-gram forms a node in a directed graph with weighted edges. The key design point: every node keeps two distributions.

┌─────────────────────────────────────────────────────────────────────────┐
│                    MARKOV CHAIN STRUCTURE                                │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  "sphi" ─────(w:4)────▶ "phin" ─────(w:4)────▶ "hinx"                   │
│    │                      │                      │                       │
│    ▼                      ▼                      ▼                       │
│  children              children              last_children               │
│  (mid-word)            (mid-word)            (word-end)                  │
│                                                                          │
│  • children       → transitions that continue a word                    │
│  • last_children  → transitions that END a word                         │
│                                                                          │
│  Generation samples a target length from the learned word-length         │
│  distribution and, on reaching it, terminates via a real word-ending     │
│  n-gram — natural lengths and endings without rejection sampling.        │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

---

The .ngram File Format (binary v3)

Normative reference

The byte-level layout is specified in phony-core/FORMAT.md (in the engine repository) — that file is the cross-runtime contract; this section summarizes it.

A trained model is a portable binary encoding, gzipped, with an 8-byte ASCII magic PHNYNG03 outside the gzip stream (so a reader can dispatch without decompressing). It is not JSON: every field is read with plain integer reads — no schema library, no reflection. A reader rejects anything not starting with the magic (the project is pre-release; there is no legacy format).

Encoding conventions

Notation	Meaning
uv	unsigned LEB128 varint (7 bits/byte, high bit = continue) — most ids and weights fit in one byte
iv	signed varint via zig-zag ((n << 1) ^ (n >> 31), then uv) — used for position keys like -1
u8	one raw byte (only token_type)
str	uv byte length, then UTF-8 bytes
dist	uv count, then { id: uv, weight: uv } records in ascending id order
lendist	uv count, then { length: uv, weight: uv } records

Layout

magic:           8 bytes = "PHNYNG03"   (ASCII, uncompressed)
body:            gzip stream of:

  order:           uv
  token_type:      u8      (0 = char, 1 = word)
  position_depth:  uv
  config:          str     (tokenizer config as JSON — provenance only)
  metadata:        str     (metadata as JSON)

  vocab_count:     uv
  vocab:           vocab_count × str   (sorted lexicographically; index = id)

  first:           dist                (n-grams that start a word)

  # graph, one record per id, in id order (id is implicit):
  elements:        vocab_count × { children: dist, last_children: dist }

  positions:            count + (key: iv, d: dist) …   (sentence positions)
  paragraph_positions:  count + (key: iv, d: dist) …

  word_lengths:      lendist
  sentence_lengths:  lendist
  paragraph_lengths: lendist

  originals_count:   uv               (number of UNIQUE training items)
  originals:         originals_count × { item: str, count: uv }

Why it looks like this

• Interned vocab, sorted. Every n-gram string is stored once in a lexicographically sorted vocabulary; everywhere else it is referenced by u32 id. Sorting is normative: ids follow vocab order and every dist lists edges in ascending id, so cumulative-weight sampling is identical in every runtime.
• CSR graph in memory. from_bytes builds the same layout directly: a sorted vocab, compressed-sparse-row arrays (child_off/child_id/child_cum and the last_* twins), and id-based opener pools — no intermediate string-keyed structures. This also makes a future uncompressed, mmap-zero-copy variant possible (roadmap).
• Delta-encoded cumulative weights. Distributions store per-edge weight deltas as varints; a weight of 1 (the overwhelming common case) is one byte.
• Deduplicated originals. Training items are stored as unique item + count — real_word samples by count, preserving the raw frequency distribution, at a fraction of the size.
• Why gzip. The vocab and originals are text and compress well.

Determinism

vocab is sorted, ids follow that order, and every dist lists edges in ascending id. Combined with the portable SplitMix64 PRNG and inverse-CDF sampling over cumulative weights (binary search via partition point), any runtime reproduces identical output from a seed.

---

Positional N-grams

The engine tracks which N-grams open words by sentence position (and which open sentences by paragraph position).

┌─────────────────────────────────────────────────────────────────────────┐
│                    POSITIONAL N-GRAM CONCEPT                             │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  Sentence: "The quick brown fox jumps"                                  │
│             ▲   ▲     ▲     ▲   ▲                                       │
│           pos:1 pos:2  ...  pos:-2 pos:-1                               │
│                                                                          │
│  positions[1]  → N-grams that START sentences                           │
│  positions[-1] → N-grams that END sentences                             │
│                                                                          │
│  In Turkish: "bir" commonly starts sentences                            │
│  In English: "The" commonly starts sentences                            │
│                                                                          │
│  The same idea repeats one level up: paragraph_positions[1] holds       │
│  n-grams that open a paragraph's FIRST sentence, etc.                   │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

With position_depth = 3 (the built-in default for text training): positions 1, 2, 3 and -3, -2, -1 are tracked; middle words fall back to the generic first pool. word/phrase training uses depth 0 (no positions). The depth is stored in the model; a CLI flag to override it is roadmap.

---

Tokenization

How input splits into tokens before counting. The tokenizer config is stored in the model for provenance only — tokenization runs at training time.

{
  "word_separator": "\\s+",
  "sentence_separator": "[.!?:;\\n]+",
  "paragraph_separator": "\\n\\s*\\n",
  "word_filter": "[^0-9A-Za-zçğıöşüÇĞİÖŞÜ]+",
  "min_word_length": 1,
  "to_lowercase": false,
  "locale": "tr_TR"
}

Field	Description	Default
word_separator	Regex to split words	\s+
sentence_separator	Regex to split sentences	[.!?:;\n]+
paragraph_separator	Regex to split paragraphs	\n\s*\n
word_filter	Regex of characters to drop from each word	none
min_word_length	Drop words shorter than this	1
to_lowercase	Normalize case before training	false
locale	Locale tag stored in the model	none

Presets (built)

Preset	Filter	Selected by
Turkish	keep 0-9A-Za-zçğıöşüÇĞİÖŞÜ	--locale tr*
Alphabetical	keep 0-9A-Za-z	explicit
Default	no filter	everything else

Additional per-language presets (French, Japanese/CJK ranges, \p{L} classes) are roadmap — today a custom --word-filter REGEX covers them.

---

Token Type: Character vs Word

Terminology Note: Don't confuse token_type (how the model was trained) with generation.mode (how output is produced). They are independent:

• token_type: set at training time; determines what a "token" is (character or word).
• generation.mode: set at generation time in PGDL; determines output shape (word, sentence, text, …).

Character Token Type (default)

N-grams are character sequences; the model learns character-by-character patterns.

Training: ["sphinx", "quarter", "quick"]
N-grams:  "sphi" → "phin" → "hinx"
          "quar" → "uart" → "arte" → "rter"
          "quic" → "uick"

Output: "sphinter" (new word, never in training!)

Use for: names, usernames, made-up words. (phony train -t char, and also the basis of -t text prose models.)

Word Token Type

N-grams are word sequences; the model learns word-by-word patterns for multi-word outputs.

Training corpus (company names):
  "Yılmaz Holding A.Ş."
  "Koç Holding A.Ş."
  "Yılmaz Gıda Sanayi"
  "Koç Otomotiv Sanayi"

Word bigrams (n=2):
  ["Yılmaz", "Holding"] → ["Holding", "A.Ş."]
  ["Koç", "Otomotiv"] → ["Otomotiv", "Sanayi"]

Generated outputs:
  "Yılmaz Otomotiv Sanayi"  (new combination!)
  "Koç Gıda Sanayi"         (new combination!)

Use for: company names, product names, multi-word phrases. (phony train -t word.)

Text Token Type (CLI)

phony train -t text builds a prose model: char n-grams plus the full learned length hierarchy (word → sentence → paragraph lengths) and the sentence/paragraph positional opener pools. This is what powers sentence/text/paragraph generation.

---

Design Rationale

Why Single N-gram Order?

Phony uses a single N-gram order (e.g., only 4-grams) rather than multi-order approaches. This was a deliberate design choice after evaluating academic smoothing methods.

┌─────────────────────────────────────────────────────────────────────────┐
│                    THE LOREM IPSUM PRINCIPLE                             │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  Phony generates FAKE data that LOOKS LIKE real data.                   │
│  It doesn't need to BE real data.                                       │
│                                                                          │
│  Priority 1: Speed (generate millions of records fast)                  │
│  Priority 2: Plausibility (output looks locale-appropriate)             │
│  Priority 3: NOT coverage (we don't need every possible word)           │
│                                                                          │
│  Academic smoothing methods optimize for coverage.                       │
│  We optimize for speed and plausibility.                                │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

Evaluated But Rejected

Method	What It Does	Why Not For Phony
Kneser-Ney Smoothing	Redistributes probability mass using continuation counts	Complexity overhead, diminishing returns for fake data
Modified Kneser-Ney	Three discount parameters (D₁, D₂, D₃₊)	Even more complexity, marginal quality gain
Interpolation	λ-weighted mix of all n-gram orders	Requires storing all orders (2x-4x model size)
Stupid Backoff	Fixed discount (0.4) without normalization	Still requires multi-order storage

References:

• Chen & Goodman (1999). "An Empirical Study of Smoothing Techniques for Language Modeling"
• Kneser & Ney (1995). "Improved backing-off for M-gram language modeling"

Our Approach: KISS

Single n-gram order + graph-native word endings
────────────────────────────────────────────────
✓ One model file (not separate files per order)
✓ Smaller memory footprint
✓ Faster generation (no interpolation math)
✓ Good enough for fake data

Locale-Based N-gram Defaults (target design)

Different languages have different sweet-spot orders. Today the CLI default is order 3 for every locale (-n/--ngram-order, range 2–5); automatic per-locale defaults are target design. The table is authoring guidance:

Locale	Suggested N	Rationale
en_*	3	Shorter words, common patterns
tr_TR	4	Agglutinative, longer morphemes
de_DE	4	Compound words, longer stems
ja_JP	2	Character-based (hiragana/katakana)
zh_*	2	Character-based (hanzi)
ar_*	3	Root-pattern morphology

---

Sparse Data & Fallback (as built)

When a starts_with prefix has no matching opener n-gram:

• The opener pools support prefix-filtered sampling: a uniform pick among the pool's n-grams whose string starts with the requested prefix (the sorted vocab makes the strings available for the match). Prefixes up to the n-gram order work; longer prefixes constrain the walk's first node only.
• If nothing matches: word mode retries its bounded loop (up to 64 attempts) and returns its best effort; inside sentence/paragraph generation the first word falls back to an unconstrained word rather than being dropped.

A multi-level prefix-shortening fallback (xyz* → xy* → x*) and a configurable fallback: none | prefix mode were considered and are not built — the bounded-retry + unconstrained-fallback behaviour above is the whole story today.

---

Generation Modes (engine API)

All modes are driven by an explicit SplitMix64 seed, so output is deterministic.

Engine call	Output	Key parameters
word(rng, constraints)	one word	constraints (below)
words(rng, count, constraints)	N words	count
real_word(rng, prefix?)	a real training item (frequency-weighted) or null	prefix
sentence(rng, num_words?, punctuation, starts_with?)	one sentence, capitalized + punctuated	num_words defaults to the learned sentence-length distribution
sentences(rng, count, punctuation, starts_with?)	N sentences joined	count
text(rng, max_chars, suffix, starts_with?)	sentences until max_chars, truncated	max_chars, suffix
paragraph(rng, num_sentences?, starts_with?)	one paragraph	num_sentences defaults to the learned paragraph-length distribution
poem(rng, verses, stanza_length, max_words)	verse lines (+ blank line per stanza)	no ending punctuation
acrostic(rng, initials, max_words)	one line per initial, each starting with it	lines end with .

Word lengths are sampled from the learned word_lengths distribution (clamped by min_length/max_length); there is no user-supplied length_hint parameter.

Two additional built primitives matter for the platform:

• generate_unique(seed, count, constraints) — up to count distinct values with a bounded retry budget (for unique/PK columns).
• word_for(key, constraints) — deterministic keyed generation: the seed is FNV-1a of key, so the same key always maps to the same output (referential integrity across tables after anonymisation).

Constraints (built)

Constraint	Description
starts_with	Prefix constraint (prefix-filtered opener sampling)
ends_with	Suffix constraint (checked in the retry loop)
contains	Substring constraint (checked in the retry loop)
min_length / max_length	Hard bounds in characters (also steer the length target)
exclude_originals	Reject outputs identical to any training item

Constraint checking is a bounded retry loop (64 attempts): the engine regenerates until the output satisfies all constraints, then returns its best candidate if the budget is exhausted.

Privacy guards (built)

• min_count pruning (training-time): drop n-gram transitions seen fewer than N times at finalize — a transition seen once is often a unique, identifying fragment. Shrinks the model too. Originals are kept regardless (they back exclude_originals/real_word).
• Verbatim-run guard (generation-time): set_verbatim_guard(max_run) rejects any output sharing a verbatim character run longer than max_run with the training data (precomputed char-gram index; char models only). Pairs with min_count for a two-layer anti-memorization defence.

Sampling policy (built)

A generation-time knob (model.sampling), not serialized — it's a generation choice, not learned data:

Knob	Effect
temperature	1.0 = faithful count-proportional sampling (the exact-integer, cross-runtime-reproducible path); <1 sharper, >1 flatter
top_k	sample only among the k highest-weight transitions
top_p	nucleus sampling: smallest set whose mass reaches p
no_repeat	don't place the same word twice in a row (prose quality)

Non-default temperature/top_k/top_p trade strict cross-runtime determinism for diversity control.

---

Binary Search Weighted Random

The core selection algorithm — O(log n) via cumulative weights:

┌─────────────────────────────────────────────────────────────────────────┐
│                    WEIGHTED RANDOM SELECTION                             │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  Elements: ["a", "b", "c", "d"]                                         │
│  Weights:  [1,   2,   3,   4]                                           │
│  Cumulative: [1, 3, 6, 10]                                              │
│                                                                          │
│  r = rng.below(10) = 5                                                   │
│                                                                          │
│  Binary search for first cum > r  → index 2 → "c"                       │
│                                                                          │
│  Probability distribution: a: 10%, b: 20%, c: 30%, d: 40%               │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

Because edge order is fixed by the format (ascending id == lexicographic rank), this draw is bit-identical across runtimes.

---

Training

CLI (built flags)

# Basic: char model, order 3, one item per line
phony train names.txt -o models/names.ngram

# All real flags
phony train names.txt \
  --output models/tr_TR/names.ngram \   # -o
  --ngram-order 4 \                     # -n, range 2-5, default 3
  --token-type char \                   # -t: char | word | text
  --locale tr_TR \                      # tokenizer preset + stored tag
  --min-count 2 \                       # prune transitions seen < N times
  --min-word-length 3 \                 # tokenizer override
  --word-filter '[^a-zçğıöşü]+' \       # tokenizer override (drop regex)
  --lowercase                           # tokenizer override

Flag	Description
-o, --output	Output model file (default model.ngram)
-n, --ngram-order N	N-gram order, 2–5 (default 3)
-t, --token-type char|word|text	char = words/names · word = phrases · text = prose
--locale TAG	Tokenizer preset by locale, stored in the model
--min-count N	Prune n-gram transitions seen fewer than N times (privacy + size; 0 = keep all)
--min-word-length N	Tokenizer override: minimum word length
--lowercase	Tokenizer override: lowercase before training
--word-filter REGEX	Tokenizer override: characters to drop

Input is a plain-text file: one item per line for char/word, the whole file (split into paragraphs) for text.

Roadmap (not built): structured inputs (data.csv --column email, data.json --path "$.users[*].name"), multiple input files, --position-depth, and a --word-separator/--sentence-separator override pair.

Streaming & parallel training (built, library level)

The ModelBuilder trains incrementally: the underlying counts form a commutative monoid, so feeding batches in any order — or splitting the stream across workers and merging — produces a model byte-identical to a one-shot build.

let mut b = ModelBuilder::text(3, &cfg).min_count(2);
while let Some(batch) = source.next_batch() {
    b.feed_text(&batch);            // paragraphs sharded across cores (rayon)
}
let model = b.finalize();           // finalize once, at the end

• ModelBuilder::words / phrases / text pick token type + position depth.
• feed_items / feed_text accept batches; merge folds another builder's counts in (parallel workers).
• feed_text internally counts paragraph shards in parallel and merges — deterministic regardless of thread count.
• Memory is O(unique n-grams + batch), not O(corpus) — a remote DB can be trained from in batches. (DB orchestration itself is a cloud concern.)

---

PGDL Integration

Model generators reference a model asset by name (resolved through the locale chain; the .ngram file path lives in the owning package's phony.json). The generation block defaults to word mode.

Generation Block Syntax

{
  "type": "model",
  "source": "@phony/person:first_names",
  "generation": {
    "mode": "word | sentence | text | paragraph | poem | acrostic | real_word",
    "params": { }
  },
  "constraints": { }
}

Structure:

• generation.mode (optional, default word): how to produce output
• generation.params (optional): mode-specific parameters
• constraints (optional): output validation (min_length, max_length, starts_with, ends_with, contains, exclude_originals)

Available Modes (PGDL surface, as built)

Mode	Output	Params (with defaults)
word	Single word	— (constrain via constraints)
sentence	Single sentence	word_count (learned dist.), punctuation (".", or array to pick from), starts_with
text	Truncated text	max_chars (200), suffix (""), starts_with
paragraph	Paragraph	sentence_count (learned dist.), starts_with
poem	Poem with stanzas	verses (4), stanza_length (4), max_words (8)
acrostic	Acrostic poem	initials (required), max_words (8)
real_word	Pick from training items	prefix

The engine also has words/sentences (multi-value) calls; they are not exposed as PGDL modes — compose with a composition instead.

Dynamic Parameters (inside compositions)

Inside a composition, string params are PEL templates evaluated against the composition's bindings, so values thread through — including inline generators:

{
  "name": "@acme/demo:tagline",
  "let": {
    "line": {
      "type": "model",
      "source": "@acme/demo:slogans",
      "generation": {
        "mode": "sentence",
        "params": {
          "word_count": "{{number:3-8}}",
          "punctuation": [".", "!"]
        }
      }
    }
  },
  "body": "{{ line }}"
}

Complete Examples

Simple word generation:

{
  "type": "model",
  "source": "@phony/person:first_names",
  "generation": { "mode": "word" },
  "constraints": { "min_length": 3, "max_length": 12 }
}

Prose paragraph:

{
  "type": "model",
  "source": "@acme/demo:reviews",
  "generation": {
    "mode": "paragraph",
    "params": { "sentence_count": 3, "starts_with": "B" }
  }
}

Acrostic poem:

{
  "type": "model",
  "source": "@acme/demo:poetry",
  "generation": {
    "mode": "acrostic",
    "params": { "initials": "WELCOME", "max_words": 6 }
  }
}

Pick a real training item:

{
  "type": "model",
  "source": "@phony/person:first_names",
  "generation": {
    "mode": "real_word",
    "params": { "prefix": "A" }
  }
}

Mode Selection Guide

┌─────────────────────────────────────────────────────────────────────────┐
│                    GENERATION MODE SELECTION                             │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  Need a single generated item?                                          │
│  ├── Name, username, made-up word    → mode: "word"                     │
│  ├── Company name (multi-word)       → mode: "word" + word-mode model   │
│  └── Known/real name from data       → mode: "real_word"                │
│                                                                          │
│  Need text content? (train with -t text)                                │
│  ├── Short tagline, motto            → mode: "sentence"                 │
│  ├── Bio, description (fixed length) → mode: "text" + max_chars         │
│  └── Article, review                 → mode: "paragraph"                │
│                                                                          │
│  Need creative/structured text?                                          │
│  ├── Poem with stanzas               → mode: "poem"                     │
│  └── Hidden message in initials      → mode: "acrostic"                 │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

---

Performance Characteristics

Operation	Complexity	Notes
Training (feed)	O(n × k)	n = chars, k = ngram order; text mode parallel across paragraphs
Finalize	O(m log m)	m = unique ngrams (sorting the vocab)
Weighted random	O(log m)	Binary search over cumulative weights
Word generation	O(length)	id-based CSR walk — no per-step hashing
Model size	100KB – 10MB	Varint + dedup'd originals; depends on corpus

---

Future Optimizations

Uncompressed mmap variant (roadmap)

The in-memory representation already mirrors the file layout (sorted vocab, id-indexed CSR arrays). A future uncompressed, fixed-width variant of the format would allow mmap zero-copy loading — pointing at the file is loading the model. Valuable for the cloud engine's model-per-locale switching; low priority for the CLI, which loads a model once per run.

Structured training inputs (roadmap)

phony train data.csv --column first_name and phony train data.json --path "$.users[*].name" — today, extract to a plain text file first.

Streaming and parallel training, formerly listed here as future work, are built — see Streaming & parallel training.