Grammar-Constrained Decoding and Deterministic Local Tools for TinyRustLM

Full report

On this page

Executive summary and assumptions

The uploaded research brief supplies a specific implementation topic despite the surrounding request describing the topic as unspecified. This report therefore treats grammar-constrained browser-local generation and deterministic local tools for TinyRustLM as the governing research subject. It assumes no access to TinyRustLM source code, model files, tokenizer fixtures, private schemas, tests, traces, or generated outputs, and it does not imply that any recommendation has been validated against the private implementation.

Executive recommendation. TinyRustLM should adopt one clean first-release architecture:

1. A bounded deterministic EBNF subset as the canonical grammar language.
2. A restricted JSON Schema adapter that lowers into the same internal representation.
3. A byte-oriented predictive parser-state machine with bounded stack, rather than a character-only parser or unrestricted general-purpose regex engine.
4. An exact token-ID-to-byte mapping and a shared tokenizer byte trie for incremental allowed-token discovery.
5. A strict separation between syntactic admissibility, schema validity, semantic validation, deterministic computation, and tool authority.
6. A fixed-precision decimal calculator and, initially, no other automatically executed tool except narrow read-only deterministic transforms.
7. A versioned, hash-bound local tool envelope in which tool names map only to compiled application capabilities.
8. No output repair, hidden retry-until-valid behavior, model-produced code execution, user-controlled file paths, or model-selected network destinations.
9. Raw token decisions, allowed-token counts, stop reasons, constraint identities, and tool provenance retained for authorized local auditing.

Constrained decoding can guarantee membership in the implemented formal language, but not factual truth, semantic correctness, safety, or faithful fulfillment of user intent. The distinction is not merely theoretical: structured-generation implementations themselves warn that valid formatting does not imply semantic correctness and that aggressive masking can worsen content quality.

The proposed internal design deliberately sacrifices some grammar expressiveness for predictable compilation, deterministic rejection, small native Rust implementation size, and resistance to state-explosion attacks. Recent systems such as XGrammar, XGrammar 2, Outlines, LM Format Enforcer, and llguidance demonstrate that trie indexing, state caching, specialized JSON handling, and parser-aware token masks can make constrained generation practical. They also illustrate why TinyRustLM should adopt the underlying ideas rather than import a broad, dynamically extensible grammar ecosystem into a security-sensitive, zero- or low-dependency browser core.

Priority conclusion. The first three projects should be developed as a single gated program:

The medium estimates are planning figures, not vendor quotes. They assume loaded engineering costs around $18,000–$22,000 per full-time-equivalent month, part-time security and quality review, browser/device testing, and approximately 15% contingency.

Assumptions.

Evidence base, claim taxonomy, and first-release scope

The evidence base combines recent primary research, official specifications, and pinned public implementations. Grammar-constrained decoding has shown benefits in information extraction, disambiguation, parsing, and structured generation, while JSONSchemaBench provides approximately 9,558 curated real-world schemas for evaluating efficiency, feature coverage, and output quality. Recent work also reports substantial gains from vocabulary indexing, context-independent token classification, just-in-time mask compilation, cross-grammar caching, and repetition compression. Those findings motivate the architecture but do not establish that the same performance or quality will hold for TinyRustLM’s unknown model and tokenizer.

Claim vocabulary.

The practical consequence is that user-interface labels must say “JSON complete and profile-valid”, “semantic validation failed”, or “generation cancelled with partial raw output”, rather than the ambiguous “validated” or “correct.”

Recommended first-release scope.

JSON itself requires UTF-8 for interoperable exchange, recommends unique object names, prohibits leading zeroes in numbers, and permits lexical numeric magnitudes that may exceed interoperable binary64 limits. RFC 8259 specifically notes exact interoperability for integers only through the binary64-safe range of ±(2^53−1). TinyRustLM should therefore implement a deliberately stricter profile, not claim unrestricted JSON or unrestricted JSON Schema support.

JSON Schema Draft 2020-12 includes dynamic references, unevaluated-item semantics, Unicode-aware regular expressions, conditional composition, and other features whose complete interaction is disproportionate to a bounded first-release engine. The official language-agnostic test suite exists precisely because seemingly simple validators differ in edge cases. TinyRustLM should publish a supported-keyword matrix and reject every unknown keyword rather than ignore it.

Prioritized research portfolio

The following eight proposals form a coherent implementation and evaluation program. Priority scores are an internal decision model combining prerequisite value, expected risk reduction, user impact, feasibility, and reversibility. They are not empirical performance results.

xychart-beta
    title "Research portfolio priority score"
    x-axis ["Byte core","Tokenizer","JSON","Calculator","Security","Browser perf","Quality","Observability"]
    y-axis "Score" 0 --> 100
    bar [96,93,88,80,78,74,71,66]

Portfolio comparison.

Canonical architecture and implementation contract

Recommended architecture. The public contract should consist of a bounded EBNF grammar plus a restricted JSON Schema profile, both lowering into one immutable compiled constraint. Internally, TinyRustLM should use deterministic parser-state transitions over bytes, with bounded pushdown state for nesting and byte-DFA states for terminals. Grammars that are ambiguous under the implementation’s predictive analysis should be rejected, not interpreted through undocumented tie-breaking.

flowchart LR
    A[Untrusted grammar or schema bytes] --> B[Bounded UTF-8 parser]
    B --> C[AST and feature validation]
    C --> D[Nullable FIRST FOLLOW analysis]
    D --> E{Deterministic and within limits?}
    E -- No --> F[Explicit compile failure]
    E -- Yes --> G[Byte terminal automata]
    G --> H[Bounded parser-state machine]
    H --> I[Canonical encoding and SHA-256 identity]
    I --> J[Atomic publication]
    J --> K[Tokenizer byte-trie product]
    K --> L[Allowed token mask]
    L --> M[Sampling]
    M --> N[Raw token and stop trace]

Formalism comparison.

Research systems support broader grammars than the proposed TinyRustLM subset. XGrammar uses optimized context-free execution; XGrammar 2 adds Earley-based masking, dynamic dispatch, JIT compilation, and cross-grammar caching; llguidance supports a large JSON Schema subset and CFGs. Those are useful upper-bound references, but TinyRustLM’s zero-dependency and adversarial-input constraints justify a narrower deterministic core.

Canonical grammar input contract: trg-1.

Safe compilation pipeline.

1. Enforce input byte and UTF-8 limits before allocation proportional to declarations.
2. Parse into an arena-indexed AST with checked integer arithmetic.
3. Resolve names and reject duplicates, missing references, reserved names, and unreachable rules if strict mode is enabled.
4. Compute nullable sets to a fixed point, charging every update against a cycle budget.
5. Detect nullable cycles and direct or indirect left recursion.
6. Compute FIRST and FOLLOW sets and reject predictive conflicts.
7. Expand bounded repetition symbolically; do not duplicate subtrees naively.
8. Compile string literals and character primitives into byte-level automata.
9. Construct parser-state templates and intern structurally identical states.
10. Enforce state, transition, stack, and memory ceilings after every expansion phase.
11. Serialize the compiled artifact deterministically, hash it, and run internal self-checks.
12. Publish the artifact with a single atomic pointer swap only after all checks pass.

Recommended initial ceilings are 65,536 parser or terminal states, 1,048,576 transitions, 32 MiB compiled memory per constraint, 64 MiB total constraint cache, and 50 million charged compilation operations. These are engineering starting points requiring browser measurement, not externally sourced constants.

A simple upper-bound accounting model is:

\[ M_{\text{compiled}} \le H + S \cdot b_s + T \cdot b_t + B_{\text{terminal}} + B_{\text{diagnostic}} \]

where \(S\) is state count, \(T\) is transition count, \(b_s\) and \(b_t\) are implementation-specific fixed record sizes, and all additions and multiplications use checked arithmetic. Compilation must abort before an allocation if the projected bound exceeds the configured budget.

Token, byte, and Unicode reconciliation. The grammar consumes bytes, while global output validity is tracked by an incremental UTF-8 validator. A token is not treated as a Unicode character or ordinary string. Each vocabulary entry must have a verified exact byte sequence corresponding to generation, with the following classifications:

UTF-8 validation must reject overlong encodings, surrogate-code-point encodings, invalid continuation bytes, and values above U+10FFFF. Unicode explicitly treats non-shortest and irregular sequences as illegal because alternate interpretations create interoperability and security problems.

Allowed-token algorithm.

allowed_tokens(compiled, parser_state, utf8_state, token_trie):
    key = (
        compiled.hash,
        tokenizer.hash,
        compiler.version,
        parser_state.id,
        utf8_state,
        special_token_policy.version
    )

    if mask_cache.contains(key):
        return mask_cache[key]

    allowed = empty_bitset(vocabulary_size)
    work = stack()
    work.push(token_trie.root, parser_state, utf8_state)

    while work not empty:
        cancellation_checkpoint()

        trie_node, pstate, ustate = work.pop()

        for edge_byte, child in trie_node.children:
            next_utf8 = utf8_step(ustate, edge_byte)
            if next_utf8 is INVALID:
                continue

            next_parser = parser_step(pstate, edge_byte, next_utf8)
            if next_parser is DEAD:
                continue

            work.push(child, next_parser, next_utf8)

            for token_id in child.terminal_token_ids:
                if token_is_complete_and_legal(token_id, next_parser, next_utf8):
                    allowed.set(token_id)

    if parser_state.accepting and utf8_state.complete:
        allowed.set(EOS)

    mask_cache.insert_if_within_budget(key, allowed)
    return allowed

The naive vocabulary scan costs approximately

\[ O\left(V\bar{L}C_p\right) \]

per generation step, where \(V\) is vocabulary size, \(\bar L\) average token-byte length, and \(C_p\) parser transition cost. Trie traversal costs

\[ O\left(E_{\text{visited}}C_p + A\right), \]

where \(E_{\text{visited}}\) is the number of trie edges compatible with the current parser prefix and \(A\) is the number of allowed terminal token IDs. In the worst case the trie still approaches the total vocabulary byte count, but shared prefixes avoid repeated parser work. LM Format Enforcer publicly describes this parser/trie intersection approach, while XGrammar and Outlines describe vocabulary indexes and cached state/token mappings.

Cache identity must include tokenizer bytes, special-token policy, grammar hash, compiler version, parser state, UTF-8 state, and any JSON-profile mode. A cache entry from one tokenizer or compiler must never be reused by another merely because token IDs or grammar text appear similar.

Sampling order and edge cases.

The normative order should be:

1. Read raw model logits.
2. Convert every NaN logit to forbidden and increment an audit counter; retain positive or negative infinity only according to a declared policy, preferably failing if positive infinity appears.
3. Apply the grammar-allowed mask.
4. Apply independently forbidden special-token and policy masks.
5. Apply repetition or frequency penalties only to remaining tokens.
6. Apply temperature.
7. Apply minimum-probability filtering, if supported.
8. Apply top-k.
9. Apply top-p.
10. Normalize probabilities.
11. Draw once from the recorded RNG state.
12. Advance parser, UTF-8, repetition, and trace state atomically.

An empty allowed set produces constraint_empty_set, never repair or automatic retry. A set containing only EOS terminates without an RNG draw. At temperature zero, select the maximum logit and break exact ties by smallest token ID. EOS is impossible before an accepting parser state. If all surviving logits are non-finite or all probability mass is removed, stop with an explicit sampling failure.

Bitwise deterministic replay should be claimed only for the same model build, tokenizer, compiled constraint, numerical kernel, sampling implementation, and stored RNG state—or when the original post-model logits are retained. Cross-device floating-point execution may otherwise differ at close probability boundaries.

Streaming, stopping, and cancellation. Raw token IDs and bytes are the authoritative stream. UI text may display only complete UTF-8 scalars; trailing incomplete byte sequences remain buffered. A partial JSON document may be shown as “structured output in progress” but must not be deserialized into application objects or displayed as completed JSON. Cancellation returns a status record with raw partial bytes or text where locally authorized, parser state, and completed: false. It never appends brackets, closes strings, inserts missing fields, or retries.

Bounded JSON profile: trj-1.

RFC 8259 allows duplicate object names syntactically but warns that receiving implementations behave unpredictably, while JCS requires unique property names and valid Unicode for stable canonicalization. JCS also rejects NaN and infinity and recommends string representations for values that do not fit natural binary64 interchange.

Deferred JSON Schema features should include remote $ref, recursive and dynamic references, pattern, patternProperties, unevaluatedProperties, unevaluatedItems, general oneOf/anyOf, not, if/then/else, contains, dependentSchemas, complex multipleOf, content vocabularies, and assertion-level format. Deferral is not a statement that these features are undesirable; it reflects their interaction complexity and state-growth risks.

Syntax-to-semantics boundary. An extraction result should use an application schema similar to:

{
  "status": "supported | unknown | unsupported | conflict",
  "value": "schema-typed value or null",
  "evidence": [
    {
      "source_id": "local-content-hash",
      "start_byte": 120,
      "end_byte": 145,
      "quoted_sha256": "…",
      "transform": "exact | trim | casefold | parse_integer | parse_decimal"
    }
  ],
  "unit": "declared-unit-or-null",
  "validation": {
    "enum_member": true,
    "range_ok": true,
    "cross_field_ok": true
  }
}

Only listed transformations are permitted. A value absent from the source must become unknown; a present but schema-inexpressible value must become unsupported; inconsistent evidence must become conflict. Unit conversions require an explicit deterministic conversion rule and must preserve the original evidence value. Semantic failure remains visible and does not trigger model rewriting.

Deterministic calculator. The calculator should avoid binary floating-point as its normative arithmetic type. ECMAScript’s default Number is IEEE 754 binary64, and its JSON serialization maps NaN and infinities to null, behavior unsuitable for an exact calculator boundary. Rust’s i128 exposes checked addition, multiplication, division, power, and related operations suitable for a bounded native decimal representation.

Recommended calculator contract:

Example result:

{
  "protocol": "tinycalc-1",
  "status": "ok",
  "expression_sha256": "…",
  "value": "0.333333333333333333",
  "scale": 18,
  "rounding": "half_even",
  "exact": false,
  "operations": 1,
  "implementation": "tinycalc-rust-1.0.0"
}

Local tool envelope.

{
  "protocol": "tinyrust-tool-1",
  "request_id": "019…",
  "composition": {
    "model_id": "sha256:…",
    "tokenizer_id": "sha256:…",
    "prompt_policy_id": "sha256:…"
  },
  "tool": {
    "name": "calculator.evaluate",
    "version": "1.0.0",
    "capability": "deterministic.compute"
  },
  "schemas": {
    "input_sha256": "…",
    "output_sha256": "…"
  },
  "authorization": {
    "class": "automatic_read_only",
    "user_gesture_id": null,
    "granted": true
  },
  "limits": {
    "input_bytes": 4096,
    "output_bytes": 8192,
    "operations": 10000,
    "timeout_ms": 100
  },
  "input": {
    "expression": "1 / 3"
  }
}

The tool name is matched against a compiled enum. It never names Rust functions, JavaScript functions, executable files, paths, URLs, modules, or network endpoints. The request ID may use a standards-conforming UUID, but uniqueness is bookkeeping rather than authority. RFC 9562 is the current UUID standard.

erDiagram
    MODEL_COMPOSITION ||--o{ TOOL_REQUEST : proposes
    TOOL_DEFINITION ||--o{ TOOL_REQUEST : constrains
    INPUT_SCHEMA ||--|| TOOL_DEFINITION : validates
    OUTPUT_SCHEMA ||--|| TOOL_DEFINITION : validates
    AUTHORIZATION ||--|| TOOL_REQUEST : permits
    TOOL_REQUEST ||--o| TOOL_RESULT : produces
    TOOL_RESULT ||--|| PROVENANCE : records
    TOOL_RESULT ||--o{ REINSERTION_RECORD : reinserts_as_untrusted_data

    MODEL_COMPOSITION {
        string model_hash
        string tokenizer_hash
        string policy_hash
    }
    TOOL_DEFINITION {
        string name
        string version
        string capability
        string implementation_hash
    }
    AUTHORIZATION {
        string class
        bool granted
        string user_gesture_id
    }
    TOOL_REQUEST {
        string request_id
        string input_schema_hash
        int max_input_bytes
        int timeout_ms
    }
    TOOL_RESULT {
        string status
        string output_schema_hash
        bool truncated
        string result_hash
    }
    PROVENANCE {
        string implementation_hash
        bool deterministic
        string stop_reason
    }

Authority matrix.

Browser permission specifications model powerful-feature access as a user choice that can be granted or denied, while Permissions Policy can disable classes of browser capability. TinyRustLM should mirror that approach internally even for capabilities not directly governed by browser permission APIs.

Prompt-injection and confused-deputy controls. Prompt text, quoted content, retrieved memory, JSON values, schemas, tool arguments, tool results, and model output all belong to the data plane. Only compiled application configuration belongs to the control plane.

NIST’s Generative AI Profile recommends systematic risk identification, measurement, documentation, and testing rather than relying on a model’s own claims of safety. That principle supports treating all model-mediated text as untrusted and keeping authority in deterministic application code.

Tool-result reinsertion. Results should be inserted as a typed record, not concatenated prose:

{
  "role": "tool_result",
  "trust": "untrusted_data",
  "request_id": "…",
  "tool": "calculator.evaluate@1.0.0",
  "status": "ok",
  "schema_sha256": "…",
  "result_sha256": "…",
  "truncated": false,
  "content": {
    "value": "0.333333333333333333"
  }
}

The system must serialize and escape this structure itself. Result text cannot change instruction precedence. Token budgeting occurs before insertion; truncation must preserve valid envelope syntax and expose the truncation. The current user turn and application policy remain authoritative regardless of result contents.

Detailed plans for the leading proposals

The top three projects overlap substantially and should share a program manager, formal specification repository, test corpus, and promotion gate. The low case assumes a small senior team and limited device coverage. The medium case supports independent review and serious adversarial testing. The high case adds parallel implementation, formal-methods support, broad browser/device coverage, and external audit.

Integrated program budget.

Some labor is double-counted if the projects are priced separately; the integrated total reflects shared staffing and infrastructure.

Byte-accurate constrained-decoding core.

Milestones:

Primary risks and mitigations:

Tokenizer-byte conformance and trie engine.

Milestones:

Primary risks and mitigations:

Bounded JSON profile and semantic validation.

Milestones:

Primary risks and mitigations:

Integrated timeline.

gantt
    title TinyRustLM constrained-generation research program
    dateFormat  YYYY-MM-DD
    axisFormat  %b %d

    section Shared specification
    Claim taxonomy and limits             :a1, 2026-08-10, 14d
    Test corpus architecture               :a2, 2026-08-10, 21d

    section Byte core
    Grammar parser and AST                 :b1, 2026-08-24, 21d
    Static analyses                        :b2, after b1, 21d
    Parser-state compiler                  :b3, after b2, 21d
    Sampling and streaming integration     :b4, after b3, 21d
    Hardening and gate                     :b5, after b4, 14d

    section Tokenizer and trie
    Token-byte fixture and probes          :c1, 2026-09-07, 21d
    UTF-8 and trie engine                  :c2, after c1, 21d
    Cache and performance work             :c3, after c2, 21d
    Integration gate                       :c4, after c3, 14d

    section JSON and semantics
    JSON profile freeze                    :d1, 2026-09-21, 14d
    Schema compiler                        :d2, after d1, 28d
    Official and corpus conformance        :d3, after d2, 21d
    Semantic evidence validator            :d4, after d2, 28d
    End-to-end gate                        :d5, after d3, 21d

    section Program promotion
    Security review                        :e1, 2026-11-30, 21d
    Sealed quality evaluation              :e2, 2026-12-07, 28d
    Release decision                       :milestone, e3, 2027-01-11, 0d

Failure semantics, testing, performance, and clean adoption

Failure taxonomy. Every failure returns a stable machine-readable code, human-readable local diagnostic, constraint/tool identity, and raw stop state where retention is authorized. No failure is converted into a plausible-looking answer.

Privacy-safe observability.

Private local traces may contain:

• model, tokenizer, prompt-policy, grammar, schema, compiler, and tool implementation hashes;
• generated token IDs and exact generated bytes when the user has authorized diagnostic retention;
• allowed-token count at each step;
• selected token rank and pre/post-mask score summaries;
• parser-state ID, UTF-8 state, cache hit/miss, compile and mask timings;
• RNG algorithm/version and initial state;
• stop/failure reason;
• tool request ID, capability, schema hashes, authorization class, result status, truncation, and deterministic provenance.

Public aggregate reports must exclude prompts, outputs, document text, tool input values, file names, private paths, credentials, user identifiers, and per-session traces. They may report distributions such as compile time, mask time, allowed-set size, failure frequency, schema-feature coverage, and quality scores.

Conformance and adversarial corpus.

The official JSON Schema Test Suite should be vendored at a pinned revision, but only tests applicable to the declared profile should be classified as required. Every remaining test must be marked unsupported rather than silently skipped. JSONSchemaBench should be used for coverage and performance analysis, not as the sole correctness oracle.

Quality experiment design.

The principal experiment should use four arms:

Tasks should cover ordinary conversation, summarization, rewriting, extraction, JSON generation, code explanation, ambiguity handling, practical reasoning, and arithmetic. The evaluation set must be sealed after prompt and feature decisions. Metrics should include completion rate, valid syntax, profile validity, semantic accuracy, evidence accuracy, unsupported/unknown calibration, helpfulness, instruction adherence, refusal appropriateness, truncation, latency, peak memory, compile time, allowed-token counts, and mask intervention severity.

A useful intervention metric is:

\[ I = \frac{1}{N}\sum_{t=1}^{N} \left[ \log p_t^{\text{unmasked}}(x_t^\*) - \log p_t^{\text{unmasked}}(x_t) \right], \]

where \(x_t^\*\) is the model’s unconstrained top token and \(x_t\) the constrained selected token. High intervention indicates that the grammar repeatedly forces the model away from its preferred distribution and should be correlated with semantic quality. LM Format Enforcer exposes similar token-level diagnostics and explicitly cautions that syntactic enforcement can increase hallucination or force low-weight tokens.

Performance formulas and targets.

Initial product targets should be treated as hypotheses: median warm mask computation under 0.25 ms, p99 under 2 ms on a representative middle-tier desktop, cold compilation under 50 ms for ordinary schemas, peak compiled constraint under 8 MiB for typical cases, and cancellation acknowledgment under 16 ms. Public systems report substantially lower typical per-token overhead under server-class conditions, including llguidance’s reported sub-50-microsecond average over its benchmark and XGrammar’s reported near-zero end-to-end overhead, but browser-local targets must be measured independently.

TDD backlog and promotion gates.

Recommended release gates are: 100% pass on required conformance tests; zero silent repair; zero unknown-key acceptance; no crash or hang in adversarial corpus; no tool dispatch outside the compiled registry; exact replay on the supported reference environment; syntactic-validity improvement without a statistically or practically unacceptable decline in semantic correctness or helpfulness; and privacy review of every trace field.

Clean deletion rules. Because no legacy compatibility is required, any unpublished format or mechanism should be deleted if it:

• requires answer repair or retry-until-valid to meet its success criterion;
• cannot map tokens to exact bytes;
• ignores unknown grammar or schema constructs;
• permits unbounded repetition, recursion, state growth, or memory use;
• has nondeterministic compilation or conflicting grammar interpretations;
• needs general regex, dynamic code loading, or executable descriptions;
• exposes user-controlled paths or destinations;
• allows tool results to change authority;
• lacks an explicit raw failure state;
• performs worse than the canonical protocol on both quality and resource use without a unique required capability;
• cannot be independently tested against the reference interpreter.

Gap analysis and recommended next steps

Critical unknowns requiring authorized local access.

No final conformance claim should be made before the tokenizer and sampler are inspected. In particular, a grammar engine cannot safely be “adapted later” to an unknown tokenizer by applying character-level rules to token IDs.

Gap analysis by discipline.

Recommended immediate next steps.

The first irreversible decision should not be a broad grammar feature. It should be the token-byte identity contract, because every compiler, trie, cache, mask, stream, replay record, and JSON guarantee depends on it.

Annotated primary-source register

All sources below were retrieved on August 1, 2026. Repository releases should be pinned to exact source commits in the implementation lockfile; a release tag alone is not sufficient for reproducible security review.