단층 어텐션에서 불리언 함수의 헤드 복잡도
The Head Complexity of Boolean Functions in Single-Layer Attention
한국어 초록
단일 셀프 어텐션(self-attention) 층은 무엇을 계산할 수 있는가? 본 논문은 헤드 복잡도(head complexity), 즉 1층 어텐션 전용 모델에서 어떤 함수를 계산하는 데 필요한 어텐션 헤드의 최소 개수를 연구한다. 우리는 이 척도에 대한 정확한 계층 구조를 확립한다: $k$개의 헤드는 $k$비트 패리티(parity)를 계산할 수 있지만 $(k+1)$비트 패리티는 계산할 수 없다. 이 하한은 트랜스포머가 활용할 수 있는 두 자원에 대해 무조건적(unconditional)이다. 즉, 임베딩 차원과 수치 정밀도가 무한한 경우에도 성립한다. 증명은 교대합 장애물(alternating-sum obstruction)에 기반한다. 소프트맥스 분모를 소거한 뒤 얻어지는 결정 다항식의 모든 단항식은 $k+1$개의 입력 비트 중 적어도 하나를 포함하지 않으며, 이로 인해 패리티와의 상관관계가 0이 된다. 동일한 장애물은 잘 연구된 멀티홉 유도 헤드(induction-head) 과제를 포함한 관련 과제들에 대해서도 하한을 도출한다. 또한 임베딩 차원과 수치 정밀도에 대한 압축성(compactness) 한계도 확립한다. 구체적으로, 압축성 정리는 계산 가능한 모든 함수가 과제의 이산적 데이터, 즉 헤드 수, 알파벳 크기, 길이로 제한되는 임베딩 차원과 정밀도만으로 계산될 수 있음을 보인다. 따라서 잠재적으로 무한한 차원이나 정밀도는 헤드를 대체할 수 없음이 증명된다. 마지막으로, 일반 이진 함수에 대해 거의 일치하는 보편적 한계를 도출한다: 다중선형 전개의 단항식당 헤드 하나를 사용하면 $2^n$개의 헤드로 모든 $n$비트 이진 함수를 계산할 수 있으며, 계수 논증(counting argument)에 따르면 거의 모든 이러한 함수는 $Ω(2^n/n^2)$개의 헤드를 필요로 한다. 이 하한은 차원과 정밀도가 무한한 경우에도 상한과 $\operatorname{poly}(n)$ 배 이내로 일치한다. 이러한 결과들을 종합하면, 이 모델에서 불리언 계산에 필요한 헤드 요구량이 규명된다.
원문 초록
What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit; it holds at unbounded embedding dimension and unbounded numerical precision. The proof rests on an alternating-sum obstruction: after clearing the softmax denominators, every monomial in the resulting decision polynomial omits at least one of the $k+1$ input bits, forcing its correlation with parity to vanish. The same obstruction yields lower bounds for related tasks, including the well-studied multi-hop induction-head task. We also establish compactness bounds for embedding dimension and numerical precision. Specifically, a compactness theorem shows that any function computable at all can be computed with embedding dimension and precision bounded by the discrete data of the task, namely, head count, alphabet size, and length. Thus, potentially unbounded dimension or precision provably cannot substitute for heads. Finally, we derive nearly matching universal bounds for general binary functions: $2^n$ heads suffice to compute every $n$-bit binary function, with one head per monomial in its multilinear expansion, while a counting argument shows almost all such functions require $Ω(2^n/n^2)$ heads. This lower bound matches the upper bound to within a $\operatorname{poly}(n)$ factor, even when dimension and precision are unbounded. Together, these results characterize head requirements for Boolean computation in this model.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.04046v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.