대규모 언어 모델을 위한 효율적인 생성 유도: 반복적인 FSM 처리 및 인덱싱

링크 표

• 초록 및 소개
• LLM 샘플링 및 유도 생성
• 반복적인 FSM 처리 및 인덱싱
• 반복적 구문 분석에 대한 확장
• 토론, 참고자료 및 감사의 말

3. 반복적인 FSM 처리 및 인덱싱

정확하게 말하면 5-튜플 유한 자동 장치 형식의 정규식을 고려합니다 [Sipser, 1996, 정의 1.5]:

정의 1 (유한 오토마톤). 유한 오토마톤 또는 유한 상태 기계는 (Q, Σ, δ, q0, F)로 제공됩니다. 여기서 Q는 유한 상태 집합, Σ는 유한 알파벳, δ : Q × Σ → Q 전이 함수입니다. q0 ∈ Q는 시작 상태이고 F ⊆ Q는 승인 상태 세트입니다.

V의 문자열을 구성하는 문자는 Σ에서 추출됩니다. 즉, V ⊂ P(Σ)입니다. 전체적으로 FSM 상태 Q는 단순화를 위해 정수 값으로 표시됩니다.

예제 1. 그림 1에서는 부동 소수점 숫자를 생성하는 데 사용할 수 있는 정규식 ([0-9]*)?\.?[0-9]*에 대한 FSM 샘플링 프로세스를 보여줍니다. 단순화를 위해 어휘 V는 문자열 "A", ".", "42", ".2" 및 "1"로만 구성됩니다.

생성이 시작되면 FSM은 상태 0에 있으므로 알고리즘은 문자열 "A"를 마스크합니다. 이는 FSM에서 허용되지 않기 때문입니다. 이 경우에는 ".", "42", ".2" 및 "1"만 샘플링할 수 있습니다.

".2"를 샘플링하면 FSM을 상태 3으로 진행합니다. 이 경우 "42"와 "1"만 유효한 완성이므로 샘플링하기 전에 다른 값을 마스킹합니다. 대신 "1"을 샘플링하면 FSM을 상태 1로 진행합니다. 이 경우 ".", ".42", ".2" 및 "1"은 유효한 완성이고 마스크는 변경되지 않은 상태로 유지됩니다.

유효한 다음 토큰을 결정하기 위해 어휘를 반복하는 것이 여전히 가장 큰 문제입니다. 이를 위해 정규식의 FSM을 사용하여 어휘를 전처리하고 색인을 구축합니다. 중요한 부분은 어휘의 문자열이 정규식의 임의 부분과 일치할 수 있고 해당 부분이 암시적으로 FSM 상태이기 때문에 실행 가능한 모든 FSM 상태에서 시작하는 것을 고려한다는 것입니다.

FSM의 임의 지점에서 시작하여 일치 항목을 생성하는 절차는 알고리즘 3에 나와 있습니다. 결과는 제공된 문자열을 수락할 때 FSM이 통과하는 상태를 자세히 설명하는 하위 시퀀스 목록입니다.

이러한 하위 시퀀스의 시작 상태를 알고리즘 2의 루프의 단일 단계에서 도착한 마지막 FSM 상태와 일치시킴으로써 FSM 상태를 연결하는 맵 σ : Q → P(V)를 사용하여 어휘를 효율적으로 인덱싱할 수 있습니다. 그리고 해당 주에서 FSM이 수용할 어휘 요소 세트입니다.

알고리즘 4는 σ의 구성을 설명합니다.

σ에 대한 해시 맵을 사용하면 알고리즘 2의 m 단계 비용은 평균 O(1)에 불과합니다. 또한 σ는 토큰 샘플링 절차 외부에서 구성되므로 이론적으로는 FSM의 상태 수(예: |Q|)와 동일한 메모리가 필요하지만 런타임 비용은 사실상 관련이 없습니다. 다행스럽게도 정규식과 어휘의 비병리학적 조합의 경우 어휘의 모든 문자열이 FSM에서 허용되는 것은 아니며 모든 FSM 상태가 V에서 문자열로 표시되는 것은 아닙니다.

3.1 예

이 섹션에서는 GPT2-medium(355M 매개변수)을 사용하여 정규식 안내 생성이 실제로 어떻게 작동하는지 보여줍니다. 우리는 이를 생성하기 위해 아웃라인 라이브러리를 사용합니다:

목록 3.1 – 계속

목록 3.3 - 계속

3.2 현행 방식과의 비교

여기에 설명되고 개요에 구현된 색인화 접근 방식의 효율성을 설명하기 위해 지침 라이브러리와 간단한 비교를 수행합니다. 이 글을 쓰는 시점에서 Guidance 라이브러리는 매번 샘플링된 시퀀스의 시작부터 적용되는 부분 정규식 일치를 사용하고 각 단계에서 LLM의 어휘(N = 50, 257)를 반복해야 합니다.

이 비교에 사용된 지침 코드와 프롬프트는 다음과 같습니다.

목록 3.4 - 계속

해당 개요 코드는 다음과 같습니다.

목록 3.5 - 계속

max_tokens의 값은 다양하며 단일 루프 및 단일 반복 값에 대해 timeit으로 타이밍이 기록됩니다(즉, max_tokens의 각 값에 대해 하나의 샘플만 수집됩니다). 결과는 섹션 3.2에 표시되어 있습니다.

큰 런타임 불일치를 야기할 수 있는 구성 감독을 제외하고, 관찰된 샘플링된 토큰의 최대 수의 확장은 눈에 띄며 접근 방식에 의해 암시되는 계산 문제가 커지고 있음을 나타냅니다.