Named entities, information extraction and structured output
Many real jobs need a row in a database, not a paragraph: the names in a contract, the fields of an invoice, the arguments of a tool call. This session shows the three ways to get structure out of a model: tag every token (BIO tags with a small encoder), ask an LLM to fill a JSON schema, and force the LLM to stay inside a grammar while it decodes. It ends with an honest comparison: when a small fine-tuned model beats a big prompted one.
What you will learn
- The extraction tasks (entities, relations, events, slot filling) and the three ways to solve them: token tagging, generative extraction, constrained generation
- BIO and BIOES tags, why some tag sequences are invalid, and how constrained Viterbi decoding repairs a tagger's mistakes
- Extraction with JSON Schema and function calling: what the model sees, what can go wrong, and the validate-and-retry loop
- Grammar-constrained decoding: the token mask, how a regular expression becomes a state machine over tokens (Outlines), and how context-free grammars are made fast (XGrammar)
- Why a valid structure is not a correct answer: the mask distorts the distribution and can force hallucinated values
- When a small fine-tuned encoder beats a big prompted LLM, with a compute calculator and published results, and how to combine them by distillation
Why this matters
A lot of useful work with language models ends in a database row, not in a paragraph. A bank wants the amount, date and payee from each invoice. A hospital wants the drug names and doses from each note. An agent wants the exact arguments of a function call. In all of these, a free-text answer is useless unless a program can read it.
This job is called information extraction: turn unstructured text into structured data with a fixed shape. The oldest form is named-entity recognition (NER): find the spans of text that name a person, a place, an organization, a date. Newer forms ask for relations (who works for whom), events (who did what, when) and whole records (fill every field of a form). In 2026 the same problem appears inside every LLM product as structured output: the model must answer in valid JSON that follows a given schema, so that the next program in the chain does not crash.
There are three ways to do it, and this session builds all three: (1) a small encoder tags every token, as in session 55; (2) an LLM reads a JSON schema and writes the JSON; (3) the same LLM, but the decoder is forced to follow a grammar, so the output is valid by construction. Then we ask the practical question that interviews and design reviews always ask: when is the small fine-tuned model the better choice?
The extraction tasks
All extraction tasks fill a fixed shape from free text. They differ in how complex the shape is.
| Task | Output shape | Example from “Tim Cook visited Apple Park in Cupertino on 5 May.” |
|---|---|---|
| Named-entity recognition (NER) | A list of (type, span) | (PER, “Tim Cook”), (LOC, “Apple Park”), (LOC, “Cupertino”), (DATE, “5 May”) |
| Relation extraction | A list of (head, relation, tail) | (“Apple Park”, located_in, “Cupertino”) |
| Event extraction | A trigger word plus typed arguments | visit(agent = “Tim Cook”, place = “Apple Park”, time = “5 May”) |
| Slot filling / record extraction | A record with named fields (often JSON) | {"person": "Tim Cook", "place": "Apple Park", "date": "05-05"} |
| Function calling | A function name plus arguments that match a schema | log_visit(person="Tim Cook", city="Cupertino") |
Two properties matter for the rest of this session. First, NER is grounded: every answer is a span of the input, with start and end positions. Slot filling is often normalized: “5 May” becomes a date in a fixed format, and that value does not appear in the text. Second, the shape is either fixed (always the same 4 entity types) or open (a new schema for each customer). Grounded and fixed favors a tagger. Normalized and open favors a generator.
Route 1: token classification with BIO tags
We met this in session 55; here is the short version, and then the part that was missing: valid tag sequences. A span is turned into one label per token with the BIO scheme. B-X marks the first token of an entity of type X, I-X a token inside it, and O a token outside any entity. With \(E\) entity types there are \(2E + 1\) tags; CoNLL-2003 (PER, LOC, ORG, MISC) has 9. A variant called BIOES (also BILOU) adds E-X for the last token and S-X for a single-token entity, so \(4E + 1\) tags (17 for CoNLL). It gives the model a clearer signal at span ends. [Likely]
An encoder such as BERT gives a hidden vector \(\mathbf{h}_t\) for every token \(t\). One linear layer turns it into a distribution over the \(K\) tags:
Training minimizes the cross-entropy summed over the labeled tokens (special tokens and the extra subword pieces of a word are skipped, with label −100 in PyTorch):
- Read the symbols
- \(\mathbf{x}\)
- the input tokens
- \(\mathbf{h}_t \in \R^{d}\)
- the encoder’s hidden state at token \(t\); it has read the whole sentence, left and right
- \(K\)
- the number of tags (\(2E+1\) for BIO)
- \(y_t^{\star}\)
- the true tag of token \(t\)
- \(\mathcal{T}\)
- the tokens that carry a label (the first subword of every word)
BERT-base and BERT-large fine-tuned this way reached 92.4 and 92.8 test F1 on CoNLL-2003. [Certain] That is entity-level F1: an entity counts only if its type and both ends are exactly right.
Not every tag sequence is legal
Formula (146.1) predicts each tag on its own. Nothing stops the model from writing B-ORG followed by I-LOC, which describes no span at all. In BIO, I-X may only follow B-X or I-X, and a sentence may not start with I-X. These rules form a tiny grammar over tags. Taking the argmax per token ignores it. The fix is to search for the best sequence that obeys it.
Write the rules as a transition matrix \(A\) with \(A_{ij} = 0\) if tag \(j\) may follow tag \(i\) and \(A_{ij} = -\infty\) if it may not. The Viterbi algorithm finds the sequence with the highest total log-probability among the legal ones, by dynamic programming. Let \(\delta_t(j)\) be the best score of any legal sequence of the first \(t\) tags that ends in tag \(j\):
Start with \(\delta_1(j) = \log p(y_1 = j \mid \mathbf{x}) + s_j\), where \(s_j = -\infty\) for the I- tags. Keep the argmax at each step, and at the end walk back from the best final tag. The cost is \(O(T K^2)\): for 9 tags, 81 additions per token, nothing next to the encoder. When \(A\) is learned instead of fixed, this is a conditional random field (CRF) layer, the standard NER head before BERT (BiLSTM-CRF). [Certain] With a strong encoder, the hard \(0/{-\infty}\) rules give most of the benefit at no training cost. [Likely]
B-ORG and B-LOC (the two always add up to 0.88).How to read Figure 2
In greedy mode, “Apple” gets B-ORG (0.48) and “Park” gets I-LOC (0.55). That pair is illegal, so the scorer reads it as two entities, ORG “Apple” and LOC “Park”: both wrong. Switch to Viterbi. The best legal path changes “Apple” to B-LOC, and the entity becomes LOC “Apple Park”, which is right. The path is less likely word by word (−2.228 instead of −2.045), but it is the most likely legal path. Now move the slider. Greedy switches at 0.44; Viterbi keeps LOC until \(p(\text{B-ORG}) = 0.645\); above that, the legal path B-ORG O wins and the output becomes ORG “Apple” with “Park” as O.
Only “Apple Park” is in doubt; the other words are the same in every path. Compare the legal options for the two words (products of probabilities):
B-ORG I-ORG: \(0.48 \times 0.15 = 0.072\). B-ORG O: \(0.48 \times 0.20 = 0.096\). B-LOC I-LOC: \(0.40 \times 0.55 = 0.220\). The winner is B-LOC I-LOC.
The illegal greedy pair B-ORG I-LOC has \(0.48 \times 0.55 = 0.264\), higher than any legal pair, which is why greedy picks it. Its log-probability is higher by \(\ln(0.48/0.40) = 0.182\), exactly the gap between −2.045 and −2.228 in the readout.
When does Viterbi switch to ORG? With \(x = p(\text{B-ORG})\) and \(p(\text{B-LOC}) = 0.88 - x\), LOC wins while \((0.88 - x) \cdot 0.55 \gt 0.20\,x\), so while \(x \lt 0.484/0.75 = 0.645\).
- input: words, a fine-tuned encoder with a tag head, the tag list (\(K = 2E+1\))
- build \(A_{ij} = -\infty\) if tag \(j\) is
I-Xand tag \(i\) is neitherB-XnorI-X, else 0; \(s_j = -\infty\) for everyI-X// built once - run the encoder; keep the log-probabilities of the first subword of each word // formula (146.1)
- \(\delta_1 \leftarrow s + \log p_1\)
- for \(t = 2..T\): \(\delta_t(j) \leftarrow \log p_t(j) + \max_i (\delta_{t-1}(i) + A_{ij})\); store the argmax \(i\) // formula (146.3)
- take \(j^\star = \argmax_j \delta_T(j)\) and follow the stored pointers back to \(t = 1\)
- turn the tags into spans: open at
B-X, extend onI-X, close otherwise; return (type, start, end) with character offsets
Where BIO stops working
BIO gives every token exactly one tag. So it cannot express nested entities: in “Bank of China”, the whole span is an ORG and “China” is a LOC. It also cannot express discontinuous ones (“left and right lung”, where “left lung” is one entity). And it needs a fixed label set at training time. Span-based models score every candidate span \((i, j)\) directly instead of tagging tokens, which handles nesting. GLiNER goes further: it embeds the entity type names as text and matches them against span embeddings, so the label set can change at inference time. [Certain] Its encoder is DeBERTa-v3, with 50M to 300M parameters. [Certain]
Route 2: generative extraction with JSON schemas
A decoder-only LLM can do extraction with no training at all: describe the record in the prompt and ask for JSON. The standard way to describe the record is JSON Schema, a JSON document that says which fields exist, their types, which are required, and which values are allowed:
{"type": "object",
"properties": {
"name": {"type": "string"},
"age": {"type": ["integer", "null"]},
"role": {"type": "string", "enum": ["author", "editor", "other"]}},
"required": ["name", "age", "role"],
"additionalProperties": false}
The model reads the schema as plain text in its prompt (as in session 143), writes its answer, and your code parses it. It works surprisingly often, and it can do things a tagger cannot: normalize “thirty-six” to 36, pick one value from an enum, combine facts from different sentences, follow a new schema for every request.
Function calling is the same thing
Function calling (also called tool use) is structured extraction where the record is the argument list of a function. You give the model a list of tools; each has a name, a description in words, and a JSON Schema for its parameters. The model either answers in text or emits a call: a tool name and a JSON object of arguments. Your code runs the function and sends the result back as a new message (session 154). Inside the model, the tool list and the call are just tokens laid out by the chat template, usually between special tokens that mark “this is a tool call” (session 9). Models learn this format in post-training on many examples of tool calls. [Certain] Toolformer was an early paper that taught a model to insert API calls into its own text. [Certain]
What can go wrong
Without any constraint, the output can fail at four levels, from easy to hard to detect:
- Not JSON at all: “Sure! Here is the JSON:” before the object, a Markdown code fence around it, a trailing comma, a comment, a cut-off ending at the token limit.
- JSON, but not the schema: a missing required field, an extra field,
"age": "36"(a string where an integer was asked), a value outside theenum. - Valid, but not grounded: a name that is not in the document, a date the model guessed.
- Valid and grounded, but wrong: the right kind of value from the wrong place (the sender’s address instead of the receiver’s).
Levels 1 and 2 can be checked by a program: parse, then validate against the schema. The classic fix is a loop: if validation fails, send the error back and ask again. If one try is valid with probability \(p\) and tries are independent, then with at most \(k\) tries
With \(p = 0.9\) and \(k = 3\) that is 0.999; with \(p = 0.6\), only 0.936, and every retry adds a full generation of latency and cost. Tries are not really independent either: a model that misreads a field tends to misread it again. Levels 3 and 4 cannot be fixed by any parser; they need evaluation against labeled data (formula 146.9 below). The next route removes levels 1 and 2 completely.
- input: document, JSON Schema \(S\), maximum tries \(k\)
- prompt \(\leftarrow\) instructions + \(S\) + (optional) 1 to 3 worked examples + document
- for try \(= 1..k\):
- out \(\leftarrow\) LLM(prompt), with temperature 0 // or constrained decoding, Route 3
- if out parses as JSON and validates against \(S\): break
- prompt \(\leftarrow\) prompt + out + “Error: ” + validator message // formula (146.4)
- ground every string field: find it in the document (exact, then fuzzy match); flag values that are not found
- return the record, its character offsets, and flags for review
Route 3: grammar-constrained decoding
Why ask nicely when you can forbid? At every decoding step the model gives a distribution over the whole vocabulary. Some tokens would make the output impossible to complete as valid JSON for this schema; we simply set their probability to zero. If \(\mathcal{A}_t\) is the set of tokens that keep the output a valid prefix (the start of some valid output), the decoder samples from
- Read the symbols
- \(p(v \mid y_{\lt t})\)
- the model’s probability of token \(v\) after the tokens written so far
- \(\mathcal{A}_t\)
- the allowed tokens at step \(t\), given by the grammar and the text so far
- \(\mathbf{1}[\cdot]\)
- 1 if the condition is true, else 0
- \(Z_t\)
- the probability mass the model put on allowed tokens; dividing by it makes \(q\) sum to 1
In code this is one line: add \(-\infty\) to the logits of the forbidden tokens before the softmax. It works with greedy decoding, sampling, top-p, everything from session 79. If the grammar is right, the output is valid by construction: it parses, it has every required field, the integers are integers. The model never “tries and fails”. Figure 3 runs it step by step.
{"name": string, "age": integer} from the text “Ada Lovelace wrote the first program.” The toy model has a 16-token vocabulary and fixed, made-up probabilities. Each token is shown in quotes (single quotes when the token itself contains a double quote): a space inside the quotes is part of the token, so " Lovelace" is one token that starts with a space. The text never says how old she is.How to read Figure 3
Step 1: the model would rather say “Sure” (0.55) than “{” (0.35). The mask removes “Sure”, so the output starts correctly. Steps inside the string allow 12 of 16 tokens: almost anything except quotes. Now watch step 11, the age. The model’s favorite is null (0.62), because the text has no age. The schema says integer, so the mask keeps only 36 and 28, which together had 0.16. After dividing by \(Z = 0.16\), “36” gets 0.625, and the output says she was 36: a valid, confident, invented fact. Tick “allows null” and step again: now null is allowed and wins with 0.795.
At the age step the model gives null 0.62, ' "' (a space and a quote) 0.14, 36 0.10, 28 0.06, thirty 0.05, and 0.03 spread over the other 11 tokens.
Schema “integer”: \(\mathcal{A} = \{36, 28\}\), \(Z = 0.10 + 0.06 = 0.16\). So \(q(36) = 0.10/0.16 = 0.625\) and \(q(28) = 0.375\). The model put 84% of its mass on “this is not an integer”, and the mask threw all of that away.
Schema “integer or null”: \(Z = 0.16 + 0.62 = 0.78\), and \(q(\text{null}) = 0.62/0.78 = 0.795\). The lesson: a schema must have a legal way to say “not found”. A small \(Z_t\) is a warning sign; log it.
From a grammar to a token mask
How do we compute \(\mathcal{A}_t\)? The grammar is written over characters, but the model emits tokens, and one token can be many characters (“100”, “":”, “ Lovelace”, with its leading space). A token is allowed if reading all of its characters keeps us inside the grammar.
Start with the simple case: a regular expression, such as the one for a JSON integer, -?(0|[1-9][0-9]*). Every regular expression can be turned into a deterministic finite automaton (DFA): a small set of states \(Q\), a start state, a set of accepting states, and a transition function \(\delta(s, c)\) that says where character \(c\) leads from state \(s\) (or to “dead” if \(c\) is not allowed). Extend \(\delta\) to strings by reading one character after the other, and call it \(\delta^{*}\). Then
The key idea of Outlines (Willard and Louf) is that \(\mathcal{A}(s)\) depends only on the DFA state \(s\), not on the rest of the text. So you can compute it once for every state, before generation starts: walk each vocabulary token from each state, and store the result in an index, a table from state to allowed token ids. During decoding, each step is a table lookup plus one DFA move. [Certain] JSON Schemas without recursion can be compiled to one big regular expression, so this covers many practical schemas. [Certain] Figure 4 builds the index for the integer DFA.
-?(0|[1-9][0-9]*) (double circles accept) and the Outlines-style index for an 11-token vocabulary. The token “}” stands for “the number ends here”, so it is allowed only in accepting states. Click a state, or the circles, to see its row of the index.How to read Figure 4
From q0, 7 of the 11 tokens are allowed: “05” is not (a JSON integer cannot start with 0 and continue), and “}” is not (an empty number is not a number). From q2 (the output so far is “0” or “-0”) only “}” is allowed: nothing may follow a leading zero. From q3, “05” is allowed, since “1” followed by “05” is “105”. The same token can be legal in one state and illegal in another; this is why the index is keyed by state. Type a multi-character string into the box to watch \(\delta^{*}\) walk it.
Context-free grammars and XGrammar
Regular expressions cannot count. JSON objects can nest inside arrays inside objects to any depth, and a recursive schema (a tree of comments, say) needs to remember how many brackets are open. That needs a context-free grammar (CFG), and a CFG is recognized by a pushdown automaton: a state machine plus a stack. Now the allowed set depends on the whole stack, not on one small state, so a simple precomputed index no longer works, and checking 128k tokens at every step against the stack is slow.
XGrammar (Dong et al., 2024) splits the vocabulary in two. For a given position in the grammar, most tokens are context-independent: whether they are allowed can be decided from the top of the stack alone, so it can be precomputed and cached. The few context-dependent tokens (for example ones that close a bracket and continue past it) are checked at run time against the full stack. For the JSON grammar with the Llama 3.1 vocabulary, the paper counts fewer than 1% context-dependent tokens: 1,134 out of about 128k. [Certain] The cache for each grammar position stores whichever set is smaller (accepted or rejected tokens). XGrammar also uses a persistent stack (cheap to copy and roll back) and computes the mask on the CPU while the GPU runs the forward pass. The paper reports under 40 µs per token for the mask with JSON Schema, up to 100 times faster than earlier systems for CFGs, and up to 80 times faster end to end in serving with structured output. [Certain: as reported by the authors]
Making it faster than unconstrained decoding
Sometimes the grammar allows exactly one continuation: after {"name": "Ada Lovelace", the only legal next text is "age": . There is no reason to run the model token by token through it. SGLang’s compressed finite-state machine merges such single-path stretches and appends them in one go (“jump-forward” decoding). [Certain] So structured output with fixed keys can be faster than free text. One care point: jumping forward inserts text that the tokenizer might have split differently, so systems re-tokenize at the boundary. [Likely]
- input: model, tokenizer vocabulary \(\mathcal{V}\), grammar \(G\) (regex, JSON Schema or CFG)
- compile \(G\) to an automaton; precompute, for each automaton state, the allowed token set (Outlines index) or the context-independent part of it (XGrammar cache) // formula (146.6), once per schema, cached
- state \(\leftarrow\) start; \(y \leftarrow\) []
- repeat:
- if only one string is legal next: append its tokens, advance the state, continue // jump-forward
- logits \(\leftarrow\) model\((y)\) on the GPU, while the CPU builds the mask for the current state
- logits\([v] \leftarrow -\infty\) for \(v \notin \mathcal{A}\); \(v \leftarrow\) sample or argmax // formula (146.5)
- advance the automaton with the characters of \(v\); append \(v\); log \(Z_t\)
- until the automaton is in an accepting state and the end token was chosen
Valid is not the same as good
The mask fixes the form. It can also change the content, in three ways.
1. It distorts the distribution. What we would like is the model’s distribution over full outputs, restricted to valid ones: \(p(y \mid \text{valid}) = p(y)/P(\text{valid})\). What the mask gives, step by step, is different:
The denominator \(\prod_t Z_t\) is different for every \(y\). Paths where the model “did not want” the valid tokens (small \(Z_t\)) are boosted. The mask is myopic: it only checks that the prefix can still be completed, not how likely the model is to complete it well. Exercise 4 has a two-token example where the constrained sampler picks a path 60% of the time that the true conditional gives only 7.7%.
2. It can force invented values, as in Figure 3. Make fields nullable, add an “evidence” field with the quoted source text, and check that the evidence really is in the document.
3. It can hurt reasoning. If the schema makes the model write the answer field first, it has no room to think before it commits. Tam et al. report lower reasoning accuracy under strict format restrictions, with the largest drops for the strictest formats. [Certain] Others argue that good prompts and schemas remove most of the gap. [Likely] Practical rule: put a free-text "reasoning" field before the answer fields (key order is part of the schema), or let the model think freely first and constrain only the final record.
When a small fine-tuned model beats a big prompted one
Constrained decoding makes an LLM’s output valid. It does not make it cheap, fast or accurate. For a fixed set of entity types with labeled data, a small fine-tuned encoder is often better on all three.
Compute
A forward pass costs about \(2N\) FLOPs per token for a model with \(N\) parameters (Session 1). The encoder reads only the document of length \(L\). The LLM reads the document plus a prompt overhead \(L_p\) (instructions, schema, examples) and then writes \(L_o\) output tokens, one at a time:
With BERT-base (110M), a 70B LLM, a 300-token document, 800 tokens of prompt overhead and 80 output tokens: \(\frac{70\text{B}}{110\text{M}} \times \frac{1180}{300} \approx 2{,}503\). Even an 8B model costs about 286 times more. And FLOPs flatter the LLM: the encoder does one parallel forward pass, while the LLM also runs \(L_o\) sequential, memory-bound decode steps (session 82). Prefix caching can remove most of the repeated prompt overhead \(L_p\) (session 134). Try it in Figure 5.
How to read Figure 5
The defaults give a ratio of about 2,500. Shrink the prompt overhead to 0 (perfect prefix caching) and the ratio for the 70B model is still about 806 (the model-size ratio alone is 636). Make the document long and the overhead matters less. No slider setting makes the LLM cheaper; the question is only whether its extra ability is worth the price.
Accuracy: published results
- On CoNLL-2003, fine-tuned BERT-large reaches 92.8 entity F1. [Certain] Prompted LLMs without fine-tuning have been reported well below supervised models on standard NER benchmarks. [Likely]
- GLiNER (a 0.3B encoder) beats ChatGPT in zero-shot NER, where neither model saw the target datasets: average F1 60.9 against 47.5 on an out-of-domain benchmark, and 47.8 against 36.5 on a set of 20 NER datasets. It also beats UniNER-7B (53.7 and 45.7). [Certain]
- UniversalNER distilled ChatGPT’s NER ability into a 7B model trained on ChatGPT-labeled data; on a benchmark of 43 datasets across 9 domains it averages 7 to 9 F1 points above ChatGPT itself. [Certain]
The pattern: a model trained for the exact task, even a small one, beats a general model that is only asked nicely. Three reasons. The encoder sees the full context on both sides (Session 55). Its output is a span of the input, so it cannot paraphrase or invent. And the training data teach it the annotation guidelines (is “Apple Park” a place or an organization?), which are hard to explain in a prompt.
When the LLM is the right tool
The prompted LLM wins when there are no labeled data and no time to make them; when the schema changes often or is different for each customer; when the output must be normalized (dates, units, codes) or reasoned (“the earliest deadline in this contract”); when documents are long and facts are spread across pages; and when the volume is small enough that cost does not matter.
The common production answer is both, in sequence: start with a prompted, constrained LLM to ship fast and to label data; review a sample; then fine-tune a small model on those labels and serve it, with the LLM as a fallback for low-confidence cases. This is distillation (session 59), and UniversalNER is exactly this recipe at scale.
Measuring extraction
For records, the usual metric compares (field, value) pairs after normalization (lower-case, trim, parse dates). Let \(\hat{R}\) be the predicted pairs and \(R\) the gold pairs over the whole test set:
A predicted null for a field that is truly absent is a correct answer; count it. Report the schema-valid rate separately: with constrained decoding it should be 100%, and if it is not, your grammar or your parser has a bug.
Putting it together in code
The code below is deterministic and needs only PyTorch on a CPU (it runs in about a second). Part 1 is Algorithm 1 on the sentence of Figure 2. Part 2 builds the Outlines-style index of Figure 4 and runs Algorithm 3 with a toy random “language model”, with and without the mask, 1,000 times each.
import math, re, torch torch.manual_seed(0) # ---- 1) BIO tags and constrained Viterbi, formula (146.3) ---- TAGS = ["O", "B-PER", "I-PER", "B-ORG", "I-ORG", "B-LOC", "I-LOC"] words = ["Tim", "Cook", "visited", "Apple", "Park", "in", "Cupertino"] P = torch.tensor([ # p(tag | word) from a tagger (rows sum to 1) [0.04, 0.90, 0.02, 0.01, 0.01, 0.01, 0.01], [0.05, 0.03, 0.88, 0.01, 0.01, 0.01, 0.01], [0.94, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01], [0.06, 0.02, 0.02, 0.48, 0.01, 0.40, 0.01], [0.20, 0.01, 0.01, 0.01, 0.15, 0.07, 0.55], [0.94, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01], [0.10, 0.02, 0.01, 0.10, 0.01, 0.70, 0.06]]) def allowed(prev, cur): # I-X only after B-X or I-X return not cur.startswith("I-") or prev[2:] == cur[2:] and prev != "O" A = torch.tensor([[0.0 if allowed(p, c) else -math.inf for c in TAGS] for p in TAGS]) start = torch.tensor([-math.inf if t.startswith("I-") else 0.0 for t in TAGS]) def viterbi(logp, A, start): T, K = logp.shape d = start + logp[0]; back = [] for t in range(1, T): s = d[:, None] + A + logp[t][None, :] # s[i, j]: best path ending i -> j d, arg = s.max(0); back.append(arg) path = [int(d.argmax())] for arg in reversed(back): path.append(int(arg[path[-1]])) return path[::-1], float(d.max()) def spans(tags): out, cur = [], None for i, t in enumerate(tags + ["O"]): if cur and (t == "O" or t.startswith("B-") or t[2:] != cur[0]): out.append((cur[0], " ".join(words[cur[1]:i]))); cur = None if t.startswith("B-") or (t.startswith("I-") and cur is None): cur = (t[2:], i) return out logp = P.log() greedy = [TAGS[i] for i in logp.argmax(1)] vpath, vscore = viterbi(logp, A, start) vit = [TAGS[i] for i in vpath] print("greedy :", greedy, round(float(logp.max(1).values.sum()), 3)) print("viterbi:", vit, round(vscore, 3)) print("spans :", spans(vit)) # ---- 2) a token mask from a DFA for integers -?(0|[1-9][0-9]*), formula (146.6) ---- def step(q, ch): # states: 0 start, 1 after '-', 2 after '0', 3 digits; None = dead if q in (0, 1) and ch == "0": return 2 if q in (0, 1) and ch in "123456789": return 3 if q == 0 and ch == "-": return 1 if q == 3 and ch.isdigit(): return 3 return None ACCEPT = {2, 3} VOCAB = ["-", "0", "7", "42", "-5", "05", "100", "-0", "3a", "--", "}"] # "}" ends the number def walk(q, tok): for ch in tok: q = step(q, ch) if q is None: return None return q index = {q: [v for v, tok in enumerate(VOCAB) if (tok == "}" and q in ACCEPT) or (tok != "}" and walk(q, tok) is not None)] for q in range(4)} # built once, before decoding print({q: [VOCAB[v] for v in vs] for q, vs in index.items()}) W = torch.randn(4, len(VOCAB)) * 2.0 # a toy "LM": logits depend on the state only def decode(constrained, g): q, out = 0, "" for _ in range(8): logits = W[q].clone() if constrained: mask = torch.full_like(logits, -math.inf); mask[index[q]] = 0.0 logits = logits + mask # formula (146.5) v = int(torch.multinomial(torch.softmax(logits, -1), 1, generator=g)) if VOCAB[v] == "}": return out out += VOCAB[v] q2 = walk(q, VOCAB[v]) q = q2 if q2 is not None else 0 # after an illegal token the toy LM restarts return out ok = lambda s: re.fullmatch(r"-?(0|[1-9][0-9]*)", s) is not None for c in (False, True): g = torch.Generator().manual_seed(1) outs = [decode(c, g) for _ in range(1000)] print("constrained" if c else "free ", "valid:", sum(map(ok, outs)) / 1000, outs[:5])
Output of our run: greedy gives B-ORG I-LOC for “Apple Park” with log-probability −2.045; Viterbi gives B-LOC I-LOC with −2.228 and the spans PER “Tim Cook”, LOC “Apple Park”, LOC “Cupertino”. The index is {q0: 7 tokens, q1: 0 7 42 100, q2: }, q3: 0 7 42 05 100 }}, matching Figure 4. Without the mask, 44% of the 1,000 samples are valid integers; with it, 100%. [Certain: our run]
Where this is used
| Application | Usual route | Why |
|---|---|---|
| Personal-data redaction (names, phone numbers, IDs) in logs and documents | Small encoder tagger (+ regex for fixed formats) | Huge volume, must be grounded to exact character offsets, often must run on-premise |
| Invoice, receipt and form extraction | LLM or VLM with a JSON Schema and constrained decoding; small model once labels exist | Many layouts, normalization of dates and amounts, fixed record shape |
| Function calling in agents and assistants | LLM with the tool schemas in the prompt, often constrained | A malformed call breaks the agent loop (session 154) |
| Medical, legal and financial entity extraction | Domain-tuned encoder (BIO or span), LLM for relations and normalization | Fixed label sets with expert guidelines; auditable spans |
| Search and knowledge graphs | Encoder NER + relation extraction, then entity linking | Billions of documents; cost per document decides |
| Video key-moment detection and temporal segmentation | BIO-style tags over frames or clips (“B-goal, I-goal, O”), scored with event-level F1 | The same span decoding and the same legal-transition rules, on the time axis |
| Video event logs and Video-RAG metadata | VLM writes JSON per scene (start, end, objects, action) under a schema | The index for retrieval needs typed fields, not prose; timestamps must parse |
| Text-to-SQL and code generation in a fixed language | LLM with a CFG (SQL, a DSL), constrained | Every output must parse; grammars are context-free, the XGrammar case |
Common mistakes
- Greedy argmax over BIO tags. It produces illegal sequences such as
O I-PERorB-ORG I-LOC, which scorers turn into wrong entities. Use constrained Viterbi (Algorithm 1) or a CRF head. - Required, non-nullable fields for facts that may be missing. With constrained decoding, the model must then invent a value (Figure 3). Allow
null, and test on documents where the field is absent. - Answer fields before reasoning. Key order is generation order. If the model must think, put the reasoning field first, or constrain only the final step.
- Trusting valid JSON. Schema-valid means parseable, not correct. Ground string values in the source text and measure field-level F1 (formula 146.9) on labeled data.
- Using JSON mode when you need a schema. A “JSON mode” that only guarantees syntax still allows missing fields and wrong types. Use full schema-constrained decoding, and check which JSON Schema features your engine supports; unsupported keywords may be silently ignored. [Likely]
- Unbounded whitespace or strings in the grammar. If the grammar allows any amount of whitespace, a model can keep emitting spaces or newlines until the token limit. Limit whitespace and set
maxLengthwhere you can. [Likely] - Rebuilding the grammar for every request. Compiling a schema into an automaton and its index takes much longer than one decode step. Cache compiled grammars by schema.
- Choosing a 70B LLM for a fixed-label, high-volume job without computing formula (146.8). For fixed entity types with a few thousand labels, train the small model first.
Interview questions
What is BIO tagging, and how many tags does a scheme with E entity types have?basic
B-X begins an entity of type X, I-X continues it, O is outside. With \(E\) types there are \(2E + 1\) tags (9 for CoNLL-2003). BIOES adds end and single tags, \(4E + 1\) in total. A linear head on an encoder predicts one tag per token (formula 146.1), trained with token-level cross-entropy on the first subword of each word.Your tagger outputs “B-ORG I-LOC”. What went wrong and how do you fix it at inference time?core
I-LOC may only follow B-LOC or I-LOC. Fix it with constrained Viterbi decoding: a transition matrix with 0 for legal and \(-\infty\) for illegal pairs, plus a start rule forbidding I- tags, and dynamic programming (formula 146.3) to find the most probable legal sequence, at \(O(TK^2)\) cost. In Figure 2 this turns ORG “Apple” + LOC “Park” into the correct LOC “Apple Park”. A learned version of \(A\) is a CRF layer.How do you guarantee that an LLM returns JSON that matches a schema?core
Explain how Outlines turns a regular expression into a token mask efficiently.advanced
Why do nested JSON and recursive schemas need more than a regex, and how does XGrammar keep it fast?advanced
Can constrained decoding make answers worse? Give two concrete ways.core
What is function calling, mechanically?basic
You must extract 4 entity types from 50 million short documents per day. Which model do you choose?core
When would you pick a prompted LLM over a fine-tuned tagger?core
How can structured output be faster than free-text generation?advanced
", "age": ), the system can append the whole string without a model step. SGLang’s compressed FSM merges these single-path transitions (jump-forward decoding), so fixed scaffolding costs no decode steps; only the variable values need the model. Care is needed at the boundary to re-tokenize the inserted text.How do you evaluate an extraction system?basic
Exercises
- A BIOES scheme is used for 6 entity types. How many tags? How large is the transition matrix \(A\)?
- In Figure 2, set \(p(\text{B-ORG} \mid \text{Apple}) = 0.70\). What do greedy and Viterbi output for “Apple Park”? Check in the figure.
- One prompted try returns valid JSON with probability 0.75. How many tries (at most) do you need for at least 99% validity, assuming independence? What is the expected number of tries with no limit?
- A grammar allows two first tokens, A and B. The model gives \(p(A) = 0.6\), \(p(B) = 0.4\). After A, valid continuations have total probability 0.05; after B, 0.9. (a) With the mask, how often does the constrained sampler choose A? (b) What is \(p(A \mid \text{valid})\) under the true conditional? Use formula (146.7).
- Using the DFA of Figure 4, list the allowed tokens from q1 among: “-”, “0”, “05”, “-5”, “100”, “}”.
- Formula (146.8): an 8B LLM, a 300M encoder, \(L = 300\), \(L_p = 800\), \(L_o = 80\). What is the compute ratio?
Answerscheck
B-ORG I-LOC, read as ORG “Apple” + LOC “Park”. Viterbi: \(0.70 \cdot 0.20 = 0.140\) for B-ORG O against \(0.18 \cdot 0.55 = 0.099\) for B-LOC I-LOC, so B-ORG O: ORG “Apple”. (0.70 is above the 0.645 switch point.) 3. \(1 - 0.25^k \ge 0.99\) needs \(0.25^k \le 0.01\): \(k = 4\) (\(0.25^3 = 0.0156\), \(0.25^4 = 0.0039\)). Expected tries \(1/0.75 = 1.33\). 4. (a) The mask allows both first tokens, so A is chosen 60% of the time, and then forced to some valid continuation. (b) \(P(\text{valid}) = 0.6 \cdot 0.05 + 0.4 \cdot 0.9 = 0.03 + 0.36 = 0.39\), so \(p(A \mid \text{valid}) = 0.03/0.39 = 0.077\). The constrained sampler over-picks A by almost 8 times. 5. “0” and “100” (q1 has read “-”; “05” dies after the 0 because q2 accepts nothing more, “-5” has a second minus, “}” is not allowed in a non-accepting state). 6. \(\frac{8\text{B}}{300\text{M}} \cdot \frac{1180}{300} = 26.7 \times 3.93 \approx 105\).Key takeaways
- Extraction turns text into a fixed shape: entities, relations, events, records, function calls. Grounded, fixed-label tasks suit taggers; normalized, open-schema tasks suit generators.
- BIO tagging (146.1, 146.2) has illegal tag sequences; constrained Viterbi (146.3) finds the best legal one at \(O(TK^2)\) cost.
- Prompted JSON plus validate-and-retry only raises the odds of valid output (146.4). Grammar-constrained decoding (146.5) makes it certain by masking forbidden tokens.
- Regex grammars become a DFA with a precomputed state-to-tokens index (146.6, Outlines); nested JSON needs a pushdown automaton, made fast by caching context-independent tokens (XGrammar, under 40 µs per token).
- Valid is not correct: the mask distorts the distribution (146.7) and can force invented values. Use nullable fields, evidence fields, and reasoning before answers.
- For fixed labels at high volume, a small fine-tuned encoder is cheaper by orders of magnitude (146.8) and often more accurate; use the LLM to label data and distill. Measure with field-level F1 (146.9).
Key formulas
References for this session
- Devlin et al. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
- Willard & Louf (2023). Efficient Guided Generation for Large Language Models
- Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
- Devlin et al. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
- Willard & Louf (2023). Efficient Guided Generation for Large Language Models
- Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
- Tjong Kim Sang & De Meulder (2003). Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition
- Lafferty, McCallum & Pereira (2001). Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
- Lample et al. (2016). Neural Architectures for Named Entity Recognition
- Zaratiana et al. (2023). GLiNER: Generalist Model for Named Entity Recognition using Bidirectional Transformer
- Zhou et al. (2023). UniversalNER: Targeted Distillation from Large Language Models for Open Named Entity Recognition
- Tam et al. (2024). Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models
- Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
- Schick et al. (2023). Toolformer: Language Models Can Teach Themselves to Use Tools