Factored linear model: tiled matrix for coarse + frequent-lexical features

[eiennohito]

Problem

The linear model scoring is the performance bottleneck.
Each lattice connection currently requires ~69 hash computations + random reads into a 16 MB weight table (4M float32 entries, 2^22 slots).
These are effectively random memory accesses with no spatial locality — every feature hashes to a scattered address.

The weight table also has structural problems:

• 56% of entries are zero (wasted space from hash distribution)
• Hash collisions silently degrade accuracy — colliding features share a weight and get blended gradients during training
• No way to distinguish "this weight is zero because the feature is unimportant" from "this slot has no feature mapped to it"

Proposal: factored scoring with three tiers

Split features by representation, each tier trained as first-class parameters (not derived from each other):

Tier 1: Unigram scores → dictionary entries

All 33 unigrams depend only on t0 (the current node).
Precompute a single score per dictionary entry at build time.
Eliminates ~33 hash+weight-reads per node.
UNK nodes still compute at runtime.

Tier 2: Coarse + frequent-lexical bigrams → tiled matrix

The Jumandic spec has 32 bigram feature templates.
21 of them reference only coarse categorical fields (pos, subpos, conjtype, conjform).
The grammar defines ~336 distinct (pos, subpos, conjtype, conjform) categories.

Extend the matrix index with frequent lexical items.
Morpheme frequency follows Zipf's law — the top ~15 morphemes (が, の, は, を, た, etc.) cover ~25% of all tokens; top ~50 cover ~40%.
Promoting these into the matrix (giving them individual row/column IDs rather than sharing their coarse category's row) captures lexical bigram interactions for the most frequent connections.

Matrix design:

• Frequency-sorted IDs: ID 0 = most frequent morpheme, ensuring the hot core sits at the top-left corner
• Left/right IDs can differ: a node stores both left_id (for when it's t1) and right_id (for when it's t0), encoding different feature subsets
• Tiled layout with power-of-2 tile size for cache-friendly access with shift/mask indexing:

  tile_index = (r >> S) * NT + (c >> S)
  intra_tile = (r & TMASK) * T + (c & TMASK)
  offset     = (tile_index << (2*S)) | intra_tile
  

• Sized to fit L2 (~256 KB–1 MB). ~30% of tiles are L2-resident at any time. The hot core (top-64 × top-64 at tile size 16) is ~4 KB — permanently L1-resident.
• Element precision is a research question: start with f32, investigate i16/i8 with quantization-aware training later.

Tier 3: Rare lexical features → hash table (unchanged)

Remaining lexical bigrams/trigrams ({baseform}×{baseform}, {surface}×{auxWord}, {lexicalized}×{lexicalized}×{lexicalized}, etc.) stay hash-based.
The hash table stays roughly the same size — it's dominated by the lexical feature cross-products.
But it now serves ~14 features per connection instead of ~69, reducing the random-access pressure.

Sizing estimates

Assuming ~500 matrix dimension (336 coarse + ~150 promoted lexical items), padded to 512:

Element type	Total matrix	Hot core (64×64)
f32	1 MB	16 KB
i16	512 KB	8 KB
i8	256 KB	4 KB

Key design parameters

All independent, can be tuned separately:

• K (promoted lexical items): Zipf-driven, ~50–200. Start with corpus frequency, possibly iterate with weight-magnitude feedback.
• Element precision: f32 → i16 → i8 (research question)
• Tile size T: 8 or 16 (sweep parameter)
• Total dimension: 336 + K, padded to power-of-2 multiple of T
• Left/right ID sets: can use different feature subsets

Trigram prefix participation

The 3 coarse trigrams ({pos}³, {pos,subpos}³, {pos,subpos,conjform}³) could have their (t2, t1) partial scores precomputed in the same or a parallel matrix.
This is a further extension — not required for the initial implementation.

Impact

This changes the scoring pipeline, the codegen system, training, and the model file format.
The matrix entries are first-class trained parameters with zero hash collisions and dense gradient coverage.

Per-connection scoring cost:

	Current	Factored
Hash+random-reads into 16 MB table	~69	~14
Matrix reads (L1/L2)	0	1
Precomputed score adds	0	1