Tạo hướng dẫn hiệu quả cho các mô hình ngôn ngữ lớn: Lập chỉ mục và xử lý FSM lặp

Bảng liên kết

• Tóm tắt và giới thiệu
• Lấy mẫu LLM và tạo hướng dẫn
• Xử lý và lập chỉ mục FSM lặp
• Phần mở rộng cho phân tích lặp
• Thảo luận, Tài liệu tham khảo và Lời cảm ơn

3. Xử lý và lập chỉ mục FSM lặp

Nói một cách chính xác, chúng tôi xem xét các biểu thức chính quy ở dạng máy tự động hữu hạn 5 bộ [Sipser, 1996, Định nghĩa 1.5]:

Định nghĩa 1 (Máy tự động hữu hạn). Một máy tự động hữu hạn, hay máy trạng thái hữu hạn, được cho bởi (Q, Σ, δ, q0, F), trong đó Q là tập hữu hạn các trạng thái, Σ một bảng chữ cái hữu hạn, δ : Q × Σ → Q hàm chuyển tiếp, q0 ∈ Q là trạng thái bắt đầu và F ⊆ Q là tập hợp các trạng thái chấp nhận.

Các ký tự tạo nên các chuỗi trong V được rút ra từ Σ: tức là V ⊂ P(Σ). Xuyên suốt, các trạng thái FSM, Q, sẽ được biểu diễn bằng các giá trị nguyên để đơn giản.

Ví dụ 1. Chúng tôi minh họa quy trình lấy mẫu FSM trong Hình 1 cho biểu thức chính quy ([0-9]*)?\.?[0-9]*, có thể được sử dụng để tạo số dấu phẩy động. Để đơn giản, hãy để từ vựng V chỉ bao gồm các chuỗi: "A", ".", "42", ".2" và "1".

Khi quá trình tạo bắt đầu, FSM ở trạng thái 0, vì vậy thuật toán của chúng tôi che dấu chuỗi "A", vì nó sẽ không được FSM chấp nhận. Chúng tôi chỉ có thể lấy mẫu ".", "42", ".2" và "1" trong trường hợp này.

Nếu chúng tôi lấy mẫu ".2", chúng tôi sẽ nâng FSM lên trạng thái 3. Trong trường hợp này, chỉ "42" và "1" là các phần hoàn thành hợp lệ, vì vậy chúng tôi che dấu các giá trị khác trước khi lấy mẫu. Thay vào đó, nếu lấy mẫu "1", chúng tôi sẽ chuyển FSM lên trạng thái 1, trong trường hợp đó ".", ".42", ".2" và "1" là các phần hoàn thành hợp lệ và mặt nạ vẫn không thay đổi.

Việc lặp lại từ vựng để xác định các mã thông báo tiếp theo hợp lệ vẫn là vấn đề lớn nhất. Để làm được điều đó, chúng tôi xử lý trước từ vựng bằng cách sử dụng FSM của biểu thức chính quy và xây dựng chỉ mục. Phần quan trọng là chúng tôi cân nhắc việc bắt đầu ở mọi trạng thái FSM khả thi, bởi vì các chuỗi trong từ vựng có thể khớp với các phần tùy ý của một biểu thức chính quy và những phần đó hoàn toàn là trạng thái FSM.

Quy trình tạo ra các kết quả khớp bắt đầu tại bất kỳ điểm nào trong FSM được đưa ra trong Thuật toán 3. Kết quả là một danh sách các chuỗi con nêu chi tiết các trạng thái mà FSM sẽ đi qua khi chấp nhận chuỗi được cung cấp.

Bằng cách khớp trạng thái bắt đầu của các chuỗi con này với trạng thái FSM cuối cùng đạt được trong một bước của vòng lặp trong Thuật toán 2, chúng ta có thể lập chỉ mục từ vựng một cách hiệu quả bằng bản đồ, σ : Q → P(V), kết nối các trạng thái FSM và tập hợp các thành phần từ vựng sẽ được FSM chấp nhận ở các trạng thái đó.

Thuật toán 4 mô tả việc xây dựng σ.

Việc sử dụng bản đồ băm cho σ có thể làm cho bước m trong Thuật toán 2 chỉ tốn trung bình O(1). Hơn nữa, do σ được xây dựng bên ngoài quy trình lấy mẫu mã thông báo, nên chi phí thời gian chạy của nó thực sự không liên quan, mặc dù về mặt lý thuyết, nó yêu cầu bộ nhớ bằng số trạng thái trong FSM (tức là |Q|). May mắn thay, đối với sự kết hợp không mang tính bệnh lý của các biểu thức chính quy và từ vựng, không phải mọi chuỗi trong từ vựng sẽ được FSM chấp nhận và không phải mọi trạng thái FSM sẽ được biểu thị bằng một chuỗi trong V.

3.1 Ví dụ

Trong phần này, chúng tôi sử dụng phương tiện GPT2 (tham số 355M) để minh họa cách hoạt động của việc tạo hướng dẫn biểu thức chính quy trong thực tế. Chúng tôi sử dụng thư viện Outlines để tạo chúng:

Liệt kê 3.1 – tiếp theo

Liệt kê 3.3 – tiếp theo

3.2 So sánh với các phương pháp hiện tại

Để minh họa tính hiệu quả của phương pháp lập chỉ mục được mô tả ở đây và được triển khai trong Đề cương, chúng tôi thực hiện một so sánh đơn giản với thư viện Hướng dẫn. Khi viết bài này, thư viện Hướng dẫn sử dụng đối sánh biểu thức chính quy một phần—được áp dụng từ đầu chuỗi được lấy mẫu mỗi lần—và phải lặp lại từ vựng của LLM (N = 50, 257) trên mỗi bước.

Mã hướng dẫn và lời nhắc được sử dụng để so sánh này như sau:

Liệt kê 3.4 – tiếp theo

Mã Outlines tương ứng như sau:

Liệt kê 3.5 – tiếp theo

Giá trị của max_tokens rất đa dạng và thời gian được ghi lại bằng timeit cho một vòng lặp và giá trị lặp lại duy nhất (tức là chỉ thu thập một mẫu cho mỗi giá trị của max_tokens). Kết quả được vẽ ở Phần 3.2.

Ngoại trừ bất kỳ sự giám sát cấu hình nào có thể tạo ra sự khác biệt lớn về thời gian chạy, tỷ lệ quan sát được về số lượng mã thông báo được lấy mẫu tối đa là rất đáng chú ý và là dấu hiệu cho thấy vấn đề tính toán ngày càng tăng mà phương pháp này ngụ ý.