論文の概要: Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models

• arxiv url: http://arxiv.org/abs/2603.22784v1
• Date: Tue, 24 Mar 2026 04:19:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-25 19:53:37.300629
• Title: Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models
• Title（参考訳）: Caterpillar of Thoughts: 大規模言語モデルのための最適テスト時間アルゴリズム
• Authors: Amir Azarmehr, Soheil Behnezhad, Alma Ghafari,
• Abstract要約: マルコフ連鎖と相互作用するアルゴリズムとしてテスト時間計算をモデル化する。 バックトラックは指数関数的に世代数を減少させることができるが、理論的にはバックトラックの非常に限られた形態が十分であることを示す。 最適アルゴリズムの特性から,新しいテスト時間計算アルゴリズムであるCaterpillar of Thoughts (CaT)を提案する。
• 参考スコア（独自算出の注目度）: 3.810612452609132
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) can often produce substantially better outputs when allowed to use additional test-time computation, such as sampling, chain of thought, backtracking, or revising partial solutions. Despite the growing empirical success of such techniques, there is limited theoretical understanding of how inference time computation should be structured, or what constitutes an optimal use of a fixed computation budget. We model test-time computation as an algorithm interacting with a Markov chain: at any point, the algorithm may resume generation from any previously observed state. That is, unlike standard Markov chains where the states are drawn passively, we allow the algorithm to backtrack to any previously observed state of the Markov chain at any time. Many of the existing test-time algorithms, such as Chain-of-Thought (CoT) (Wei et al., 2023), Tree-of-Thoughts (ToT) (Yao et al., 2023), or Best-of-$k$ (Brown et al., 2024) could be seen as specific algorithms in this model. We prove that while backtracking can reduce the number of generations exponentially, a very limited form of backtracking is theoretically sufficient. Namely, we show that the optimal algorithm always generates a caterpillar tree. That is, if we remove the leaves of the state tree generated by the optimal algorithm, we obtain a path. Motivated by our characterization of the optimal algorithm, we present Caterpillar of Thoughts (CaT), a new test-time computation algorithm, reducing the number of token/state generations. Our empirical evaluation shows that CaT, compared to ToT, achieves a better success rate while also reducing the number of token generations.
• Abstract（参考訳）: 大規模な言語モデル(LLM)は、サンプリング、思考の連鎖、バックトラック、部分的な解決策の修正など、追加のテスト時間計算を使用することが許される場合、かなり優れた出力を生成することができる。 このような手法の実証的な成功にもかかわらず、推論時間計算がどのように構成されるべきか、あるいは固定された計算予算の最適利用を構成するかという理論的な理解は限られている。 我々はマルコフ連鎖と相互作用するアルゴリズムとしてテスト時間計算をモデル化する。 すなわち、状態が受動的に描画される標準的なマルコフ連鎖とは異なり、アルゴリズムはいつでもマルコフ連鎖の任意の観測状態にバックトラックすることができる。 既存のテストタイムアルゴリズム、例えばChain-of-Thought (CoT) (Wei et al , 2023), Tree-of-Thoughts (ToT) (Yao et al , 2023), Best-of-k$ (Brown et al , 2024)は、このモデルで特定のアルゴリズムとして見られる。 バックトラックは指数関数的に世代数を減少させることができるが、理論的にはバックトラックの非常に限られた形態が十分であることを示す。 すなわち、最適なアルゴリズムが常に毛虫の木を生成することを示す。 すなわち、最適アルゴリズムによって生成される状態木の葉を取り除いたら、経路を得る。 最適アルゴリズムの特性から,新しいテスト時間計算アルゴリズムであるCaterpillar of Thoughts (CaT)を提案する。 実験により,ToTと比較してCaTの方が良好な成功率を示し,トークン生成数も減少することがわかった。

関連論文リスト

• Discovering Algorithms with Computational Language Processing [0.7062238472483737]
  本稿では,トークンとして表現された操作列を概念化し,アルゴリズム発見を自動化するフレームワークを提案する。 これらの計算トークンは文法を用いてチェーン化され、より洗練された手続きの形成を可能にする。 我々のアンサンブルであるモンテカルロ木探索(MCTS)は、強化学習(RL)によって導かれ、トークン連鎖を探索し、新しいトークンの作成を促進する。
  論文  参考訳（メタデータ） (2025-07-03T21:45:17Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms [1.104960878651584]
  本稿では,アルゴリズムの実行時/実行時/実行時における集中テールバウンドを導出する問題について考察する。 この定理は、正、弱、零、負のドリフトが与えられた正確な指数的なテールバウンドを与える新しいドリフト定理を提供する。 我々のドリフト定理は、AIにおけるアルゴリズムのランタイム/レグレットの強い集中力を証明するのに使うことができる。
  論文  参考訳（メタデータ） (2024-05-07T16:45:15Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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