사고의 연쇄(Chain-of-Thought) 트랜스포머를 이용한 알고리즘의 효율적 표현
Efficiently Representing Algorithms With Chain-of-Thought Transformers
한국어 초록
추론 모델 -- 답변을 생성하기 전에 일련의 추론 또는 사고 토큰을 출력하는 언어 모델 -- 의 인기가 증가하고 있는데, 이는 부분적으로 사고의 연쇄(Chain-of-Thought, CoT) 트랜스포머가 튜링 머신을 시뮬레이션할 수 있고 따라서 임의의 계산을 수행할 수 있다는 이론적 결과에 의해 정당화됩니다. 그러나 튜링 머신은 복잡도 이론적 분석에는 적합하지만, 알고리즘을 논의하는 데에는 편리하거나 직관적이거나 효율적이지 않습니다. 알고리즘은 일반적으로 더 높은 추상화 수준에서 설계 및 분석되며, 이는 랜덤 액세스 메모리와 $\bigO(\log n)$비트 워드에 대한 단위 비용 연산을 갖는 워드 RAM(Word RAM) 모델로 포착됩니다. 결과적으로, 워드 RAM 알고리즘은 튜링 머신 대응물보다 훨씬 더 효율적일 수 있으며, 이는 다음과 같은 질문을 제기합니다: CoT 트랜스포머는 워드 RAM 알고리즘을 효율적으로 시뮬레이션할 수 있습니까? 예를 들어, $n$개의 항목을 $\bigO(n \log n)$ 단계로 정렬하거나 다익스트라 알고리즘을 $\bigO(E + V \log V)$ 단계로 실행할 수 있습니까? 우리는 다중 로그(poly-logarithmic) 오버헤드 범위 내에서 이에 긍정적으로 답합니다. 우리는 먼저 다중 로그 너비와 가장 오른쪽 고유 하드 어텐션을 갖는 유한 정밀도 트랜스포머에 대해 이를 확립한 다음, 유한 너비와 로그 정밀도를 갖는 두 가지 더 실용적인 설정으로 결과를 강화합니다: 추론이 토큰이 아닌 벡터 형태를 취하는 연속형 CoT와 트랜스포머 층이 순환(선형 RNN) 층 위에 있는 하이브리드 아키텍처입니다. 이 세 가지 경우 모두에서, 우리는 CoT가 $n$에 대한 다중 로그 오버헤드만으로 어떤 워드 RAM 알고리즘도 효율적으로 시뮬레이션할 수 있음을 발견했습니다. 이 오버헤드는 워드 RAM이 "플랫(flat)" 명령어 세트를 가질 때 로그 제곱으로 줄어들고, 곱셈이 없는 플랫 명령어의 경우 로그 수준으로만 줄어듭니다 -- 이는 워드 RAM에 대해 이차 오버헤드가 필요한 알려진 튜링 머신의 CoT 시뮬레이션과는 현저한 대조를 이룹니다.
원문 초록
The increasing popularity of \emph{reasoning} models -- language models that output a series of reasoning or thought tokens before producing an answer -- is justified, in part, by theoretical results showing that chain-of-thought (CoT) transformers can simulate Turing machines, and thus perform arbitrary computation. However, the Turing machine, while suitable for complexity-theoretic analysis, is not convenient, intuitive, or efficient for discussing algorithms. Algorithms are typically designed and analyzed at a higher level of abstraction, captured by the \emph{Word RAM} model with random-access memory and unit-cost operations on $\bigO(\log n)$-bit words. As a result, Word RAM algorithms can be substantially more efficient than their Turing machine counterparts, raising the question: \emph{Can CoT transformers efficiently simulate Word RAM algorithms?} For instance, can they sort $n$ items in $\bigO(n \log n)$ steps or run Dijkstra's algorithm in $\bigO(E + V \log V)$ steps? We answer affirmatively, up to poly-logarithmic overhead. We first establish this for finite-precision transformers with poly-logarithmic width and rightmost unique hard attention, then strengthen the result to two more practical settings with finite width and log-precision: \emph{continuous} CoT, where reasoning takes the form of vectors rather than tokens, and a \emph{hybrid} architecture in which transformer layers sit atop a recurrent (linear RNN) layer. In all three cases, we find that CoT \emph{can} efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in $n$. This overhead reduces to log-square when the Word RAM has a ``flat'' instruction set, and only logarithmic for multiplication-free flat instructions -- in stark contrast to known CoT simulations of Turing machines, which require quadratic overhead over Word RAM.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.19697v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
대규모 추론 모델에서 추론 시점 역량과 효율성의 스케일링
Scaling of Capability and Efficiency at Inference Time in Large Reasoning Models
역량과 효율성은 대규모 언어 모델(LLM)에서 추론의 두 가지 핵심 차원이다. 역량은 주어진 문제를 올바르게 풀 능력을, 효율성은 제한된 자원으로 그렇게 할 수 있는 능력을 가리킨다. LLM이 사고의 연쇄(Chain-of-Thought, CoT) 추론을 사용해 난이도가 통제된 문제를 풀 때, 올바르게 풀린 문제 수와 정답에 도달하는 데 필요한 토큰(token) 수는 모두 문제 난이도와 모델(model) 크기에 따라 달라진다. 그러나 이러한 요인들이 역량과 효율성을 어떻게 공동으로 형성하는지는 여전히 잘 이해되지 않았다. 본 연구에서는 계층 베이지안(hierarchical Bayesian) 모델을 사용해 DeepSeek-R1-Distill 모델 계열의 LLM에 대해 산술 및 알고리즘 추론 문제 네 클래스 전반에서 역량과 효율성을 평가한다. 고정된 모델 크기에서, 사례를 올바르게 풀 확률은 문제 난이도의 대리 변수인 사례 크기에 대해 대략 지수적으로 감쇠한다. 감쇠 스케일은 모델 크기에 대해 아선형(sublinearly)으로 증가하며, 이는 더 큰 모델이 더 역량이 높지만 역량 향상이 스케일(scale)에 따라 수확 체감(diminishing returns)을 보임을 나타낸다. 출력 길이는 난이도의 대리 변수인 사례 크기에 대해 거듭제곱 법칙(power law)으로 증가한다. 그러나 이 거듭제곱 법칙의 매개변수는 모델 크기에 따라 체계적으로 변하지 않으며, 이는 더 큰 모델이 더 효율적이 되지 않음을 시사한다. 종합하면, 이러한 결과는 더 역량 있는 AI 시스템을 개발하기 위한 전략으로서 순진한 스케일링(naive scaling)의 잠재적 한계를 드러낸다: 역량은 수확 체감과 함께 개선되지만, 효율성은 거의 또는 전혀 개선되지 않는다.
유능하면서도 간결한: 최전선 모델에서 숨겨진 사고의 연쇄 추출 및 특성화
Capable yet Parsimonious: Extracting and Characterizing Hidden Chain-of-Thought in Frontier Models
최전선 언어 모델의 급격한 능력 향상은 널리 개선된 추론 능력 덕분으로 여겨지지만, 폐쇄형 시스템에서는 원시 사고의 연쇄(CoT) 추적이 숨겨져 있어 이를 검증할 수 없다. 표준 API 기능을 통해 간단한 사용자 정의 도구를 등록함으로써, 우리는 최전선 모델이 중간 추론을 외부화하도록 유도한다. 이러한 추적이 진정한 추론이 아니라 사후 합리화를 반영할 수 있기 때문에, 먼저 오픈소스 모델에서 네이티브 CoT와 대조 평가하고 GPT-6 Astra를 포함한 폐쇄형 최전선 모델로 확장한다. 추출된 추론은 네이티브 추론 성능과 일치하며, 경쟁 수학·과학·코드 생성 전반에서 추론 없음 기준선을 크게 능가함을 확인한다. 이어 최전선 모델이 중간 추론을 어떻게 구조화하는지 특성화한다. 토큰 효율, 추론 단계 유형, 유도된 추론 트리에 걸쳐, 모델이 추론을 외부화·압축·조직하는 방식에서 체계적 차이를 확인한다. Astra는 토큰 효율적인 지향적 추론을 보이며, 더 일찍 올바른 궤적을 선택하는 한편 기초 단계는 내부에서 처리하고 핵심 추론만 외부화한다. 이러한 결과는 벤치마크 점수를 넘어 최전선 모델 추론에 대한 행동적 관점을 제공한다.
LIMIT: Text-to-SQL에서 지시 미세조정은 적을수록 더 낫다
LIMIT: Less Is More for Instruction Tuning in Text-to-SQL
대규모 언어 모델(LLM)은 추론 강화 미세조정을 통해 Text-to-SQL에서 눈에 띄는 진전을 이뤘지만, 기존 접근법은 대체로 규모가 성능을 이끈다는 가정 아래 방대한 지시 코퍼스에 의존한다. 우리는 효과적인 Text-to-SQL 지시 미세조정을 위해 필요한 최소 데이터 요구량이 무엇인지라는 근본적 질문을 조사함으로써 이러한 패러다임에 도전한다. 우리는 LIMIT(Less Is More for Instruction Tuning in Text-to-SQL)를 제안한다. 이는 예시를 전략적으로 선별할 때 극도로 소규모인 학습 집합만으로도 강력한 데이터베이스 추론이 창발할 수 있음을 보여 주는 데이터 중심 프레임워크이다. LIMIT는 네 단계로 동작한다: 모델의 학습 프런티어(learning frontier) 내 샘플을 식별하는 난이도 인식 필터링, 일관성 기반 선별과 함께하는 사고의 연쇄(Chain-of-Thought) 합성, LLM-as-judge를 통한 다차원 품질 점수화, 스키마 커버리지와 샘플 품질을 공동으로 극대화하는 유전 알고리즘 최적화. BIRD 및 Spider 벤치마크에서 LIMIT는 각각 796개와 863개 샘플만 선별하면서 100% 테이블 커버리지를 달성하여 Qwen3-8B가 실행 정확도(execution accuracy) 69.1%와 88.9%에 이른다. 이 결과는 20배 더 많은 데이터로 학습한 방법을 능가하며 오픈소스 접근법 가운데 새로운 최첨단(state-of-the-art)을 세운다. 우리의 발견은 규모보다는 신중한 데이터 큐레이션이 효율적인 Text-to-SQL 학습의 핵심임을 시사한다.
PACE-dLLM: 확산 언어 모델을 위한 신뢰도 절벽 추정 기반 탄력적 블록 디코딩
PACE-dLLM: Elastic Block Decoding via Confidence Cliff Estimation for Diffusion Language Models
정교한 축출 정책이 실패할 때: LLM 접두 문맥 재사용을 위한 캐시 교체 정책의 재고
When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
KDFP: 대규모 언어 모델의 지식 증류를 위한 제1원리적 접근법
KDFP: A first-principles approach to knowledge distillation in large language models
지식 증류(knowledge distillation)는 더 크고 성능이 뛰어난 교사 모델의 표현(representation)을 활용해 작고 효율적인 학생 모델을 학습(training)시킴으로써 그 역량을 향상시키는 잘 정립된 기법입니다. 대규모 언어 모델(LLM) 증류에 관한 최근 연구의 상당수는 지시사항 준수(instruction following), 사고의 연쇄(Chain-of-Thought) 추론, 도구 사용 등 사후 학습(post-training) 과정에서 습득된 능력을 증류하는 데 집중되어 왔습니다. 이로 인해 엣지 기기 배포에 적합한 효율적이고 프라이버시가 보장되는 시스템을 개발하는 데 필수적인 LLM의 일반 지식 증류 연구에는 큰 공백이 남게 되었습니다. 본 연구에서는 이전 연구들의 교훈을 평가하고 새로운 탐색을 수행하는 제1원리적(first-principles) 접근법을 취하여 현대 LLM에 적합한 증류 방법론을 개발합니다. 본 논문에서는 LLM의 화이트박스 일반 지식 증류를 위한 새로운 방법론인 KDFP를 제시합니다. 실험을 통해 KDFP가 임시 매개변수(parameter) 감축을 통해 학습 효율성을 최대 99.1%까지 향상시키면서, 9개 벤치마크 전반에서 기존 기법들을 1.6% $-$ 4.9% 능가함을 입증합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.