arXiv:2502.12465

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification

Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, Dylan J. Foster

제출 2025-02-18

원문 초록

Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling, but, in practice, suffers from error amplification, where errors in the model compound and generation quality degrades as sequence length $H$ increases. From a theoretical perspective, this phenomenon should not appear in well-specified settings, and, indeed, a growing body of empirical work hypothesizes that misspecification, where the learner is not sufficiently expressive to represent the target distribution, may be the root cause. Under misspecification -- where the goal is to learn as well as the best-in-class model up to a multiplicative approximation factor $C\geq 1$ -- we confirm that $C$ indeed grows with $H$ for next-token prediction, lending theoretical support to this empirical hypothesis. We then ask whether this mode of error amplification is avoidable algorithmically, computationally, or information-theoretically, and uncover inherent computational-statistical tradeoffs. We show: (1) Information-theoretically, one can avoid error amplification and achieve $C=O(1)$. (2) Next-token prediction can be made robust so as to achieve $C=\tilde O(H)$, representing moderate error amplification, but this is an inherent barrier: any next-token prediction-style objective must suffer $C=\Omega(H)$. (3) For the natural testbed of autoregressive linear models, no computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e^{(\log H)^{1-\Omega(1)}}$; however, at least for binary token spaces, one can smoothly trade compute for statistical power and improve on $C=\Omega(H)$ in sub-exponential time. Our results have consequences in the more general setting of imitation learning, where the widely-used behavior cloning algorithm generalizes next-token prediction.

함께 살펴볼 논문

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

arXiv:2610.03391v2cs.CV공통 태그 Imitation Learning

월드 액션 모델을 위한 비디오 기반 네이티브 액션 사전확률 학습

Native Action-Prior Learning from Videos for World Action Models

월드 액션 모델(World action models)은 미래의 시각적 역역학과 로봇 액션 예측을 통합하지만, 액션 레이블이 지정된 로봇 궤적이 필요하다는 점에서 확장성에 한계가 있습니다. 관찰 전용(observation-only) 비디오는 상호작용 역학에 대한 풍부한 정보를 담고 있지만, 기존 접근법들은 대개 이를 사후에 제어용으로 조정해야 하는 시각적 표현을 사전학습(pre-training)하는 데 사용하거나, 추후 로봇 명령으로 그라운딩되는 잠재 액션(latent actions)을 추론하는 데 활용하는 데 그칩니다. 본 연구에서는 간접적인 표현-제어 간 전이나 별도의 잠재 액션 모델 없이 관찰 전용 비디오로부터 액션 정책을 직접 사전학습하는 네이티브 액션 사전확률 학습(native action-prior learning)을 도입한 NAVA-WAM을 제시합니다. 우리의 학습(training)은 2단계로 구성됩니다. 첫째, 관찰 전용 비디오를 통해 사전학습을 진행하며, 시각적 전이에 대한 미래 비디오 플로우 매칭(flow-matching) 감독 신호가 전이 구조화된 결합 어텐션을 통해 전파되어 Action-DiT를 최적화하고 액션 관련 사전확률을 학습합니다. 둘째, 액션 레이블이 지정된 시연 데이터를 사용하여 결합 비디오-액션 플로우 매칭을 통해 로봇 제어를 위한 Action-DiT 사후학습(post-training)을 수행하며, 이때 비대칭 어텐션이 시각 브랜치를 반복적인 액션 노이즈 제거 과정과 분리하여 효율적인 액션 전용 추론(inference)을 가능하게 합니다. 광범위한 실험 결과, NAVA-WAM은 분포 내(in-distribution) 및 분포 외(out-of-distribution) 설정 모두에서 기존 접근 방식을 일관되게 능가하는 동시에 뛰어난 액션 레이블 효율성과 효과적인 실제 로봇 일반화 성능을 입증했습니다. 이러한 결과는 네이티브 액션 사전확률 학습이 관찰 전용 비디오로부터 액션 정책을 직접 사전학습하는 효과적인 접근법임을 입증하며, 액션 레이블 기반 로봇 데이터를 뛰어넘는 확장 가능한 경로를 제공합니다.

arXiv:2609.28182v2cs.AI공통 태그 Imitation Learning

AI 기반 그리드 엣지 협조를 위한 유한 표본 확률적 안전성 인증

Finite-Sample Probabilistic Safety Certification for AI-Based Grid-Edge Coordination

다수의 유연한 그리드 엣지 기기를 조정하면 시간과 자본이 많이 드는 전력망 증설의 필요성을 줄일 수 있다. 다중 에이전트 강화학습이나 모방학습과 같은 인공지능(AI) 기반 제어 방법은 실시간 의사결정 확장성 덕분에 이러한 조정에 유망하다. 그러나 시스템 운영자에게는 주어진 AI 시스템이 배포에 충분히 안전한지 판단할 독립적이고 엄밀한 방법이 여전히 필요하다. 본 논문은 AI 기반 그리드 엣지 조정을 위한 \emph{유한 표본} 확률적 안전성 인증 프레임워크를 개발한다. 핵심 아이디어는 입력–AI–의사결정–평가의 전체 워크플로를 운영자가 정의한 안전 사양 하의 이진 비안전 결과로 축약한 다음, 정확한 이항 추론을 사용하여 해당 비안전 운영 확률을 인증하는 것이다. 보류된 보정 시나리오 집합이 주어지면, 이 프레임워크는 가장 엄밀한 단측 상한 인증서와 거짓 안전 인증의 확률을 제어하는 수락/거부 배포 기준을 반환한다. 인증은 향후 운영과 \emph{다를} 수 있는 보정 분포에 대한 것이므로, 우리는 명목 인증서를 AI 모델의 취약성을 조사하는 데 널리 쓰이는 개념인, 물리적으로 해석 가능한 표본 공간 적대적 공격과 추가로 결합한다. 1,000개 에이전트 AI 모델(독립 파라미터)을 사용한 그리드 엣지 유연성 조정 사례 연구를 통해, 안전성 보장과 함께 롤링 윈도우 방식의 학습–인증–배포 흐름에 적대적 공격을 통합하는 것의 가치를 검증한다.

arXiv:2610.10857v2cs.AI공통 태그 Imitation Learning

호라이즌 불변 행동 복제를 위한 자기 지도 키프레임 발견

Self-Supervised Keyframe Discovery for Horizon-Invariant Behavior Cloning

비마르코프 환경에서의 행동 복제(BC)는 정책이 장기 지평에 걸친 문맥 정보를 추론해야 하므로 어려운 문제이다. 기존 정책 아키텍처는 장기 의존성을 포착하기 위해 순환 또는 어텐션 기반 메커니즘에 의존한다. 그러나 순환 모델은 시간에 대한 역전파에서 은닉 상태 붕괴와 기울기 불안정성을 겪으며, 어텐션 기반 모델은 근본적으로 문맥 길이에 의해 제한된다. 이러한 문제를 해결하기 위해 본 논문은 무작위로 추출한 과거 관측으로부터 목적 함수를 학습하고 이를 키프레임 선택의 보상으로 사용하여 정보상 핵심적인 관측 집합($\textit{mnemonics}$)을 $\textit{발견}$하는 새로운 자기지도 방법인 Keyframe Mnemonics를 제안한다. 이후 발견된 키프레임을 조건으로 하는 BC 정책을 학습하여 행동 분포를 모델링한다. 단순성 편향 가정 하에서, 본 정식화는 정책의 작업 기억에 의사결정과 관련된 소수의 키프레임만을 유지하면서도 무한 지평에 걸친 문맥 유지 보장을 제공한다. 합성 기억 도메인에서 평가한 결과, mnemonic 조건부 BC 정책은 $100$%의 성공률(SR)을 달성하고 성능 저하 없이 학습 지평을 수 자릿수 넘어서는 지평으로 일반화한다. 또한 기억 집약적인 로봇 조작 벤치마크에서 $23$개 과제에 걸쳐 가장 강력한 기준선 대비 평균 절대 SR이 $13.9$% 향상되었다. 마지막으로 실제 로봇에서 $20\times$ 더 긴 시간 지평에서도 $80$%의 SR로 일반화됨을 보인다. 코드와 영상은 https://keyframe-mnemonics.github.io 에서 확인할 수 있다.

arXiv:2607.20345v2cs.RO공통 태그 Imitation Learning

실험실-매장 격차 해소: 소매 휴머노이드를 위한 데이터 효율적 사후 학습 및 경험 기반 학습 VLA 프레임워크

Closing the Lab-to-Store Gap: A Data-Efficient Post-Training and Experience-Driven Learning VLA Framework for Retail Humanoids

벤치마크 성능과 신뢰할 수 있는 실세계 운용 사이의 격차를 좁히는 것은 실행 오류, 분포 이동(distribution shift), 환경 변동성을 처리해야 하는 비전-언어-행동(VLA) 휴머노이드 로봇의 핵심 과제로 남아 있다. 본 논문은 DEED(Data-Efficient Post-Training and Experience-Driven Learning, 데이터 효율적 사후 학습 및 경험 기반 학습)를 제안하며, 이는 Unitree G1-Edu 휴머노이드 로봇과 GR00T N1.6 파운데이션 모델을 사용한 슈퍼마켓 과자 재입고 작업에서 평가된 시스템 수준 접근법이다. DEED는 세 가지 핵심 구성 요소로 이루어진다: (1) 제어 주파수 정렬, 데이터 큐레이션, 작업 관련 시각적 강조, VLA 의존도 감소를 포함하는 데이터 효율적 사후 학습 파이프라인; (2) 텍스트 기반 advantage 접두 문맥과 비전-언어 가치 함수를 통해 RECAP에서 적용한 경험 기반 정제의 실세계 연구; (3) 분포 내(in-distribution) 및 분포 외(out-of-distribution) 행동을 연구하기 위한 잠재 공간(latent-space) 분석 도구. 우리의 결과는 실험실-매장 격차를 메우는 것이 주로 아키텍처 문제가 아니라 시스템 통합 과제임을 시사한다. 신중한 데이터 설계와 표적화된 사후 학습은 단순 미세조정에서 실패하는 정책을 단일 GPU만으로 유능한 실세계 시스템으로 변환할 수 있다.

arXiv:2607.22535v2cs.RO공통 태그 Imitation Learning

로봇 렌더링을 통한 로봇 요인 분리 월드 모델

Robot-Factored World Models via Robot Rendering

행동 조건부 비디오 월드 모델은 초기 관측과 행동 신호로부터 미래 관측을 예측한다. 우리는 행동 실현과 장면 반응 예측을 분리하기 위해 두 가지 로봇 특유의 요인을 월드 모델 밖으로 옮기는 로봇 분해형 월드 모델(RoFacto)을 제안한다. 첫째는 행동 실현으로, 각 명령 시퀀스를 장면 접촉 없이 로봇 자체의 제어기와 기구학을 통해 전개하여, 미래의 실현된 상태를 요구하지 않는 배포 가능한 공칭 궤적을 얻는다. 둘째는 로봇 렌더링으로, 이 공칭 궤적을 로봇 URDF를 통해 렌더링함으로써 로봇의 형상, 기구학, 외형을 모델에서 분리하여 명시적인 렌더링된 로봇 기하로 옮긴다. 쌍을 이루는 엔드 이펙터 및 장면 깊이는 접촉과 가림에 대한 기하학적 단서를 제공하며, 카메라를 고려한 정적 RGB 문맥과 렌더링된 로봇 기하는 시점과 형태를 가로지르는 공유 시각 인터페이스를 이루고, 모델은 이를 통해 장면 반응을 학습한다. 실험 결과, 렌더링 인터페이스는 벡터 조건부 기준선을 능가하고, 보지 못한 로봇 형태로의 전이를 지원하며, 리타기팅된 인간 시연으로부터 로봇 조작 비디오를 생성한다.

arXiv:2609.27144v2cs.LG공통 태그 Prediction

미관측 교란 변수에 강건한 위험 점수 학습

Learning Risk Scores Robust to Unobserved Confounders

미관측 교란의 영향을 받는 역사적 관찰 데이터로부터, 희소 자원이나 개입 대상 개인의 우선순위를 정하기 위한 위험 점수를 학습하는 문제를 다룬다. 누가 희소 자원을 받을지에 대한 결정은 설문 응답과 같이 기록된 특성에 기반한 위험 점수에 의해 종종 안내된다. 이러한 위험 점수는 개인의 특성, 배분 결정, 결과에 대한 역사적 기록인 관찰 데이터로부터 직접 학습되는 경우가 점점 늘고 있다. 역사적 배분 정책이 도입한 바이어스를 보정하는 역 성향 가중치(inverse propensity weighting, IPW)와 같은 표준 방법은, 역사적 결정 과정이 기록된 특성으로 완전히 설명될 수 있다면 정확한 위험 점수를 학습하는 데 사용될 수 있다. 그러나 실무에서는 역사적 결정이 종종 기록되지 않은 정보에 의존하여, 학습된 위험 점수가 과거 우선순위를 이끌었던 기록되지 않은 상황을 가진 개인들을 정확히 체계적으로 과소 우선순위화하게 만든다. IPW를 기반으로, 이러한 종류의 미관측 교란에 강건한 위험 점수를 학습하는 방법을 제안한다. 미관측 교란 하에서는 성향 가중치를 신뢰할 수 있게 추정할 수 없으므로, 대신 관측 가능한 데이터와 교란 정도에 대한 도메인 정보 기반 추정치로 결정되는 불확실성 집합에 속하는 것으로 취급하며, 인과 추론(causal inference)의 민감도 분석(sensitivity analysis)과 Wasserstein 분포적 강건 최적화(Wasserstein distributionally robust optimization)를 결합한다. 그 결과 강건 위험 점수 학습 문제는 표본 기반 근사를 허용하며, 이를 기성 솔버와 호환되는 지수 원뿔 프로그램(exponential cone program)으로 재공식화한다. UCI Machine Learning Repository의 데이터셋에서 파생된 반합성(semi-synthetic) 데이터에서 접근법의 효과를 입증한다. 제안 방법은 다른 지표를 손상하지 않으면서, 전통적 벤치마크 대비 보정(calibration)을 최대 29.2%까지, 최신(state of the art) 대비 최대 11.1%까지 개선한다.

토론

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