- ARC-AGI처럼 적은 예시에서 규칙을 찾아야 하는 문제에서 CompressARC는 사전 훈련·외부 데이터셋·대규모 탐색 없이 퍼즐별 추론 시점 학습만으로 해법을 찾음
- 핵심 아이디어는 정답까지 포함한 퍼즐 표현이 더 짧아지도록 무손실 정보 압축 목적을 최적화하면 지능적 행동이 나타날 수 있다는 실험임
- RTX 4070에서 퍼즐당 약 20분을 사용해 훈련 세트 34.75%, 평가 세트 20% 를 기록했으며, 목표 퍼즐 하나만 학습 데이터로 쓰는 신경망 접근이라는 점이 특징임
- 아키텍처는 예시 순서, 색상 순열, 회전·반사에 대한 등변성을 중심으로 설계됐고, 여러 랭크의 텐서를 묶은 multitensor 표현을 사용함
- 색상-절차 매핑, 채우기, 자르기, 점 연결, 짧은 이동에는 강점을 보이지만 숫자 세기, 장거리 패턴 확장, 회전·복사·크기 조정, 에이전트 계획은 아직 병목으로 남아 있음
압축만으로 ARC-AGI를 풀 수 있는지 실험
- 핵심 질문은 무손실 정보 압축만으로 지능적 행동을 만들 수 있는지임
- CompressARC는 ARC-AGI 퍼즐을 대상으로, 압축 기반 목적함수만으로 동작하는 방법임
- 세 가지 제약을 둠
- 사전 훈련 없음: 모델은 무작위 초기화되고 추론 시점에 학습됨
- 데이터셋 없음: 한 모델은 목표 ARC-AGI 퍼즐 하나만 학습하고 답 하나를 출력함
- 탐색 없음: 대부분의 의미에서 탐색 없이 경사하강법만 사용함
- 결과는 훈련 세트 34.75%, 평가 세트 20% 이며, 각 퍼즐은 RTX 4070에서 대략 20분 걸림
- 목표 퍼즐만 학습 데이터로 쓰는 ARC-AGI용 신경망 방법으로는 처음이라는 설명이 붙어 있음
ARC-AGI 문제 설정
- ARC-AGI는 2019년에 소개된 AI 벤치마크로, 적은 예시에서 추상 규칙을 추론하고 일반화하는 능력을 테스트함
- 각 퍼즐은 입력-출력 예시 여러 개와 테스트 입력 하나를 제공하며, 시스템은 테스트 출력 격자를 맞혀야 함
- 한 퍼즐당 두 번의 시도가 가능하고, 둘 중 하나가 맞으면 점수 1점을 받음
- 출력 격자의 크기를 바꾸고 모든 픽셀의 색을 선택할 수 있음
- 퍼즐은 사람이 합리적으로 풀 수 있지만 기계에는 더 어렵게 설계됨
- 평균 인간은 훈련 세트의 76.2% 를 풂
- 인간 전문가는 98.5% 를 풂
- 400개 훈련 퍼즐은 나머지보다 쉽고, 다음 패턴을 학습하게 하는 용도임
- 객체성: 객체는 이유 없이 나타나거나 사라지지 않음
- 목표 지향성: 일부 객체는 의도를 가진 에이전트처럼 동작함
- 숫자와 세기: 객체 수, 정렬, 비교, 덧셈·뺄셈 같은 기본 수학이 쓰임
- 기하와 위상: 도형의 반사, 회전, 이동, 변형, 결합, 반복, 거리 차이 등이 포함됨
- ARC Prize의 최근 Kaggle 대회는 최대 100만 달러 이상의 상금이 있었고, 주요 상은 제한 환경에서 12시간 연산으로 비공개 100문제에서 85%를 달성하는 방법에 배정됨
CompressARC의 동작 방식
- CompressARC에서는 더 낮은 비트 수로 압축되는 표현이 더 정확한 퍼즐 해답과 연결됨
- 시스템은 불완전한 퍼즐을 완성된 퍼즐로 바꾸는 압축 표현을 찾고, 이 표현을 압축 해제하면 퍼즐과 해답이 재구성되도록 함
- 신경망은 디코더 역할을 맡음
- 별도의 인코더 신경망은 없음
- 인코딩은 추론 시점에 디코더를 학습하는 경사하강법으로 구현됨
- 최적화된 가중치와 입력 분포 설정이 퍼즐과 답을 담은 압축 비트 표현 역할을 함
- 표준 머신러닝 표현으로는 다음 절차임
- ARC-AGI 퍼즐을 받음
- 퍼즐의 예시 수와 관측 색상 수에 맞춰 신경망
f를 구성함 z ~ N(μ, Σ)인 무작위 정규 입력을 받아 모든 격자의 픽셀별 색상 로짓을 출력함- 알려진 격자에 대한 교차엔트로피 합을 최소화하고, 답 격자는 무시함
N(μ, Σ)가N(0,1)에 가깝도록 KL 발산 패널티를 둠- 학습 중 생성된 답 격자들을 저장하고, 가장 자주 나온 답을 최종 예측으로 선택함
fθ는 입력-출력 쌍 순서 변경, 색상 순열, 공간 회전·반사 같은 일반적 증강에 대해 등변적으로 설계됨
압축 관점에서의 유도
- 무손실 압축은 정보를 가능한 적은 비트로 표현하되, 그 비트 표현에서 원본을 정확히 복원하는 문제임
- ARC-AGI에서는 원래라면 퍼즐과 답 쌍 전체를 심볼로 보고 압축해야 하지만, 실제로는 답을 인코더 입력으로 갖고 있지 않고 퍼즐 생성 분포도 모름
- ARC-AGI 데이터셋에 대해 실용적으로 구현 가능한 비트 효율적 압축 시스템이 존재한다고 가정함
- 분포
p를 모르더라도 프로그램f와 입력s의 길이len(f)+len(s)를 최소화하는 보편 압축기를 생각할 수 있음- 디코더는
f(s)를 실행해 원본을 복원함 - 알고리듬 정보 이론상 원래 압축기보다
f의 길이만큼만 더 비효율적일 수 있음 - 실제로는 프로그램 공간을 탐색하는 인코더가 실용적이지 않음
- 디코더는
- CompressARC는 프로그램 공간 탐색 대신 신경망 forward pass를 고정 프로그램으로 선택함
s는 가중치θ, 입력z, 출력 보정ε로 구성됨θ와z는 Relative Entropy Coding(REC) 관점에서,ε는 arithmetic coding 관점에서 코드 길이를 계산함- 출력 보정 코드 길이는 알려진 격자의 총 교차엔트로피와 같아짐
z의 코드 길이는KL(pz || qz)가 되고,qz = N(0,I)로 둠
- 전체 코드 길이는 VAE 손실과 같은 형태임
- 재구성 오류
z에 대한 KL- 디코더 정규화
- CompressARC 구현은 이 유도에서 정규화 일부와 등변성, 퍼즐 간 독립성 관련 수정을 포함한 형태임
아키텍처: multitensor와 등변성
- 아키텍처의 가장 중요한 특징은 등변성임
- 입력
z가 변환되면 출력 ARC-AGI 퍼즐도 같은 방식으로 변환되어야 함 - 예시는 입력-출력 쌍 재정렬, 색상 셔플, 격자 뒤집기·회전·반사임
- 입력
- 설계는 먼저 완전히 대칭적인 기본 아키텍처를 만들고, 필요한 비등변 능력을 주는 비대칭 레이어를 추가해 불필요한 대칭을 하나씩 깨는 방식임
- 내부 데이터는 multitensor라는 형식으로 흐름
- 여러 랭크와 shape를 가진 텐서들의 묶음임
- 차원은 최대
[n_examples, n_colors, n_directions, height, width, n_channels]의 부분집합으로 구성됨 - 항상
channel차원은 유지됨 - 규칙을 적용해 multitensor 안의 합법적 텐서 수를 18개로 줄임
- 퍼즐은
[examples, colors, height, width, channel]텐서로 표현될 수 있음channel은 입력 또는 출력 격자를 선택하는 데 쓰임width와height는 픽셀 위치를 나타냄color차원은 픽셀 색상의 원-핫 표현을 담음
- 전체 아키텍처는 다음 흐름을 가짐
z분포 파라미터에서 시작- Decoding Layer
- Multitensor Communication, Softmax, Directional Cummax, Directional Shift, Directional Communication, Nonlinear, Normalization 등을 4회 반복
- Linear Heads로 ARC-AGI 퍼즐 분포를 출력함
성능 결과
- 훈련은 Adam으로 2000 iterations 수행함
- 학습률은
0.01 β1 = 0.5,β2 = 0.9
- 학습률은
- 훈련 세트 결과
- 100 iteration: Pass@2 2.25%
- 500 iteration: Pass@2 27.5%
- 1000 iteration: Pass@2 31.75%
- 2000 iteration: Pass@2 34.75%
- 2000 iteration의 Pass@1000은 52.75%
- 평가 세트 결과
- 100 iteration: Pass@2 1.25%
- 500 iteration: Pass@2 15%
- 1000 iteration: Pass@2 19.25%
- 2000 iteration: Pass@2 20%
- 2000 iteration의 Pass@1000은 33.75%
- ARC-AGI 채점은 두 번 시도할 수 있으므로 본문 핵심 결과는 Pass@2 기준임
풀 수 있는 퍼즐과 어려운 퍼즐
- CompressARC는 가진 능력으로 가능한 만큼 규칙을 파악하지만, 아키텍처가 갖지 못한 능력에서 병목에 걸림
- 가능한 작업 예시는 다음과 같음
- 개별 색상을 개별 절차에 할당
- 채우기
- 자르기
- 45도 대각선을 포함한 점 연결
- 같은 색상 감지
- 픽셀 인접성 식별
- 예시별 색상 할당
- 도형의 부분 식별
- 짧은 거리 이동
- 어려운 작업 예시도 분명함
- 두 색상을 서로 대응시키기
- 같은 연산을 여러 번 연속 반복
- 이동, 회전, 반사, 크기 조정, 이미지 복제
- 연결성 같은 위상 속성 감지
- 에이전트 행동 계획과 시뮬레이션
- 장거리 패턴 확장
- 훈련 퍼즐 28e73c20에서는 가장자리에서 중앙으로 패턴을 확장해야 하는데, CompressARC는 짧은 거리 확장은 하지만 중앙 근처에서는 추측에 의존함
사례: Color the Boxes
- 사람 풀이에서는 입력이 상자들로 나뉘어 있고, 출력에서는 그 상자들이 색칠된다는 점을 파악함
- 모서리는 항상 검정
- 가운데는 항상 마젠타
- 변 쪽 상자는 방향에 따라 위 빨강, 아래 파랑, 오른쪽 초록, 왼쪽 노랑으로 색이 정해짐
- CompressARC의 학습 진행은 단계별로 달라짐
- 50 step: 입력의 하늘색 행·열이 출력에도 대응된다는 점을 반영함
- 150 step: 가까운 픽셀끼리 비슷한 색을 갖는 출력 형태를 보임
- 200 step: 하늘색 경계로 잘린 더 큰 색상 덩어리와 검정 모서리 덩어리를 모방함
- 350 step: 중심 기준 방향에 맞는 상자 색을 대체로 맞힘
- 1500 step: 출력은 거의 정제되지만 샘플에서는 드물게 실수가 남음
- 학습된
z분포를 분석하면 색상-방향 대응표와 행·열 구분선 위치를 코드화한 것으로 나타남 - 네 개 텐서만 정보량을 유지함
(examples, height, channel): 각 예시의 하늘색 행 위치를 담음(examples, width, channel): 각 예시의 하늘색 열 위치를 담음(direction, color, channel): 방향과 색상 대응을 담음(color, channel): 마젠타와 하늘색의 특별한 역할을 구분함
추가 사례와 표현 분석
-
Bounding Box 퍼즐 6d75e8bb
- 사람 풀이는 빨간 도형을 감싸는 가장 작은 하늘색 박스를 그리는 방식임
- CompressARC는 100 step에서 공통 bounding box를 파악한 흔적을 보이고, 150 step에서는 답을 알아낸 뒤 이후 학습으로 답을 정제함
- 살아남은 주요 텐서는
(examples, height, channel),(examples, width, channel),(color, channel)임 - 행·열 텐서는 하늘색 픽셀이 많은 행과 열을 나타내지만, 경계 위치를 어떻게 아는지는 불명확함
-
Center Cross 퍼즐 41e4d17e
- 입력의 파란 버블 중심에서 마젠타 광선을 상하좌우로 그리고, 버블 색은 광선 위에 덮어야 함
- CompressARC는 입력을 복사한 뒤 마젠타 행·열이 나타나고 점차 올바른 위치로 안정됨
- 사람 풀이처럼 광선을 버블 위에 잘못 그리는 실수는 보이지 않음
- 살아남은 텐서는
(examples, height, width, channel)과(color, channel)임 (examples, height, width, channel)은 버블 중심을 코드화함
개선 아이디어
- 퍼즐별로 따로 압축하는 대신 전체 ARC-AGI 데이터셋을 함께 압축하면 퍼즐 간 계산을 공유해 더 나은 귀납 편향을 얻을 수 있음
- 같은 네트워크 가중치를 모든 퍼즐에 쓰고, 퍼즐별 제한된 perturbation을 주는 방법을 고려함
- 퍼즐별 고차원 임베딩을 학습하고, 이 임베딩에서 네트워크 가중치로 가는 선형 매핑을 학습하는 hypernetwork 방식도 제안함
- 이 방향은 연구 반복 속도를 늦출 수 있어 시도하지 않음
- 도형 복사 작업에는 convolution 계열 레이어가 유용할 수 있음
- 한 격자는 도형을 저장하고 다른 격자는 복사 위치를 나타내면 convolution으로 복사 결과를 만들 수 있음
- 일반 convolution은 노이즈를 신호보다 크게 증폭하는 문제가 있었음
- tropical convolution은 장난감 퍼즐에서는 잘 동작했지만 ARC-AGI 훈련 퍼즐에는 충분하지 않았음
- posterior collapse 완화를 위해 KL floor를 두는 방법도 고려됨
- 중요한 텐서의 KL이 0으로 떨어지면 다시 회복하지 못하는 현상을 관찰함
- KL을 한동안 0보다 크게 유지하면 네트워크가 해당 정보를 쓰도록 학습할 수 있음
- 구현은 했지만 텐서가 회복되는 사례를 보지 못했고, KL floor 스케줄을 다르게 설계할 필요가 있음
- 정규화는 구현에서 사용하지 않음
- 문제 공식화에서는
f의 복잡도를 측정하는 요소이고 CompressARC 유도에 포함됨 - 구현에서 제외한 것은 다소 무모하다고 평가함
- 문제 공식화에서는
관련 작업과 연구적 위치
- 압축과 지능의 등가성 아이디어는 Hutter Prize에서 영감을 받음
- Hutter Prize는 Wikipedia 텍스트 파일을 가장 잘 압축하는 시스템에 상을 주며, 정보 압축 능력을 지능과 연결함
- 이론적 배경에는 Solomonoff Induction, Kolmogorov Complexity, Minimum Description Length가 포함됨
- 정보 이론 측면에서는 Relative Entropy Coding이 핵심임
- KL 발산을 제한할 수 있으면 압축 알고리듬 구성이 가능하다고 보고, 실제 이진 코드 구현 문제를 추상화함
- VAE 관점에서는 디코더가 압축 해제 알고리듬 역할을 함
- 더 일반적인 능력을 가진 neural Turing machine도 고려할 수 있지만, 경사하강법 최적화에 적합하지 않아 VAE 쪽을 사용함
- beta-VAE식 재구성 손실 재가중은 이 경우 잘 작동함
- 기존 ARC-AGI 방법은 주로 LLM, 데이터 증강, 대체 데이터셋, 테스트 시점 학습, 도메인 특화 언어 기반 프로그램 탐색을 사용함
- CompressARC는 외부 사전 훈련과 대규모 탐색 없이 딥러닝을 사용하는 방법이라는 점을 강조함
- 프로젝트 코드는 GitHub에 공개됨