論文の概要: High-Performance Generation of Constrained Input

• arxiv url: http://arxiv.org/abs/2511.05987v1
• Date: Sat, 08 Nov 2025 12:26:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:44.697869
• Title: High-Performance Generation of Constrained Input
• Title（参考訳）: 制約入力の高速生成
• Authors: Addison Crump, Alexi Turcotte, José Antonio Zamudio Amaya, Andreas Zeller,
• Abstract要約: 言語ベースのテストは、文脈のない文法定義と意味制約を組み合わせてテスト入力を生成する。 進化的言語に基づく新しい手法を提案し,現状よりも3～4桁の性能向上を図っている。 本稿では,FANDANGO-RSが1分間に401の多様で複雑で有効なテスト入力を生成できるCサブセットのケーススタディにより,これを実証する。
• 参考スコア（独自算出の注目度）: 4.837737516460689
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Language-based testing combines context-free grammar definitions with semantic constraints over grammar elements to generate test inputs. By pairing context-free grammars with constraints, users have the expressiveness of unrestricted grammars while retaining simple structure. However, producing inputs in the presence of such constraints can be challenging. In past approaches, SMT solvers have been found to be very slow at finding string solutions; evolutionary algorithms are faster and more general, but current implementations still struggle with complex constraints that would be required for domains such as compiler testing. In this paper, we present a novel approach for evolutionary language-based testing that improves performance by 3-4 orders of magnitude over the current state of the art, reducing hours of generation and constraint solving time to seconds. We accomplish this by (1) carefully transforming grammar definitions into Rust types and trait implementations, ensuring that the compiler may near-maximally optimize arbitrary operations on arbitrary grammars; and (2) using better evolutionary algorithms that improve the ability of language-based testing to solve complex constraint systems. These performance and algorithmic improvements allow our prototype, FANDANGO-RS, to solve constraints that previous strategies simply cannot handle. We demonstrate this by a case study for a C subset, in which FANDANGO-RS is able to generate 401 diverse, complex, and valid test inputs for a C compiler per minute.
• Abstract（参考訳）: 言語ベースのテストでは、文脈のない文法定義と文法要素に対する意味制約を組み合わせてテスト入力を生成する。 制約付き文脈自由文法をペアリングすることで、ユーザーは単純な構造を維持しながら制約のない文法を表現することができる。 しかし、そのような制約が存在する場合に入力を生成することは困難である。 進化的アルゴリズムはより高速でより一般的なものであるが、現在の実装ではコンパイラテストのようなドメインに必要な複雑な制約に悩まされている。 本稿では,現在最先端技術に対して3～4桁の性能向上を図り,生成時間の短縮と問題解決時間を秒に短縮する,進化言語に基づく新しい手法を提案する。 我々は(1)文法定義をRustタイプやトレイト実装に慎重に変換し、コンパイラが任意の文法に対する任意の操作をほぼ最大限に最適化できるようにする。 これらの性能改善とアルゴリズム改良により、我々のプロトタイプであるFANDANGO-RSは、以前の戦略が単純に扱えない制約を解決することができる。 本稿では,FANDANGO-RSが1分あたり401の多様で複雑で有効なテスト入力を生成できるCサブセットのケーススタディにより,これを実証する。

関連論文リスト

• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars [11.279507894576213]
  本稿では,構文的に正しくないコードの早期拒絶を可能にするインクリメンタルな合成に寄与する。 文脈自由文法の左右商を許容するために、Earey解析アルゴリズムを拡張した。
  論文  参考訳（メタデータ） (2024-02-28T02:12:47Z)
• Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation [7.687678490751105]
  我々は、プリ計算と投機的復号化を利用して、ほとんどオーバーヘッドが無く、場合によっては、制約のない復号化よりも約2$times$のスピードアップを達成できる新しい復号アルゴリズムDOMINOを提案する。
  論文  参考訳（メタデータ） (2024-02-07T13:36:02Z)
• Toward Unified Controllable Text Generation via Regular Expression Instruction [56.68753672187368]
  本稿では,正規表現の利点をフル活用し,多様な制約を一様にモデル化する命令ベース機構を用いた正規表現指導(REI)を提案する。 提案手法では,中規模言語モデルの微調整や,大規模言語モデルでの少数ショット・インコンテクスト学習のみを要し,各種制約の組み合わせに適用した場合のさらなる調整は不要である。
  論文  参考訳（メタデータ） (2023-09-19T09:05:14Z)
• COLLIE: Systematic Construction of Constrained Text Generation Tasks [33.300039566331876]
  COLLIEは文法ベースのフレームワークで、多種多様な世代レベルのリッチで構成的な制約を仕様化することができる。 本研究では,制約構造と生テキストコーパスが与えられたタスクインスタンスの自動抽出ツールを開発する。 我々は、最先端の5つの言語モデルに対して体系的な実験を行い、その性能を分析し、欠点を明らかにする。
  論文  参考訳（メタデータ） (2023-07-17T17:48:51Z)
• Controlled Text Generation with Natural Language Instructions [74.88938055638636]
  InstructCTGは、異なる制約を含む制御されたテキスト生成フレームワークである。 まず、既製のNLPツールと単純な動詞の組み合わせにより、自然文の基本的制約を抽出する。 制約の自然言語記述といくつかの実演を予測することにより、様々な種類の制約を組み込むために、事前訓練された言語モデルを微調整する。
  論文  参考訳（メタデータ） (2023-04-27T15:56:34Z)
• POINTER: Constrained Progressive Text Generation via Insertion-based Generative Pre-training [93.79766670391618]
  ハードコントラストテキスト生成のための新しい挿入ベースアプローチであるPOINTERを提案する。 提案手法は,既存のトークン間で段階的に新しいトークンを並列に挿入することによって動作する。 結果として生じる粗大な階層構造は、生成プロセスを直感的で解釈可能である。
  論文  参考訳（メタデータ） (2020-05-01T18:11:54Z)

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

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