arXiv:2611.21597v1 cs.LG

배깅을 통한 최적의 자기회귀 사고 과정 학습

Optimal Autoregressive Chain-of-Thought Learning via Bagging

Awni Altabaa, John Lafferty, Omar Montasser

제출 2026-11-16

한국어 초록

클래스 $\mathcal{F}$에 속하는 자기회귀 다음 토큰 생성기 $f\colon\Sigma^\star\to\Sigma$가 만든 길이 $T$의 사고 과정(CoT) 시연을 바탕으로 $f$를 학습하는 방법을 연구한다. 배깅을 기반으로 하는 간단한 알고리즘을 제시한다. 이 알고리즘은 학습 데이터의 부트스트랩 표본마다 CoT와 일치하도록 생성기를 학습시키고, 여러 생성기의 다수결 결과를 출력한다. 이진 토큰 집합에서는 CoT 길이 $T$와 무관하게 최적 표본 복잡도 $O((d_{\mathrm{VC}}+\log(1/\delta))/\epsilon)$를 달성한다. 여기서 $d_{\mathrm{VC}}$는 $\mathcal{F}$의 VC 차원이다. 유한 토큰 집합 $\Sigma$에서는 다중 클래스에 대응하는 그래프 차원 $d_{\mathrm{G}}$가 VC 차원을 대신한다. 이때 표본 복잡도는 $\log|\Sigma|$ 인자를 제외하면 최적이다. 다수결 앙상블에 포함되는 생성기의 수는 $O(\log(T/\delta))$이다. 레이블이 없는 프롬프트 $n\log(nT)$개를 추가로 사용하면 앙상블을 $\mathcal{F}$에 속하는 단일 생성기로 증류할 수 있음을 보인다.

원문 초록

We study how to learn an autoregressive next-token generator $f\colon\Sigma^\star\to\Sigma$ from a class $\mathcal{F}$, given chain-of-thought (CoT) demonstrations of length $T$ generated by $f$. We present a simple algorithm based on bagging, which outputs a majority vote of generators that are trained to be CoT-consistent on bootstrap samples of the training data. For binary token sets, it achieves the optimal sample complexity of $O((d_{\mathrm{VC}}+\log(1/\delta))/\epsilon)$, independent of the CoT length $T$, where $d_{\mathrm{VC}}$ is the VC dimension of $\mathcal{F}$. For finite token sets $\Sigma$, the VC dimension is replaced by a multiclass analogue, the Graph dimension $d_{\mathrm{G}}$, and the sample complexity is optimal up to a $\log|\Sigma|$ factor. The number of generators in the majority-vote ensemble is $O(\log(T/\delta))$, and we show that the ensemble can be distilled into a single generator in $\mathcal{F}$ at the expense of $n\log(nT)$ unlabeled prompts.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.21597v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.