論文の概要: Trie Automata for Constrained Decoding over Large Finite Sets

• arxiv url: http://arxiv.org/abs/2608.12574v1
• Date: Wed, 12 Aug 2026 20:38:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-14 18:29:38.322144
• Title: Trie Automata for Constrained Decoding over Large Finite Sets
• Title（参考訳）: 大規模有限集合上の制約付きデコードのためのトライオートマタ
• Abstract要約: 有限集合構造を利用する特殊機構である三重オートマトンを導入する。 トリエはステップ毎の有効解演算を7倍高速化する。 100ms未満のコンパイルをK = 10,000まで維持し、設定サイズに関係なくステップ毎のコストを平らにする。
• 参考スコア（独自算出の注目度）: 4.37891903761924
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models increasingly need to generate structured outputs that conform to predefined schemas, with one common constraint being selection from a finite set of valid strings. Current constrained decoding systems handle this through general-purpose grammar compilation, which becomes prohibitively slow as the number of valid values grows into the thousands, a cardinality wall. We introduce the trie automaton, a specialized mechanism that exploits finite-set structure (shared prefixes, bounded depth, known cardinality) via Aho-Corasick multi-pattern matching to precompute per-node token masks. The trie achieves 7X faster per-step valid-token computation (0.65 us vs. 5.8 us) compared to XGrammar, one of the primary backends in vLLM and SGLang, and 2--6.5X faster compilation at K >= 300. Because precomputed masks enable a stateless serving path that bypasses the guided decoding pipeline, this advantage compounds in batch serving: end-to-end vLLM throughput reaches 219 req/s vs. XGrammar's 7.5 req/s at batch size 256 (29X). The 29X combines the algorithmic speedup with integration-path savings that only precomputed masks can unlock. Across seven tokenizer families (32K--262K vocabulary), the trie maintains sub-100ms compilation up to K = 10,000 and flat per-step cost regardless of set size, while guaranteeing 100% output validity.
• Abstract（参考訳）: 大規模言語モデルは、定義済みのスキーマに準拠した構造化された出力を生成する必要がますます多くなり、一つの共通の制約は、有効な文字列の有限セットから選択される。 現在の制約付き復号化システムは、汎用文法コンパイルによってこれを処理し、有効値の数が数千に増加するにつれて、不当に遅くなる。 本稿では,Aho-Corasickマルチパターンマッチングを用いてノード単位のトークンマスクをプリコンプリートする有限集合構造(共有プレフィックス,有界深さ,既知の濃度)を利用する特殊機構である三重オートマトンを紹介する。 トリエは、vLLMとSGLangの主要なバックエンドの一つであるXGrammarと比較して、ステップ毎のバリデーショントーケン計算(0.65 us vs. 5.8 us)が7倍速く、K >= 300で2--6.5X高速コンパイルを実現している。 事前計算されたマスクは、ガイドされた復号パイプラインをバイパスするステートレスなサーブパスを可能にするため、バッチサービスにおけるこの利点は以下のとおりである: エンドツーエンドのvLLMスループットは、バッチサイズ256 (29X) でXGrammarの7.5 req/sに対して219 req/sに達する。 29Xはアルゴリズムのスピードアップと、事前計算されたマスクだけをアンロックできる統合パスセーブを組み合わせる。 7つのトークンライザファミリー(32K--262K語彙)にまたがって、Trieは100ms未満のコンパイルをK = 10,000まで維持し、設定サイズに関係なくフラットな1ステップあたりのコストを保証し、100%の出力妥当性を保証する。

関連論文リスト

• Transformer Accelerator (TFA): A Macro-Op INT8 Hardware Chip for Transformer Inference and Machine Translation [0.3882135185458233]
  Transformer Accelerator (TFA) は、Transformer推論のためのシンセサイザー可能な、パラメータ化可能なINT8メモリ・ツー・メモリエンジンである。 TFAは行列乗法、ソフトマックス、RMSNorm、要素演算、コピー/ガザ演算を8つの512ビットマクロ-op記述子で実装している。 RTLは出力定常多重累積配列と、DMAと計算の重なり合うピンポンバッファ、ビットエクサクサク逆二乗根と分割単位、キー値キャッシュと埋め込みアドレス処理、およびアボトセーフゼロパディング書き込みエンジンを結合する。
  論文  参考訳（メタデータ） (2026-08-06T06:59:25Z)
• GRID: Grammar-Railed Decoding for Enterprise SQL Generation [0.0]
  文法制約付き復号エンジンGRID(Grammar-Railed Decoding)を提案する。 LALR(1)自体を実行可能なオラクルとして使用する。 4つの保証(音量、完全性、終了、およびほぼ一定に近いコスト)は明示的な前提条件で記述される。
  論文  参考訳（メタデータ） (2026-07-11T19:25:23Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  有限オートマトンとして表現可能な任意の制約の下で,制約付き平均場後部からサンプリングする,正確かつトラクタブルなアルゴリズムを提案する。 このアプローチは、構築による制約満足度を保証し、欲求とサンプリングベースのデコーディングの両方をサポートし、並列およびブロックワイドデコーディングと互換性がある。 Dream-7B と LLaDA-8 の実証的な評価は、様々なタスクにおいてかなりの精度の向上を示した。
  論文  参考訳（メタデータ） (2026-07-08T05:48:57Z)
• XFP: Quality-Targeted Adaptive Codebook Quantization with Sparse Outlier Separation for LLM Inference [0.0]
  XFPはコードブックのサイズ、アウトリーチ予算、レイヤごとのパッケージを自動的に決定する。 XFPはワークステーションハードウェア上で128 tok/sのシングルストリームデコードに達する。 対象メモリエンベロープに収まらないモデルに対しては、H-Processを示す。
  論文  参考訳（メタデータ） (2026-05-14T13:52:31Z)
• DMax: Aggressive Parallel Decoding for dLLMs [77.24184219948337]
  効率的な拡散言語モデル(dLLM)のための新しいパラダイムであるDMaxを提案する。 並列デコードにおけるエラーの蓄積を軽減し、生成品質を維持しながらアグレッシブデコードを可能にする。 当社のアプローチの核心は、マスクと均一なdLLMを効率的に統合する新しいトレーニング戦略であるOn-Policy Uniform Trainingである。
  論文  参考訳（メタデータ） (2026-04-09T14:35:42Z)
• Frequency-Ordered Tokenization for Better Text Compression [0.0]
  MethodはByte Pairでテキストをトークン化する。 結果を可変長整数でエンコードし、任意の標準圧縮機に渡す。 enwik8(100MBウィキペディア)では、zlibが7.08ポイント(pp)、LZMAが1.69pp、zstdが0.76pp改善されている。
  論文  参考訳（メタデータ） (2026-02-26T12:53:48Z)
• REAR: Rethinking Visual Autoregressive Models via Generator-Tokenizer Consistency Regularization [130.46612643194973]
  reARはトークン単位の正規化目標を導入する単純なトレーニング戦略です。 ImageNetでは、gFIDを3.02から1.86に削減し、標準化ベースのトークンーザを使用してISを316.9に改善している。 高度なトークン化器に適用すると、177Mパラメータしか持たない1.42のgFIDが達成され、その性能はより大きな最先端拡散モデル(675M)と一致する。
  論文  参考訳（メタデータ） (2025-10-06T02:48:13Z)
• dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
  拡散大言語モデル(dLLM)は並列トークン予測と低推論遅延を提供する。 既存のオープンソースモデルは、パフォーマンスを確保するためにトークン長のデコードステップをほとんど必要としています。 高速サンプリングのためにdLLMs固有の並列性を解き放つシンプルで効果的な方法であるdParallelを導入する。
  論文  参考訳（メタデータ） (2025-09-30T16:32:52Z)
• A Simple Linear Patch Revives Layer-Pruned Large Language Models [58.056251480151104]
  大規模言語モデル(LLM)の圧縮技術として広く使われているレイヤプルーニング(Layer pruning)が登場している。 textscLinearPatchはプルーニングインターフェイスで2つの操作を1つの行列に乗算する。 パッチはメモリ効率の悪いオフライン蒸留によって5Kの未ラベルのサンプルでさらに洗練され、1つのGPUでわずか30分で95.16%に保留できる。
  論文  参考訳（メタデータ） (2025-05-30T15:06:08Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
  LLM(Large Language Models)の自動回帰デコーディングは、ハードウェアの性能に大きなオーバーヘッドをもたらす。 トレーニング可能なパラメータを0.0002$%しか必要とせず,A100-40GBのGPUをたった16時間で効率的にトレーニングできる並列プロンプトデコーディングを提案する。 我々のアプローチでは、最大2.49$times$ スピードアップを示し、最小のメモリオーバーヘッドは0.0004$%である。
  論文  参考訳（メタデータ） (2024-05-28T22:19:30Z)
• Prepacking: A Simple Method for Fast Prefilling and Increased Throughput in Large Language Models [48.592730159983276]
  Prefillingは、自己回帰生成前のプロンプトにおける入力トークンのキー値キャッシュの計算である。 より長い入力プロンプト長の場合、プリフィルはデコード時間にかなりのオーバーヘッドをもたらす。 本稿では,プリフィル計算を最適化する簡易かつ効果的な方法であるPrepackingを提案する。
  論文  参考訳（メタデータ） (2024-04-15T07:49:10Z)
• Hydragen: High-Throughput LLM Inference with Shared Prefixes [39.622276190997205]
  Hydragenはハードウェアを意識した、共有プレフィックスによる注意の正確な実装である。 提案手法は,エンドツーエンドのCodeLlama-13bスループットを最大32倍向上させる。
  論文  参考訳（メタデータ） (2024-02-07T18:53:01Z)
• Vcc: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens [65.4435926060951]
  本稿では,超長周期の変換器の効率を,各層でより小さな表現に圧縮することで向上することを提案する。 我々のアルゴリズムは効率的であるだけでなく(4Kと16Kのベースラインに比べて3倍以上の効率向上を達成する)、多数のタスクで競合/ベターパフォーマンスを提供する。
  論文  参考訳（メタデータ） (2023-05-07T10:32:18Z)

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

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