어텐션 인증의 병목은 소프트맥스가 아닌 가변 쿼리와 키의 이중선형 결합이다

무엇인가

이 논문은 트랜스포머의 한 어텐션 헤드가 입력 토큰의 연속적 섭동에 따라 출력을 얼마나 바꿀 수 있는지, 그 최악값을 보증하는 문제를 다룬다. 헤드 출력에 선형 범함수 c를 적용한 값을 최대화하는 문제로 정의하고, 기존 검증기들이 상한을 주긴 해도 그 상한이 참 최악값에서 얼마나 느슨한지에 대한 보증이 없다는 점을 문제로 삼는다. 그래서 약한 인증서와 실제로 취약한 모델을 구분하기 어렵다. 논문은 이 간극을 콘프로그래밍으로 분석하고, 문제의 계산 복잡도와 달성 가능한 정확도 차수를 함께 제시한다.

어떻게 동작하나

핵심 주장은 어려움이 소프트맥스에 있지 않다는 것이다. 소프트맥스는 범위 기반 립시츠 상한, 닫힌 형태의 어텐션 구간, 지수 원뿔로 표현되는 정확한 지수 하한과 할선 상한을 갖는다. 반면 가변 쿼리와 키의 이중선형 점수 z_i^T M z_j가 문제를 어렵게 만든다. 박스형 입력에서 쿼리가 변하면 두 토큰만으로도 NP-hard이고, 어텐션 로짓이 상수만큼 움직일 수 있으면 근사도 어렵다. 쿼리가 고정되면 최악값은 분리 가능한 스칼라 방정식의 근으로 다항시간에 계산되며, 나열된 토큰 치환도 임의 쿼리에 대해 정확히 풀린다.

무엇과 다른가

인증서는 두 층으로 구성된다. 먼저 허용 가능한 어텐션 패턴 위의 선형계획을 탐욕적으로 풀어 1차 정확도의 상한을 얻는다. 다음으로 모멘트 행렬을 도입한 1단계 지수 원뿔 모멘트 완화가 2차 정확도를 준다. 이 완화는 어디에 주의를 기울이는지와 무엇을 읽는지를 결합하며, 그 간극은 값가중 할선 여유, 즉 각 키의 할선 오차를 출력 값의 초과분으로 가중한 분수 배낭 문제로 상한된다. 이 여유는 점수 폭과 섭동 반경에 대해 제곱으로 줄어들고, 두 키와 고정 쿼리만 있는 경우에도 정확히 2차 차수가 나타나므로 더 개선할 수 없다. 또한 연산을 하나씩 완화하는 선형 경계 전파류는 2차 항에서 결합 최댓값 하나 대신 연산별 최댓값의 합을 지불한다는 것을 보인다.

어떻게 쓰나

실험은 GPT-2 small의 12개 블록, 12개 헤드, 즉 144개 헤드 전체에서 정규화된 토큰 섭동으로 수행됐다. 쿼리 고정 시 정확한 최악값과 비교했고, 쿼리가 변하는 경우에는 탐색으로 찾은 실행 가능한 최댓값과 비교했다. 네 쿼리 위치, 다섯 프롬프트, 여섯 반경 조합으로 17,280개 단위를 계산했으며, 인증 구간은 값 스프레드의 10^-10보다 좁고 출력 이동 범위의 중앙값 6×10^-10 수준이었다. 위치 4의 2,880개 단위에서 상대 간극은 반경 0.002에서 0.004, 0.02에서 0.048이었고, 단위별 로그 기울기는 2.04로 1차 인증서의 1.04, 출력 이동 범위의 1.00과 대비됐다. 간극은 2차 상한의 최대 0.78배였고, 반경 0.002 이하에서는 모든 단위가 이동 범위의 10% 안에, 0.001에서는 절반 이상이 1% 안에 인증됐다.

전제와 한계

CROWN과 α-CROWN 비교도 수치로 제시된다. 동일한 헤드, 입력 집합, 명세에서 쿼리 고정 2,880개와 가변 2,880개를 측정했을 때, 구간 경계 전파는 상대 간극 5.7에서 19로 사실상 무의미했다. CROWN과 α-CROWN은 실험적으로 2차 차수를 보였지만 상수 항이 컸다. 단위별 기울기는 쿼리 고정 2.11, 가변 2.39로 인증서의 2.05와 비슷했다. 쿼리 고정 시 이들의 간극은 모든 반경에서 인증서의 3.8~4.7배였고, 쿼리 가변 시 반경 0.001에서 7.8배(α-CROWN 6.7배)에서 0.01에서 22배(17.5배)로 커졌다. 인증서는 5,760개 단위 전부에서 더 타이트했고 96%에서 최소 2배 타이트했다. 다만 CROWN은 단위당 0.01~0.02초, α-CROWN은 0.2~0.7초로, 쿼리 고정 인증서 중앙값 10초·가변 22초보다 훨씬 빨랐다. 저자들은 가장 작은 반경에서는 CROWN이 1차 인증서보다 타이트해 빠른 상한으로 더 낫다고 적는다.

블록 잔차 실험은 경계 전파의 느슨함이 연산별 최댓값 합 때문이라는 예측을 검증한다. GPT-2 블록의 잔차 스트림을 헤드가 읽는 정규화 토큰으로 보내는 함수의 잔차 f를 잡고, 132개 단위에서 CROWN 상한과 다중 시작 상승법으로 찾은 최댓값을 비교했다. 반경 0.001 이하에서 f의 실제 최댓값은 정확한 2차 항과 0.04~1.5% 안에서 일치했고, CROWN 상한은 연산별 합의 1.26~2.34배(중앙값 1.63배)였다. CROWN 느슨함과 예측 느슨함의 순위 상관은 96개 단위에서 0.98, 전체 132개에서 0.90이었다. 전체 예측 느슨함은 중앙값 140배(33~722배)였고, 유효 랭크는 중앙값 11(2.4~50)이었다. 소프트맥스를 한 연산으로 세면 연산별 합은 0.75~1.01배로 바뀌고 순위 상관은 0.98로 유지됐다.

개발자에게 이 논문은 LLM 어텐션의 강건성 검증에서 “인증서가 느슨한 것인지 모델이 취약한 것인지”를 구분하는 기준을 준다. 특히 쿼리 고정이나 나열된 토큰 치환처럼 정확한 최악값을 계산할 수 있는 경우에는 인증서의 오차를 직접 측정할 수 있고, 가변 쿼리에서는 값가중 할선 여유와 분수 배낭 항으로 상한의 느슨함을 예상할 수 있다. CROWN류를 쓸 때는 경험적으로 2차 차수가 나와도 상수가 수배에서 수십 배 커질 수 있고, 작은 반경에서는 속도 이점이 크다는 점을 함께 봐야 한다. 다만 이 결과는 한 헤드의 연속 토큰 섭동과 출력의 선형 범함수에 한정되므로, 전체 트랜스포머의 이산 토큰 치환이나 다층 인증으로 바로 일반화되지는 않는다.

저자들이 밝힌 한계도 분명하다. 분석은 한 어텐션 헤드, 헤드가 읽는 토큰의 연속 섭동, 출력에서 선형으로 읽는 명세에 국한된다. 정확한 최악값은 쿼리 고정 또는 나열된 치환에서만 효율적으로 계산되고, 가변 쿼리는 NP-hard라 실험에서도 실행 가능한 최댓값과 비교한다. 깊이 방향 인증은 블록 연산의 2차 항을 결합하는 새 상한이 필요하고, 키 수에 대해 선형으로 커지는 희소 완화가 규모 확장의 과제다. 또한 인증서는 반경이 작은 2차 영역에서 의미가 크고, 계산 비용과 수치 오차, 안전한 반올림 허용치를 관리해야 한다. 저자들은 이 정확도 상수를 미분 가능하게 만들어 훈련 중 인증 가능성을 제약하는 방향을 향후 과제로 제시한다.