본 논문은 부울 함수의 계층(rank)에 대한 새로운 특징을 제시합니다. 기존에는 PAC 학습 이론에서 다항식 크기의 의사결정 트리를 위한 준다항 시간 학습 알고리즘을 가능하게 하는 핵심 개념으로 여겨졌던 부울 함수의 계층을, 잘 알려진 Transformer 아키텍처를 기반으로 새롭게 특징짓습니다. 특히, 함수 f의 계층은 하드 어텐션을 사용하는 단일 레이어 Transformer가 f를 계산하는 데 필요한 최소 Chain of Thought (CoT) 단계 수와 일치함을 보여줍니다. 이러한 특징을 바탕으로 특정 문제에 필요한 CoT 단계 수에 대한 엄격한 경계를 설정하고, ℓ-겹 함수 합성에는 정확히 ℓ개의 CoT 단계가 필요함을 증명합니다. 또한, 부울 수열에서 1이 k번째로 나타나는 위치를 식별하는 문제를 분석하여 k개의 CoT 단계가 필요함을 증명합니다. 마지막으로, 다중 헤드 단일 레이어 Transformer를 포착하는 다중 헤드 계층(multi-head rank) 개념을 도입하고, 제한된 다중 헤드 계층을 갖는 함수 클래스의 PAC 학습 가능성을 분석합니다.
