HermitCrab analysis: prune on root substring at rule outputs, gated by restoration flags #562

HermitCrab analysis keeps unapplying rules on a word whose shape contains no root as a substring, although no lookup below it can hit. The trigger is a concatenative grammar parsed against a small or early lexicon, where most words fail lexically. The cost is 13.6-38.5% of analysis events on real grammars below the topmost such node.

Problem (census, steps)

Census predicate H2, "the shape contains no root as a substring", at analysis rule outputs. Share of analysis events below the topmost such node (ceiling): Mbugwe 38.5%, Indonesian 29.6%, Sena 16.8%, Aweti 14.8%, Amharic 13.6%, conformance 1.3%. Topmost violations on the five real grammars: 0. But 29 nodes on conformance success paths satisfy H2, because stem material can be restored later (nasal substitution, stem restoration, infix removal, reduplication). So the predicate is unsound without static flags.

Proposed change

At a rule output word N in stratum S (rule outputs of AnalysisAffixProcessRule, AnalysisRealizationalAffixProcessRule, and the head output of AnalysisCompoundingRule): prune when no root allomorph of S or any deeper stratum occurs as a contiguous run of N's Segment nodes. Add an internal substring probe to RootAllomorphTrie (transduce from each Segment annotation, no end anchor, stop at first accept). Enabled per stratum by static flags computed once in the Morpher constructor.

Soundness

Lookup is exact (Morpher.LexicalLookup, trie anchored at both ends). Call a rule allomorph contiguous-removing if its RHS is inserted material, then all LHS parts as unmodified CopyFromInputs in LHS order with nothing inserted between them, each copied once, then inserted material. The flag for stratum S is true iff (a) every morphological, template-slot and compounding rule of S and of every deeper stratum is contiguous-removing, (b) no deeper stratum has phonological rules (S's own are unapplied at its entry, before any rule output), and (c) the language has no lexical-pattern roots (guessRoot analyses). Then any shape looked up below N is a contiguous run of N's shape, so an exact root match there is a substring match in N. A compound passes the test because it contains its head root. LexEntrySelector only removes roots, so searching all tries is sound. Infixation, reduplication, ModifyFromInput and truncation-restoring rules turn the flag off, which is exactly the conformance violation class.

Memory bound

No new structure: one bool per stratum and the existing root tries. No cache.

Expected value (low and uncertain)

v1 is narrow on real grammars. Sena has no phonological, restoring, infixing or reduplicating rules, so v1 should reach most of 16.8% (est. 8-17%). Indonesian (reduplication), Amharic (infix-like -ä-), Mbugwe and Aweti (segment-restoring slot rules) probably have the flag off, so v1 likely gives 0 there. The follow-up for them is #568. The prune matters most for concatenative languages parsed against a small early lexicon (stress fixture est. at least 40%). Cost: one substring probe per rule output when the flag is on, counted as trie probes beside the savings.

Measurement plan

1. Internal Morpher mode Off | Shadow | On (default On); shadow evaluates the predicate and records a violation if any parse completes below a fired node.
2. Steps per grammar in census and censusmerge modes, same grammars and sampling as HermitCrab analysis: skip template partials whose required slot material is absent #561; report which strata have the flag on per grammar.
3. Stress fixture "Early-lexicon agglutinative": single stratum, 25 unordered suffixal rules (pure concatenation, MaxApplicationCount 1) with vowel-harmony phonology in the same stratum, 20 roots, 60 words (40 with roots absent from the lexicon and long suffix chains).
4. Gates as HermitCrab analysis: skip template partials whose required slot material is absent #561: tests on branch and master, conformance verdicts identical, parses identical, csharpier, comment hygiene.

Kill criterion

Any shadow violation: stop, soundness bug. Close and record as a ledger row-27 reconfirmation if the flags leave the prune on for no real grammar, or if the shadow saving is under 5% on every real grammar where it is on and under 25% on the stress fixture. Also close if trie probes exceed the events saved.

Overlaps and dependencies

• Reopens ledger row 27 by a different route. Row 27 closed root-reachability summaries because dead internal nodes were 0-5% on 6 of 8 lists and nodes may still compound. This differs: the test is a substring test (a compound passes), it runs at internal nodes including template-slot outputs, and static flags disable the restoration cases. Row 27's reopening condition is "a shadow summary deciding a meaningful share"; the shadow phase is that test. If it repeats row 27's numbers, the row stays closed.
• Related: Analysis search is nogood-dominated on a template-heavy Bantu grammar; memoization yields ~6%, and the HasReachableRoot prune is absent from all refs #485 asks for a HasReachableRoot-style reachability prune on a template-heavy Bantu grammar; this is a different predicate with static soundness flags. HermitCrab: cull analysis candidates at emission by stratum+shape lexical lookup (memory on truncation-heavy grammars) #512 culls candidates at emission (memory); this prunes earlier, inside the search. HermitCrab: partial lexical entries switch off final-template pruning for the whole grammar #551 (partial lexical entries) is unaffected because only root allomorph strings are used.
• Follow-up: HermitCrab analysis: subsequence fallback and insertion classes for the root prune (v2) #568 (subsequence fallback and insertion classes) depends on this issue.

Related

• PR HermitCrab optimization round record: what was tried, and a faster package that is not mergeable #490: HermitCrab optimization round record (ledger rows cited above are in it).
• PR Add a conformance suite for HermitCrab, with its adequacy argument #480: HermitCrab conformance suite. Conformance per-fixture verdicts must be identical with and without the change.
• Units: deterministic analysis events and synthesis steps, never ms. "% less work" = (off - on) / off per grammar, never pooled. Census figures are ceilings unless stated. Ranges marked "est." are estimates that the shadow phase replaces with measurements.
• Owner constraint: no memo or cache; any new structure must be grammar-sized and at most a few MB.

🤖 Generated with Claude Code