論文の概要: Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs
- arxiv url: http://arxiv.org/abs/2504.11239v1
- Date: Tue, 15 Apr 2025 14:40:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-24 00:31:09.148579
- Title: Nondeterministic Polynomial-time Problem Challenge: An Ever-Scaling Reasoning Benchmark for LLMs
- Title（参考訳）: 非決定論的多項式時間問題問題: LLMの非決定論的推論ベンチマーク
- Authors: Chang Yang, Ruiyu Wang, Junzhe Jiang, Qi Jiang, Qinggang Zhang, Yanchen Deng, Shuxin Li, Shuyue Hu, Bo Li, Florian T. Pokorny, Xiao Huang, Xinrun Wang,
- Abstract要約: 非決定論的多項式時間問題(Nondeterministic Polynomial-time Problem Challenge, NPPC)は、大規模言語モデル (LLM) の非決定論的推論ベンチマークである。
NPPCは、難解で、ハック不能で、自動検証可能で、一般的なものである。
NPPCは、LLMが人工知能(AGI)に向かわせるための、調査不可能でハック不能なテストベッドとして機能する、最初のスケール可能な推論ベンチマークである、と我々は信じている。
- 参考スコア（独自算出の注目度）: 29.42570946991691
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reasoning is the fundamental capability of large language models (LLMs). Due to the rapid progress of LLMs, there are two main issues of current benchmarks: i) these benchmarks can be crushed in a short time (less than 1 year), and ii) these benchmarks may be easily hacked. To handle these issues, we propose the ever-scalingness for building the benchmarks which are uncrushable, unhackable, auto-verifiable and general. This paper presents Nondeterministic Polynomial-time Problem Challenge (NPPC), an ever-scaling reasoning benchmark for LLMs. Specifically, the NPPC has three main modules: i) npgym, which provides a unified interface of 25 well-known NP-complete problems and can generate any number of instances with any levels of complexities, ii) npsolver: which provides a unified interface to evaluate the problem instances with both online and offline models via APIs and local deployments, respectively, and iii) npeval: which provides the comprehensive and ready-to-use tools to analyze the performances of LLMs over different problems, the number of tokens, the aha moments, the reasoning errors and the solution errors. Extensive experiments over widely-used LLMs demonstrate: i) NPPC can successfully decrease the performances of advanced LLMs' performances to below 10%, demonstrating that NPPC is uncrushable, ii) DeepSeek-R1, Claude-3.7-Sonnet, and o1/o3-mini are the most powerful LLMs, where DeepSeek-R1 outperforms Claude-3.7-Sonnet and o1/o3-mini in most NP-complete problems considered, and iii) the numbers of tokens, aha moments in the advanced LLMs, e.g., Claude-3.7-Sonnet and DeepSeek-R1, are observed first to increase and then decrease when the problem instances become more and more difficult. We believe that NPPC is the first ever-scaling reasoning benchmark, serving as the uncrushable and unhackable testbed for LLMs toward artificial general intelligence (AGI).
- Abstract（参考訳）: 推論は、大きな言語モデル(LLM)の基本的な能力である。
LLMの急速な進歩により、現在のベンチマークには2つの大きな問題がある。
一 これらのベンチマークは、短時間(一年以内)に破砕することができる。
ii)これらのベンチマークは簡単にハックされるかもしれません。
これらの問題に対処するため、我々は、チェック不能で、ハック不能で、自動検証可能で、一般的なベンチマークを構築するための、常にスケール性を提案する。
本稿では,LLMの非決定論的多項式時間問題問題(NPPC)を提案する。
具体的には、NPPCには3つの主要なモジュールがある。
i)npgymは、よく知られたNP完全問題25の統一インターフェースを提供し、任意のレベルの複雑さを持つ任意の数のインスタンスを生成することができる。
ii) npsolver: APIとローカルデプロイメントを通じて,オンラインモデルとオフラインモデルの両方で問題インスタンスを評価する統一インターフェースを提供する。
三 異なる問題、トークンの数、ahaモーメント、推論エラー及びソリューションエラーに関するLCMのパフォーマンスを分析するための包括的で使用可能なツールを提供する。
広く使われているLDMに関する大規模な実験は以下のとおりである。
一 NPPCは、高度LLMの性能を10%以下に下げることに成功し、NPPCが精査不能であることを示す。
i)DeepSeek-R1、Claude-3.7-Sonnet、o1/o3-miniは最も強力なLCMであり、ほとんどのNP完全問題において、DeepSeek-R1はClaude-3.7-Sonnetおよびo1/o3-miniより優れており、また、
三 先進LLMにおけるトークンの数、ahaモーメント、例えば、Claude-3.7-Sonnet及びDeepSeek-R1が最初に観測され、問題事例がますます難しくなったときに減少する。
NPPCは、LLMが人工知能(AGI)に向かわせるための、調査不可能でハック不能なテストベッドとして機能する、最初のスケール可能な推論ベンチマークである、と私たちは信じています。
関連論文リスト
- InductionBench: LLMs Fail in the Simplest Complexity Class [53.70978746199222]
大規模言語モデル(LLM)は推論において顕著に改善されている。
帰納的推論(inductive reasoning)は、観測されたデータから基礎となるルールを推測するものであり、まだ探索されていない。
本稿では, LLMの帰納的推論能力を評価するための新しいベンチマークであるインジェクションベンチを紹介する。
論文 参考訳（メタデータ） (2025-02-20T03:48:00Z) - Calling a Spade a Heart: Gaslighting Multimodal Large Language Models via Negation [65.92001420372007]
本稿では,様々なベンチマークにおいて最先端MLLMを体系的に評価する。
本稿では,MLLMの脆弱性を否定的議論に対して評価するために設計された,最初のベンチマークであるGaslightingBenchを紹介する。
論文 参考訳（メタデータ） (2025-01-31T10:37:48Z) - Leveraging Online Olympiad-Level Math Problems for LLMs Training and Contamination-Resistant Evaluation [55.21013307734612]
AoPS-Instructは60,000以上の高品質QAペアのデータセットである。
LiveAoPSBenchは、最新のフォーラムデータから派生したタイムスタンプによる進化的評価セットである。
我々の研究は、高度な数学推論のための大規模で高品質なデータセットの作成と維持にスケーラブルなアプローチを提示している。
論文 参考訳（メタデータ） (2025-01-24T06:39:38Z) - Dspy-based Neural-Symbolic Pipeline to Enhance Spatial Reasoning in LLMs [29.735465300269993]
大規模言語モデル(LLM)は、様々なタスクにまたがる顕著な能力を示してきたが、しばしば空間的推論に苦しむ。
本稿では LLM と Answer Set Programming (ASP) の反復的フィードバックにより LLM の空間推論能力を高める新しいニューラルシンボリックフレームワークを提案する。
我々は、StepGameとSparQAという2つのベンチマークデータセットに対するアプローチを評価した。
論文 参考訳（メタデータ） (2024-11-27T18:04:05Z) - MR-Ben: A Meta-Reasoning Benchmark for Evaluating System-2 Thinking in LLMs [55.20845457594977]
大規模言語モデル(LLM)は、問題解決と意思決定の能力の向上を示している。
本稿ではメタ推論技術を必要とするプロセスベースのベンチマークMR-Benを提案する。
メタ推論のパラダイムは,システム2のスロー思考に特に適しています。
論文 参考訳（メタデータ） (2024-06-20T03:50:23Z) - 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) - PECC: Problem Extraction and Coding Challenges [3.287942619833188]
PECCは、Advent Of Code(AoC)の課題とProject Eulerから派生した、新しいベンチマークである。
従来のベンチマークとは異なり、PECCは物語に埋め込まれた問題を解釈し、要求を抽出し、コードを生成するためにLCMを必要とする。
結果は、ユーラー数に基づく部分集合において、物語的問題と中立的問題の間に様々なモデル性能を示す。
論文 参考訳（メタデータ） (2024-04-29T15:02:14Z) - Achieving >97% on GSM8K: Deeply Understanding the Problems Makes LLMs Better Solvers for Math Word Problems [50.76385564061713]
CoT(Chain-of-Thought)のプロンプトにより、さまざまな推論タスクにわたるLLM(Large Language Models)のパフォーマンスが向上した。
CoTは通常、セマンティックな誤解エラー、計算エラー、ステップミスという3つの落とし穴に悩まされる。
意味的誤解の誤りに対処し,LLMの数学的問題解決能力を改善するために,DUP(Deeply Understanding the Problems)を提案する。
論文 参考訳（メタデータ） (2024-04-23T12:16:05Z) - Reasoning on Efficient Knowledge Paths:Knowledge Graph Guides Large Language Model for Domain Question Answering [18.94220625114711]
大きな言語モデル(LLM)は驚くほどよく機能し、多くのタスクにおいて人間の専門家より優れています。
本稿では,LLMに基づいてKGから推論経路を選択するパイプラインを統合し,最適化する。
また,思考の連鎖(CoT)とページランクに基づく,シンプルで効果的なサブグラフ検索手法を提案する。
論文 参考訳（メタデータ） (2024-04-16T08:28:16Z) - Are More LLM Calls All You Need? Towards Scaling Laws of Compound Inference Systems [76.69936664916061]
LM呼び出し回数がVotteとFilter-Voteのパフォーマンスに与える影響について検討する。
意外なことに、複数の言語タスクにおいて、VoteとFilter-Voteの両方のパフォーマンスは、まず増大するが、LM呼び出しの回数の関数として減少する可能性がある。
論文 参考訳（メタデータ） (2024-03-04T19:12:48Z) - AQA-Bench: An Interactive Benchmark for Evaluating LLMs' Sequential
Reasoning Ability [29.1826948551409]
AQA-Benchは、大規模言語モデルの逐次推論能力を評価するための新しいベンチマークである。
AQA-Benchは,2進探索,深さ優先探索,幅優先探索という3つのアルゴリズムで構築されている。
我々の調査では興味深い発見がいくつか示されている。
論文 参考訳（メタデータ） (2024-02-14T18:59:33Z) - Evaluating LLMs' Mathematical and Coding Competency through Ontology-guided Interventions [47.83142414018448]
算術的推論とコード生成という,2つの一般的な推論タスクに注目します。
i) 数学やコーディング問題に対する摂動の一般的なオントロジー, (ii) 摂動を応用するための半自動手法, (iii) 2つのデータセットを紹介する。
混乱した質問に対して、すべてのモデルで大幅なパフォーマンス低下を示します。
論文 参考訳（メタデータ） (2024-01-17T18:13:07Z) - PAL: Program-aided Language Models [112.94785609781503]
自然言語問題を理解するために,プログラム支援言語モデル(PaL)を提案する。
PaLはソリューションステップをPythonインタプリタのようなプログラムランタイムにオフロードする。
私たちは12のベンチマークで新しい最先端の結果を設定しました。
論文 参考訳（メタデータ） (2022-11-18T18:56:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。