How Function Calling Actually Works: Grammar-Constrained Decoding Under the Hood

You send a function definition with a JSON schema. The model responds with a perfect tool call — valid JSON, correct types, enum values from the allowed list, required fields present. No parsing errors. No retries.

It looks like the model "understands" the schema. It doesn't.

What actually happens: your JSON schema gets compiled into a context-free grammar. That grammar drives a pushdown automaton at inference time. At every decoding step, the automaton computes which vocabulary tokens would keep the output valid. Those tokens keep their logits. Every other token gets its logit set to negative infinity. The model samples from what remains.

The model still decides which tool to call and what arguments to pass. But the braces, commas, quotes, property names, type constraints, and enum restrictions? Those are mechanically guaranteed. The model literally cannot produce invalid structure.

---

The Problem: Free Text Doesn't Guarantee Structure

An LLM trained on next-token prediction assigns probabilities to every token in its vocabulary. Nothing in the training objective forces the sequence to form valid JSON, match a regex, or satisfy a context-free grammar.

The failure modes are familiar:

• Missing or extra braces — the model loses track of nesting depth
• Wrong type — an integer field gets a quoted string
• Hallucinated enum values — the model invents a value outside the allowed set
• Truncated output — the model emits EOS mid-object
• Key name drift — user_id becomes userId under paraphrase pressure

Post-hoc repair (parsing with fallback, asking the model to fix its own output) adds latency and is unreliable. The only robust solution: prevent invalid token sequences from being sampled in the first place.

---

The Key Insight: Local Validity Is Enough

You don't need to forbid bad sequences globally. You only need to forbid the single next token that, given what has been emitted so far, would make the sequence irrecoverable.

This is exactly what an automaton state transition tells you.

---

From JSON Schema to Context-Free Grammar

When you send a function tool definition, the provider's infrastructure converts the JSON schema into a context-free grammar (CFG). The conversion is mechanical:

JSON Schema	Grammar Rule
"type": "string"	Matches any valid JSON string
"type": "number"	Matches JSON number literals
"type": "object" with "properties"	Matches object with exactly those keys and value types
"enum": [...]	Alternation listing only allowed literals
"required": [...]	Restricts which property combinations are accepted
Nested objects/arrays	Recursive grammar rules

For a get_weather function:

{
  "type": "object",
  "properties": {
    "city": { "type": "string" },
    "unit": { "enum": ["celsius", "fahrenheit"] }
  },
  "required": ["city"]
}

The resulting grammar (Lark-like notation):

start: "{" ws pair_city ws maybe_unit "}"
pair_city: "\"city\"" ws ":" ws STRING
maybe_unit: ("," ws pair_unit)?
pair_unit: "\"unit\"" ws ":" ws UNIT_ENUM
UNIT_ENUM: "\"celsius\"" | "\"fahrenheit\""
STRING: "\"" /[^"\\]*/ "\""
ws: /\s*/

This grammar accepts {"city": "Tokyo"} and {"city": "Tokyo", "unit": "celsius"} but rejects {"city": 42}, {"unit": "kelvin"}, and {"temperature": 22}.

---

Finite-State Machines vs Pushdown Automata

Regular expressions (finite-state machines) handle flat patterns — phone numbers, UUIDs, ISO 8601 dates. They cannot handle arbitrary nesting.

JSON with arbitrarily nested objects and arrays requires a context-free grammar, which corresponds to a pushdown automaton — a finite automaton plus a stack. The stack tracks nesting depth: every { pushes, every } pops. When the stack is empty and you're in an accepting state, the JSON is complete and valid.

---

Logit Masking: The Enforcement Mechanism

At each decoding step:

1. The model computes raw logits ℓ ∈ ℝ^|V| (one per vocabulary token)
2. The grammar engine inspects tokens generated so far, determines valid next tokens given current automaton state
3. Invalid tokens get logit = -∞
4. Softmax, temperature, top-k, top-p proceed over remaining valid tokens
5. Token is sampled from constrained distribution
6. Automaton advances with the chosen token

ℓ̃_v = ℓ_v          if valid[q_t][v] = 1
      = -∞           otherwise

After softmax, disallowed tokens have probability zero. The sampler operates on the masked distribution exactly as it would on an unconstrained one. Temperature scaling, top-p, top-k all compose cleanly.

The model's relative preferences over allowed tokens are preserved. If the model thought "Tokyo" was twice as likely as "Osaka" before constraining, it's still twice as likely after. The grammar only removes options that would violate the schema.

---

Token-Level Masks: Why Character Simulation Matters

Tokenizers operate over multi-character tokens, not single characters. A token like "weather" (single token) or "42" (single token in many tokenizers) consumes multiple characters at once.

The mask must simulate each token's full character span through the automaton, not just check the first character.

Example: Grammar requires exactly 4 digits ([0-9]{4}).

• At state q0 (0 digits seen): token "27" (2 chars) is allowed → lands at q2
• At state q3 (3 digits seen): token "27" is forbidden → second char would overshoot into dead state

A token's legality flips with the state. This is why production systems (XGrammar, llguidance, Outlines) pre-compute token-level masks by simulating each token's full decoded string through the automaton.

---

Inside XGrammar: Compiled Grammar + Matcher

XGrammar (used in vLLM, SGLang) implements this at production speed:

1. Grammar — describes output structure (JSON Schema → CFG)
2. GrammarCompiler — compiles grammar to CompiledGrammar (pre-computes token masks, builds transition tables)
3. GrammarMatcher — stateful, per-request object:
   • accept_token(token_id) — advances internal state
   • fill_next_token_bitmask() — produces 32-bit compressed bitmask for current state

The bitmask is a compressed bitset (int32 array). For 128K vocabulary: ~16 KB per request. The matcher only runs on CPU; the bitmask is copied to GPU where a single kernel applies it to logits before sampling.

Adaptive token mask caching: requests with identical grammar/tokenizer state share masks. The cache key is the stack top node — validity of future tokens is determined by the current parser state.

---

The Function Calling Pipeline End-to-End

1. Schema Conversion
   JSON Schema → Context-Free Grammar (cached)

2. Prompt Construction
   Tool definitions serialized into model's prompt format
   (Harmony tokens, XML-wrapped definitions, etc.)

3. Free Generation
   Model generates conversational text unconstrained
   Until it emits tool-call trigger token (e.g., `<|tool_call|>`)

4. Constrained Generation
   Grammar engine activates
   At each step: compute valid tokens → mask logits → sample → advance automaton
   Continues until complete valid JSON object produced

5. Parsing
   Output (guaranteed structurally valid) parsed to extract function name + args

6. Execution
   Tool call returned to developer or executed server-side
   Result flows back to model, generation continues

---

Why This Matters

Structural correctness is a hard guarantee. The model's training only needs to handle the semantic side: deciding which tool to call and what argument values to pass. The scaffolding — braces, commas, quotes, property names, type constraints — is enforced mechanically at every token.

This is why function calls almost never return malformed JSON. Not because the model is that reliable. Because the sampling process won't let it be unreliable.

---

What Developers Should Know

• Prompt the structure anyway. Constrained decoding only affects sampling. You want the model's underlying distribution to already align with the structure. Describe the expected output in the prompt.
• First request with a new schema is slower. Grammar compilation and caching happen on first use. Subsequent requests reuse the compiled grammar.
• Not all JSON Schema features are enforceable. Recursive schemas, unbounded nesting, and some validation keywords may not be fully enforced by the decoder. Check your provider's supported subset.
• API-based services can't do this. OpenAI, Anthropic APIs don't expose logit access. Constrained decoding requires access to the decoding loop (local models, vLLM, SGLang, self-hosted).

---

The Takeaway

Function calling isn't magic. It's not prompt engineering. It's a pipeline where a JSON schema compiles to a formal grammar, and that grammar constrains the model's sampling so it can only produce valid output.

The model does the hard part: understanding intent, choosing the right tool, selecting the right values. The grammar engine does the mechanical part: guaranteeing every brace, comma, quote, and type constraint is correct.

Next time you see a perfect tool call, remember: the model didn't "learn JSON." The decoder was simply forbidden from getting it wrong.