Transformers는 본질적으로 간결함 (2025)

Source: Hacker News

Abstract

우리는 변환기(transformer)의 개념을 기술하는 표현력의 척도로서 간결성(succinctness) 을 제안한다. 이를 위해 변환기가 유한 자동자와 선형 시계 논리(LTL) 공식과 같은 전통적인 형식 언어 표현보다 훨씬 더 간결하게 형식 언어를 나타낼 수 있다는 점에서 매우 높은 표현력을 가지고 있음을 증명한다. 이러한 표현력의 부수 효과로, 변환기의 속성을 검증하는 것이 이론적으로 난해함(provably intractable) (즉, EXPSPACE‑complete) 임을 보인다.

Subjects

• Formal Languages and Automata Theory (cs.FL)
• Machine Learning (cs.LG)
• Logic in Computer Science (cs.LO)

Citation

• arXiv: arXiv:2510.19315 (cs.FL)
• Version: arXiv:2510.19315v2 (cs.FL)
• DOI: 10.48550/arXiv.2510.19315 (arXiv‑issued DOI via DataCite)

Submission history

• v1: Wed, 22 Oct 2025 07:25:54 UTC (28 KB) – submitted by Pascal Bergsträßer
• v2: Thu, 23 Oct 2025 08:09:19 UTC (28 KB)

View PDF | HTML (experimental)