This document introduces the multi-tier Weighted Finite State Transducer (WFST) architecture for correction across written, spoken, and programming languages. The architecture includes the foundational three-tier WFST plus additional layers for dialogue context, LLM integration, and adaptive learning.
Sources:
/home/dylon/Workspace/f1r3fly.io/liblevenshtein-rust//home/dylon/Workspace/f1r3fly.io/MORK//home/dylon/Workspace/f1r3fly.io/MeTTa-Compiler/Related Integration Docs:
Extended Architecture Docs:
Original WFST Documentation (detailed implementation specs):
Programming Language Correction (5-layer design with SMT repair):
Error correction spans multiple domains with distinct requirements:
| Domain | Error Types | Correction Needs |
|---|---|---|
| Written Text | Typos, spelling, grammar | Dictionary lookup, context |
| Spoken Language | Phonetic confusion, homophones | Phoneme similarity, ASR lattices |
| Programming Languages | Syntax errors, type mismatches | Grammar validation, semantic types |
A unified architecture must handle all these while maintaining:
The complete correction architecture extends the three-tier WFST core with additional layers for dialogue context, LLM integration, and adaptive learning. This multi-layer design enables:
┌─────────────────────────────────────────────────────────────────────────┐
│ EXTENDED CORRECTION ARCHITECTURE (Full Stack) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ DIALOGUE CONTEXT LAYER │ │
│ │ Turn History │ Entity Registry │ Topic Graph │ Speaker Models │ │
│ │ [Discourse semantics, coreference resolution, topic tracking] │ │
│ │ See: ../dialogue/README.md │ │
│ └────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌───────────────────────────┼────────────────────────────────────────┐ │
│ │ ▼ │ │
│ │ THREE-TIER WFST CORE │ │
│ │ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │ │
│ │ │ Tier 1: │→ │ Tier 2: │→ │ Tier 3: │ │ │
│ │ │ Lexical │ │ Syntactic │ │ Semantic │ │ │
│ │ │ (libleven.) │ │ (MORK/CFG) │ │ (MeTTaIL) │ │ │
│ │ └──────────────┘ └──────────────┘ └──────────────┘ │ │
│ │ [Edit distance, phonetic rules, grammar validation, type checking]│ │
│ │ See: #three-tier-wfst-core below │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌───────────────────────────┼────────────────────────────────────────┐ │
│ │ ▼ │ │
│ │ PRAGMATIC REASONING LAYER │ │
│ │ Speech Act Classifier │ Implicature Resolver │ Relevance Ranker │ │
│ │ [Intent detection, indirect speech acts, contextual relevance] │ │
│ │ See: ../dialogue/04-pragmatic-reasoning.md │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌───────────────────────────┼────────────────────────────────────────┐ │
│ │ ▼ │ │
│ │ LLM INTEGRATION LAYER │ │
│ │ ┌────────────────────────────────────────────────────────────┐ │ │
│ │ │ PROMPT PREPROCESSING │ │ │
│ │ │ Correction → Coreference → Context Injection → RAG │ │ │
│ │ └────────────────────────────┬───────────────────────────────┘ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ LLM API │ │ │
│ │ └──────┬───────┘ │ │
│ │ ▼ │ │
│ │ ┌────────────────────────────────────────────────────────────┐ │ │
│ │ │ RESPONSE POSTPROCESSING │ │ │
│ │ │ Coherence Check → Fact Verification → Hallucination Detect │ │ │
│ │ └────────────────────────────────────────────────────────────┘ │ │
│ │ See: ../llm-integration/README.md │ │
│ └────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ┌───────────────────────────┼────────────────────────────────────────┐ │
│ │ ▼ │ │
│ │ AGENT LEARNING LAYER │ │
│ │ Feedback Collection │ Pattern Learning │ User Preferences │ │
│ │ Online Learning │ Threshold Adaptation │ Model Versioning │ │
│ │ [Adaptive correction weights, personalized dictionaries] │ │
│ │ See: ../agent-learning/README.md │ │
│ └────────────────────────────────────────────────────────────────────┘ │
│ │
└──────────────────────────────────────────────────────────────────────────┘
| Layer | Components | Purpose |
|---|---|---|
| Dialogue Context | Turn History, Entity Registry, Topic Graph | Multi-turn conversation tracking |
| WFST Core | Lexical, Syntactic, Semantic Tiers | Fundamental correction pipeline |
| Simplification | Analysis, Rules, Strategy, Verification | Post-correction source optimization |
| Pragmatic | Speech Acts, Implicatures, Relevance | Intent understanding |
| LLM Integration | Preprocessing, Postprocessing | LLM agent support |
| Agent Learning | Feedback, Patterns, Preferences | Adaptive personalization |
The foundational correction system uses three progressively refined tiers:
┌─────────────────────────────────────────────────────────────────────┐
│ UNIFIED CORRECTION WFST ARCHITECTURE │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ INPUT: Erroneous text (written/spoken/code) │
│ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ Tier 1: Lexical Correction │ │
│ │ (liblevenshtein) │ │
│ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │
│ │ │ Edit Dist. │ │ Phonetic │ │ Custom │ │ │
│ │ │ Automata │ │ Rules │ │ Weights │ │ │
│ │ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │ │
│ │ └─────────────────┼─────────────────┘ │ │
│ │ ▼ │ │
│ │ ┌────────────────────────┐ │ │
│ │ │ Candidate Lattice │ │ │
│ │ └───────────┬────────────┘ │ │
│ └──────────────────────────┼───────────────────────────────────┘ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ Tier 2: Syntactic Validation │ │
│ │ (CFG + MORK/PathMap) │ │
│ │ ┌─────────────────────────────────────────────────────────┐ │ │
│ │ │ MORK Space │ │ │
│ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │
│ │ │ │ Grammar │ │ Pattern │ │ Bloom + │ │ │ │
│ │ │ │ Rules │ │ Matching │ │ LRU │ │ │ │
│ │ │ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │ │ │
│ │ │ └─────────────────┼─────────────────┘ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌─────────────────────┐ │ │ │
│ │ │ │ PathMap │ │ │ │
│ │ │ │ (Shared Storage) │ │ │ │
│ │ │ └──────────┬──────────┘ │ │ │
│ │ └──────────────────────────┼──────────────────────────────┘ │ │
│ │ ▼ │ │
│ │ ┌────────────────────────┐ │ │
│ │ │ Syntactically Valid │ │ │
│ │ │ Candidates │ │ │
│ │ └───────────┬────────────┘ │ │
│ └──────────────────────────┼───────────────────────────────────┘ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ Tier 3: Semantic Type Checking │ │
│ │ (MeTTaIL / MeTTaTron / Rholang) │ │
│ │ ┌─────────────────────────────────────────────────────────┐ │ │
│ │ │ MeTTaTron │ │ │
│ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │
│ │ │ │ MeTTa │ │ Type │ │ Behavioral │ │ │ │
│ │ │ │ Atomspace │ │ Checking │ │ Predicates│ │ │ │
│ │ │ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │ │ │
│ │ │ └─────────────────┼─────────────────┘ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────────────────────────┐ │ │ │
│ │ │ │ OSLF Predicate Evaluation │ │ │ │
│ │ │ │ (structural + behavioral types) │ │ │ │
│ │ │ └───────────────┬──────────────────┘ │ │ │
│ │ └────────────────────────┼────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ┌────────────────────────┼────────────────────────────────┐ │ │
│ │ │ Rholang Bridge │ │ │
│ │ │ PathMap <-> MeTTa State <-> Rholang Par │ │ │
│ │ │ (Enables cross-language semantic checking) │ │ │
│ │ └────────────────────────┼────────────────────────────────┘ │ │
│ │ ▼ │ │
│ │ ┌────────────────────────┐ │ │
│ │ │ Semantically Valid │ │ │
│ │ │ Corrections │ │ │
│ │ └───────────┬────────────┘ │ │
│ └──────────────────────────┼───────────────────────────────────┘ │
│ ▼ │
│ OUTPUT: Ranked corrections with confidence scores │
│ │
└─────────────────────────────────────────────────────────────────────┘
| Tier | Component | Purpose | Speed |
|---|---|---|---|
| 1 | liblevenshtein | Lexical candidates via edit distance | Fastest |
| 2 | MORK/PathMap | Syntactic filtering via CFG | Fast |
| 3 | MeTTaIL/Rholang | Semantic type checking | Thorough |
The dialogue context layer extends correction capabilities for multi-turn conversations, enabling context-aware corrections that consider the full discourse history.
Full documentation: Dialogue Context Documentation
| Component | Purpose | PathMap Key |
|---|---|---|
| Turn Tracker | Conversation history with sliding window | /dialogue/{id}/turn/ |
| Entity Registry | Cross-turn entity tracking and coreference | /dialogue/{id}/entity/ |
| Topic Graph | Discourse structure and topic continuity | /dialogue/{id}/topic/ |
| Speaker Models | Per-participant vocabulary and style | /dialogue/{id}/speaker/ |
Coreference Resolution: Resolves pronouns and references across turns
Discourse Coherence: Validates corrections maintain conversation flow
Topic Management: Tracks and validates topic shifts
Dialogue Context → WFST Core
─────────────────────────────
• Entity salience affects candidate ranking
• Topic keywords influence lexical tier
• Speaker vocabulary personalizes dictionary
• Discourse coherence validates semantic tier
The LLM integration layer provides preprocessing and postprocessing for language model interactions, ensuring corrected input and validated output.
Full documentation: LLM Integration Documentation
Transforms user input before LLM processing:
User Input → Correction → Coreference → Context Injection → RAG → LLM Prompt
| Stage | Function | Documentation |
|---|---|---|
| Correction | Three-tier WFST fixes errors | This document |
| Coreference | Resolves references using dialogue context | 02-coreference-resolution.md |
| Context Injection | Formats dialogue history for prompt | 04-context-injection.md |
| RAG | Retrieves relevant knowledge | 04-context-injection.md |
Documentation: Prompt Preprocessing
Validates and corrects LLM responses:
LLM Response → Coherence → Fact Check → Hallucination → Correction → Final Output
| Stage | Function | Documentation |
|---|---|---|
| Coherence Check | Validates response addresses query | 02-output-postprocessing.md |
| Fact Verification | Checks factual claims against knowledge | 03-hallucination-detection.md |
| Hallucination Detection | Identifies fabricated content | 03-hallucination-detection.md |
| Correction | Three-tier WFST fixes errors | This document |
Documentation: Output Postprocessing
| Type | Detection Method | Example |
|---|---|---|
| Fabricated Fact | Knowledge base mismatch | Invented statistics |
| Nonexistent Entity | Entity registry lookup | Made-up person names |
| Temporal Error | Timeline validation | Wrong date claims |
| Contradiction | Dialogue consistency | Conflicting statements |
Documentation: Hallucination Detection
The agent learning layer provides adaptive correction through feedback collection, pattern learning, and online weight updates.
Full documentation: Agent Learning Documentation
| Component | Purpose | Documentation |
|---|---|---|
| Feedback Collection | Capture user responses to corrections | 01-feedback-collection.md |
| Pattern Learning | Extract error patterns from feedback | 02-pattern-learning.md |
| User Preferences | Model individual user characteristics | 03-user-preferences.md |
| Online Learning | Incremental weight and threshold updates | 04-online-learning.md |
User Action → Signal Detection → Normalization → Learning Update
───────────────────────────────────────────────────────────────
Accept (fast) → Strong positive → +0.8 to +1.0
Accept (slow) → Weak positive → +0.3 to +0.5
Modify → Correction signal → Pattern extraction
Reject → Negative signal → -0.8 to -1.0
Ignore → Weak negative → -0.1 to -0.3
| Adaptation | Scope | Effect |
|---|---|---|
| Edit Weights | Global/User | Character-level substitution costs |
| Feature Weights | Global/User | Ranking factor importance |
| Thresholds | User/Domain | Correction confidence cutoffs |
| Vocabulary | User | Personal dictionary additions |
| Patterns | Global | Recognized error→correction pairs |
/learning/
/patterns/ # Learned error patterns
/user/{user_id}/ # Per-user profiles
/vocabulary/ # Personal dictionary
/weights/ # Personalized weights
/thresholds/ # Confidence thresholds
/models/ # Version-controlled models
/current/ # Active model
/checkpoints/ # Historical snapshots
The three-tier architecture is implemented through four progressive phases, each building on the previous. See the MORK Integration Overview for complete implementation details.
┌─────────────────────────────────────────────────────────────────────┐
│ MORK Integration Phases │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ Phase A: FuzzySource Trait │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ • Trait abstraction for fuzzy dictionary backends │ │
│ │ • PathMap + DAWG + DoubleArrayTrie implementations │ │
│ │ • Integration point: liblevenshtein → MORK │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ ↓ │
│ Phase B: Lattice Infrastructure │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ • Weighted DAG for multi-candidate representation │ │
│ │ • K-best path extraction (Dijkstra-based) │ │
│ │ • LatticeZipper for MORK ProductZipper integration │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ ↓ │
│ Phase C: WFST Composition │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ • Semiring weights (Tropical, Log, Probability) │ │
│ │ • Phonetic NFA via Thompson's construction │ │
│ │ • FST ∘ FST ∘ Trie composition operators │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ ↓ │
│ Phase D: Grammar Correction │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ • CFG rules as pattern/template pairs │ │
│ │ • MORK match2() for structural matching │ │
│ │ • query_multi_i() for O(K×N) lattice processing │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────┘
Documentation: FuzzySource Implementation
The FuzzySource trait provides a unified interface for fuzzy dictionary lookups across
different storage backends:
/// Unified trait for fuzzy dictionary sources.
pub trait FuzzySource {
/// Query with fuzzy matching up to max_distance.
fn fuzzy_lookup(&self, query: &[u8], max_distance: u8)
-> impl Iterator<Item = (Vec<u8>, u8)>;
}
Implementations:
PathMap: Trie-based storage with zipper navigationDynamicDawg / DynamicDawgChar: SIMD-optimized for runtime updatesDoubleArrayTrie / DoubleArrayTrieChar: Optimized for static dictionariesIntegration Point: Tier 1 (Lexical Correction) uses FuzzySource for candidate generation.
Documentation: Lattice Integration
Lattices represent the space of correction candidates as weighted directed acyclic graphs:
Query Term: "teh"
│
▼
Transducer::query_lattice()
│
│ Builds DAG of candidates with weighted edges
▼
Lattice { nodes, edges, vocab }
│
▼
LatticeZipper (MORK adapter)
│
│ Iterates paths by total weight
▼
ProductZipper → Unification → Ranked Results
Key Components:
Lattice: Core DAG structure with vocabulary deduplicationLatticeBuilder: Incremental construction APIPathIterator / k_best(): Path extraction algorithmsLatticeZipper: Adapter for MORK's ProductZipperIntegration Point: Bridge between Tier 1 and Tier 2.
Documentation: WFST Composition
Full Weighted Finite State Transducer infrastructure with phonetic NFA composition:
Query Pattern: "(ph|f)(o|oa)(n|ne)"
│
▼
PhoneticNfa::compile() ← Thompson's construction
│
▼
ComposedAutomaton::new(phonetic_nfa, levenshtein, dictionary)
│
│ FST ∘ FST ∘ Trie composition
▼
Lattice with phonetic-weighted edges
Key Concepts:
| Semiring | $\oplus$ (combine) | $\otimes$ (extend) | Use Case |
|---|---|---|---|
| Tropical | min | + | Shortest path (Viterbi) |
| Log | log-sum-exp | + | Probabilistic (forward-backward) |
| Probability | + | × | Raw probabilities |
Integration Point: Tier 1 phonetic expansion before Tier 2 filtering.
Documentation: Grammar Correction
CFG-based error correction using MORK's pattern matching as the rule engine:
; CFG Rule: Subject-Verb Agreement Error
Pattern: (s (np ?Subj :number singular) (vp (v ?V :number plural) ?Rest))
Template: (s (np ?Subj :number singular) (vp (v (singularize ?V)) ?Rest))
Cost: 1.0
Key MORK Functions:
| Function | Location | Purpose |
|---|---|---|
match2() | expr/src/lib.rs:921 | Recursive structural matching |
unify() | expr/src/lib.rs:1849 | Variable binding + constraints |
query_multi_i() | kernel/src/space.rs:992 | $\mathcal{O}(K\times N)$ lattice queries |
transform_multi_multi_() | kernel/src/space.rs:1221 | Pattern→template application |
Integration Point: Tier 2 (Syntactic Validation) rule engine.
| Phase | Tier | Primary Function | Output |
|---|---|---|---|
| A | 1 | Fuzzy lookup | Raw candidates |
| B | 1→2 | Lattice construction | Weighted DAG |
| C | 1 | Phonetic expansion | Expanded candidates |
| D | 2 | Grammar filtering | Valid corrections |
Each tier reduces the candidate set before the next:
Input Error: "teh" in "teh cat sat"
│
▼ Tier 1 (Lexical)
Candidates: [the, tea, ten, tee, tech, ...] (~100 candidates)
│
▼ Tier 2 (Syntactic)
Valid in context: [the, tea] (grammar allows determiner or noun)
│
▼ Tier 3 (Semantic)
Best correction: "the" (matches "cat sat" semantic context)
| Tier | Complexity | Candidates |
|---|---|---|
| 1 | $\mathcal{O}(n \times d)$ | Generate many |
| 2 | $\mathcal{O}(n \times g)$ | Filter structurally |
| 3 | $\mathcal{O}(n \times t)$ | Verify semantically |
Where:
By filtering at each tier, expensive semantic checks only run on valid candidates.
Each tier has distinct expertise:
| Tier | Knowledge Required |
|---|---|
| 1 | Character/phoneme similarity |
| 2 | Language grammar |
| 3 | Type system, domain semantics |
PathMap serves as the shared storage layer across all tiers:
┌─────────────────────────────────────────────────────────────────┐
│ PathMap Integration │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────┐ │
│ │ liblevenshtein │ │
│ │ Dictionary │──────┐ │
│ └─────────────────┘ │ │
│ │ │
│ ┌─────────────────┐ │ ┌─────────────────────────┐ │
│ │ MORK Grammar │──────┼─────>│ PathMap │ │
│ │ Rules │ │ │ (Trie-based Storage) │ │
│ └─────────────────┘ │ └─────────────────────────┘ │
│ │ │ │
│ ┌─────────────────┐ │ │ │
│ │ MeTTa Type │──────┘ ▼ │
│ │ Predicates │ ┌────────────────────────────┐ │
│ └─────────────────┘ │ Shared Query Interface │ │
│ │ - Pattern matching │ │
│ │ - Fuzzy lookup │ │
│ │ - Type queries │ │
│ └────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
| Component | Typical Size |
|---|---|
| Dictionary (English) | 50-100 MB |
| Grammar (Programming Language) | 10-50 MB |
| Type Predicates | 5-20 MB |
| Working Set (LRU) | 10-50 MB |
The extended correction architecture provides:
| From | To | Interface |
|---|---|---|
| liblevenshtein | PathMap | FuzzySource trait |
| MORK | PathMap | Native storage backend |
| MeTTaTron | PathMap | Type predicate storage |
| Rholang | PathMap | Par conversion |
| Dialogue Context | WFST Core | Entity salience, speaker vocab |
| LLM Layer | WFST Core | Pre/post-processing pipeline |
| Agent Learning | All Layers | Adaptive weights and thresholds |
Dialogue Context Layer
│
▼
Three-Tier WFST Core ←────────────────────────────┐
│ │
▼ │
Pragmatic Reasoning Layer │
│ │
▼ │
LLM Integration Layer │
│ │
▼ │
Agent Learning Layer ──────────────────────────────┘
│ (feedback loop)
▼
PathMap Storage
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |