XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models

• URL: http://arxiv.org/abs/2411.15100v1
• Date: Fri, 22 Nov 2024 18:01:37 GMT
• Title: XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
• Authors: Yixin Dong, Charlie F. Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, Tianqi Chen,
• Abstract summary: Context-free grammar is a flexible approach to enable structured generation via constrained decoding. XGrammar is a flexible and efficient structure generation engine for large language models. XGrammar can achieve up to 100x speedup over existing solutions.
• Score: 3.9417976759908573
• License:
• Abstract: The applications of LLM Agents are becoming increasingly complex and diverse, leading to a high demand for structured outputs that can be parsed into code, structured function calls, and embodied agent commands. These developments bring significant demands for structured generation in LLM inference. Context-free grammar is a flexible approach to enable structured generation via constrained decoding. However, executing context-free grammar requires going through several stack states over all tokens in vocabulary during runtime, bringing non-negligible overhead for structured generation. In this paper, we propose XGrammar, a flexible and efficient structure generation engine for large language models. XGrammar accelerates context-free grammar execution by dividing the vocabulary into context-independent tokens that can be prechecked and context-dependent tokens that need to be interpreted during runtime. We further build transformations to expand the grammar context and reduce the number of context-independent tokens. Additionally, we build an efficient persistent stack to accelerate the context-dependent token checks. Finally, we co-design the grammar engine with LLM inference engine to overlap grammar computation with GPU executions. Evaluation results show that XGrammar can achieve up to 100x speedup over existing solutions. Combined with an LLM inference engine, it can generate near-zero overhead structure generation in end-to-end low-LLM serving.

Related papers

• COrAL: Order-Agnostic Language Modeling for Efficient Iterative Refinement [80.18490952057125]
  Iterative refinement has emerged as an effective paradigm for enhancing the capabilities of large language models (LLMs) on complex tasks. We propose Context-Wise Order-Agnostic Language Modeling (COrAL) to overcome these challenges. Our approach models multiple token dependencies within manageable context windows, enabling the model to perform iterative refinement internally.
  arXiv  Detail & Related papers  (2024-10-12T23:56:19Z)
• ULLME: A Unified Framework for Large Language Model Embeddings with Generation-Augmented Learning [72.90823351726374]
  We introduce the Unified framework for Large Language Model Embedding (ULLME), a flexible, plug-and-play implementation that enables bidirectional attention across various LLMs. We also propose Generation-augmented Representation Learning (GRL), a novel fine-tuning method to boost LLMs for text embedding tasks. To showcase our framework's flexibility and effectiveness, we release three pre-trained models from ULLME with different backbone architectures.
  arXiv  Detail & Related papers  (2024-08-06T18:53:54Z)
• Struct-X: Enhancing Large Language Models Reasoning with Structured Data [38.558614152006975]
  Struct-X operates through five key phases: read-model-fill-reflect-reason'' It encodes structured data into a topological space using graph embeddings. It fills in missing entity information with knowledge retrieval modules. The final phase involves constructing a topological network with selected tokens.
  arXiv  Detail & Related papers  (2024-07-17T13:06:25Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• A Simple but Effective Approach to Improve Structured Language Model Output for Information Extraction [11.165093163378152]
  Large language models (LLMs) have demonstrated impressive abilities in generating unstructured natural language according to instructions. This paper introduces an efficient method, G&O, to enhance their structured text generation capabilities.
  arXiv  Detail & Related papers  (2024-02-20T20:42:02Z)
• Efficient Guided Generation for Large Language Models [0.21485350418225244]
  We show how the problem of neural text generation can be constructively reformulated in terms of transitions between the states of a finite-state machine. This framework leads to an efficient approach to guiding text generation with regular expressions and context-free grammars.
  arXiv  Detail & Related papers  (2023-07-19T01:14:49Z)
• COLLIE: Systematic Construction of Constrained Text Generation Tasks [33.300039566331876]
  COLLIE is a grammar-based framework that allows the specification of rich, compositional constraints with diverse generation levels. We develop tools for automatic extraction of task instances given a constraint structure and a raw text corpus. We perform systematic experiments across five state-of-the-art instruction-tuned language models and analyze their performances to reveal shortcomings.
  arXiv  Detail & Related papers  (2023-07-17T17:48:51Z)
• Grammar Prompting for Domain-Specific Language Generation with Large Language Models [40.831045850285776]
  Large language models (LLMs) can learn to perform a wide range of natural language tasks from just a handful of in-context examples. We propose emphgrammar prompting, a simple approach to enable LLMs to use external knowledge and domain-specific constraints.
  arXiv  Detail & Related papers  (2023-05-30T17:26:01Z)
• Adapting Language Models to Compress Contexts [71.98287002918941]
  Transformer-based language models (LMs) are powerful and widely-applicable tools, but their usefulness is constrained by a finite context window. We propose to adapt pre-trained LMs into AutoCompressors, which are capable of compressing long contexts into compact summary vectors. We fine-tune OPT and Llama-2 models on sequences of up to 30,720 tokens and show that AutoCompressors can utilize long contexts to improve perplexity.
  arXiv  Detail & Related papers  (2023-05-24T06:42:44Z)
• Inference with Reference: Lossless Acceleration of Large Language Models [97.04200102556551]
  LLMA is an accelerator to speed up Large Language Model (LLM) inference with references. It is motivated by the observation that there are abundant identical text spans between the decoding result by an LLM and the reference that is available in many real world scenarios.
  arXiv  Detail & Related papers  (2023-04-10T09:55:14Z)
• GATE: Graph Attention Transformer Encoder for Cross-lingual Relation and Event Extraction [107.8262586956778]
  We introduce graph convolutional networks (GCNs) with universal dependency parses to learn language-agnostic sentence representations. GCNs struggle to model words with long-range dependencies or are not directly connected in the dependency tree. We propose to utilize the self-attention mechanism to learn the dependencies between words with different syntactic distances.
  arXiv  Detail & Related papers  (2020-10-06T20:30:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.