Forem: delimitter

Type-Guided Constrained Decoding: How to Stop LLMs from Hallucinating Code

delimitter — Fri, 03 Apr 2026 08:18:05 +0000

From GBNF Grammars to Type-Directed Generation: Guarantees Instead of Hope

Who this is for. If you've ever had ChatGPT generate code that doesn't compile — this article explains how to eliminate that completely. All technical terms explained in footnotes and the glossary at the end.

In previous articles, we showed that reducing tokens saves money, energy, and compute. But there's a more serious problem: LLMs generate incorrect code. And every retry doubles the token spend.

The Scale of the Problem

Type errors account for 33.6% of all failures in LLM-generated code (Mündler et al., PLDI 2025¹). These aren't typos — they're structural errors: wrong argument types, incompatible return values, accessing nonexistent fields.

When an LLM generates a sort function that doesn't compile, the cost doubles — either a human fixes it (time) or an agent retries (tokens).

But what if the model physically cannot generate syntactically invalid code?

Three Levels of Constraints

Level 1: Grammar (Syntactic Correctness)

At each generation step, the set of grammatically² valid tokens is determined. All others are masked — probability set to zero.

Example: if the model just generated [, then the next token can be a number, identifier, ], or [ — but not +, not =, not ).

Tools:

XGrammar³ — default backend in SGLang⁴, vLLM, TensorRT-LLM⁵. Works with context-free grammars (CFG⁶). Approaches zero overhead.
Outlines⁷ — structured generation via finite state machines (FSM⁸). Supports regex and CFG.
llama.cpp⁹ — built-in GBNF grammar¹⁰ support.
Guidance (Microsoft) — template-based generation with constraints.

Result: 100% syntactic correctness. Every generated fragment is a valid program.

Level 2: Types (Semantic Correctness)

Grammar guarantees that f x = x + 1 is syntactically valid. But not that x is a number. Type-constrained decoding¹¹ adds a second layer: only tokens compatible with the current type context are allowed.

Mündler et al. (PLDI 2025) showed that type-constrained decoding reduces compilation errors by 74.8% compared to 9.0% for syntax-only constraints.

This requires type inference¹² — so the compiler can determine valid types at every generation point without explicit annotations.

Level 3: Specification (Logical Correctness)

The most powerful level: constraints based on formal specification. A sort function doesn't just have the right type — it actually sorts. This is an area of active research (dependent types, refinement types). Not yet in production tools.

How XGrammar Works

XGrammar's key optimization: splitting the vocabulary into two classes:

Context-independent tokens (~80%+). Validity determined at preprocessing, before generation. For each grammar state, a bitmask of valid tokens is precomputed. O(1) per token.

Context-dependent tokens (~20%). Validity depends on the current PDA¹³ state. Checked at runtime, but few in number.

Result: near-zero overhead. Constrained decoding adds no measurable overhead to TPOT¹⁴.

BPE Misalignment Breaks Constrained Decoding

This is where language design becomes critical.

When a language grammar isn't aligned to BPE boundaries, constrained decoding faces the bridge token problem — a BPE token spanning two grammatical symbols.

Domino (ICML 2024¹⁵) showed that bridge tokens distort the model's probability distribution. Grammar-Aligned Decoding (NeurIPS 2024¹⁶) formalized the problem and proposed a fix — but with added overhead.

If a language is designed so bridge tokens never arise — every grammatical symbol coincides with one BPE token — the problem disappears entirely.

Deterministic CFG = Zero Overhead

Nondeterministic CFG — when parsing, multiple rules may apply. Requires backtracking¹⁷. Expensive.

Deterministic CFG (DCFG)¹⁸ — exactly one rule applies at each step. Compiles to an FSM. No backtracking. No ambiguity.

Tian et al. (CoLM 2024¹⁹) proved that for DCFGs, constrained decoding compiles in closed form — overhead approaches zero.

If a language has a DCFG grammar with BPE-aligned operators, constrained decoding is free: zero overhead + zero bridge tokens.

In Practice: GBNF Grammar

root    ::= program
program ::= (decl newline)* decl newline?
decl    ::= func-def | type-sig | type-def

func-def ::= lower-id ws (pattern ws)* "=" ws expr
cond-expr ::= "?" ws expr ws "->" ws expr ws ":" ws expr

Plugging into SGLang:

response = client.chat.completions.create(
    model="default",
    messages=[{"role": "user", "content": "Write factorial"}],
    extra_body={"ebnf": open("synoema.gbnf").read()},
)
# Result: GUARANTEED syntactically valid code

Or llama.cpp:

./main -m model.gguf --grammar-file synoema.gbnf \
  -p "-- Quicksort:" -n 128 --temp 0.2

The Economic Impact

Lever	Mechanism	Savings
BPE-aligned grammar	46% fewer tokens	-46% direct
Quadratic attention	54% length → 29% cost	-71% on attention
Constrained decoding	0 invalid code → 0 retries	-10–30%
Type constraints	-74.8% type errors	-5–15% additional

Combined: 50–70% savings in cost and energy vs unoptimized Python generation.

What's Next

In the next article, we'll introduce Synoema — a language with all three levers: BPE-aligned grammar (33 single-token operators), Hindley-Milner²⁰ type inference, and Cranelift²¹ JIT for native speed.

Series: Token Economics of Code

Why Every Token Costs More Than You Think
The Anatomy of BPE: Why Python Wastes 46% of Tokens
Type-Guided Constrained Decoding: How to Stop LLMs from Hallucinating Code ← you are here
Compilation for LLMs: Cranelift JIT, 4.4× Faster Than Python (coming soon)
Hindley-Milner for LLMs: Type Inference Without Annotations (coming soon)
Show HN: Synoema — The First Programming Language Designed for LLMs (coming soon)
The Future of Code Generation: From Prompts to Compilation (coming soon)

Glossary

Term	Explanation
Constrained decoding	Technology forbidding invalid tokens during generation. Guarantees correctness
XGrammar	Constrained decoding engine, de facto standard for LLM inference
SGLang	Open-source LLM inference engine from UC Berkeley
vLLM	Open-source LLM inference engine with memory optimization
TensorRT-LLM	NVIDIA's inference engine, fastest on their GPUs
GBNF	Grammar description format for llama.cpp
llama.cpp	Popular project for running LLMs on commodity hardware
CFG	Context-Free Grammar — formal grammar describing language syntax
DCFG	Deterministic CFG — unambiguous parsing, enables zero-overhead constraints
FSM	Finite State Machine — model for fast token validity checking
PDA	Pushdown Automaton — FSM with a stack for nested structures
TPOT	Time Per Output Token — main LLM inference speed metric
Bridge token	BPE token spanning two grammar symbol boundaries
Type inference	Automatic type deduction by the compiler, no annotations needed
Hindley-Milner	Most powerful type inference algorithm. Used in Haskell, OCaml
Cranelift	Rust-based compiler backend. Fast JIT compilation to native code
PLDI / ICML / NeurIPS	Top academic conferences on PL, ML, and AI respectively
Backtracking	Parsing by trial-and-error with rollbacks. Slow but universal

PLDI (Programming Language Design and Implementation) — one of the most prestigious academic conferences on programming languages. Papers undergo rigorous peer review. If a result is published at PLDI, it's trustworthy. ↩
Formal grammar — a set of rules describing which sequences of symbols are valid in a language. For example, "after [, the next symbol can be a number, identifier, or ]" is part of a grammar. Python has a complex grammar (hundreds of rules); JSON has a simple one (~10 rules). ↩
XGrammar — constrained decoding engine from the MLC-AI team. The de facto standard for LLM inference. Its key innovation: splitting the vocabulary into "easy" tokens (80%+, checked at preprocessing) and "hard" tokens (20%, checked at runtime), yielding near-zero overhead. ↩
SGLang — open-source LLM inference engine from UC Berkeley. One of the fastest ways to serve LLMs. Supports constrained decoding via XGrammar out of the box. ↩
TensorRT-LLM — NVIDIA's inference engine, optimized for their GPUs. Fastest on NVIDIA hardware, but complex to set up. ↩
CFG (Context-Free Grammar) — a class of grammars where each rule has the form "symbol → sequence of symbols." Most programming languages are described by CFGs. JSON, XML, HTML, Python, JavaScript all have CFGs. ↩
Outlines — open-source library for structured generation. Compiles a grammar or regex into a finite state machine that filters tokens on the fly. ↩
FSM (Finite State Machine) — a mathematical model that at any moment is in one of a finite number of states and transitions between them on input symbols. Used for fast checking of whether the next token is valid. ↩
llama.cpp — the most popular open-source project for running LLMs on commodity hardware (CPU, Mac M1/M2, budget GPUs). Written in C++, works without Python. Supports GBNF grammars for constrained decoding. ↩
GBNF (GGML BNF) — grammar description format used in llama.cpp. Extension of standard Backus-Naur Form. Example: expr ::= number | expr "+" expr. ↩
Type-constrained decoding — an extension of constrained decoding that checks types in addition to grammar. If a function expects Int, the model can't substitute String. Requires type inference — automatic type deduction by the compiler. ↩
Type inference — the compiler's ability to determine types of all expressions automatically, without programmer annotations. Instead of int add(int x, int y) (as in C), you write just add x y = x + y, and the compiler deduces Int → Int → Int. The most powerful type inference algorithm is Hindley-Milner, used in Haskell and ML. ↩
PDA (Pushdown Automaton) — an extension of a finite state machine with a stack. Needed for grammars with nesting (brackets, code blocks). A regular FSM can't count brackets — a PDA can. ↩
TPOT (Time Per Output Token) — the time to generate one output token. The main metric for LLM inference speed. For GPT-4: ~20–30 ms; for small models on powerful GPUs: 5–10 ms. ↩
ICML (International Conference on Machine Learning) — one of the top three ML conferences (with NeurIPS and ICLR). Publication at ICML signals high-quality research. ↩
NeurIPS (Neural Information Processing Systems) — the largest AI/ML conference. ~15,000 attendees annually. Publication at NeurIPS is the gold standard for ML research. ↩
Backtracking — a parsing method where the parser tries one rule, and if it fails, backtracks and tries another. Slow because the same text may be parsed multiple times. ↩
DCFG (Deterministic Context-Free Grammar) — a subclass of CFG where parsing is unambiguous at every step. Compiles to an efficient automaton. Most real programming languages are DCFGs (or close). Python technically isn't due to indentation, but with the offside rule it approximates one. ↩
CoLM — a newer conference at the intersection of language models and formal methods. Focuses on how compiler theory can improve LLMs. ↩
Hindley-Milner — the most powerful automatic type inference algorithm, developed in the 1960s–80s. Allows the compiler to determine types of all expressions without a single annotation. Used in Haskell, OCaml, F#, Elm. Detailed in the fifth article. ↩
Cranelift — a compiler backend written in Rust. Converts intermediate representation (IR) to native machine code (x86-64, ARM). Alternative to LLVM: compiles 10× faster, though generated code is ~14% slower. Ideal for JIT compilation where compilation speed matters more than peak optimization. ↩

The Anatomy of BPE: Why Python Wastes 46% of Tokens

delimitter — Thu, 02 Apr 2026 15:11:31 +0000

How BPE Tokenization Works and What It Means for Language Design

Who this is for. If you want to understand how ChatGPT "sees" your code and why the same program costs different amounts in different languages — read on. All terms explained in footnotes and the glossary at the end.

In the previous article, we established that inference cost grows quadratically with token count. The natural question: can we reduce token count without losing semantics?

To answer that, we need to understand how LLMs see code. Not as text — as a sequence of tokens. And between how a programmer sees def factorial(n): and how GPT-4 sees it, there's a chasm.

How BPE Works

BPE (Byte Pair Encoding)¹ is the algorithm that converts text into sequences of integers (tokens). It underlies all modern LLMs: GPT-4 uses the cl100k_base² vocabulary, Claude uses a modified BPE, and Llama uses SentencePiece³ BPE.

The algorithm is simple:

Start with an alphabet of individual bytes (256 characters).
Find the most frequent pair of adjacent symbols in the corpus⁴.
Create a new symbol for that pair and add it to the vocabulary.
Repeat steps 2–3 until the desired vocabulary size (~100K).

The result is a vocabulary of ~100,000 "subwords" of variable length. Short, frequent words (the, is, def) encode as a single token. Rare words get split: tokenization → token + ization.

The critical property: BPE is trained on natural language, not code. So it's optimized for English prose, not Python syntax.

The Misalignment Problem

The grammatical units of a programming language — operators, keywords, delimiters — don't align with BPE token boundaries. This creates two types of waste.

Type 1: Redundant tokens on syntax.

Take a simple Python function:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

BPE (cl100k_base) splits this into 29 tokens. Semantically significant: factorial, n, 0, 1, *, -. The remaining 23 tokens are syntactic overhead: def, spaces, (, ), :, if, ==, return (twice), indentation, newlines.

The equivalent program in a minimal-syntax functional language:

fac 0 = 1
fac n = n * fac (n - 1)

16 tokens. Same semantics. 45% fewer.

Type 2: Bridge tokens⁵.

Sometimes a single BPE token spans two grammatical symbols. For example, "name" in JSON may become one token, even though grammatically it's space + quote + identifier + quote. This creates problems for constrained decoding⁶.

Benchmark: 12 Programs, 3 Languages

I compared token counts for equivalent programs in three languages: Python, Haskell⁷, and an optimized language where every operator is exactly one BPE token.

Program	Optimized	Python	Haskell	Saving vs Python
Factorial	16	29	16	45%
Map	20	42	23	52%
QuickSort	51	83	54	39%
FizzBuzz	44	64	49	31%
Filter	27	67	36	60%
Fibonacci	26	46	26	43%
Sum	16	33	19	52%
Length	16	30	19	47%
Reverse	18	35	18	49%
Compose	38	75	39	49%
Maximum	28	58	37	52%
Zip	32	53	37	40%
Total	332	615	373	46%

The optimized language uses 46% fewer tokens than Python, and 11% fewer than Haskell.

Given quadratic attention cost: 46% fewer tokens ≈ 71% less computation in attention layers.

Where the Savings Come From

Function Definition

# Python: 6 tokens of boilerplate
def add(x, y):
    return x + y

# Optimized: 0 boilerplate tokens
add x y = x + y

Conditional

# Python: 6 overhead tokens
if x > 0:
    return x
else:
    return -x

# Optimized: 3 tokens
? x > 0 -> x : -x

Lists

[1, 2, 3, 4, 5]  # 9 tokens (commas are waste)
[1 2 3 4 5]       # 7 tokens (no commas needed)

Pattern Matching⁸

# Python: 29 tokens
def fac(n):
    if n == 0:
        return 1
    return n * fac(n - 1)

# Optimized: 16 tokens
fac 0 = 1
fac n = n * fac (n - 1)

BPE-Aligned Grammar

The savings above aren't just "terse syntax." They're achieved through deliberate grammar design accounting for BPE tokenizer properties.

The BPE-aligned grammar⁹ principle: every language operator must be exactly one BPE token.

For the optimized language, all 33 operators were verified — each encodes to exactly 1 BPE token on cl100k_base (GPT-4/Claude) and o200k_base¹⁰ (GPT-4o):

Two chars, 1 token:    -> <- |> ++ >> == != <= >= && || ..
One char, 1 token:     ? : . = @ | \ _ , + - * / % < >
Delimiters, 1 token:   ( ) [ ]

This isn't coincidence — it's a design constraint. If an operator doesn't fit in one BPE token, it gets replaced by one that does.

What This Means for LLMs

When an LLM generates code in the optimized language instead of Python, it generates 46% fewer tokens (faster, cheaper), spends 71% less on attention (larger codebases fit), creates no bridge tokens (cleaner constrained decoding), and can't "babble" (minimal syntax prevents bloat).

What's Next

In the next article, we'll look at constrained decoding — the technology that guarantees 100% syntactic correctness. And we'll show why BPE-aligned grammar makes constrained decoding free.

Series: Token Economics of Code

Why Every Token Costs More Than You Think
The Anatomy of BPE: Why Python Wastes 46% of Tokens ← you are here
Type-Guided Constrained Decoding: How to Stop LLMs from Hallucinating Code (coming soon)
Compilation for LLMs: Cranelift JIT, 4.4× Faster Than Python (coming soon)
Hindley-Milner for LLMs: Type Inference Without Annotations (coming soon)
Show HN: Synoema — The First Programming Language Designed for LLMs (coming soon)
The Future of Code Generation: From Prompts to Compilation (coming soon)

Glossary

Term	Explanation
BPE	Byte Pair Encoding — algorithm splitting text into tokens by merging frequent character pairs
cl100k_base	GPT-4/Claude's BPE vocabulary with ~100K tokens
o200k_base	GPT-4o's newer BPE vocabulary with ~200K tokens
SentencePiece	Google's BPE alternative used in Llama and open models
Corpus	Massive text dataset for training BPE and LLMs (web, books, code)
Bridge token	BPE token spanning the boundary of two grammar symbols
BPE-aligned grammar	Grammar where every operator = exactly 1 BPE token
Pattern matching	Defining functions by examples: `fac 0 = 1` instead of `if n == 0`
Constrained decoding	Technology forbidding invalid tokens during generation
Haskell	Functional language with minimal syntax, brevity benchmark

BPE (Byte Pair Encoding) — a text compression algorithm invented in 1994 and adapted for LLMs. The idea: find the most frequent pairs of characters in a huge text corpus and merge them into a new symbol. Repeat ~100,000 times. The result is a vocabulary of "subwords" that the model thinks in. ↩
cl100k_base — the specific BPE token vocabulary used by GPT-4 and Claude. Contains ~100,000 tokens. Trained primarily on English internet text. GPT-4o uses a newer vocabulary called o200k_base with ~200,000 tokens. ↩
SentencePiece — Google's alternative BPE implementation, used in Llama and other open models. Works at the Unicode character level instead of bytes, which is better for non-English languages. ↩
Corpus — the massive text dataset used to train the BPE vocabulary (and the LLM itself). Includes web pages, books, articles, GitHub code. Usually hundreds of billions of tokens. Code makes up only ~5–15% of a typical corpus — which is why BPE is optimized for English prose, not Python syntax. ↩
Bridge token — a BPE token that spans the boundary between two grammatical symbols. For example, BPE might merge a space and keyword if into one token. This creates problems for constrained decoding engines, which must "split" the token, distorting the model's probability distribution. More details in the third article. ↩
Constrained decoding — technology that forbids invalid tokens at each generation step. Guarantees syntactically valid output. Covered in detail in the third article. ↩
Haskell — a functional programming language with minimal syntax. Used as the "brevity benchmark" among existing languages. fac 0 = 1 in Haskell and the optimized language look nearly identical, but the optimized language additionally accounts for BPE boundaries. ↩
Pattern matching — defining a function by "examples." Instead of if n == 0: return 1, you write fac 0 = 1 — literally: "factorial of zero is one." The compiler generates the check automatically. Shorter, clearer, and eliminates an entire class of errors. ↩
BPE-aligned grammar — a language design principle where every operator, keyword, and delimiter encodes to exactly one BPE token. This means: no "wasted" tokens on syntax and no bridge tokens. Conventional languages don't account for BPE — they were created long before LLMs. ↩
o200k_base — the newer BPE vocabulary used by GPT-4o. Contains ~200,000 tokens (twice cl100k_base). Better coverage of code and non-English languages, but same underlying principles. ↩

Why Every Token Costs More Than You Think

delimitter — Thu, 02 Apr 2026 15:07:06 +0000

Why Every Token Costs More Than You Think

The Quadratic Price of Attention: How Context Length Is Killing Your AI Budget

Who this is for. If you use ChatGPT, Claude, Copilot, or Cursor to write code, this article explains why the same tasks can cost 2–4× less. No technical background required — all terms are explained inline and in the glossary at the end.

When you ask Claude or GPT to write a sorting function, the model generates ~50 tokens¹ per second. Each token costs fractions of a cent. Seems cheap.

But behind that simplicity lies an engineering reality most people overlook: the cost of each token grows quadratically with context length². If you're working with codebases spanning thousands of lines, this quadratic relationship transforms from a theoretical abstraction into a line item that can double your AI budget.

In this article, I'll show where this cost comes from, why inference — not training — is the dominant consumer of resources, and what can be done about it.

Inference Consumes 90%+ of All Energy

There's a common misconception: the major cost of LLMs³ is training. Training GPT-4 reportedly cost $50–100M. An impressive number.

But training is a one-time capital expense. Inference⁴ is an ongoing operational cost that occurs with every request, every second, for every user.

According to AWS, inference consumes more than 90% of total energy in the LLM lifecycle. The AI inference market is valued at $106 billion in 2025, projected to exceed $250 billion by 2030 at a 19.2% compound annual growth rate.

Every token ChatGPT generates costs OpenAI approximately $0.00012. Sounds negligible. But at billions of daily requests, this adds up to hundreds of millions of dollars per year — and terajoules of electricity.

The Quadratic Trap

Here's the key fact that changes everything.

In a standard transformer⁵ with self-attention⁶, the computational cost of processing a sequence of n tokens is:

Cost(n) = O(n² · d)

where d is the model dimension. This is not a linear relationship. It's quadratic.

What this means in practice:

Context	Relative attention cost
1,000 tokens	1× (baseline)
2,000 tokens	4×
4,000 tokens	16×
8,000 tokens	64×
32,000 tokens	1,024×

Doubling the context increases attention cost fourfold, not twofold. This means reducing context by 50% saves not 50%, but 75% of attention computation.

When a developer sends a 2,000-line Python file (~8,000 tokens) to an LLM for refactoring, the attention cost is 64× higher than for a simple 1,000-token question. And that's just one request.

Real Money

Let's calculate for a typical team.

A team of 10 developers uses an AI assistant (Cursor, Copilot, Claude Code). Each makes an average of 100 requests per day. Average request context: 2,000 input tokens. Average response: 500 output tokens.

At Claude Sonnet 4 pricing ($3/M input, $15/M output):

Input:  10 × 100 × 2,000 = 2M tokens/day × $3/M  = $6/day
Output: 10 × 100 × 500   = 500K tokens/day × $15/M = $7.50/day
Total: ~$13.50/day = ~$405/month

Now imagine expressing the same programs with 46% fewer tokens (I'll show in the next article that this is achievable):

Input:  2M × 0.54 = 1.08M tokens/day × $3/M  = $3.24/day
Output: 500K × 0.54 = 270K tokens/day × $15/M = $4.05/day
Total: ~$7.29/day = ~$219/month

Savings: $186/month for 10 people, or $2,200/year.

For 100 developers: $22,000/year. For 1,000: $220,000. And this is a conservative estimate with a relatively affordable model and moderate workload.

The Energy Dimension

Measurements on LLaMA-65B⁷ (A100 GPUs⁸) show energy consumption in the range of 3–4 joules per output token. On modern H100s with optimized inference engines like vLLM⁹, efficiency has improved roughly 10×, down to ~0.39 J per token. But usage scale has grown even faster.

ChatGPT processes an estimated one billion requests daily. At an average response of 500 tokens:

1B requests × 500 tokens × 0.39 J ≈ 195 GJ/day ≈ 54,000 kWh/day

That's the energy consumption of a small town — every single day. Reducing token count isn't just about saving money. It's a direct reduction in energy consumption and carbon footprint.

The Babbling Problem

The study "Towards Green AI" (2026) found that 3 out of 10 tested models exhibit "babbling" behavior — generating significantly more text than necessary. Suppressing this yielded energy savings of 44% to 89%.

But what if the language the LLM writes code in is designed so that "babbling" is physically impossible?

Python code is inherently verbose. def, return, if/elif/else, commas in lists — all syntactic overhead¹⁰ that consumes tokens without carrying semantic information.

Three Optimization Levers

Lever 1: Representation compression. Express the same program with fewer tokens. This isn't obfuscation — it's grammar design optimized for BPE tokenizers¹¹. Potential: 35–50%.

Lever 2: Constrained decoding¹². Prevent the model from generating syntactically invalid code. Every error = retry = double token spend.

Lever 3: Type guarantees. Type errors account for 33.6% of all failures in LLM-generated code. Type-guided generation¹³ reduces them by 74.8%.

Combining all three levers can yield 60–80% cumulative savings in tokens, money, energy, and time.

What's Next

In the next article, we'll examine how BPE tokenization actually works and why Python syntax wastes 46% of tokens on structural noise.

Series: Token Economics of Code

Why Every Token Costs More Than You Think ← you are here
The Anatomy of BPE: Why Python Wastes 46% of Tokens (coming soon)
Type-Guided Constrained Decoding: How to Stop LLMs from Hallucinating Code (coming soon)
Compilation for LLMs: Cranelift JIT, 4.4× Faster Than Python (coming soon)
Hindley-Milner for LLMs: Type Inference Without Annotations (coming soon)
Show HN: Synoema — The First Programming Language Designed for LLMs (coming soon)
The Future of Code Generation: From Prompts to Compilation (coming soon)

Glossary

Term	Explanation
Token	Smallest text unit for an LLM. Roughly ¾ of a word or 3–4 characters
LLM	Large Language Model — neural network that generates text/code (GPT-4, Claude, Llama)
Inference	Generating a response from a trained model. Happens with every request
Context	Everything the model "sees" — prompt, chat history, files. Measured in tokens
Transformer	Neural network architecture underlying all LLMs. Uses attention mechanism
Self-attention	Mechanism where every token considers all others. Cost: O(n²)
BPE	Byte Pair Encoding — algorithm that splits text into tokens
Constrained decoding	Technology forbidding invalid tokens during generation
GPU	Graphics card for AI computation. NVIDIA H100 is standard for LLM inference
vLLM	Open-source engine for fast LLM serving
Overhead	Parts of code/computation carrying no useful payload

Token — the smallest unit of text an LLM processes. Not a letter, not a word, but a "chunk" of text 1–15 characters long. The word "hello" is 1 token; the code def factorial(n): is 6 tokens. The model doesn't see characters — it sees a sequence of tokens. ↩
Context (context window) — everything the model "sees" at once: your question, previous messages, attached files. Measured in tokens. GPT-4 has a context of up to 128K tokens, Claude up to 200K. The longer the context, the more computation the model needs. ↩
LLM (Large Language Model) — a neural network trained on massive amounts of text that can generate text, code, and answer questions. Examples: GPT-4, Claude, Llama, Gemini. ↩
Inference — the process of using an already-trained model to generate responses. When you type a prompt into ChatGPT and get an answer, that's inference. Unlike training (which happens once), inference happens billions of times per day. ↩
Transformer — the neural network architecture underlying all modern LLMs. Invented at Google in 2017 ("Attention Is All You Need" paper). Its key feature is the "attention" mechanism, which lets the model consider relationships between any words in the text, even distant ones. ↩
Self-attention — a mechanism where every token "looks at" every other token in the context to understand their relationships. This gives transformers their power — but also creates quadratic cost: if there are n tokens, there are n × n pairs to compare. ↩
LLaMA — a family of open-source language models from Meta (Facebook). Available for download and self-hosted deployment, unlike GPT-4. ↩
GPU (Graphics Processing Unit) — originally a graphics card, now used for AI computation. NVIDIA A100 and H100 are specialized GPUs for LLM inference and training. A single H100 costs ~$30–40K and draws 700 watts. ↩
vLLM — an open-source engine for fast LLM serving. Optimizes GPU memory usage through PagedAttention, enabling more simultaneous requests. ↩
Syntactic overhead — parts of code required by the language's syntax but carrying no meaning. For example, Python's def before a function definition and return before a return value are mandatory but contain no information about what the function does. ↩
BPE (Byte Pair Encoding) — the algorithm that splits text into tokens. Used in all modern LLMs. Finds the most frequent pairs of characters in a huge text corpus and merges them into new "subwords." Result: a vocabulary of ~100,000 tokens. Covered in detail in the second article. ↩
Constrained decoding — a technology that forbids the model from choosing invalid tokens at each generation step. If the model is generating JSON, it ensures brackets are closed and commas are in the right places. The same can be done for any language with a formal grammar. ↩
Type-guided generation — an extension of constrained decoding where the model is additionally prevented from generating code with type errors. A second layer of guarantees on top of syntactic ones. ↩

Forem: delimitter

Type-Guided Constrained Decoding: How to Stop LLMs from Hallucinating Code

From GBNF Grammars to Type-Directed Generation: Guarantees Instead of Hope

The Scale of the Problem

Three Levels of Constraints

Level 1: Grammar (Syntactic Correctness)

Level 2: Types (Semantic Correctness)

Level 3: Specification (Logical Correctness)

How XGrammar Works

BPE Misalignment Breaks Constrained Decoding

Deterministic CFG = Zero Overhead

In Practice: GBNF Grammar

The Economic Impact

What's Next

Series: Token Economics of Code

Glossary

The Anatomy of BPE: Why Python Wastes 46% of Tokens

How BPE Tokenization Works and What It Means for Language Design

How BPE Works

The Misalignment Problem

Benchmark: 12 Programs, 3 Languages

Where the Savings Come From

Function Definition

Conditional

Lists

Pattern Matching8

BPE-Aligned Grammar

What This Means for LLMs

What's Next

Series: Token Economics of Code

Glossary

Why Every Token Costs More Than You Think

Why Every Token Costs More Than You Think

The Quadratic Price of Attention: How Context Length Is Killing Your AI Budget

Inference Consumes 90%+ of All Energy

The Quadratic Trap

Real Money

The Energy Dimension

The Babbling Problem

Three Optimization Levers

What's Next

Series: Token Economics of Code

Glossary

Pattern Matching⁸