論文の概要: STAB: Specification-driven Testing for Algorithmic Bottlenecks

• arxiv url: http://arxiv.org/abs/2605.27981v1
• Date: Wed, 27 May 2026 05:18:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-28 17:38:55.765215
• Title: STAB: Specification-driven Testing for Algorithmic Bottlenecks
• Title（参考訳）: STAB: アルゴリズム型ブートネックの仕様駆動テスト
• Authors: Soohan Lim, Joonghyuk Hahn, Hyundong Jin, Yo-Sub Han,
• Abstract要約: STABは自然言語の問題仕様だけでアルゴリズムのボトルネックを明らかにするテストケースを生成する。 CodeContestsでは、STABはアルゴリズムのボトルネックを平均で50.43%から73.45%に拡大するテストケースを生成する。
• 参考スコア（独自算出の注目度）: 9.382652543336624
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Evaluating the efficiency of algorithmic code requires test cases that expose runtime bottlenecks. Previous methods generate efficiency test cases either by increasing input size or by generating code-specific inputs that make the given implementation run slowly. Consequently, they do not address the structural input conditions that drive the algorithmic worst case. We introduce STAB, a specification-driven pipeline that generates test cases that expose algorithmic bottlenecks from a natural-language problem specification alone. STAB separates the task into constraint-bound maximization and adversarial structure injection. (i) The constraint saturator extracts constraints and resolves large admissible size assignments using rule-based saturation and CP-SAT optimization over related variables. (ii) The adversarial scenario injector retrieves implementation-level adversarial construction principles from a curated scenario catalog using keyword matching and K-nearest neighbors (KNN). STAB encodes the problem specification, resolved boundary, and retrieved construction principles into a structured generation specification, from which the LLM synthesizes a Python test case generator. On CodeContests, STAB raises the rate of generated test cases that expose algorithmic bottlenecks from 50.43% to 73.45% on average across open-source LLMs and from 57.45% to 71.85% on average across closed-source LLMs, with consistent gains across Python, Java, and C++. Our code is available at https://github.com/suhanmen/STAB.
• Abstract（参考訳）: アルゴリズムコードの効率を評価するには、実行時のボトルネックを明らかにするテストケースが必要です。 以前の方法は、入力サイズを増やすか、与えられた実装をゆっくりと実行させるコード固有のインプットを生成することによって、効率テストケースを生成する。 したがって、アルゴリズム上の最悪のケースを駆動する構造的な入力条件には対処しない。 本稿では,自然言語問題仕様のみからアルゴリズムボトルネックを公開するテストケースを生成する,仕様駆動パイプラインSTABを紹介する。 STABはタスクを制約バウンドの最大化と逆構造注入に分離する。 (i)制約飽和器は制約を抽出し、ルールベースの飽和と関連する変数に対するCP-SAT最適化を用いて大きな許容サイズの割り当てを解く。 (II) 逆シナリオインジェクタは、キーワードマッチングとK-nearest neighbors (KNN) を用いて、キュレートされたシナリオカタログから実装レベルの逆構成原理を検索する。 STABは、問題仕様、解決された境界を符号化し、構築原則を構造化された生成仕様に変換し、LLMはPythonテストケースジェネレータを合成する。 CodeContestsにおいて、STABは、アルゴリズムのボトルネックを平均50.43%から73.45%に、クローズドソースLLMの平均57.45%から71.85%に拡大し、Python、Java、C++で一貫して増加している。 私たちのコードはhttps://github.com/suhanmen/STAB.comで利用可能です。

関連論文リスト

• LLM-Based Static Verification of Code Against Natural-Language Requirements: An Industrial Experience Report [3.5867640049033054]
  本稿では,この課題に対処するための2段階のLLMベースのワークフローを,インテリジェント車両サイバーセキュリティケーススタディで紹介する。 第一段階では、AIベースのルールマイナーが自然言語要求から検証可能なルールを抽出する。 第2段階では、AIベースのコード監査者が、抽出されたルールに対する実装証拠をチェックする。
  論文  参考訳（メタデータ） (2026-05-18T06:34:03Z)
• From I/O to Code with Discovery Agent [103.88427301265669]
  IO2Codeの発見エージェントであるDIO-Agentを提案する。 本手法は,プログラム空間上の進化的探索としてIO2Codeをフレーム化する。 大規模な実験により、DIO-Agentは従来のプログラムバイサンプル法とSOTA進化エージェントベースラインの両方を一貫して上回っていることが示された。
  論文  参考訳（メタデータ） (2026-05-14T18:57:32Z)
• You Don't Need Public Tests to Generate Correct Code [0.9668407688201359]
  大規模言語モデルには,有効な入力を自律的に構築し,自己補正のための実行フローをシミュレートする能力があることを示す。 我々は,LLMが反復的に計画し,独自のテスト入力を合成し,シミュレートされた実行を行うことで,地平データの必要性を解消するフレームワークであるDryRUNを紹介した。
  論文  参考訳（メタデータ） (2026-04-23T12:21:03Z)
• Synthesizing File-Level Data for Unit Test Generation with Chain-of-Thoughts via Self-Debugging [40.29934051200609]
  本稿では,高品質なUTトレーニングを実現するための新しいデータ蒸留手法を提案する。 このパイプラインをオープンソースプロジェクトの大規模なコーパスに適用します。 実験により, 微調整モデルにより, UT生成効率が高いことを示す。
  論文  参考訳（メタデータ） (2026-02-03T06:52:54Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  大きな言語モデル(LLM)は、機能記述からコードを実装するのに優れているが、アルゴリズムの問題に悩まされている。 我々は,アルゴリズムプログラムを LLM 生成 Oracle で合成するフレームワーク ALGO を提案し,その生成をガイドし,その正確性を検証する。 実験の結果,ALGOを装着すると,Codexモデルよりも8倍,CodeTよりも2.6倍の1サブミッションパス率が得られることがわかった。
  論文  参考訳（メタデータ） (2023-05-24T00:10:15Z)
• Interactive Code Generation via Test-Driven User-Intent Formalization [60.90035204567797]
  大きな言語モデル(LLM)は、非公式な自然言語(NL)の意図からコードを生成する。 自然言語は曖昧であり、形式的な意味論が欠けているため、正確性の概念を定義するのは難しい。 言語に依存しない抽象アルゴリズムと具体的な実装TiCoderについて述べる。
  論文  参考訳（メタデータ） (2022-08-11T17:41:08Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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