Average Attention Transformers and Arithmetic Circuits

기술 요약: 평균 어텐션 트랜스포머와 산술 회로

문제 제기
기존 트랜스포머 표현력에 대한 이론적 분석은 주로 유한 알파벳에 대한 결정 문제, 즉 부울 회로 클래스 (예: $AC^0$, $TC^0$) 나 논리 형식과 트랜스포머를 비교하는 데 집중되어 왔습니다. 이러한 결과들은 언어 인식에 국한됩니다. 본 논문은 실수 또는 유리수 벡터에 대해 시퀀스 - 시퀀스 함수로 작동하는 트랜스포머의 계산 능력을 이해하는 데 존재하는 공백을 해소합니다. 저자들은 트랜스포머 인코더의 표현력을 산술 회로와 직접 비교함으로써 규명하고자 하는데, 이 산술 회로는 덧셈, 곱셈, 부호 함수와 같은 연산을 사용하여 반환 (semirings) 위에서 함수를 계산합니다.

방법론
저자들은 하오 (Hao) 등 (2022) 의 일반화된 트랜스포머 모델을 임의의 반환 위에서 작동하도록 적응시켰습니다. 주요 방법론적 선택 사항은 다음과 같습니다:

1. 모델 정의: 표준 피드포워드 네트워크를 산술 회로로 대체하고, 어텐션 메커니즘이 "평균 하드 어텐션 (모든 벡터 중 최대 어텐션 점수를 가진 벡터들에 주의를 기울이는 방식)"을 활용하는 "평균 어텐션 회로 트랜스포머"를 정의합니다.
2. 회로 군 (Circuit Families): 상수 깊이와 다항식 크기를 갖는 세 가지 산술 회로 군을 분석합니다:
   • $FNC^0_R$: 제한된 팬 - 인 (fan-in).
   • $FSAC^0_R$: 준 - 무제한 팬 - 인 (무제한 덧셈, 이진 곱셈).
   • $FAC^0_R$: 무제한 팬 - 인 (무제한 덧셈 및 곱셈).
     이러한 클래스는 불연속 연산을 처리하기 위해 sign 함수로 확장됩니다.
3. 시뮬레이션 구성:
   • 회로에서 트랜스포머로: 회로를 시뮬레이션하기 위해 저자들은 회로의 그래프 구조 (게이트와 엣지) 를 벡터 시퀀스로 인코딩합니다. 각 벡터는 엣지나 게이트를 나타내며, 선행자/후행자에 대한 인덱스, 게이트 유형, 그리고 값을 포함합니다.
   • 어텐션 메커니즘: 벡터들이 인덱스 매칭을 기반으로 선행자들에게 주의를 기울일 수 있도록 특정 어텐션 함수 ($f^{att}_E$ 및 $f^{att}_V$) 를 설계합니다.
   • 풀링 및 활성화: 선행자들로부터 값을 집계하기 위해 평균 하드 어텐션 풀링을 활용합니다. 핵심적으로, 벡터에 인코딩된 게이트 유형에 따라 적절한 연산 (덧셈, 곱셈, 또는 항등) 을 선택하는 활성화 함수를 구성합니다.
   • 스케일링 처리: 평균 어텐션은 결과를 $1/k$ (여기서 $k$는 주의를 기울인 벡터의 수) 로 스케일링하므로, 구성에는 선행자를 세고 올바른 산술 값을 복원하기 위해 출력을 재스케일링하는 메커니즘이 포함됩니다.

주요 결과
본 논문은 이러한 특정 트랜스포머의 계산 능력과 산술 회로 클래스 간의 정밀한 대응 관계를 확립합니다:

1. 상한 (Upper Bound): 임의의 반환 $R$에 대해, 평균 어텐션 회로 트랜스포머가 계산하는 함수들은 $FSAC^0_R[\text{sign}]$ 클래스 내에 포함됩니다. 이는 활성화 함수가 동일한 회로 클래스로 제한된다면 일반적인 평균 어텐션을 사용하는 표준 트랜스포머에도 적용됩니다.
2. 하한 (시뮬레이션, Lower Bound): 기본 반환 $R$이 유리수 ($\mathbb{Q}$) 의 $\mathbb{Z}$-순서 링 확장일 경우, 깊이 $K$를 갖는 $FSAC^0_R[\text{sign}]$ 회로 군의 모든 회로에 대해, 전체 군을 시뮬레이션할 수 있는 $2K$ 레이어를 가진 트랜스포머가 존재합니다.
   • 이 시뮬레이션은 평균 어텐션을 사용하는 무제한 팬 - 인 회로에 대해 작동합니다.
   • 준 - 무제한 팬 - 인 회로의 경우, 구성을 표준 도트 - 프로덕트 어텐션을 사용하도록 적응시킬 수 있습니다.
   • 제한된 팬 - 인 회로의 경우, 구성을 더 제한하여 왼쪽 또는 오른쪽 하드 어텐션을 사용하도록 할 수 있습니다.
3. 특정 정리:
   • 정리 4.5: 차원 7 과 $2K$ 레이어를 가진 트랜스포머는 깊이 $\le K$인 임의의 무제한 팬 - 인 $R$-회로를 시뮬레이션할 수 있습니다 (여기서 $R$은 $\mathbb{Q}$의 $\mathbb{Z}$-순서 확장입니다).
   • 정리 4.11: 차원 9 와 $2K$ 레이어를 가진 트랜스포머는 임의의 $FSAC^0_R[\text{sign}]$-회로를 시뮬레이션할 수 있습니다.

의의 및 주장
저자들은 그들의 결과가 기계 학습 이론과 대수적 계산 분야를 연결함으로써 트랜스포머 표현력에 대한 새로운 관점을 제공한다고 주장합니다.

• 이론적 동등성: 그들은 평균 어텐션 트랜스포머가 무제한 덧셈, 이진 곱셈, 그리고 부호 게이트를 갖는 상수 깊이 산술 회로 클래스 ($FSAC^0_R[\text{sign}]$) 와 계산적으로 동등함을 입증합니다.
• 한계: 본 논문은 이 동등성이 트랜스포머가 산술 회로 (또는 동등한 함수) 를 활성화 함수로 사용할 때에만 성립한다고 명시적으로 지적합니다. 피드포워드 네트워크를 사용하는 표준 트랜스포머는 시뮬레이션에 필요한 두 개의 임의 입력의 곱셈을 본질적으로 수행할 수 없기 때문에 이러한 회로를 시뮬레이션할 수 없습니다.
• 비균일성 (Non-Uniformity): 저자들은 트랜스포머가 특정 회로 군을 시뮬레이션할 수 있다고 해서 $FSAC^0_R[\text{sign}]$의 모든 함수가 단일 트랜스포머에 의해 계산되는 것을 의미하지는 않는다고 명확히 합니다. 회로 군은 계산의 비균일 모델이기 때문입니다.
• 미래 가능성: 본 논문은 대수적 계산 분야의 이론적 진전이 기계 학습 이론에 도움이 될 수 있고 그 반대의 경우도 가능하다고 제안하며, 이론적 결과가 실용적 발전을 영감할 수 있다고 언급하지만 구체적인 응용 사례는 제시하지 않습니다.

이 연구는 2026 년 5 월 하노버 라이프니츠 대학교 이론 컴퓨터 과학 연구소에서 발표한 프리프린트입니다.