論文の概要: Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints

• arxiv url: http://arxiv.org/abs/2604.13371v1
• Date: Wed, 15 Apr 2026 00:35:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.338291
• Title: Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints
• Title（参考訳）: 明示的妥当性制約を伴う有限離散状態空間問題に対する大規模言語モデルにおける複雑性誘発極限の実証的証拠
• Authors: Md. Fahad Ullah Utsho, Mohd. Ruhul Ameen, Akif Islam, Md. Golam Rashed, Dipankar Das,
• Abstract要約: 問題複雑性の増大にともなうLarge Reasoning Models (LRM) における推論の頑健さを系統的に評価した。 我々は,9つの古典的推論タスク,ブール満足度,クリプトリズム,グラフカラーニング,河川横断,ハノイ塔,ウォータージャグ,チェッカージャンプ,スドゥーク,ルービックキューブを構築した。 非一貫性な推論トレース,制約違反,状態追跡の喪失,確実な不正確なアウトプットを伴って,50%を超える相当な精度低下を観測する。
• 参考スコア（独自算出の注目度）: 0.6524460254566904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Models (LLMs) are increasingly described as possessing strong reasoning capabilities, supported by high performance on mathematical, logical, and planning benchmarks. However, most existing evaluations rely on aggregate accuracy over fixed datasets, obscuring how reasoning behavior evolves as task complexity increases. In this work, we introduce a controlled benchmarking framework to systematically evaluate the robustness of reasoning in Large Reasoning Models (LRMs) under progressively increasing problem complexity. We construct a suite of nine classical reasoning tasks: Boolean Satisfiability, Cryptarithmetic, Graph Coloring, River Crossing, Tower of Hanoi, Water Jug, Checker Jumping, Sudoku, and Rubik's Cube, each parameterized to precisely control complexity while preserving underlying semantics. Using deterministic validators, we evaluate multiple open and proprietary LRMs across low, intermediate, and high complexity regimes, ensuring that only fully valid solutions are accepted. Our results reveal a consistent phase transition like behavior: models achieve high accuracy at low complexity but degrade sharply beyond task specific complexity thresholds. We formalize this phenomenon as reasoning collapse. Across tasks, we observe substantial accuracy declines, often exceeding 50%, accompanied by inconsistent reasoning traces, constraint violations, loss of state tracking, and confidently incorrect outputs. Increased reasoning length does not reliably improve correctness, and gains in one problem family do not generalize to others. These findings highlight the need for evaluation methodologies that move beyond static benchmarks and explicitly measure reasoning robustness under controlled complexity.
• Abstract（参考訳）: 大規模言語モデル(LLM)は、数学的、論理的、計画的ベンチマークで高いパフォーマンスをサポートする強力な推論能力を持つと、ますます説明されている。 しかしながら、既存の評価のほとんどは、タスクの複雑さが増大するにつれて、推論の振る舞いがどのように進化するかを、固定されたデータセットよりも集約的精度に依存している。 本研究では,大規模推論モデル(LRM)における推論の頑健さを,問題を徐々に複雑化する中で体系的に評価する,制御されたベンチマークフレームワークを提案する。 本研究では,9つの古典的推論課題であるブール・サティフィビリティ,クリプト・スメティック,グラフ・カラーリング,リバー・クロッシング,ハノイ塔,ウォータージャグ,チェッカージャンプ,スドゥーク,ルービックキューブをパラメータ化して,基礎的意味を保ちながら複雑性を正確に制御する。 決定論的検証器を用いて、低、中、高複雑性の条件で複数のオープンかつプロプライエタリなLEMを評価し、完全に有効な解のみが受け入れられることを保証する。 モデルは低い複雑性で高い精度を達成するが、タスク固有の複雑性しきい値を超えて急激に劣化する。 我々はこの現象を推論崩壊として定式化する。 タスク全体にわたって、不整合な推論トレース、制約違反、状態追跡の喪失、確実な不正確なアウトプットを伴って、50%を超える相当な精度低下を観測する。 推論長の増加は正確さを確実に改善しないし、ある問題族で得られる利益は他の問題に一般化しない。 これらの知見は、静的なベンチマークを超えて、制御された複雑さの下で頑健な推論を明示的に測定する評価手法の必要性を強調している。

関連論文リスト

• Beyond Accuracy: Diagnosing Algebraic Reasoning Failures in LLMs Across Nine Complexity Dimensions [8.616356693448985]
  代数的推論は、大きな言語モデルにとって最も有意義なストレステストの1つである。 現在のベンチマークでは、特定の原因に障害をもたらすメカニズムを提供していません。 我々は、各因子が独立に変化し、他の因子は全て固定される9次元の枠組みを導入する。
  論文  参考訳（メタデータ） (2026-04-08T08:12:45Z)
• CoT-Seg: Rethinking Segmentation with Chain-of-Thought Reasoning and Self-Correction [50.67483317563736]
  本稿では,段階的に考察し,必要な情報を検索し,結果を生成し,自己評価を行い,結果を洗練するシステムを提案する。 CoT-Segは、思考の連鎖推論と自己補正を組み合わせることで、推論セグメンテーションを再考する、トレーニング不要のフレームワークである。
  論文  参考訳（メタデータ） (2026-01-24T11:41:54Z)
• seqBench: A Tunable Benchmark to Quantify Sequential Reasoning Limits of LLMs [1.0519693622157462]
  我々は,Large Language Models (LLMs) における逐次推論限界を探索するベンチマークであるseqBenchを紹介する。 検索の複雑さが最小限であるにもかかわらず、セクベンチの構造的推論タスクでは、トップパフォーマンスモデルでさえ体系的に失敗することがわかった。
  論文  参考訳（メタデータ） (2025-09-21T01:32:13Z)
• Less is More Tokens: Efficient Math Reasoning via Difficulty-Aware Chain-of-Thought Distillation [82.2288581878096]
  本稿では,問題複雑性に基づいてモデルに推論深度を動的に調整する難易度推論の枠組みを提案する。 モデルにそのような動的推論経路を与えることができ、アーキテクチャ上の変更を加えることなく実現可能であることを示す。
  論文  参考訳（メタデータ） (2025-09-05T16:40:13Z)
• The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity [16.266145641151375]
  大規模な推論モデルは、回答を提供する前に詳細な思考プロセスを生成する。 我々は, LRM がある種の複雑さを超えて完全に精度の低下に直面していることを示す。 また、より深く推論の痕跡を調べ、探索された解のパターンを研究する。
  論文  参考訳（メタデータ） (2025-06-07T22:42:29Z)
• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThinkは、外部から推定されるタスクの難しさと内部で測定されたモデルの不確実性を統合する、シンプルで効果的なスキームである。 シーンの複雑さと予測信頼度に応じて推論の長さを圧縮することを学ぶ。 実験により,提案手法は推論効率と全体セグメンテーション性能の両方を改善した。
  論文  参考訳（メタデータ） (2025-05-29T17:55:49Z)
• THOUGHTTERMINATOR: Benchmarking, Calibrating, and Mitigating Overthinking in Reasoning Models [65.39456695678713]
  本稿では,問題レベルの難易度を近似的に測定し,問題の難易度と最適なトークン使用量との間に明確な関係があることを実証する。 一般に、推論モデルは、特に簡単な問題に対して、キャリブレーションが不十分である。 トレーニング不要なブラックボックス復号法であるTHOUGHTTERMINATORを導入する。
  論文  参考訳（メタデータ） (2025-04-17T22:16:30Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化 正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。 新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
  論文  参考訳（メタデータ） (2025-04-02T17:45:58Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)

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

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