장거리 의존성의 환상에 대하여: 정수 곱셈 응용을 중심으로

On the Mirage of Long-Range Dependency, with an Application to Integer Multiplication

정수 곱셈은 오랫동안 신경망에서 어려운 문제로 여겨져 왔으며, 이러한 어려움은 주로 carry chain에 의해 유발되는 O(n)의 장거리 의존성 때문이라고 널리 알려져 있습니다. 우리는 이러한 진단이 틀렸다고 주장합니다. 장거리 의존성은 곱셈 자체의 고유한 특성이 아니라, 계산 공간의 선택에 의해 만들어진 환상일 뿐입니다. 우리는 이러한 '환상'의 개념을 명확히 하고, 이를 뒷받침하는 구체적인 증명을 제시합니다. 두 개의 n비트 이진 정수를 2차원 외적 격자로 표현하면, 장거리 곱셈의 각 단계는 $3 imes 3$ 크기의 로컬 이웃 연산으로 축소됩니다. 이러한 표현 방식 하에서, 321개의 학습 가능한 파라미터만을 가진 신경망 세포 자동화(neural cellular automaton)가 학습 범위의 최대 683배까지 완벽한 길이 일반화 성능을 달성합니다. Transformer (6,625 파라미터), Transformer+RoPE, 그리고 Mamba를 포함한 다섯 가지 대체 아키텍처 모두 동일한 표현 방식 하에서 실패합니다. 또한, 부분적인 성공 사례들이 어떻게 연구 커뮤니티를 잘못된 진단으로 이끌었는지 분석하고, 장거리 의존성이 필요하다고 진단된 모든 작업은 먼저 해당 의존성이 작업 자체의 고유한 특성인지, 아니면 계산 공간에 의해 유발되는 것인지 검토해야 한다고 주장합니다.

Integer multiplication has long been considered a hard problem for neural networks, with the difficulty widely attributed to the O(n) long-range dependency induced by carry chains. We argue that this diagnosis is wrong: long-range dependency is not an intrinsic property of multiplication, but a mirage produced by the choice of computational spacetime. We formalize the notion of mirage and provide a constructive proof: when two n-bit binary integers are laid out as a 2D outer-product grid, every step of long multiplication collapses into a $3 \times 3$ local neighborhood operation. Under this representation, a neural cellular automaton with only 321 learnable parameters achieves perfect length generalization up to $683\times$ the training range. Five alternative architectures -- including Transformer (6,625 params), Transformer+RoPE, and Mamba -- all fail under the same representation. We further analyze how partial successes locked the community into an incorrect diagnosis, and argue that any task diagnosed as requiring long-range dependency should first be examined for whether the dependency is intrinsic to the task or induced by the computational spacetime.