LLM & VLM courseBlog
146Track 6: LLM applications · session 4 of 20

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.

Time: 3 hours (reading 2 hours, exercises 1 hour)Level: IntermediateBefore this: Sessions 9, 55 and 79

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?

Figure 1. Three routes from the same sentence to the same record. Top: an encoder gives one tag per token, and the tags are turned into spans. Middle: an LLM reads the schema in its prompt and writes JSON, which may or may not parse. Bottom: the LLM writes JSON, but at every step a grammar removes the tokens that would break the structure.

The extraction tasks

All extraction tasks fill a fixed shape from free text. They differ in how complex the shape is.

TaskOutput shapeExample 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 extractionA list of (head, relation, tail)(“Apple Park”, located_in, “Cupertino”)
Event extractionA trigger word plus typed argumentsvisit(agent = “Tim Cook”, place = “Apple Park”, time = “5 May”)
Slot filling / record extractionA record with named fields (often JSON){"person": "Tim Cook", "place": "Apple Park", "date": "05-05"}
Function callingA function name plus arguments that match a schemalog_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:

\[ p(y_t = j \mid \mathbf{x}) = \softmax(W \mathbf{h}_t + \mathbf{b})_j, \qquad W \in \R^{K \times d} \tag{146.1} \]

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):

\[ \mathcal{L} = -\sum_{t \in \mathcal{T}} \log p(y_t^{\star} \mid \mathbf{x}) \tag{146.2} \]
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\):

\[ \delta_t(j) = \log p(y_t = j \mid \mathbf{x}) + \max_{i} \big( \delta_{t-1}(i) + A_{ij} \big) \tag{146.3} \]

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]

cell shade = probabilitychosen tag, legal stepchosen tag after an illegal step
Figure 2. A tagger’s output for one sentence: each column is a word, each row a tag, and each cell is \(p(\text{tag} \mid \text{word})\) from formula (146.1). The slider moves probability for “Apple” between 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.

The numbers from Figure 2

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\).

Algorithm 1: BIO tagging with constrained Viterbi decoding
  1. input: words, a fine-tuned encoder with a tag head, the tag list (\(K = 2E+1\))
  2. build \(A_{ij} = -\infty\) if tag \(j\) is I-X and tag \(i\) is neither B-X nor I-X, else 0; \(s_j = -\infty\) for every I-X // built once
  3. run the encoder; keep the log-probabilities of the first subword of each word // formula (146.1)
  4. \(\delta_1 \leftarrow s + \log p_1\)
  5. 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)
  6. take \(j^\star = \argmax_j \delta_T(j)\) and follow the stored pointers back to \(t = 1\)
  7. turn the tags into spans: open at B-X, extend on I-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:

  1. 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.
  2. JSON, but not the schema: a missing required field, an extra field, "age": "36" (a string where an integer was asked), a value outside the enum.
  3. Valid, but not grounded: a name that is not in the document, a date the model guessed.
  4. 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

\[ P(\text{valid within } k \text{ tries}) = 1 - (1 - p)^k, \qquad \E[\text{tries, no limit}] = \frac{1}{p} \tag{146.4} \]

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.

Algorithm 2: prompted extraction with validation and retry
  1. input: document, JSON Schema \(S\), maximum tries \(k\)
  2. prompt \(\leftarrow\) instructions + \(S\) + (optional) 1 to 3 worked examples + document
  3. for try \(= 1..k\):
  4.   out \(\leftarrow\) LLM(prompt), with temperature 0 // or constrained decoding, Route 3
  5.   if out parses as JSON and validates against \(S\): break
  6.   prompt \(\leftarrow\) prompt + out + “Error: ” + validator message // formula (146.4)
  7. ground every string field: find it in the document (exact, then fuzzy match); flag values that are not found
  8. 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

\[ q(v \mid y_{\lt t}) = \frac{p(v \mid y_{\lt t})\, \mathbf{1}[v \in \mathcal{A}_t]}{Z_t}, \qquad Z_t = \sum_{u \in \mathcal{A}_t} p(u \mid y_{\lt t}) \tag{146.5} \]
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.

model probability \(p\)after the mask, \(q\) (formula 146.5)forbidden by the grammar
Figure 3. Greedy constrained decoding of {"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.

Worked example: a valid output that is a hallucination

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

\[ \mathcal{A}(s) = \{\, v \in \mathcal{V} : \delta^{*}(s, \operatorname{str}(v)) \neq \text{dead} \,\} \tag{146.6} \]

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.

Figure 4. The DFA for the JSON integer -?(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]

Algorithm 3: grammar-constrained decoding
  1. input: model, tokenizer vocabulary \(\mathcal{V}\), grammar \(G\) (regex, JSON Schema or CFG)
  2. 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
  3. state \(\leftarrow\) start; \(y \leftarrow\) []
  4. repeat:
  5.   if only one string is legal next: append its tokens, advance the state, continue // jump-forward
  6.   logits \(\leftarrow\) model\((y)\) on the GPU, while the CPU builds the mask for the current state
  7.   logits\([v] \leftarrow -\infty\) for \(v \notin \mathcal{A}\); \(v \leftarrow\) sample or argmax // formula (146.5)
  8.   advance the automaton with the characters of \(v\); append \(v\); log \(Z_t\)
  9. 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:

\[ q(y) = \prod_{t} \frac{p(y_t \mid y_{\lt t})}{Z_t} = \frac{p(y)}{\prod_t Z_t} \quad \text{versus} \quad p(y \mid \text{valid}) = \frac{p(y)}{P(\text{valid})} \tag{146.7} \]

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:

\[ \frac{C_{\text{LLM}}}{C_{\text{enc}}} \approx \frac{2 N_{\text{LLM}} (L + L_p + L_o)}{2 N_{\text{enc}} L} = \frac{N_{\text{LLM}}}{N_{\text{enc}}} \cdot \frac{L + L_p + L_o}{L} \tag{146.8} \]

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.

EncoderLLM
Figure 5. Forward-pass compute per document from formula (146.8), on a log scale. This counts only the \(2N\) FLOPs per token of the weights; it ignores attention cost and the extra slowness of sequential decoding, both of which make the LLM look better than it is.
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:

\[ P = \frac{|\hat{R} \cap R|}{|\hat{R}|}, \qquad R_{\text{ec}} = \frac{|\hat{R} \cap R|}{|R|}, \qquad F_1 = \frac{2 P R_{\text{ec}}}{P + R_{\text{ec}}} \tag{146.9} \]

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

ApplicationUsual routeWhy
Personal-data redaction (names, phone numbers, IDs) in logs and documentsSmall encoder tagger (+ regex for fixed formats)Huge volume, must be grounded to exact character offsets, often must run on-premise
Invoice, receipt and form extractionLLM or VLM with a JSON Schema and constrained decoding; small model once labels existMany layouts, normalization of dates and amounts, fixed record shape
Function calling in agents and assistantsLLM with the tool schemas in the prompt, often constrainedA malformed call breaks the agent loop (session 154)
Medical, legal and financial entity extractionDomain-tuned encoder (BIO or span), LLM for relations and normalizationFixed label sets with expert guidelines; auditable spans
Search and knowledge graphsEncoder NER + relation extraction, then entity linkingBillions of documents; cost per document decides
Video key-moment detection and temporal segmentationBIO-style tags over frames or clips (“B-goal, I-goal, O”), scored with event-level F1The same span decoding and the same legal-transition rules, on the time axis
Video event logs and Video-RAG metadataVLM writes JSON per scene (start, end, objects, action) under a schemaThe index for retrieval needs typed fields, not prose; timestamps must parse
Text-to-SQL and code generation in a fixed languageLLM with a CFG (SQL, a DSL), constrainedEvery 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-PER or B-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 maxLength where 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
BIO turns spans into one label per token: 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
Each tag was chosen independently by argmax, and the pair is illegal: 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
Grammar-constrained decoding: compile the schema to an automaton, and at each step set the logits of all tokens that cannot extend a valid prefix to \(-\infty\) (formula 146.5). Then every output parses and validates by construction, as long as generation is not cut off by the token limit. Prompting plus validate-and-retry only raises the probability (formula 146.4) and adds latency for each retry. Engines: Outlines, XGrammar (used in vLLM and SGLang), llama.cpp grammars, and hosted APIs’ strict structured-output modes. [Likely for the integration details]
Explain how Outlines turns a regular expression into a token mask efficiently.advanced
The regex becomes a DFA over characters. For each DFA state \(s\), a token is allowed if walking its characters from \(s\) does not reach the dead state (formula 146.6). This set depends only on \(s\), so it is precomputed once for all states and the whole vocabulary and stored as an index. At decode time, each step is a lookup of the current state’s allowed ids plus advancing the DFA by the chosen token. The cost moves from every step to compile time, and the compiled index is cached per schema.
Why do nested JSON and recursive schemas need more than a regex, and how does XGrammar keep it fast?advanced
Arbitrary nesting needs a stack to match brackets, so it is a context-free language recognized by a pushdown automaton; the allowed set depends on the stack, not on a small finite state. XGrammar splits tokens into context-independent ones (decidable from the current grammar position alone, precomputed and cached, storing the smaller of the accepted or rejected sets) and context-dependent ones (checked at run time against the stack). For JSON with the Llama 3.1 vocabulary, fewer than 1% are context-dependent (1,134 of about 128k). With a persistent stack and CPU mask computation overlapped with the GPU forward pass, the paper reports under 40 µs per token for JSON Schema.
Can constrained decoding make answers worse? Give two concrete ways.core
Yes. (1) Forced hallucination: if the model wants to say “not present” and the schema forbids it, the mask renormalizes over the remaining tokens and outputs a confident invented value (Figure 3: 84% of the mass on “null” is thrown away, “36” gets 0.625). Fix with nullable fields and evidence fields. (2) Distortion: the per-step mask gives \(q(y) = p(y)/\prod_t Z_t\), not \(p(y)/P(\text{valid})\) (formula 146.7), so it favors paths the model did not want to complete. (3) If the schema puts answers first, the model cannot reason before committing; reported reasoning drops under strict formats. Put a reasoning field first.
What is function calling, mechanically?basic
The application passes tool definitions (name, description, JSON Schema of parameters) to the model; the chat template renders them as tokens in the prompt. The model, post-trained on tool-use examples, either replies in text or emits a structured call (tool name plus a JSON argument object) between special tokens. The application parses it, validates the arguments, runs the tool and returns the result as a new message. It is structured extraction where the record is the argument list, and constrained decoding can guarantee the arguments match the schema.
You must extract 4 entity types from 50 million short documents per day. Which model do you choose?core
A small fine-tuned encoder (BERT or DeBERTa size) with a BIO or span head. Formula (146.8): with 300-token documents, 800 tokens of prompt overhead and 80 output tokens, a 70B LLM costs about 2,500 times the FLOPs of a 110M encoder, and it also needs sequential decoding. Fixed types with labels are where fine-tuned models are strongest (BERT-large 92.8 F1 on CoNLL-2003). If labels are missing, use a constrained LLM to label a sample, review it, and distill, as UniversalNER did. Keep the LLM as a fallback for low-confidence documents.
When would you pick a prompted LLM over a fine-tuned tagger?core
No labeled data and a need to ship now; schemas that change per customer or per request; outputs that need normalization (dates, currencies, codes) or reasoning across sentences or pages; relations and events rather than flat spans; low volume. Use JSON Schema with constrained decoding, ground every string value back in the source, and measure field-level F1.
How can structured output be faster than free-text generation?advanced
When the grammar admits only one continuation (fixed keys, punctuation such as ", "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
For NER: entity-level precision, recall and F1 with exact type and span match (conlleval or seqeval), not token accuracy. For records: field-level P, R and F1 over normalized (field, value) pairs (formula 146.9), counting correct nulls. Report separately the schema-valid rate, the grounding rate (string values found in the source), and cost and latency per document. Slice by document type and by fields that are often absent.

Exercises

  1. A BIOES scheme is used for 6 entity types. How many tags? How large is the transition matrix \(A\)?
  2. 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.
  3. 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?
  4. 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).
  5. Using the DFA of Figure 4, list the allowed tokens from q1 among: “-”, “0”, “05”, “-5”, “100”, “}”.
  6. Formula (146.8): an 8B LLM, a 300M encoder, \(L = 300\), \(L_p = 800\), \(L_o = 80\). What is the compute ratio?
Answerscheck
1. \(4 \times 6 + 1 = 25\) tags; \(A\) is \(25 \times 25 = 625\) entries. 2. Greedy: 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

\[ \delta_t(j) = \log p_t(j) + \max_i \big(\delta_{t-1}(i) + A_{ij}\big), \qquad q(v \mid y_{\lt t}) = \frac{p(v \mid y_{\lt t})\,\mathbf{1}[v \in \mathcal{A}_t]}{Z_t} \]
\[ \mathcal{A}(s) = \{v : \delta^{*}(s, \operatorname{str}(v)) \neq \text{dead}\}, \qquad \frac{C_{\text{LLM}}}{C_{\text{enc}}} \approx \frac{N_{\text{LLM}}}{N_{\text{enc}}} \cdot \frac{L + L_p + L_o}{L} \]

References for this session

  1. Devlin et al. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
  2. Willard & Louf (2023). Efficient Guided Generation for Large Language Models
  3. Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
  4. Devlin et al. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
  5. Willard & Louf (2023). Efficient Guided Generation for Large Language Models
  6. Dong et al. (2024). XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
  7. Tjong Kim Sang & De Meulder (2003). Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition
  8. Lafferty, McCallum & Pereira (2001). Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
  9. Lample et al. (2016). Neural Architectures for Named Entity Recognition
  10. Zaratiana et al. (2023). GLiNER: Generalist Model for Named Entity Recognition using Bidirectional Transformer
  11. Zhou et al. (2023). UniversalNER: Targeted Distillation from Large Language Models for Open Named Entity Recognition
  12. Tam et al. (2024). Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models
  13. Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
  14. Schick et al. (2023). Toolformer: Language Models Can Teach Themselves to Use Tools