論文の概要: Earley-Driven Dynamic Pruning for Efficient Structured Decoding

• arxiv url: http://arxiv.org/abs/2506.01151v1
• Date: Sun, 01 Jun 2025 20:05:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:33.954577
• Title: Earley-Driven Dynamic Pruning for Efficient Structured Decoding
• Title（参考訳）: 効率的な構造化復号化のためのEarey-Driven Dynamic Pruning
• Authors: Xintong Sun, Chi Wei, Minghao Tian, Shiwen Ni,
• Abstract要約: 大きな言語モデル(LLM)は目覚ましい能力を示しているが、その出力が厳密な構造的制約や文法的制約に適合することを保証することは依然として困難である。 そこで本稿では,Earey アルゴリズムをベースとした新しい手法を提案し,無効あるいは冗長なEarey 状態をリアルタイムに識別・排除する。 既存の最適化も取り入れたFormatronと呼ばれる制約付きデコードエンジンを実装した。
• 参考スコア（独自算出の注目度）: 6.905994258490735
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) have shown remarkable capabilities, yet ensuring their outputs conform to strict structural or grammatical constraints remains challenging, which is critical in function calls and domain-specific language (DSL) generation. Constrained decoding with context-free grammar is a flexible approach to guarantee LLMs' adherence to a specific format by dynamically building a token logits mask. However, creating this mask requires checking the validity of all tokens in the LLM vocabulary at every decoding step, which often incurs significant overheads in existing constrained decoding engines. To address this challenge, we propose $\textbf{ZapFormat}$, a novel $\textbf{dynamic pruning}$ strategy based on the Earley algorithm that identifies and eliminates invalid or redundant Earley states in real-time, significantly reducing memory occupation of the Earley algorithm's states. This further enables us to use a state cache to speed up structured generations on a large number of queries. We implemented ZapFormat in a new constrained decoding engine called Formatron which also incorporates existing optimizations. Through comprehensive experiments on structured generation tasks, including JSON generation, JSON Schema validation, and semantic parsing, we demonstrate that Formatron not only $\textbf{consistently maintains}$ high-precision compliant outputs but also achieves $\textbf{significant improvements}$ in inference speed up to 2x compared to state-of-the-art implementations. More importantly, Formatron is generally applicable across various LLM architectures. We release Formatron as open source at https://github.com/Dan-wanna-M/formatron.
• Abstract（参考訳）: 大規模言語モデル(LLM)は目覚ましい機能を示しているが、その出力が厳密な構造的制約や文法的制約に適合することを保証することは、依然として困難であり、関数呼び出しやドメイン固有言語(DSL)生成において重要である。 文脈自由文法による制約付き復号法は、トークンロジットマスクを動的に構築することにより、LLMが特定のフォーマットに忠実であることを保証する柔軟な手法である。 しかし、このマスクを作成するには、全ての復号ステップでLLM語彙の全てのトークンの妥当性を確認する必要がある。 この課題に対処するために、Eareyアルゴリズムに基づく新しい$\textbf{ZapFormat}$戦略である$\textbf{dynamic pruning}$を提案する。 これにより、ステートキャッシュを使用して、多数のクエリで構造化世代を高速化することができます。 我々は、既存の最適化を取り入れた、Formatronと呼ばれる新しい制約付きデコードエンジンにZapFormatを実装した。 JSON生成、JSONスキーマバリデーション、セマンティックパースといった構造化された生成タスクに関する包括的な実験を通じて、Formatronが$\textbf{consistently maintains}$高精度準拠の出力を得るだけでなく、$\textbf{significant Improvement}$推論速度を最先端の実装の2倍に向上することを示した。 さらに重要なのは、Formatronは様々なLLMアーキテクチャに適用可能であることだ。 Formatronはhttps://github.com/Dan-wanna-M/formatron.comでオープンソースとして公開しています。

関連論文リスト

• Type-Constrained Code Generation with Language Models [51.03439021895432]
  本稿では,型システムを利用してコード生成を誘導する型制約デコード手法を提案する。 そこで本研究では,新しい接頭辞オートマトンと,在来型を探索する手法を開発し,LLM生成コードに適切な型付けを強制するための健全なアプローチを構築した。 提案手法は,コード合成,翻訳,修復作業において,コンパイルエラーを半分以上削減し,機能的正しさを著しく向上させる。
  論文  参考訳（メタデータ） (2025-04-12T15:03:00Z)
• Flexible and Efficient Grammar-Constrained Decoding [5.671312847528642]
  文法制約付き復号法(GCD)は、LLM出力がそのような規則と一致することを保証できる。 既存のGCDアルゴリズムでは、共通文法を前処理するのに何分もかかる。 本稿では,既存の手法よりも17.71倍高速なオフライン前処理を実現するGCDアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-07T17:35:17Z)
• XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models [3.9417976759908573]
  文脈自由文法は制約付き復号化による構造化生成を可能にするフレキシブルなアプローチである。 XGrammarは、大規模言語モデルのための柔軟で効率的な構造生成エンジンである。 XGrammarは、既存のソリューションで最大100倍のスピードアップを達成することができる。
  論文  参考訳（メタデータ） (2024-11-22T18:01:37Z)
• SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications [9.143856130336783]
  投機的復号化は、大規模言語モデル(LLM)推論の遅延を低減するために広く採用されている。 エージェントフレームワークは、同様のサブタスクを実行するマルチエージェントパイプラインや、アウトプットを反復的に拡張するセルフリファインメントループなど、反復的な推論要求を送信します。 本稿では,効率的な接尾辞木を用いて長いトークン列をキャッシュする新しい手法であるemphSuffixDecodingを紹介する。
  論文  参考訳（メタデータ） (2024-11-07T18:49:33Z)
• Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs [57.27982780697922]
  大規模言語モデルは、自然言語の理解と生成において例外的な能力を示した。 しかし、それらの生成速度は、その復号過程の本質的にシーケンシャルな性質によって制限される。 本稿では,データ駆動方式で実装された新しいデコーディング手法であるLexical Unit Decodingを紹介する。
  論文  参考訳（メタデータ） (2024-05-24T04:35:13Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models [83.98062659664785]
  大規模言語モデル(LLM)は通常、トランスフォーマーアーキテクチャの2次複雑さのために短いテキストセグメント(例:4Kトークン)でトレーニングする。 この研究は、この長大一般化失敗に寄与する3つの主要な要因を特定する。 本研究では,LLMの長期処理能力を高めるための簡易かつ効果的な手法であるLM-Infiniteを提案する。
  論文  参考訳（メタデータ） (2023-08-30T16:47:51Z)
• AMOM: Adaptive Masking over Masking for Conditional Masked Language Model [81.55294354206923]
  条件付きマスク付き言語モデル(CMLM)は最も汎用性の高いフレームワークの1つである。 本稿では,デコーダの高精細化を実現するため,マスク戦略よりもシンプルで効果的な適応マスキングを提案する。 提案モデルにより,ニューラルマシン翻訳における最先端の性能が得られた。
  論文  参考訳（メタデータ） (2023-03-13T20:34:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。