대규모 언어 모델(LLM)은 현대 AI 응용 분야에 사용되지만, 신뢰할 수 없는 서버에서 민감한 데이터를 처리하는 것은 개인 정보 보호 문제를 야기합니다. 동형 암호화(HE)는 암호화된 데이터에 대한 연산을 가능하게 하여 안전한 추론을 지원합니다. 그러나 신경 텍스트 생성에는 argmax 및 sampling과 같은 디코딩 방법이 필요하며, 이는 비다항식이므로 암호화 환경에서 계산 비용이 많이 들고 성능 병목 현상을 만듭니다. 본 논문에서는 HE 친화적인 argmax 알고리즘인 cutmax를 도입하여 이전 방법보다 암호문 연산을 줄여 암호화 환경에서 실용적인 greedy decoding을 가능하게 합니다. 또한, cutmax를 활용하여 효율적인 확률적 디코딩을 수행하는 최초의 HE 호환 nucleus (top-p) sampling 방법을 제안하며, 이는 입증된 개인 정보 보호 보장을 제공합니다. 두 기법 모두 다항식이며, 개인 정보 보호 환경에서 효율적인 추론을 지원합니다. 또한, 이들의 미분 가능성은 straight-through estimator의 다항식 대안으로, 기울기 기반 시퀀스 레벨 최적화를 용이하게 합니다. Cutmax에 대한 강력한 이론적 보장을 제공하며, 최대 요소와 두 번째로 큰 요소 간의 갭 비율의 지수 증폭을 통해 수렴을 증명합니다. 실제 LLM 출력에 대한 평가는 기본 설정 대비 24x-35x의 지연 시간 감소를 보여주며, 안전한 텍스트 생성을 발전시킵니다.
