초안이 좋을수록 느려졌다

2편에서 글자 하나를 뽑을 때마다 목표 모델을 한 번 통과해야 했다. 캐시를 붙여도 통과 횟수 자체는 글자 수만큼이다.

투기적 디코딩은 그 횟수를 줄인다. 싼 모델에게 k 글자를 미리 쓰게 하고, 비싼 모델에 그 k+1 자리를 한 번에 넣어 검사한다. 맞은 것은 그대로 쓰고 처음 틀린 자리에서 잘라낸다.

이상하게 들리는 주장이 하나 붙는다. 출력 분포가 목표 모델 혼자 뽑은 것과 정확히 같다. 3편에서 int8 이 손실을 0.0017 만 올렸는데도 22번째 글자에서 갈렸던 것을 생각하면 의심스럽다. 그것부터 확인한다.

왜 분포가 안 바뀌나

초안이 x 를 냈고 초안 확률이 q(x), 목표 확률이 p(x) 라 하자. 받아들이는 규칙은 이것뿐이다.

if rand() < min(1, p[x] / q[x]):
    accept(x)
else:
    resid = (p - q).clamp_min(0)
    emit(sample(resid / resid.sum()))     # 그리고 나머지는 버린다
    break

q 가 p 보다 x 를 과하게 냈으면 그 비율만큼만 받고, 거절했을 때는 p 가 q 보다 많이 원했던 부분 max(0, p-q) 에서 다시 뽑는다. 두 경우를 합치면 정확히 p 가 된다.

말이 아니라 재 봤다. 문맥을 고정하고 첫 글자를 20000번 뽑아 목표 분포와의 총변동거리를 본다.

바이그램 초안      총변동거리 0.0158
4비트 초안         총변동거리 0.0095
목표에서 직접 뽑기  총변동거리 0.0134     <- 같은 표본 수의 기준선

기준선과 같은 자리다. 20000번으로는 이만큼의 표본 오차가 나오는 게 정상이고, 투기적 디코딩이 만든 편차는 그 안에 있다. 초안 모델이 형편없어도 출력은 목표 모델 것이다.

초안 셋

초안으로 셋을 쓴다. 세 개가 다 이 시리즈 안에 있다.

바이그램: 1편의 기준선. 앞 글자만 보고 표를 찾는다
8비트: 3편에서 가중치를 int8 로 뭉갠 것
4비트: 3편에서 무너지기 직전이었던 것

수락률은 초안 품질을 따른다

   초안      k   수락률   목표통과당 글자   목표통과 수
바이그램      1   0.290       1.29           155
바이그램      8   0.059       1.47           136
8비트        1   0.896       1.89           106
8비트        8   0.610       5.88            34
4비트        1   0.653       1.65           121
4비트        8   0.351       3.77            53

예상대로다. 8비트는 목표와 거의 같은 모델이라 0.896 을 받아내고, 바이그램은 0.290 이다. k 를 키우면 수락률은 떨어지지만(뒤로 갈수록 문맥이 어긋나니까) 한 번 통과로 얻는 글자 수는 늘어난다.

8비트에 k=8 이면 목표 모델 통과가 200회에서 34회로 준다. 통과당 5.88 글자다. 2편의 캐시가 차수를 바꿨다면 이건 상수를 6분의 1로 줄인 셈이다.

그런데 실제로는 8비트가 가장 느리다

초안 길이 k 에 따른 실제 속도 배수. 선은 다섯 쌍의 중앙값이고 띠가 최소~최대다. 수락률이 가장 낮은 바이그램만 1을 넘고, 수락률 0.9 짜리 8비트 초안은 0.56 배까지 떨어진다. 수락률이 아니라 초안 값이 부호를 정한다.

   초안      k   통과당 글자   실측 배수   범위
바이그램      4       1.39       1.30    1.19~1.47
바이그램      8       1.47       1.26    1.08~1.36
8비트        4       4.35       0.80    0.79~0.91
8비트        8       5.88       0.56    0.50~0.66
4비트        8       3.77       0.41    0.38~0.47

목표 통과를 5.9배 줄인 쪽이 0.56배로 느려졌다. 반대로 통과를 겨우 1.47배 줄인 바이그램이 1.26 배 빠르다.

이유는 초안 값이다. 초안 한 글자에 드는 시간을 목표 한 번 통과에 대한 비로 재면

목표 모델 한 번 통과      1235 us
바이그램 초안 한 글자         5 us    c = 0.004
8비트 초안 한 글자         1307 us    c = 1.059
4비트 초안 한 글자         1276 us    c = 1.034

c = 1.059 다. 8비트 초안은 목표 모델보다 비싸다. 그러니 k=8 이면 목표 통과 한 번을 아끼려고 초안을 여덟 번 돌리고, 그 여덟 번이 목표 여덟 번과 같은 값이다.

3편을 다시 읽으면 당연한 결과다. 거기서 int8 이 아낀 것은 메모리였다. 2.43 MB 가 0.62 MB 가 됐지만 시간에 대해서는 아무 말도 하지 않았다. 곱셈은 여전히 float32 로 돌고, 가중치를 반올림해 둔 것뿐이다. 양자화가 속도를 준다고 읽으면 이런 실수를 한다.

예측 식이 맞는다

이 시리즈에서 처음으로 간단한 식이 실측을 맞혔다.

배수 = (목표통과당 글자) / (1 + k · c)

목표 통과 한 번당 글자를 얼마나 얻는지가 위, 그 한 번을 위해 치른 초안 값이 아래다.

   초안      k   예측   실측 중앙
바이그램      2   1.36    1.10
바이그램      4   1.37    1.30
8비트        2   0.87    0.87
8비트        4   0.83    0.80
8비트        8   0.62    0.56
4비트        2   0.67    0.67
4비트        4   0.49    0.46
4비트        8   0.41    0.41

양자화 초안 쪽은 소수점 둘째 자리까지 맞는다. 바이그램은 식이 조금 후하게 잡는데, 초안 값 c 를 한 번 호출로 재서 파이썬 반복문 몫이 안 들어갔기 때문이다. 값이 워낙 작아 그 몫이 상대적으로 크게 보인다.

2편에서 산술 계산이 134.5 배를 약속하고 실측이 2.94 배였던 것과 대비된다. 차이는 무엇을 셈에 넣었는지다. 그때는 곱셈만 셌고 지금은 치른 값을 다 셌다.

시간 측정에 대한 단서

이 편의 시간 숫자는 처음에 못 믿을 상태였다. 같은 기준선이 한 번은 749 ms, 다음엔 448 ms 로 나왔다. 노트북 부하가 흔들려서다.

그래서 기준선과 투기 실행을 번갈아 재고 쌍마다 비를 낸 뒤 다섯 쌍의 중앙값을 썼다. 드리프트가 양쪽에 같이 걸리므로 비에서는 상쇄된다. 표의 범위 열이 그 다섯 쌍의 최소와 최대이고, 바이그램 k=1 처럼 0.82~1.29 로 넓은 자리도 있다. 그림의 띠가 그 폭이다.

수락률과 목표통과 수는 씨앗이 정해지면 정확히 같은 값이 나오는 결정적 수치라 이 문제가 없다. 그래서 이 편의 결론은 시간보다 그쪽에 기대고 있다.

그래서

투기적 디코딩은 출력 분포를 바꾸지 않는다. 총변동거리 0.0158 과 0.0095, 같은 표본 수의 기준선이 0.0134 다
초안이 좋으면 수락률이 오른다. 8비트가 0.896, 바이그램이 0.290
목표 통과 횟수는 크게 준다. 8비트에 k=8 이면 200회에서 34회, 통과당 5.88 글자
그런데 그쪽이 가장 느리다. 0.56 배. 초안이 목표보다 비싸기 때문이고, c 가 1.059 다
실제로 빠른 것은 가장 나쁜 초안뿐이다. 바이그램 1.26 배, c = 0.004
부호를 정하는 것은 수락률이 아니라 초안 값이다. (통과당 글자) / (1 + k·c)

다음 편에서는 2편이 설명하지 못한 격차로 돌아간다. 오버헤드가 값이라면 그 몫이 정확히 얼마인지, 그리고 그것을 되찾는 방법이 있는지 잰다.