論文の概要: Black-box Context-free Grammar Inference for Readable & Natural Grammars

• arxiv url: http://arxiv.org/abs/2509.26616v1
• Date: Tue, 30 Sep 2025 17:54:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-01 17:09:04.652167
• Title: Black-box Context-free Grammar Inference for Readable & Natural Grammars
• Title（参考訳）: 可読・自然文法のためのブラックボックス文脈自由文法推論
• Authors: Mohammad Rifat Arefin, Shanto Rahman, Christoph Csallner,
• Abstract要約: Arvada、TreeVada、Kedavraといった既存のツールは、大規模で複雑な言語でスケーラビリティ、可読性、正確性に苦慮している。 本稿では,新しいLLM誘導文法推論フレームワークであるNatGIを紹介する。 我々は,NatGIがF1スコアにおいて強いベースラインを一貫して上回っていることを示す。
• 参考スコア（独自算出の注目度）: 4.995853115126354
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Black-box context-free grammar inference is crucial for program analysis, reverse engineering, and security, yet existing tools such as Arvada, TreeVada, and Kedavra struggle with scalability, readability, and accuracy on large, complex languages. We present NatGI, a novel LLM-guided grammar inference framework that extends TreeVada's parse tree recovery with three key innovations: bracket-guided bubble exploration, LLM- driven bubble generation and non-terminal labeling, and hierarchical delta debugging (HDD) for systematic tree simplification. Bracket-guided exploration leverages syntactic cues such as parentheses to propose well- structured grammar fragments, while LLM guidance produces meaningful non-terminal names and selects more promising merges. Finally, HDD incrementally reduces unnecessary rules, which makes the grammars both compact and interpretable. In our experiments, we evaluate NatGI on a comprehensive benchmark suite ranging from small languages to larger ones such as lua, c, and mysql. Our results show that NatGI consistently outperforms strong baselines in terms of F1 score. On average, NatGI achieves an F1 score of 0.57, which is 25pp (percentage points) higher than the best-performing baseline, TreeVada. In the case of interpretability, our generated grammars perform significantly better than those produced by existing approaches. Leveraging LLM-based node renaming and bubble exploration, NatGI produces rules with meaningful non-terminal names and compact structures that align more closely with human intuition. As a result, developers and researchers can achieve higher accuracy while still being able to easily inspect, verify, and reason about the structure and semantics of the induced grammars.
• Abstract（参考訳）: ブラックボックスの文脈自由文法推論は、プログラム分析、リバースエンジニアリング、セキュリティに不可欠であるが、Arvada、TreeVada、Kedavraといった既存のツールでは、大規模で複雑な言語でのスケーラビリティ、可読性、精度に苦労している。 そこで,本論文では,木箱誘導バブル探索,LCM駆動バブル生成,非終端ラベリング,階層的デルタデバッギング(HDD)という3つの重要なイノベーションを生かした,新しいLLM誘導文法推論フレームワークであるNatGIを紹介する。 括弧誘導探索は、括弧などの構文的手がかりを利用して、よく構造化された文法的断片を提案する一方で、LCMガイダンスは意味のある非終端名を生成し、より有望なマージを選択する。 最後に、HDDは不要な規則を漸進的に減らし、文法はコンパクトかつ解釈可能である。 実験では,小さな言語からLua,c,mysqlなどの大規模言語まで,包括的なベンチマークスイートを用いてNatGIを評価する。 以上の結果から,NatGIはF1スコアにおいて高いベースラインを一貫して上回っていることが明らかとなった。 NatGIの平均F1スコアは0.57で、これは最高のパフォーマンスのベースラインであるTreeVadaよりも25pp(パーセント)高い。 解釈可能性の場合には,既存の手法よりも優れた文法が生成される。 LLMベースのノードリネームとバブル探索を活用して、NatGIは意味のある非終端名と人間の直感とより緊密なコンパクトな構造を持つルールを生成する。 結果として、開発者や研究者は、推論された文法の構造と意味について、容易に検査、検証、推論することが可能でありながら、より高い精度を達成することができる。

関連論文リスト

• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [79.75818239774952]
  大きな言語モデル(LLM)は目覚ましい能力を示しているが、幻覚や時代遅れの情報といった問題に苦戦している。 Retrieval-augmented Generation (RAG) は、情報検索システム(IR)を用いて、外部知識のLLM出力を基底にすることで、これらの問題に対処する。 本稿では、検索後句における新しい推論誘導二重アライメントフレームワークであるAlign-GRAGを提案する。
  論文  参考訳（メタデータ） (2025-05-22T05:15:27Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• Sneaking Syntax into Transformer Language Models with Tree Regularization [33.74552367356904]
  構文的帰納バイアスの導入は、トランスフォーマー言語モデルにおけるより堅牢でデータ効率のよい学習を解放する可能性がある。 ここでは,銀パースからの括弧決定を微分可能性制約の集合に変換する補助的損失関数であるTreeRegを紹介する。 TreeRegは標準のLM目標とシームレスに統合され、アーキテクチャの変更は不要である。
  論文  参考訳（メタデータ） (2024-11-28T03:27:48Z)
• LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers [60.009969929857704]
  論理的推論は、科学、数学、社会に潜在的影響を与える可能性のある人工知能にとって重要なタスクである。 本研究では、LINCと呼ばれるモジュール型ニューロシンボリックプログラミングのようなタスクを再構成する。 我々は,FOLIOとProofWriterのバランスの取れたサブセットに対して,ほぼすべての実験条件下で,3つの異なるモデルに対して顕著な性能向上を観察した。
  論文  参考訳（メタデータ） (2023-10-23T17:58:40Z)
• Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
  文法制約付き復号法(GCD)は、大言語モデル(LM)の生成を制御するために用いられる。 GCDは一般に構造化NLPタスクの統一フレームワークとして機能する。 文法制約付きLMは、制約なしLMよりも大幅に優れるか、タスク固有の微調整モデルよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-05-23T11:54:37Z)
• MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
  多段階推論を用いた半構造化データからテキストを生成するための,ニューロシンボリックなモジュラーアプローチであるMURMURを提案する。 WebNLG や LogicNLG のような2つのデータ・テキスト生成タスクについて実験を行った。
  論文  参考訳（メタデータ） (2022-12-16T17:36:23Z)

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

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