arXiv:2606.27721v1 cs.LG

커리큘럼으로 추론 학습 II: 조합적 일반화

Learning to Reason with Curriculum II: Compositional Generalization

Nived Rajaraman, Audrey Huang, Miroslav Dudik, Robert Schapire, Dylan Foster, Akshay Krishnamurthy

제출 2026-06-26

한국어 초록

조합적 일반화, 즉 더 단순한 하위 문제에 대한 해를 조합하여 복잡한 문제를 푸는 능력은 자연 지능과 인공 지능 모두의 근본적인 능력이며, 사고의 연쇄(chain-of-thought) 추론의 핵심 메커니즘이기도 하다. 그러나 조합적 일반화의 이론적 기반은 여전히 잘 이해되지 않았다: 문제를 부분으로 분해하는 것이 직접 풀는 것보다 언제, 왜 더 효율적인 학습을 가능하게 하는가? 우리는 반자동기(semiautomata)를 시뮬레이션하는 학습(순차 계산의 $T$ 단계 결과를 예측하는)이라는 표준 문제를 통해 이 질문을 연구한다. 이 모델은 상태 추적, 정규 언어 인식, 모듈러 산술을 포괄한다. 우리는 이 시리즈의 I편을 기반으로 하는 자동 커리큘럼(autocurriculum) 접근법, 즉 더 긴 시퀀스를 더 짧은 하위 문제로 재귀적으로 분해하고 이를 학습하여 해를 구한 뒤 해를 조합하는 방식이 직접적인 방법보다 훨씬 더 나은 통계적 복잡도를 달성함을 보인다. (i) 계산의 중간 상태에 대한 대화형 피드백을 받는 지도 미세조정(SFT)에서 영감을 받은 설정에서는, 커리큘럼이 단 $2^{\mathcal{O}(\sqrt{\log T})}$개의 감독 토큰만으로 학습을 가능하게 한다. 즉 시퀀스 길이 $T$에 대해 아다(subpolynomial)적이며, 직접 시뮬레이션에 필요한 $Ω(T)$ 토큰 장벽을 극복한다. (ii) 결과 검증기(outcome verifier)를 사용하여 사전학습된 참조 모델을 개선하는 검증 가능 보상 강화학습(RLVR)에서 영감을 받은 설정에서는, 커리큘럼이 참조 모델에 대한 요구사항을 전체 시퀀스 길이 $T$에서의 커버리지에서 훨씬 짧은 블록 길이 $B \ll T$에서의 커버리지로 줄인다는 것을 보인다. 이는 지수적으로 더 약한 조건이다.

원문 초록

Compositional generalization, the ability to solve complex problems by combining solutions to simpler sub-problems, is a fundamental capability of both natural and artificial intelligence, and a key mechanism underlying chain-of-thought reasoning. However, the theoretical underpinnings of compositional generalization remain poorly understood: when and why does decomposing a problem into parts yield more efficient learning than solving it directly? We study this question through the canonical problem of learning to simulate semiautomata (predicting the outcome of $T$ steps of sequential computation), a model that captures state tracking, regular language recognition, and modular arithmetic. We show that an autocurriculum-based approach building on Part I of this series, recursively decomposing longer sequences into shorter sub-problems, learning to solve them, and composing the solutions, achieves dramatically better statistical complexity than direct methods. (i) For a setting inspired by supervised fine-tuning (SFT) where the learner receives interactive feedback on intermediate states of the computation, curriculum facilitates learning from only $2^{\mathcal{O}(\sqrt{\log T})}$ tokens of supervision; i.e., subpolynomial in the sequence length $T$, overcoming the $Ω(T)$ token barrier required by direct simulation. (ii) For a setting inspired by reinforcement learning with verifiable rewards (RLVR), where the learner improves a pre-trained reference model using an outcome verifier, we show that curriculum reduces the requirement on the reference model from coverage at the full sequence length $T$ to coverage at a shorter block length $B \ll T$, an exponentially weaker condition.

제출 이력

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

  1. arXiv:2606.27721v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2609.28085v1cs.LG공통 태그 Reinforcement Learning, Computational Efficiency, curriculum learning

잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝

Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling

잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.

arXiv:2610.13594v1cs.AI공통 태그 Reinforcement Learning, Math

MENTOR: 온-정책 교육적 개입을 통한 실패로부터의 학습

MENTOR: Learning from Failure with On-Policy Pedagogical Intervention

검증 가능한 보상을 활용한 강화학습(RLVR)은 대형 추론 모델의 핵심 동력이지만, 과제 난이도가 갑자기 높아지면서 학습 신호가 사라지는 훈련 실패 현상인 "제로 보상 붕괴(zero-reward collapse)"에 취약하다. 우리는 이러한 실패한 궤적을 폐기하는 기존 방식이 낭비적이라고 주장한다. 이 궤적들은 모델의 인지적 공백에 대한 귀중한 진단 정보를 담고 있으며, 이는 회복을 위해 활용될 수 있는 긍정적인 측면이기 때문이다. 그러나 기존 해결책들은 사전 정의된 힌트 라이브러리와 같은 정적인 "오프-정책(off-policy) 방식"의 개입으로 퇴행하거나 사후적(post-hoc) 보정을 수행하는 경우가 많아, 붕괴에서 벗어나는 데 필요한 적응적이고 미래지향적인 안내를 제공하지 못한다. 이를 해결하기 위해, 우리는 온-정책(on-policy) 교육적 개입으로의 패러다임 전환을 제안하고, 실시간 멘토 역할을 하는 다중 에이전트 프레임워크인 MENTOR를 소개한다. MENTOR는 실패의 근본 원인을 실시간으로 진단하고, 학습 에이전트의 다음 시도를 안내하기 위해 목표가 명확한 교육적 프롬프트를 동적으로 생성한다. 플러그 앤 플레이 모듈로서, MENTOR는 훈련 인프라를 수정하지 않고도 GRPO와 같은 기존 정책 최적화 파이프라인에 매끄럽게 통합된다. 수학 및 코드 생성에 대한 광범위한 실험 결과, MENTOR는 제로 보상 붕괴를 효과적으로 완화하며 최신 베이스라인들을 능가하는 것으로 나타났다. 특히, Llama-3.2-3B-Instruct에서는 기본 모델 대비 평균 최대 78.3%의 상대적 성능 향상이라는 큰 폭의 개선을 달성했다.

arXiv:2610.13669v1cs.AI공통 태그 Math, curriculum learning

한 단계 더 어렵게, 지나치지 않게: GRPO에서 커리큘럼 난이도 점진적 확장의 이점과 한계

A Step Harder, Not a Step Too Far: The Benefits and Limits of Curriculum Difficulty Progression in GRPO

커리큘럼 학습(Curriculum learning)은 일반적으로 학습 샘플을 쉬운 것부터 어려운 순서로 구성합니다. GRPO에서는 중간 난이도 샘플이 유익한 그룹 상대적 학습 신호를 생성할 가능성이 더 높기 때문에 온라인 선택 시 매력적이며, 이를 우선시하면 학습 효율성을 향상시킬 수 있습니다. 그러나 이러한 샘플을 지속적으로 선택하는 것이 최종 모델 성능의 극대화로 이어지는지, 또는 더 어려운 샘플로 점진적으로 나아가는 것이 학습에 도움이 될 수 있는지는 여전히 불분명합니다. 한편, 정책(policy)이 발전함에 따라 샘플 난이도 또한 변화하므로, 고정된 난이도 추정치는 현재 정책과 불일치할 수 있습니다. 따라서 본 연구에서는 현재 정책에 따라 샘플 난이도를 재추정하고, 쉬운 것부터 어려운 것으로 진행하는 커리큘럼 학습의 원리에 착안하여 활성 난이도 구간을 점진적으로 더 어려운 샘플 쪽으로 전환하는 단계별 커리큘럼을 설계하고 평가합니다. GSM8K 실험 결과, 지속적인 중간 난이도 선택이 가장 우수한 성능을 달성하지는 못하는 것으로 나타났습니다. 3개의 무작위 시드 전반에 걸쳐, 적당히 더 어려운 난이도 구간으로 진행했을 때 테스트 정확도는 고정 중간 커리큘럼의 $0.6449 \pm 0.0024$와 비교하여 $0.6591 \pm 0.0077$로 향상되었습니다. 그러나 난이도 구간을 더 어렵게 추가로 확장하면 정확도가 $0.6405 \pm 0.0053$으로 감소합니다. 이러한 결과는 단계별 난이도 확장이 지속적인 중간 난이도 선택보다 뛰어난 성능을 보일 수 있지만, 그 이점이 단조적이지는 않음을 보여줍니다. 따라서 효과적인 GRPO 커리큘럼은 중간 난이도를 넘어 확장함으로써 이점을 얻을 수 있지만, 지나치게 어려운 샘플로의 과도한 진행은 피해야 합니다.

arXiv:2610.13744v1cs.AI공통 태그 Reinforcement Learning, Math

점수만 매기는 특권적 교사는 탐색할 수 없다: 추론을 위한 비평 조건부 온-정책 자기 증류

A Privileged Teacher That Only Scores Cannot Search: Critique-Conditioned On-Policy Self-Distillation for Reasoning

온-정책(on-policy) 자기 증류는 검증 가능한 보상(verifiable-reward) 기반 강화학습의 희소한 결과 신호를 토큰 단위의 조밀한 크레딧으로 대체할 것을 약속한다: 참조 해답에 조건화된 교사가 학생 자신의 롤아웃(rollout)을 채점하고, 그 결과로 나타나는 분포 변화가 다시 정책으로 증류된다. 우리는 이 채점 신호가 실제로 교정적 크레딧을 담고 있는지 조사한다. 학생 롤아웃 내의 정답(gold) 오류 구간을 이용하여, 자기 증류 목적함수가 사용하는 두 가지 신호, 즉 전체 분포 KL과 토큰 로그 비율(log-ratio)이 두 가지 속성, 즉 오류를 지역화(localize)하는지 여부와 학생의 오류 토큰으로부터 확률을 밀어내는지 여부를 테스트한다. 두 신호 모두 이러한 속성을 전혀 보이지 않으며, 동일한 문제 내에서 올바른 롤아웃과 잘못된 롤아웃을 신뢰성 있게 구분하지도 못한다. 우리는 이러한 실패가 구조적이라고 주장한다: 추론 과정(reasoning trace)에서 오류를 찾아내는 것 자체가 하나의 탐색(search) 문제인 반면, 채점을 수행하는 교사는 명시적으로 그러한 탐색을 수행하도록 요구받지 않는다. 동일한 모델이 동일한 특권 정보를 가지고도, 비평(critique)을 생성하도록 허용되었을 때는 오류를 훨씬 더 잘 지역화한다. 이는 \emph{비평 조건부 자기 증류(critique-conditioned self-distillation)}의 동기가 된다: 먼저 현재 롤아웃에 대한 비평을 생성한 다음, 그 비평에 채점 교사를 조건화하는 것이다. 그 결과로 나오는 신호는 오류를 지역화하고, 오류 구간 내에서 교정적이며, "Wait", "But", "Actually"와 같이 역추적(backtracking)을 시작하는 토큰 쪽으로 확률을 이동시킨다. 우리는 나아가 이 비평이 테스트 시점(test time)과 콜드 스타트(cold-start) GRPO 양쪽 모두에서 유용함을 보인다: 테스트 시점에서는 비평을 맥락에 포함한 채 잘못된 롤아웃을 재개하는 것이 샘플링만으로는 풀 수 없었던 수학 문제를 풀 수 있게 만들며, 콜드 스타트 GRPO에서는 검증 가능한 보상만으로는 전혀 이점 신호를 제공하지 못하는 프롬프트에 대해 이점(advantage) 신호를 제공한다.

arXiv:2610.02488v2cs.LG공통 태그 Computational Efficiency, Math

LLM을 에이전트로 활용하기: 비용은 얼마인가?

Harnessing LLMs as Agents: What Does It Cost?

언어 모델 에이전트는 제한된 컨텍스트(bounded context), 영속 메모리(persistent memory), 도구, 검증, 반복 실행을 관리하는 하네스(harness)에 점점 더 의존하고 있지만, 기존의 모델 능력 개념은 이러한 메커니즘이 소비하는 계산 자원을 정량화하지 못한다. 우리는 기저 의미론적 모델(semantic model)은 고정한 채 하네스 수준의 자원을 명시적으로 과금하는 자원 제약 추상화인 언어 모델 에이전트 머신(Language Model Agent Machine, LAM)을 도입한다. 우리는 네 가지 범주의 결과를 확립한다. 통신(Communication): LAM 실행은 동시적인 호출-전송 예산(call-transfer budget) 하에서 적-청 페블링(red-blue pebbling)과 인스턴스 단위로 동등하며, 이는 고전적인 입출력 하한(I/O lower bound)을 컨텍스트-메모리 트래픽으로 전이시킨다. 접근(Access): 메모리 인터페이스는 포인터 체이싱(pointer chasing)에서 무작위 접근과 비추측적(non-speculative) 순차 접근 사이의 $Θ(n)$ 격차를 포함하여 점근적 분리(asymptotic separation)를 유발한다. 재계산(Recomputation): 비트 반전(bit-reversal) DAG는 컨텍스트 용량 $C$와 영속 메모리 용량 $S$ 하에서 $Θ(n^2/(C+S)+n)$회의 모델 호출을 필요로 하며, 이는 저장된 중간 상태가 반복적인 의미론적 계산을 언제 피할 수 있는지를 정량화한다. 신뢰성(Reliability): 우리는 엄밀한 단계별(stage-local) 샘플링 한계, 불완전 검증(imperfect-verification)의 정확한 비용, 그리고 닫힌 형태의 최적 검증 간격을 갖는 영-데일리(Young-Daly) 유형의 체크포인트 법칙을 유도한다. GPT-6 Astra에 대한 통제 실험과 홀드아웃(held-out) 실험은 체크포인트 최적값, 프로그래밍적 검사(programmatic checking) 하에서의 정책 선택, 그리고 연쇄 MATH 과제에서 호출 단위(call granularity), 논리적 입력 트래픽, 신뢰성 간의 트레이드오프를 포함하여 통신 및 신뢰성 예측을 검증한다. 종합적으로, 이 결과들은 언어 모델 에이전트 하네스의 계산 비용에 대한 자원 이론(resource theory)을 제공한다.

arXiv:2610.01140v2cs.AI공통 태그 Computational Efficiency, Math

ReSolve: 선택적 생성 조정을 통한 후보 추론 재사용

ReSolve: Reusing Candidate Reasoning through Selective Generative Moderation

여러 해법을 샘플링하는 것은 최종 답변뿐만 아니라 중간 연역 과정과 미완성된 논증에도 연산량을 소모합니다. 본 논문에서는 선택적 생성 조정(selective generative moderation)을 통해 이러한 후보 추론 과정을 재사용하는, 학습(training)이 필요 없는 추론(inference) 절차인 ReSolve를 소개합니다. 답변 분포 제어기는 후보 간 의견이 일치하지 않거나 파싱 가능한 답변이 부족할 때 모델을 호출하여 기존 유도 과정을 검토하게 한 뒤, 생성된 해법을 유계 루프(bounded loop)에 통합합니다. 독립적으로 샘플링된 두 개의 후보 풀로 평가한 130개의 경시대회 수학 문제에서 Hybrid 점수 체계 기준, ReSolve는 동일한 4개의 후보에 대한 투표 방식이 기록한 91개 및 92개와 비교해 각각 100개와 99개의 정답을 얻었으며, 두 풀 모두에서 해당 투표 대비 정답이 오답으로 바뀐 경우는 없었습니다. 8개 샘플을 사용한 자기 일관성(self-consistency)은 실질적으로 훨씬 더 많은 토큰을 소비하면서 94개 및 96개의 정답을 얻은 반면, ReSolve는 두 평가에서 토큰을 각각 46.3% 및 47.2% 적게 사용했습니다. 정답 키, 투표 수, 상태별 출력 제한 규칙은 유지한 채 가시적인 유도 과정을 제거한 통제된 절제 연구(ablation)에서는 연산량이 증가했음에도 정답 수가 100개에서 93개로 감소하여 정확도가 떨어졌습니다. 선택적 조정과 항상 켜져 있는 균일(Uniform) 조정은 모두 97개의 문제를 해결했으나, 선택성을 적용함으로써 조정 토큰을 약 54%, 전체 파이프라인 토큰을 6.2% 줄였습니다. 이러한 결과는 후보 추론 과정이 재사용 가능한 추론 연산이라는 점을 뒷받침합니다. 다만 추가 샘플링 대비 정확도 우위나 특화된 경로 지침의 뚜렷한 이점을 입증하지는 않습니다.

토론

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