Why Code, Why Now: Learnability, Computability, and the Real Limits of Machine Learning

이 논문은 코드가 강화학습보다 학습 가능한 정보 구조를 가지고 있어 예측 가능한 확장이 가능한 반면, 대부분의 강화학습 문제는 피드백의 질적 차이로 인해 단순한 모델 크기 확장에 한계가 있음을 지적하며, 표현 가능성·계산 가능성·학습 가능성의 세 가지 속성 간 관계를 규명하는 5 단계 학습 가능성 계층 구조를 제안합니다.

핵심

1. 핵심 비유: "코딩 vs. 게임"

이 논문의 가장 중요한 통찰은 **코드 (프로그래밍 언어)**와 **강화학습 (RL, 게임 등)**의 차이에서 나옵니다.

• 코드 (성공하는 이유):

  • 비유: 코딩은 레고 블록을 쌓는 것과 같습니다.
  • 이유: 레고 블록을 잘못 끼우면 바로 '딸깍' 소리가 나고 조립이 안 됩니다. 문법 오류 (세미콜론 빠짐) 나 타입 오류는 즉시, 명확하게, 어디에서 잘못되었는지 알려줍니다.
  • 결과: AI 는 실수할 때마다 "여기서 틀렸어!"라는 구체적인 피드백을 받습니다. 그래서 AI 는 코드를 아주 잘 배웁니다.

• 강화학습 (실패하는 이유):

  • 비유: 강화학습은 안개 낀 미로를 찾는 것과 같습니다.
  • 이유: AI 가 미로를 헤매다가 출구에 도달하면 "성공!"이라는 점수만 받습니다. 하지만 어떤 길로 갔을 때 성공했는지, 어디서 실수했는지는 알려주지 않습니다.
  • 결과: AI 는 "어디서부터 잘못했지?"라고 추측만 해야 합니다. 점수가 낮으면 "다시 해봐"라고만 할 뿐, 구체적인 교훈을 주지 않습니다. 그래서 AI 는 아무리 많이 시도해도 똑같은 실수를 반복하거나, 엉뚱한 길로만 빠져나갑니다.

2. 학습의 5 단계 사다리 (Hierarchy of Learnability)

저자는 모든 문제를 학습하기 쉬운 정도에 따라 5 단계로 나누었습니다.

• 0 단계 (아무 정보 없음):
  • 비유: 완전한 암흑 속의 추측.
  • 설명: 정답과 오답의 차이가 전혀 보이지 않습니다. (예: "이 프로그램이 멈출까?") 아무리 많은 데이터를 줘도 소용없습니다.
• 1 단계 (적대적/반응형 정보):
  • 비유: 달리는 표적을 쏘는 것.
  • 설명: 표적 (정답) 이 AI 가 학습하는 속도에 맞춰 움직입니다. AI 가 학습하면 게임 규칙이 바뀌거나, 경쟁자가 AI 의 전략을 알아챕니다. (예: SNS 추천 알고리즘을 속이는 스팸 계정들)
• 2 단계 (노이즈가 있는 정보):
  • 비유: 거친 바다에서 나침반 보기.
  • 설명: 대략적인 방향은 알 수 있지만, 파도 (노이즈) 때문에 가끔은 엉뚱한 방향을 가리킵니다. 하지만 데이터를 많이 모으면 결국 정답에 가까워집니다. (예: 이미지 분류, 스팸 메일 필터링) - 대부분의 기존 AI 가 여기 있습니다.
• 3 단계 (간접적 정보):
  • 비유: 옳은 길만 보여주는 나침반.
  • 설명: "틀렸다"는 말은 들을 수 있지만, "정답은 이것이다"는 말은 들을 수 없습니다. 실수를 하면 걸러지지만, 정답을 확신할 수는 없습니다. (예: 자연어 생성, 코드 작성)
• 4 단계 (직접적/확실한 정보):
  • 비유: 정답이 적힌 해답지.
  • 설명: 한 줄 한 줄이 즉시 검증됩니다. 컴파일러가 "이건 문법 오류야"라고 바로 말해줍니다. 코드 생성이 이 단계의 혜택을 가장 많이 받습니다.

3. 왜 "모델 크기"만 키우는 건 위험한가?

많은 사람이 "AI 가 못 하면 더 큰 컴퓨터를 사면 되지"라고 생각합니다. 하지만 이 논문은 **"문제 자체가 배우기 힘든 구조라면, 컴퓨터를 아무리 크게 해도 소용없다"**고 말합니다.

• 비유: 수학 문제를 푸는 것 vs. 그림 그리기.
  • 그림 그리기 (학습 가능한 구조): 실수하면 "색이 어색해"라고 바로 고칠 수 있습니다. 모델을 키우면 더 예쁜 그림을 그립니다.
  • 수학 증명 (학습하기 어려운 구조): 논리적으로 하나라도 틀리면 전체가 무너집니다. 하지만 AI 는 통계적으로 "아마도 맞을 것 같다"고 추측할 뿐, 논리적으로 증명할 수는 없습니다. 모델을 키운다고 해서 갑자기 논리 증명이 가능해지지 않습니다.

4. 결론: 앞으로의 방향은?

이 논문의 결론은 매우 명확합니다.

1. 문제 자체를 분석하라: "모델이 부족해서인가?"가 아니라 "이 문제가 학습 가능한 구조인가?"를 먼저 물어봐야 합니다.
2. 피드백을 설계하라: AI 가 배우기 쉽게 하려면, "틀렸다"는 말만 하는 게 아니라 "어디가, 왜 틀렸는지" 구체적으로 알려주는 시스템을 만들어야 합니다.
3. 작은 목표부터 시작하라: 거창한 목표를 한 번에 달성하려 하지 말고, 검증 가능한 작은 단계로 쪼개서 학습시키는 것이 성공의 비결입니다.

한 줄 요약:

"AI 가 못하는 이유는 머리가 나빠서가 아니라, 배울 수 있는 '단서'가 문제 속에 없기 때문입니다. 우리는 AI 를 키우는 것보다, AI 가 배울 수 있도록 문제를 다시 설계하는 데 집중해야 합니다."

기술 요약

1. 문제 제기 (Problem Statement)

현재 인공지능 분야에서 코드 생성 (Code Generation) 과 강화학습 (Reinforcement Learning, RL) 의 성과에는 극명한 차이가 존재합니다.

• 코드 생성: 대규모 언어 모델 (LLM) 이 예측 목적 함수 (Supervised Learning) 로 훈련될 때, 복잡한 프로그램 작성, 리팩토링, 알고리즘 문제 해결 등에서 놀라운 일관된 진보를 보이고 있습니다.
• 강화학습 (RL): 상호작용적이고 폐루프 (closed-loop) 인 설계임에도 불구하고, 분포 변화 (distribution shift) 에 취약하며 대규모 상호작용 자원을 투입해도 일반적인 역량을 축적하는 데 실패하는 경우가 많습니다.

기존의 설명 (예: "RL 은 더 많은 연산량이 필요하다", "보상 신호가 희소하다") 은 이러한 격차를 설명하지 못합니다. 하드웨어, 최적화기, 시뮬레이터의 개선에도 불구하고 이 패턴이 지속된다는 사실은, 문제가 모델 아키텍처나 자원의 부족이 아니라 문제 자체의 정보 구조 (Information Structure) 에 기인함을 시사합니다.

이 논문은 "어떤 작업이 대규모 모델 하에서 학습 가능한가?"를 질문하며, 단순히 계산 가능 (computable) 하거나 표현 가능 (expressible) 한 것을 넘어, 실제 데이터와 상호작용 regimes 하에서 학습 가능한지를 분석합니다.

2. 방법론 및 핵심 개념 (Methodology & Key Concepts)

저자는 머신러닝의 성패를 결정짓는 핵심 요인으로 정보 구조 (Information Structure) 를 제시하며, 이를 바탕으로 다음과 같은 이론적 틀을 구축합니다.

2.1 학습 가능성의 5 단계 계층 구조 (Hierarchy of Learnability)

피드백의 질과 정보의 가시성에 따라 학습 문제를 5 단계로 분류합니다.

• Level 0 (무피드백/관측 불가능): 서로 다른 가설이 동일한 관측치를 생성합니다. (예: 정지 문제, 완전히 Goodhart 된 지표). 스케일링이 무의미합니다.
• Level 1 (적대적 피드백): 정보가 존재하지만 환경이 학습자의 전략에 반응하여 목표를 이동시킵니다. (예: 순위 알고리즘 게임, 반사적 학습). 수렴이 불안정합니다.
• Level 2 (노이즈 피드백): 확률적으로 구별 가능하지만 개별 관측치는 노이즈가 있습니다. (예: 이미지 분류, 스팸 탐지). PAC 학습 (Probably Approximately Correct) 이 적용됩니다.
• Level 3 (간접 피드백/일방적 증거): 잘못된 가설은 반증되지만, 옳음은 직접 확인되지 않습니다. (예: 형식 언어 학습, 프로그램 테스트). '무한한 생성 (Generation in the limit)'은 가능하지만 '식별 (Identification)'은 불가능할 수 있습니다.
• Level 4 (직접 피드백/결정론적 검증): 모든 출력을 즉시 결정론적으로 검증할 수 있습니다. (예: 타입 체크, 컴파일, 형식 증명). 코드의 컴파일러와 테스트 케이스가 이에 해당합니다.

2.2 세 가지 속성의 구분 및 관계

논문은 세 가지 계산적 속성을 엄격히 구분하고 그 관계를 규명합니다.

1. 표현 가능성 (Expressibility): 함수 클래스 내에 정답이 존재하는가? (∃f ∀x)
2. 계산 가능성 (Computability): 정답을 계산하는 정지 알고리즘이 존재하는가? (∃M ∀x, M is total)
3. 학습 가능성 (Learnability): 제한된 데이터와 상호작용 하에서 수렴하는 알고리즘이 존재하는가? (∃A ∀D ∀ε ∃m...)

핵심 통찰: 표현 가능성이나 계산 가능성은 학습 가능성을 보장하지 않습니다. 오히려 표현력이 지나치게 높으면 (VC 차원이 무한대) 학습이 불가능해질 수 있습니다.

2.3 코드 생성이 특별한 이유

코드가 학습에 유리한 이유는 다음 세 가지 정보 구조적 특성 때문입니다.

• 강한 구문 제약 (Hard Syntactic Constraints): 문법 오류는 즉시 감지되며 이진 (유효/무효) 신호를 제공합니다.
• 지역적 식별 가능한 오류 (Locally Identifiable Errors): 오류가 전체 문맥이 아닌 특정 줄과 위치를 가리키며, 밀집된 (dense) 피드백을 제공합니다.
• 강한 구성성 (Strong Compositionality): 부분의 의미가 전체 맥락에 의존하지 않아, 한 코드베이스에서 학습된 패턴이 다른 곳으로 전이됩니다.

이는 RL 의 이진형 패스/페일 (Pass/Fail) 보상 (단일 비트, 저차원, 구조적 정보 부재) 과 대조됩니다. RL 은 중간 단계를 가르치지 못하고 결과만 평가하므로 정보 밀도가 낮습니다.

3. 주요 기여 (Key Contributions)

1. 학습 가능성의 5 단계 계층 구조 제안: 정보 구조에 기반하여 학습 문제를 분류하고, 스케일링이 언제 도움이 될지 (Level 2, 4) 언제 도움이 안 될지 (Level 0, 1) 진단하는 틀을 제시했습니다.
2. 형식적 속성 구분 및 관계 규명: 표현 가능성, 계산 가능성, 학습 가능성의 세 가지 속성을 정의하고, 그 사이의 함의 관계 (Implication) 와 반례 (Separating witnesses) 를 명시했습니다.
   • 예: 정지 문제 (Halting Problem) 는 표현 가능하지만 계산 불가능합니다.
   • 예: 암호화 함수는 계산 가능하지만 효율적으로 학습 (PAC) 불가능할 수 있습니다.
3. 코드 vs RL 성패의 정보 구조적 설명: 코드가 학습 가능한 것은 모델의 크기가 아니라, 컴파일러와 테스트 케이스가 제공하는 Level 4 의 검증 구조가 학습 과정 (Level 3) 을 지지하기 때문임을 밝혔습니다. 반면 RL 은 보상 신호의 구조적 결함 (Level 1 의 반사성, Level 0 에 가까운 Goodhart 효과) 으로 인해 한계에 부딪힙니다.

4. 결과 및 분석 (Results & Analysis)

• 스케일링의 한계: 모델 크기를 키우는 것만으로는 학습 불가능한 문제 (정보 구조가 결여된 문제) 를 해결할 수 없습니다. 오히려 학습 불가능한 문제에서 모델을 키우면 과적합이 빨라지고 실패가 가속화됩니다.
• PAC 학습과 VC 차원: 모든 계산 가능한 함수 집합은 VC 차원이 무한대이므로, 분포에 무관한 학습 (distribution-free learning) 은 불가능합니다. 실제 성공은 데이터가 고차원 공간의 특정 저차원 매니폴드 (manifold) 에 집중되어 있기 때문에 가능합니다.
• RL 의 실패 원인:
  • 정보 불일치: 행동과 보상 간의 인과적 정렬이 맞지 않음 (Credit Assignment 문제).
  • 비정상성 (Non-stationarity): 학습자의 정책 변화가 환경 분포를 바꾸어 과거 데이터가 무효화됨.
  • 반사적 보상 붕괴: 학습자가 보상을 최적화하려다 실제 목표를 훼손함 (Goodhart's Law).
• 코드 생성의 성공: 코드는 Level 4 의 검증 도구 (컴파일러 등) 를 통해 Level 3 의 학습 문제 (다음 토큰 예측) 를 지원합니다. 이는 밀집되고 지역적인 피드백을 제공하여 학습을 안정화시킵니다.

5. 의의 및 시사점 (Significance & Implications)

• AI 연구의 패러다임 전환: "모델이 충분히 강력한가?"라는 질문에서 **"이 작업이 학습 가능한가?"**라는 질문으로 초점을 옮겨야 합니다.
• 실용적 접근법:
  • 작업 분해: 학습 불가능한 거대 작업을 학습 가능한 작은 하위 작업으로 분해 (예: 전체 소프트웨어 작성 대신 토큰 예측).
  • 피드백 구조 설계: 중간 상태를 노출하고, 시의적절하며 귀속 가능한 피드백을 제공하도록 시스템을 설계해야 합니다.
  • 약한 목표 (Weak Objectives): 전역 최적을 추구하기보다 국소적으로 검증 가능한 점진적 목표를 설정해야 합니다.
  • 프록시 재인코딩: 원본 문제를 통계적 최적화가 가능한 프록시 (예: 다음 토큰 예측) 로 변환하되, 프록시와 원본 목표의 괴리를 관리해야 합니다.
• 결론: AI 의 실패는 주로 모델의 능력 부족이 아니라, 문제 자체가 학습을 허용하지 않는 정보 구조를 가지고 있다는 것을 인식하지 못했기 때문입니다. 미래의 돌파구는 더 큰 모델을 만드는 것이 아니라, 어떤 문제가 학습 가능한 구조를 가지고 있는지 식별하고, 그렇지 않은 문제를 학습 가능한 형태로 재구성하는 데서 나올 것입니다.

이 논문은 머신러닝의 한계를 모델의 능력 한계가 아닌 정보 이론적, 계산 이론적 구조의 관점에서 재정의함으로써, AI 연구의 방향성을 근본적으로 재정립할 수 있는 이론적 기반을 제공합니다.