アウニ・アルタバア (Awni Altabaa) 氏らは2026年11月16日(現地時間)、論文公開サイトarXivに「Optimal Autoregressive Chain-of-Thought Learning via Bagging」と題する研究成果を発表した。Chain-of-Thought (CoT) demonstrationを用いてautoregressive next-token generatorを学習する手法について研究し、バギング (bagging) に基づくアルゴリズムが最適なサンプル複雑度を達成することを報告している。
Awni Altabaa氏、ジョン・ラファティ (John Lafferty) 氏、オマール・モンタッサー (Omar Montasser) 氏らは、クラス $\mathcal{F}$ からautoregressive next-token generator $f$ を学習する方法を研究した。この研究では、生成器 $f$ によって作成された長さ $T$ のchain-of-thought (CoT) demonstrationを活用する。
提案されたアルゴリズムは、バギングに基づいたシンプルな手法である。これは、トレーニングデータのブートストラップサンプル上でCoT一貫性を持つように訓練された複数のジェネレータの多数決を出力する。バイナリートークンセットの場合、このアルゴリズムはCoTの長さ $T$ に依存せず、VC dimension $d_{\mathrm{VC}}$ を用いた最適なサンプル複雑度 $O((d_{\mathrm{VC}}+\log(1/\delta))/\epsilon)$ を達成する。有限トークンセット $\Sigma$ の場合、VC dimensionは多クラス類似であるGraph dimension $d_{\mathrm{G}}$ に置き換えられ、サンプル複雑度は$\log|\Sigma|$倍の係数を除いて最適とされる。
多数決アンサンブルに含まれるジェネレータの数は $O(\log(T/\delta))$ であり、このアンサンブルは $n\log(nT)$ のラベルなしプロンプトを消費することで、クラス $\mathcal{F}$ 内の単一ジェネレータへと蒸留 (distilled) できることを示している。
参考: arXiv cs.LG — 2026年11月17日 03:58 (JST)
原文ハイライト"Optimal Autoregressive Chain-of-Thought Learning via Bagging"