Prompting Is Programming: A Query Language for Large Language Models

In plain words

Prompting a language model usually means writing a block of text, sending it, reading the reply, and then pasting pieces of that reply into the next prompt by hand or with ad-hoc glue code. Each reply is free text, so if your program needs a single word or a number, you have to check it and retry when it is wrong.

This paper proposes writing the whole interaction as a small program instead. A prompt is a template with blanks. Each blank is filled by the model, and the program can rule on what each blank may contain, such as a maximum length or a fixed list of options. The program can also loop, branch, and call ordinary functions, for example a calculator. The language is called LMQL.

The runtime does the costly part. Before the model picks each next piece of text, it works out which pieces could still satisfy the rules and hides the rest. Wrong continuations are then never generated, which saves calls to the model. The paper reports this saving on three example tasks.

TL;DR

LMQL is a query language for LLMs that combines text templates with scripting and output constraints. Its runtime computes token masks from the constraints, so invalid continuations are not generated. The authors report fewer model calls and billable tokens than a chunk-wise generate() baseline in three case studies, with accuracy unchanged or slightly higher where measured. The results come from open models on research benchmarks, not from production traffic.

Problem

Interactive prompting, where a program reads model output and feeds it back into later prompts, is hard to write with high-level APIs. Those APIs return text, not tokens, so they cannot constrain a generation mid-sentence §1 §2.2. Without that control, a program either accepts malformed output or generates chunk by chunk, parsing and backtracking. Both cost extra model calls §2.2 §6.2.

The paper assumes a model whose next-token distribution the runtime can read and mask. Its implementation depends on access to the decoding loop, so it does not work with APIs that expose only text completions §6 app. A.

Method

Language. An LMQL program has five parts: a decoder, a query body, a from clause naming the model, a where clause with constraints, and an optional distribute clause §3. The query body is Python-like code with two kinds of string escape. "{name}" inserts a previously set variable, and "[NAME]" marks a hole that the model fills and whose result is stored in NAME §3 §4.

Built-in predicates. Constraints are Python expressions over hole variables. The built-ins are words(...), sentences(...), len(...) and stops_at(VAR, "phrase"), plus in tests and comparisons §3 §3.1 tab. 1 tab. 2.

Execution. The body runs like a Python function, with two changes. Each top-level string is appended to a trace u, and a hole triggers decoding. The procedure is given as alg. 1 §4:

# Evaluate one top-level string s  [alg. 1]
# Input:  s (string), trace u, scope (variables), LM f
# Output: updated trace u and scope

def eval_string(s, trace, scope, lm):
    # If s has a hole [NAME], decode it  [alg. 1]
    if has_hole(s):
        # Split s into text before, the variable name and text after  [alg. 1]
        before, name, after = unpack(s)
        trace = trace + before
        # Let the LM fill the hole, using the trace as prompt  [alg. 1]
        value = decode(lm, trace)
        scope[name] = value
        trace = trace + value
    # If s has a placeholder {NAME}, substitute its stored value  [alg. 1]
    elif has_placeholder(s):
        value = scope[unpack(s)]
        trace = trace + substitute(s, value)
    # Otherwise append the literal text  [alg. 1]
    else:
        trace = trace + s
    return trace, scope

The paper notes that a string may contain several holes and placeholders; the algorithm is written for one §4.

Decoders. The paper names argmax, sample and beam §3 §4. argmax takes the most likely token at each step, sample draws from the distribution, and beam(n) keeps the n best traces. For beam, the paper describes a scripted beam search: beams are kept over all holes and the control flow they drive, and each beam runs its own query body, so different beams may take different branches §4. A query with sample(n=k) runs k traces in lock-step so model calls can be batched §4.

Token masks. This is the core contribution §5. Each where predicate is evaluated on the partial value of a hole after every token, using two abstractions.

• Final semantics annotates each value as Fin (fixed), Var (may still change), Inc (only grows) or Dec (only shrinks). The rules for each operator are in tab. 1. A predicate with final value Fin(False) can be rejected at once, even before the hole is complete §5.1.
• Follow maps predict, for a candidate next token t, what a predicate will evaluate to after t. The rules for the core operators are in tab. 2. For example, if the hole is "Steph" and the constraint is TEXT in ["Stephen Hawking"], only tokens that continue the phrase "en Hawking" keep the predicate possibly true §5.2.

The mask for the next token is built from the follow maps of all where predicates §5.2. Soundness is defined by the equation below. It guarantees that no token that could still lead to a valid completion is masked out eq. 1 §5.2:

\forall t \in V:\ \mathrm{Follow}[e](u,t) = \mathrm{Fin}(\bot) \;\Rightarrow\; \mathrm{eval}_{v \leftarrow ut}[e] = \mathrm{Fin}(\bot) \qquad [\text{eq. 1}]

The paper proves this as Theorem 1 (Brzozowski soundness): the masked-in set contains every token that still admits a legal continuation §5.2.

Masked decoding. The decoding loop used for each hole is alg. 2 §4. It is the standard loop with one extra step, the mask. The softmax over the vocabulary is §2.1:

\mathrm{softmax}(z)_i = \frac{\exp(z_i)}{\sum_j \exp(z_j)}

# Decode one hole under constraints  [alg. 2]
# Input:  trace u, scope, LM f
# Output: decoded string v

def decode_hole(trace, scope, lm):
    # Start with an empty value  [alg. 2]
    value = ""
    while True:
        # Ask which next tokens keep every where-predicate alive  [§5.2]
        mask = compute_mask(trace, scope, value)
        # Stop if no token is allowed  [alg. 2]
        if no_token_allowed(mask):
            break
        # Renormalise the masked distribution over allowed tokens  [alg. 2]
        probs = masked_softmax(lm(trace + value), mask)
        # Pick a token with argmax, sampling or the beam rule  [§4]
        token = pick(probs)
        # End of sequence finishes the hole  [alg. 2]
        if token == EOS:
            break
        value = value + token_text(token)
    return value

When all masks are zero, Algorithm 2 breaks out and returns the partial value. The paper says that case means no legal answer was found alg. 2 §4.

Eager validation and backtracking. Predicates are checked on every new token, so a bad continuation is caught early §5.1. Where follow maps cannot express a constraint exactly, the runtime backtracks instead §5.2.

Cost model. The paper counts model queries (one per next-token call), decoder calls (one per new decoding loop, including one per scored distribute value), and billable tokens, meaning prompt plus generated tokens per decoder call §6, Metrics.

Implementation. The runtime is a Python library. A client parses the query, builds a computation graph, runs the decoding loop, and sends only the forward pass to a model server. Custom operators provide forward, final and follow methods app. A.1 app. A.2. A web playground shows the decoder graph and mask state app. A.3.

Hyperparameters

Runtime defaults in the released code, which may differ from the paper's experiments:

• argmax: max_len = 2048 decoders.py
• sample: temperature = 1, n = 1, max_len = 2048 decoders.py
• beam: n = 4 decoders.py

Results

Author-reported. Setups are as stated in the paper; no numbers were rerun.

Case study 1, chain-of-thought (GPT-J-6B and OPT-30B, Odd One Out and Date Understanding; BIG-bench tasks) tab. 3

Decoder calls fall by 25.11% (Odd One Out) and 30.47% (Date Understanding) tab. 3. The estimated saving is 0.63 cents per query (Odd One Out) and 2.57 cents per query (Date Understanding) at the 2022 price tab. 3.

A control on GPT-3.5 (text-davinci-003) is given in the text only, not in a table: Odd One Out accuracy 42.86% for both, and Date Understanding 85.29% (standard) versus 86.10% (LMQL) §6.1.

Lines of code tab. 4: Odd One Out 34 to 9; Date Understanding 38 to 13; arithmetic 59 to 22; ReAct 78 to 18.

Case study 2, interactive ReAct on HotpotQA tab. 5 §6.2, chunk-size figure

Estimated saving: 5.2 cents per query. The chunk-size figure plots the baseline at chunk sizes 20, 30, 40 and 50. Billable tokens are 4069, 3404, 3474 and 3534 and model queries are 120, 150, 200 and 250; LMQL stays at 95 queries and 807 tokens §6.2. Accuracy is not reported for this case study.

Case study 3, arithmetic on one GSM8K problem (GPT-J-6B) tab. 5

Estimated saving: 6.2 cents per query. The paper reports one example and says GPT-J does not solve it correctly; no accuracy is reported §6.3.

Paper vs code

Checked against the official repository eth-sri/lmql at fc8edd4457dc5a5e4e595302166bec797582bf53 (linked from the paper's implementation section and further-resources section). The code has evolved since the paper, so the mismatches below are between the paper's text and this commit.

• beam is not the paper's scripted search. The paper defines beam(n) as a scripted beam search over holes and control flow §4. In the code, the name beam is registered for a plain token-level beam_search with n = 4 decoders.py. The variable-local search is beam_var decoders.py and topk_var_continuations, which takes the method "beam" decoders.py. I did not run either path, so I cannot say which one matches the paper's scripted beam search.
• stops_at does not prune tokens in the code. Table 2 gives stop_at a follow rule that can mask tokens tab. 2. In the code, StopAtOp.follow returns ("*", True), which allows every token ops.py. The phrase check runs in stop() as a stopping criterion ops.py. So stops_at ends a hole but does not narrow the mask.
• Empty mask. Algorithm 2 stops the hole when no token is allowed alg. 2. The code's create_mask returns an EOS-only mask when the allowed set is empty node.py. I did not trace whether the where clause then rejects that EOS.
• Mask computation site. The paper's compute_mask is realised as where_step_for_sequence, which builds the follow map and calls create_mask interpreter.py.
• Decoder defaults. argmax and sample default to max_len = 2048 decoders.py decoders.py. The paper does not give the sampling temperature or beam width for its evaluation §6.
• ReAct decoder. The paper's text says the baseline uses chunk size 30 and compares against LMQL §6.2. The LMQL ReAct listing uses sample, not argmax §6.2 listing. The paper does not say which decoder produced the reported ReAct numbers.
• Allowed decoder names. The query builder accepts argmax, sample, beam, beam_var, var and best_k query_builder.py. The paper's beam and the code's beam may not mean the same thing (see first bullet).
• Licence. The repository's LICENSE is Apache-2.0 [LICENSE, first lines] (licence of the code only; the paper is CC BY 4.0).

No other discrepancies were checked.

Pitfalls

• Headline numbers disagree. The abstract says "26-85%" cost savings. The introduction and conclusion say "26-80%" or "up to 80%" §1 §8. Table 5 reaches 84.93% for arithmetic billable tokens. The text of §6.1 says model queries fall "by up to 41%", but Table 3 shows 43.16% to 44.86% §6.1 tab. 3. Quote the table, not the summary.
• Cost figures are old. The dollar estimates use the 2022 davinci price of $0.02 per 1K tokens §6 Metrics. The cent figures in the tables are cents per query at that price, not current prices.
• Token masks are sound, not complete. A follow map may allow tokens that lead nowhere. Constraints with forward references may need backtracking §5.2. The paper says this matches the expressiveness limits of context-free parsing §5.2.
• Subtoken prefixes need a vocabulary scan. To mask a phrase like "en Hawking", the runtime must scan the whole vocabulary for tokens that are prefixes of the phrase, because one string has several tokenisations §5.2.
• Constraints change the answer. The paper notes that forcing a model to generate under constraints changes its reasoning, so accuracy can move in either direction §6.1. Odd One Out gained 1.19 points for GPT-J and none for OPT-30B.
• Evaluation is small and under-specified. The paper reports no dataset sizes, number of runs, seeds, temperature or beam width for the main tables §6. The arithmetic result is one problem §6.3. The authors name the lack of a user study as a threat to their usability claims §6.4.
• Latency claims are design-level. The paper says mask computation can run in lock-step with the model and that speculative prediction helps when the model is remote §4 Performance. These are not measured in the tables.
• Scope of the savings. The reductions come from fewer model calls and fewer billable tokens against a chunk-wise generate() baseline with manual parsing §6. They do not compare against other constrained-decoding libraries.
• Execution safety. A query runs Python code, and the paper says queries should be sandboxed if a vendor accepts them app. A. The ReAct example calls an external Wikipedia helper §6.2 listing.
• Model access. The method needs access to the model's decoding loop, so it fits open models you can run yourself. The paper evaluates GPT-3 only in a limited way because the OpenAI API does not provide that access §6.

Lineage

• Builds on: Chain-of-thought prompting, the reasoning pattern that the Odd One Out and arithmetic queries implement §6.1 §6.3; ReAct, the interactive-prompting scheme of case study 2 §6.2; PAL, which runs generated arithmetic in an interpreter, related in §7.
• Related, not carded: Shin et al. 2021 (constrained semantic parsing with handcrafted decoders), PICARD (constrained code generation), and LangChain (prompt chaining without token-level constraints) §2.2 §7.
• Compared against: Hugging Face transformers generate(), chunk-wise, with manual parsing §6.
• Superseded by: none recorded on this wiki.