PaperlayerView exact revision on arXiv

Source-linked AI summary

Prompting Is Programming: A Query Language for Large Language Models

Luca Beurer-Kellner, Marc Fischer, Martin Vechev

arXiv:2212.06094v3cs.CLcs.AI

TL;DR

Specialized prompting with language models can require model-specific implementations and manual interaction, despite their broad task performance. The paper introduces Language Model Programming and LMQL, which combine natural-language prompts with scripting and output constraints. Across case studies, LMQL retained or slightly improved accuracy while reducing inference cost and latency by 26-80%, with costs reduced by up to 80%.

  • Problem

    Effective specialized prompting can require manual interaction, model-internal knowledge, and task-specific implementations for constraints and multi-step workflows.

  • Method

    Language Model Programming combines natural-language prompting with scripting and constraints, implemented by LMQL as a high-level, model-compatible query language and runtime.

  • Results

    Across case studies, LMQL reduced inference cost and latency by 26-80% while retaining or slightly improving task accuracy.

  • Takeaways & Limitations

    LMQL expresses complex prompting techniques as concise programs and automates interactive flows without requiring human-in-the-loop interaction.

  • Takeaways & Limitations

    Sound token masking may over-approximate valid tokens, so some constraints cannot be enforced eagerly and require backtracking.

Abstract

from arXiv · show

Large language models have demonstrated outstanding performance on a wide range of tasks such as question answering and code generation. On a high level, given an input, a language model can be used to automatically complete the sequence in a statistically-likely way. Based on this, users prompt these models with language instructions or examples, to implement a variety of downstream tasks. Advanced prompting methods can even imply interaction between the language model, a user, and external tools such as calculators. However, to obtain state-of-the-art performance or adapt language models for specific tasks, complex task- and model-specific programs have to be implemented, which may still require ad-hoc interaction. Based on this, we present the novel idea of Language Model Programming (LMP). LMP generalizes language model prompting from pure text prompts to an intuitive combination of text prompting and scripting. Additionally, LMP allows constraints to be specified over the language model output. This enables easy adaption to many tasks while abstracting language model internals and providing high-level semantics. To enable LMP, we implement LMQL(short for Language Model Query Language), which leverages the constraints and control flow from an LMP prompt to generate an efficient inference procedure that minimizes the number of expensive calls to the underlying language model. We show that LMQL can capture a wide range of state-of-the-art prompting methods in an intuitive way, especially facilitating interactive flows that are challenging to implement with existing high-level APIs. Our evaluation shows that we retain or increase the accuracy on several downstream tasks, while also significantly reducing the required amount of computation or cost in the case of pay-to-use APIs (26-85% cost savings).

1 INTRODUCTION

Language models support many language-based tasks, but using them effectively for specialized prompting can require model-specific knowledge, manual interaction, and costly implementation. Language Model Programming and LMQL address these challenges by combining scripting, output constraints, and efficient decoding in a high-level, model-agnostic interface.

  • Motivation: Language models predict token sequences for tasks including translation, summarization, question answering, reasoning, and code generation.They have become popular beyond machine learning and are being integrated into applications.
  • Challenges: Effective task-specific prompting can require understanding model internals, vendor-specific implementations, tokenization, and manual interaction.These requirements make legal-word constraints and interactive or tool-assisted prompting difficult to implement.
  • Approach: Language Model Programming combines natural-language prompting with lightweight scripting and output constraints.It separates the user-facing prompt specification from language-model internals and supports complex interactions and control flow.
  • Approach: LMQL provides a high-level query language and runtime with declarative constraints, imperative scripting, and compatibility with existing language models.Its runtime requires only a simple change to decoder logic and can express many existing prompting methods concisely.
  • Evaluation: 26-80% lower inference cost and latency was reported while retaining or slightly improving task accuracy across the evaluation.The evaluation is presented as evidence that LMQL programs can express prompting techniques concisely and execute efficiently.

2 OVERVIEW: LANGUAGE MODEL PROGRAMMING

Language models generate token sequences through decoding, while prompting methods add examples, composition, interaction, and external tools. Language Model Programming with LMQL expresses these workflows through scripting and constraints, reducing manual interaction and helping control outputs and inference cost.

  • Background: Language Models: Language models tokenize word inputs into sub-word sequences and predict scores for every possible next token.Softmax converts these scores into a probability distribution over the token vocabulary.
  • Background: Language Models: Decoding repeatedly applies the model to extend a token sequence until an end-of-sequence token or another stopping criterion is reached.Greedy decoding selects the highest-probability next token at each step but need not maximize the sequence’s overall probability.
  • Background: Language Models: Masked decoding restricts generation to viable tokens, supporting tasks such as classification, code completion, and synthesis under a grammar.The mask is applied element-wise to the next-token distribution before decoding.
  • Background: Prompting: Few-shot prompting supplies examples in the prompt so broadly trained language models can perform downstream tasks without task-specific training.The paper illustrates this with example translation pairs followed by a new translation request.
  • Key Challenges: Multi-part prompting can require manually completing one model-generated value, inserting it into a later prompt, and invoking the model again.Meta prompting illustrates this interaction by generating an expert name before asking for the expert’s answer.
  • Key Challenges: Generated text may violate required formats through digressions or awkward continuations, while expressing human-level constraints can require tokenization and decoder expertise.Such outputs are especially problematic when another computer system must process them.
  • Key Challenges: Cloud-hosted and paid language-model APIs make repeated querying costly in computational and financial terms.Efficiency and performance therefore remain practical challenges for language-model use.
  • Language Model Programming in LMQL: LMQL represents multi-part prompts with variables, scripted control flow, and declarative constraints enforced during decoding.This removes manual extraction and reinsertion of intermediate values and supports token-level inference masks with partial evaluation.

3 THE LMQL LANGUAGE

LMQL programs combine query strings, Python-like control flow, model selection, output constraints, and optional distribution instructions. The language also exposes decoding results and built-in functions for manipulating generated text.

  • Program structure: An LMQL program has five parts: decoder, query, model, constraints, and an optional distribution instruction.The query and constraints use Python syntax, while the decoder and model are specified as strings.
  • Query structure: Query blocks model interactions as restricted Python-like code whose top-level strings directly query a language model.String fields can recall variables and reference hole variables from the query scope.
  • Decoding: Decoders support argmax, sample, and scripted beam search, returning interaction traces and access to individual hole variables.Sampling and beam decoding can return n traces with their corresponding variables.
  • Constraints: Where-clause constraints restrict hole variables using comparisons, membership checks, and deterministic pure Python functions.Constraints can be combined with conjunctions or disjunctions and can be referenced by the query program.
  • Built-in functions: A distribution clause evaluates the final variable over a specified support instead of decoding it directly.The runtime returns the preceding interaction trace and a likelihood for each supported value.
  • Built-in functions: LMQL built-in functions include operations that split generated text into words or sentences and detect whether text ends at a specified token or string.These operations are listed as words, sentences, and stop_at.

4 THE LMQL RUNTIME: QUERY EXECUTION & DECODING

The LMQL runtime executes query programs while decoding model outputs, tracking parallel traces for multiple results and enforcing legal-token constraints through masks. It supports beam execution, model integration through token distributions, caching, parallel evaluation, and speculative prediction for remote models.

  • Query execution: LMQL executes the query like a Python program while maintaining an interaction trace initialized to the empty string.The runtime assumes functions are pure and deterministic.
  • Decoding: Decoding stops at an end-of-sequence token or when constraints leave no legal tokens available.Returning early indicates that no response satisfying the constraints can be found.
  • Parallel decoding: For multiple samples or beams, LMQL tracks parallel query executions and batches model calls in lockstep.This allows calls to the underlying model to be batched for improved efficiency.
  • Scripted beam search: Scripted beam search retains the top n beams while executing each beam's query independently, including potentially different control flow.Discarded interaction traces are pruned and not extended further.
  • Language-model integration: LMQL integrates language models through access to next-token distributions and can therefore support models exposed through compatible generation interfaces.The implementation uses the Hugging Face generate() function and supports models from its repository.
  • Performance considerations: Pure deterministic functions can be cached, while constraint evaluation, control flow, and token-mask computation can run in parallel with model prediction.For remote models, asynchronous token masking and speculative prediction help reduce network-induced latency.
  • Masked decoding: At each decoding step, LMQL computes a vocabulary mask that permits only tokens forming legal sequences, then renormalizes the masked distribution.The selected token depends on the decoding algorithm, such as argmax, sampling, or beam search.

5 VALIDATION AND CONSTRAINT DECODING

LMQL extends constrained decoding with eager partial evaluation and lookahead, allowing invalid continuations to be detected or masked before full sequences are generated. Final semantics and FollowMaps provide the abstractions for early validation and sound token-mask construction, while some constraints still require backtracking.

  • Naive Approach: Backtracking-based constrained decoding is computationally expensive because language-model continuations form a combinatorial search space and model queries can be costly.The naive procedure generates sequences through end-of-sequence before checking constraints, potentially backtracking across multiple holes.
  • Eager Partial Evaluation: Eager partial evaluation can terminate validation early and prune tokens guaranteed to violate a constraint before they are generated.The approach evaluates whether constraints can still hold and computes a subset of next tokens that definitively lead to violation.
  • Final Semantics: Final semantics annotate expression values as fixed, variable, monotonically increasing, or monotonically decreasing during decoding.These annotations support reasoning about partially generated outputs and enable more aggressive short-circuiting.
  • FollowMaps: FollowMaps approximate future expression values after a candidate token and recursively compose these approximations into a mask for the full validation expression.Tokens whose continuation is guaranteed to violate the expression are excluded from decoding.
  • Soundness and Limitations: The Brzozowski Soundness theorem states that all Brzozowski-admissible tokens belong to the set of tokens not rejected by Follow-based masking.Soundness prevents masking tokens that may actually remain valid, although over-approximation can leave some constraints unenforced eagerly and require backtracking.

6 EVALUATION

The evaluation studies LMQL across multiple prompting scenarios, measuring expressiveness, efficiency, cost, and accuracy against standard high-level decoding interfaces. Across case studies, LMQL generally maintains or improves accuracy while reducing model queries, billable tokens, decoder calls, and program size.

  • Evaluation criteria: LMQL is assessed for expressiveness, performance, and accuracy against a generate()-based baseline.The baseline lacks token-level validation and requires manual parsing, validation, and chunk-wise generation.
  • Chain-of-Thought Prompting: LMQL achieves the same or better accuracy than standard decoding in chain-of-thought experiments.The enforced word-limit and disallowed-token constraints alter reasoning outputs and can improve final answers on Odd One Out.
  • Chain-of-Thought Prompting: 41% fewer model queries and 31% fewer billable tokens are achieved in the chain-of-thought comparison.LMQL also reduces program size to 26% or 34% of the corresponding baseline implementation, depending on the task.
  • Control experiment: On GPT-3.5, LMQL maintains Odd One Out accuracy at 42.86% and improves Date Understanding from 85.29% to 86.10%.These results provide a control comparison using the text-davinci-003 model.
  • Interactive Prompting: Up to 80% fewer decoder calls and at least 30% fewer model queries are observed for LMQL on interactive HotpotQA prompting.LMQL validates while decoding one sequence, whereas standard decoding repeatedly generates chunks around interactions.
  • Interactive Prompting: LMQL saves up to 76% of billable tokens, corresponding to 5.2¢, and implements ReAct in 22 lines of code.The LMQL implementation uses 63% fewer lines than the Python implementation.
  • Arithmetic Reasoning: LMQL processes arithmetic expressions on the fly and requires one decoder call versus seven for standard decoding.The GSM8K example demonstrates external arithmetic evaluation and integer-constrained final output, although GPT-J 6B does not solve the problem correctly.

7 RELATED WORK

Related work covers prompting techniques and output-constrained language-model applications. It positions LMQL alongside methods for reasoning, interaction, aggregation, semantic parsing, and code generation.

  • Language Model Programming: Prior prompting methods include chain-of-thought, interactive question answering, self-consistency, ThinkSum, and Iterated Decomposition.Program-aided chain-of-thought methods additionally give language models access to an interpreter for tasks such as arithmetic.
  • Constraining Language Models: Earlier constraint-based approaches target interpretable language subsets, semantic parsing, and syntactically or semantically valid source-code generation.These methods often address specific output domains rather than providing a general prompting-and-scripting language.

8 CONCLUSION

The paper concludes that Language Model Programming and LMQL provide concise, intuitive, and efficient ways to implement complex prompting techniques. Its case studies report compute-cost reductions of up to 80%.

  • Conclusion: LMQL implements complex state-of-the-art prompting techniques as intuitive, concise, and efficient programs.The conclusion presents LMQL as a high-level query language enabled by purpose-designed evaluation semantics.
  • Conclusion: Up to 80% compute-cost reduction is demonstrated across the paper’s case studies.The reported evidence supports efficient query execution for the implemented prompting techniques.

FURTHER RESOURCES

The paper releases its evaluated artifact, updated codebase, extended paper version, and project webpage with a live demonstration.

  • Further Resources: The released resources include the evaluated artifact, an up-to-date LMQL codebase, an extended paper version, and a project webpage.The webpage includes a live demonstration.

A.1 Language Runtime

LMQL is implemented as a Python superset whose programs are transformed into executable Python functions and runtime computational graphs. This design supports interrupted execution and extensible evaluation operators.

  • LMQL extends Python, using Python’s tokenizer and parser while parsing query subexpressions as standard Python.Basic program transformations produce a Python function that interacts with the LMQL runtime and supports interrupted execution through yield and async semantics.
  • LMQL transforms Python abstract syntax trees into computational graphs that explicitly model dependencies among operations.The runtime representation implements eager evaluation semantics.
  • Custom LMQL operators can be added through a simple interface defining forward, final, and follow functions.The interface is described as similar to custom-operator integration in PyTorch.

A.2 Model Integration

LMQL separates client-side program handling and decoding from server-side model inference through a client-server architecture. Its decoding integration compiles prompting and output constraints into token-level prediction masks with minimal changes to existing decoders.

  • The LMQL server loads and manages the model, while the Python client parses LMQL code, constructs the computational graph, and runs the decoding loop.The current implementation is configured to use a specific HuggingFace Transformers model, with only the forward pass handled by the server.
  • LMQL’s client-server separation permits inference-as-a-service support through a vendor-provided inference API or direct execution of LMQL code.Direct code execution would give customers more control over decoding than standard APIs.
  • LMQL scripted prompting and output constraints compile into token-level prediction masks that existing decoders can apply through an additional runtime hook.The paper demonstrates compatibility by adapting the HuggingFace Transformers decoding loop.
  • The LMQL visual debugger is presented as a screenshot of the LMQL Playground.

A.3 Playground and Visual Debugger

The LMQL Playground provides a web-based environment for constructing, compiling, executing, and debugging LMQL programs. Its visual debugger exposes decoding branches, prompt state, constraint validation, and masking behavior during execution.

  • The web-based playground supports constructing and debugging LMQL programs, with a hosted version available at lmql.ai/playground.The playground complements command-line tooling.
  • Editor and Compiler: The editor lets users write LMQL queries and inspect the generated Python compiler output after execution.The output includes code for constructing the computational graph and executing the prompt.
  • Decoder Graph: The debugger displays active decoding branches, including parallel sampling and multi-branch methods such as beam search.Users can inspect subtokens, interaction traces, prompt-variable values, and where-clause validation at each decoder step.
  • Validation and Masking: The where-clause graph exposes expression values, partial evaluation, Final and Follow semantics, and per-operation FollowMaps.Green and red shades distinguish final and non-final True and False values.
Loading 2212.06094v3…