Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning

기술적 요약: 느린 일반화, 빠른 암기: 알고리즘 학습의 최적 지점

문제 정의
실증적 스케일링 법칙과 '그로킹 (grokking)' 연구는 더 큰 데이터셋이 일반적으로 모델 성능을 향상시키며, 일반화 임계값을 넘어서면 추가 데이터가 검증 수렴을 가속화한다고 시사합니다. 그러나 본 논문은 이러한 직관이 구조화된 출력 (structured-output) 작업에 대해 보편적으로 성립하는지 조사합니다. 구체적으로 저자들은 다음과 같은 질문을 제기합니다: 일반화가 가능해진 후, 고정된 최적화 프로토콜 하에서 가장 큰 데이터셋이 항상 가장 빠른 검증 수렴을 가져오는가? 본 연구는 두 입력 문자열로부터 전체 동적 프로그래밍 점수 행렬을 예측해야 하는 Needleman–Wunsch (NW) 행렬 생성 작업에 초점을 맞춥니다. 스칼라 산술 작업과 달리, NW 는 많은 종속 셀들의 조율된 예측을 요구하여 고복잡도 구조화된 출력을 생성합니다.

방법론
저자들은 NW 행렬 생성과 세 자리 수 곱셈 기준 작업을 위해 디코더 전용 Transformer 를 훈련시킨 통제된 실험 프로토콜을 사용합니다.

• 작업: 모델은 입력 문자열 쌍 $(x, y)$를 NW 동적 프로그래밍 재귀식으로 생성된 목표 행렬 $M(x, y)$로 매핑합니다. 정확도는 **정확 일치 정확도 (exact-match accuracy)**로 측정되며, 모든 행렬 항목이 정확해야 합니다.
• 변수: 주요 변수는 데이터셋 크기 ($N$) 로, 200 에서 300,000 개의 예제에 이르는 광범위한 범위로 조정됩니다. 모델 깊이, 옵티마이저 설정 (AdamW), 학습률 스케줄은 고정됩니다.
• 지표: 본 연구는 훈련 ($IT$) 과 검증 ($IV$) 에서 특정 정확 일치 정확도 임계값 ($\tau$) 에 도달하는 데 필요한 옵티마이저 업데이트 횟수를 측정합니다. 이 '업데이트 기반' 지표는 에포크 정규화 효율성과 구별되는 수렴 속도를 구분합니다.
• 프로브: 규칙 학습과 암기를 분리하기 위해 저자들은 목표 행렬에 4 비트 무접미사를 추가하는 **무작위 접미사 프로브 (random-suffix probe)**를 도입합니다. 이는 규칙으로 생성된 구조 (행렬) 에서 예제별 정보 (접미사) 를 분리합니다.
• 기준 작업: 세 자리 수 곱셈은 관찰된 현상이 구조화된 동적 프로그래밍에 특정한 것인지, 아니면 정확 일치 평가의 인공물인지 확인하기 위한 대비 작업으로 사용됩니다.

주요 기여
본 논문은 세 가지 주요 실증적 기여를 합니다:

1. 데이터셋 크기 최적 지점의 식별: NW 행렬 생성에서 검증 수렴은 가장 큰 데이터셋이 아닌 중간 크기의 데이터셋에서 가장 빠릅니다. 이는 일반화가 가능해진 후 "더 많은 데이터가 항상 더 빠르다"는 표준 임계값 이후 직관과 모순됩니다.
2. 부분 규칙 학습을 통한 피팅 가속: 약한 검증 역량이 처음 나타나는 영역에서 데이터셋 크기를 증가시키면 높은 훈련 정확도에 도달하는 데 필요한 업데이트 횟수가 실제로 감소할 수 있습니다. 이는 부분 규칙 학습이 단순히 암기 부담을 추가하는 것이 아니라 피팅 과정을 가속화할 수 있음을 시사합니다.
3. 압력의 기계적 분리: 저자들은 추가 데이터가 초기에는 규칙 발견 (구조적 커버리지 향상) 을 돕지만 결국 잔여 정밀 피팅 (규칙에 의해 완전히 결정되지 않은 세부 사항 암기) 의 비용을 증가시킨다는 '이중 압력 설명 (two-pressure account)'을 제안합니다.

결과

• 비단조적 검증 수렴: NW 의 경우 엄격한 검증 임계값 (예: $\tau=0.98$) 에 도달하는 데 필요한 업데이트 횟수는 U 자형 곡선을 따릅니다. 작은 데이터셋은 일반화에 실패하거나 긴 지연을 요구합니다. 중간 크기의 데이터셋이 가장 빠르게 수렴합니다. 큰 데이터셋은 여전히 일반화하지만 동일한 임계값에 도달하는 데 훨씬 더 많은 업데이트를 필요로 하여 '임계값 이후 둔화 (post-threshold slowdown)'를 나타냅니다.
• 곱셈 작업과의 대비: 곱셈 기준 작업은 이러한 둔화를 보이지 않으며, 검증 수렴은 큰 데이터셋과 함께 평탄하게 유지되거나 향상됩니다. 이는 현상이 정확 일치 지표 자체가 아니라 NW 작업의 특정 구조 (길고 종속적인 출력) 와 연관되어 있음을 확인시켜 줍니다.
• 훈련 vs 검증 타이밍: 일반화 시작 부근에서 큰 데이터셋은 높은 훈련 정확도에 필요한 업데이트 횟수를 줄일 수 있습니다. 이는 암기와 일반화가 엄격하게 순차적이지 않으며, 부분 규칙 획득이 나머지 피팅 작업을 더 쉽게 만들 수 있음을 나타냅니다.
• 무작위 접미사 진단: 더 큰 데이터셋 크기에서 모델은 무작위 접미사보다 규칙으로 생성된 행렬을 먼저 피팅합니다. 이는 구조화된 구성 요소가 학습된 규칙의 혜택을 받는 반면, 비구조화된 접미사는 데이터셋 크기가 증가함에 따라 성장하는 잔여 '정밀 피팅' 부담을 대표한다는 가설을 지지합니다.
• 훈련 - 검증 격차: 훈련 정확도와 검증 정확도 간의 격차 ($G = A_T - A_R$) 는 검증 정확도가 상승하기 시작하는 시점에 정확히 양수가 되며, 이는 동일한 규칙 매개 진행이 두 가지 모두를 주도함을 시사합니다.

의의 및 주장
본 논문은 고전적인 그로킹 및 임계 데이터 크기 문헌을 모순시키기보다 정교화한다고 주장합니다.

• 임계 데이터 크기의 정교화: 임계 데이터 크기 ($N_c$) 는 일반화의 시작점 (해결책이 식별 가능해지는 시점) 을 나타내는 반면, 저자들은 업데이트 기반 수렴 속도를 최적화하는 데이터셋 크기 ($N^*$) 는 $N_c$와 다를 수 있으며 사용 가능한 최대 데이터셋과도 다를 수 있음을 보여줍니다.
• 학습 단계의 분기: 결과는 구조화된 출력 작업에서 "규칙 학습"과 "정밀 피팅 완료"가 분기할 수 있음을 보여줍니다. 유용한 규칙이 발견된 후, 추가 데이터는 주로 잔여 세부 사항 피팅의 부담을 증가시켜 옵티마이저 업데이트 관점에서의 수렴을 늦출 수 있습니다.
• 범위: 저자들은 겸손하게 이 현상이 재사용 가능한 알고리즘적 구조와 높은 예제당 출력 복잡성 (예: 편집 거리 또는 Viterbi 디코딩과 같은 동적 프로그래밍 테이블) 을 결합한 작업에 특정한 것이라고 주장합니다. 모든 알고리즘 작업에 적용되거나 점근적 정확도에 대해 더 큰 데이터셋이 본질적으로 해롭다고 주장하는 것은 아니며, 특정 구조화된 설정에서 옵티마이저 업데이트 관점의 수렴 경로가 비단조적이라는 점에 국한됩니다.

본 연구는 구조화된 출력 학습의 경우, 규칙 발견의 이점이 포화되었으나 잔여 정밀 피팅의 비용이 아직 지배적이 되지 않은 중간 데이터셋 크기에서 검증 일반화에 도달하는 가장 빠른 경로가 발생할 수 있다고 결론지었습니다.