論文の概要: AlgoSimBench: Identifying Algorithmically Similar Problems for Competitive Programming
- arxiv url: http://arxiv.org/abs/2507.15378v1
- Date: Mon, 21 Jul 2025 08:34:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-22 20:51:32.323452
- Title: AlgoSimBench: Identifying Algorithmically Similar Problems for Competitive Programming
- Title（参考訳）: AlgoSimBench: 競合プログラミングにおけるアルゴリズム的に類似した問題を識別する
- Authors: Jierui Li, Raymond Mooney,
- Abstract要約: アルゴリズムに類似した問題(ASPs)を識別する能力を評価するために設計された新しいベンチマークであるAlgoSimBenchを紹介した。
AlgoSimBenchは1317の問題で構成されており、異なる粒度のアルゴリズムタグで注釈付けされ、そこから402の多重選択質問(MCQ)を逸脱する。
評価の結果, LLM は ASP の識別に苦慮し, MCQ タスクでは 65.9% の精度で最高の性能のモデル (o3-mini) が得られた。
本稿では,問題類似性検出のための新しい手法である解マッチング(ASM)を提案する。
- 参考スコア（独自算出の注目度）: 2.3020018305241337
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Recent progress in LLMs, such as reasoning models, has demonstrated strong abilities to solve complex competitive programming problems, often rivaling top human competitors. However, it remains underexplored whether these abilities generalize to relevant domains that are less seen during training. To address this, we introduce AlgoSimBench, a new benchmark designed to assess LLMs' ability to identify algorithmically similar problems (ASPs)-problems that can be solved using similar algorithmic approaches. AlgoSimBench consists of 1317 problems, annotated with 231 distinct fine-grained algorithm tags, from which we curate 402 multiple-choice questions (MCQs), where each question presents one algorithmically similar problem alongside three textually similar but algorithmically dissimilar distractors. Our evaluation reveals that LLMs struggle to identify ASPs, with the best-performing model (o3-mini) achieving only 65.9% accuracy on the MCQ task. To address this challenge, we propose attempted solution matching (ASM), a novel method for improving problem similarity detection. On our MCQ task, ASM yields an absolute accuracy improvement of 6.7% to 11.7% across different models. We also evaluated code embedding models and retrieval methods on similar problem identification. While the adversarial selection of problems degrades the performance to be less than random, we found that simply summarizing the problem to remove narrative elements eliminates the effect, and combining ASM with a keyword-prioritized method, BM25, can yield up to 52.2% accuracy. Code and data are available at github.com
- Abstract（参考訳）: 推論モデルのようなLLMの最近の進歩は、しばしば上位の競合相手と競合する複雑な競合プログラミング問題を解く強力な能力を示している。
しかし、これらの能力が訓練中にあまり見られていない関連領域に一般化するかどうかについては、未解明のままである。
この問題に対処するために,アルゴリズムに類似した問題(ASP)を識別するLLMの能力を評価するために設計された新しいベンチマークであるAlgoSimBenchを紹介した。
AlgoSimBenchは1317の問題からなり、231の異なる細粒度アルゴリズムタグで注釈付けされ、そこから402の多重選択質問(MCQ)をキュレートする。
評価の結果, LLM は ASP の識別に苦慮し, MCQ タスクでは 65.9% の精度で最高の性能のモデル (o3-mini) が得られた。
そこで本研究では,問題類似性検出のための新しい手法である解マッチング(ASM)を提案する。
MCQタスクでは、ASMは異なるモデルに対して6.7%から11.7%の絶対精度の向上をもたらす。
また,コード埋め込みモデルと検索手法を類似した問題同定で評価した。
課題の逆選択は、性能をランダム以下に低下させるが、物語要素を除去するために問題を要約するだけで効果を排除し、ASMとキーワード優先のBM25を組み合わせれば、最大52.2%の精度が得られることがわかった。
コードとデータはgithub.comで入手できる。
関連論文リスト
- Evaluating and Improving Large Language Models for Competitive Program Generation [18.564450345359468]
本研究では,大規模言語モデル(LLM)を現実の競合プログラミング問題の解法として評価・改善することを目的とする。
2024年に開催された9つの地域ICPC/CCPCコンテストから117の問題を収集し、4つのフィルタリング基準を設計し、80の問題をキュレートしたベンチマークを構築した。
我々は,オンライン審査員(OJ)プラットフォームを通じて,その競争プログラム生成能力を評価し,慎重に設計された基本的なプロンプトで指導する。
論文 参考訳（メタデータ） (2025-06-28T17:18:23Z) - Strategic Scaling of Test-Time Compute: A Bandit Learning Approach [13.735277588793995]
大規模言語モデルの性能向上のための効果的な戦略として,テスト時間計算のスケーリングが登場している。
本研究では,フライ時のクエリの難易度を推定し,それに応じて計算量を割り当てる適応アルゴリズムを提案する。
私たちのアルゴリズムは、MATH-500データセットで最大11.10%のパフォーマンス改善、LiveCodeBenchで最大7.41%のパフォーマンス改善を実現しています。
論文 参考訳（メタデータ） (2025-06-15T04:55:49Z) - Diverse Inference and Verification for Advanced Reasoning [19.88677753421871]
OpenAI o1、o3、DeepSeek R1のようなLLMの推論は数学とコーディングに大きな進歩をもたらした。
テスト時に複数のモデルとメソッドを組み合わせる、さまざまな推論アプローチを使用します。
数学や符号問題の検証や他の問題に対する拒絶サンプリングは簡単かつ効果的であることがわかった。
論文 参考訳（メタデータ） (2025-02-14T07:22:25Z) - Navigating the Labyrinth: Evaluating and Enhancing LLMs' Ability to Reason About Search Problems [59.72548591120689]
我々は,11種類の検索問題を含む新しいベンチマークであるSearchBenchを紹介する。
もっとも先進的なLCMでさえ、これらの問題をエンドツーエンドのテキストで解決することができないことを示す。
LLMにその問題を解決するコードを生成するように指示することは助けになるが、GPT4のパフォーマンスは11.7%向上した。
論文 参考訳（メタデータ） (2024-06-18T00:44:58Z) - Can Language Models Solve Olympiad Programming? [40.54366634332231]
本稿ではUSACOベンチマークについて,USA Computing Olympiadの307の問題点について紹介する。
競争型プログラミングのための様々なLM推論手法を初めて構築・テストする。
GPT-4 は 8.7% パス@1 の精度しか達成していない。
論文 参考訳（メタデータ） (2024-04-16T23:27:38Z) - Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation [27.378185644892984]
本稿では,Large Language Models (LLM) をアルゴリズム選択に導入する。
LLMはアルゴリズムの構造的・意味的な側面を捉えるだけでなく、文脈的認識とライブラリ機能理解も示している。
選択されたアルゴリズムは、与えられた問題と異なるアルゴリズムの一致度によって決定される。
論文 参考訳（メタデータ） (2023-11-22T06:23:18Z) - A Gold Standard Dataset for the Reviewer Assignment Problem [70.45113777449373]
類似度スコア(Similarity score)とは、論文のレビューにおいて、レビュアーの専門知識を数値で見積もるものである。
既存のアルゴリズムを比較し、より良いアルゴリズムを開発する上で重要な課題は、公開された金標準データの欠如である。
研究コミュニティにリリースした類似度スコアの新しいデータセットを収集します。
論文 参考訳（メタデータ） (2023-03-23T16:15:03Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。
本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文 参考訳（メタデータ） (2021-07-20T11:23:21Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳（メタデータ） (2020-11-17T17:27:33Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。