llama: bổ sung lấy mẫu dựa trên ngữ pháp

 (github.com/ggerganov)
1 điểm bởi GN⁺ 2023-07-23 | 1 bình luận | Chia sẻ qua WhatsApp
  • PR #1773 của llama.cpp bổ sung API giới hạn các ứng viên lấy mẫu bằng ngữ pháp phi ngữ cảnh, nhằm bảo đảm kết quả sinh ra không lệch khỏi định dạng đã chỉ định
  • API nhận cấu trúc dữ liệu ngữ pháp dựa trên code point 32-bit, lọc token ứng viên bằng llama_sample_grammar, rồi phản ánh token đã chọn vào trạng thái ngữ pháp bằng llama_grammar_accept_token
  • main được thêm các đối số --grammar và --grammar-file để nhập ngữ pháp dạng BNF mở rộng; các ví dụ gồm Chess, biểu thức số học, JSON và sinh phạm vi ký tự tiếng Nhật
  • Các bài kiểm thử được thực hiện trên M2 Max và mô hình 30B Q4_0; khi áp dụng ngữ pháp, đầu ra bị giới hạn đúng theo ký pháp cờ vua, biểu thức số học, JSON và phạm vi ký tự tiếng Nhật, trong khi không có ngữ pháp thì mô hình sinh văn bản hoặc mã nguồn thông thường không khớp với prompt
  • Phần thảo luận tập trung vào các ràng buộc khi dùng thực tế như hỗ trợ file ngữ pháp, xử lý dòng trống và chú thích, có nên đưa parser vào API, che logit bằng GPU, xử lý theo lô các token cố định và overhead hiệu năng

Thay đổi chính của PR

  • Đây là PR bổ sung lấy mẫu dựa trên ngữ pháp cho llama.cpp
  • Công việc này tham khảo phần triển khai trước đó là #1397 và công việc CFG của grantslatton
  • API mới nhận ngữ pháp phi ngữ cảnh đã được tuần tự hóa để dẫn hướng và giới hạn quá trình lấy mẫu
  • Trong main, các ví dụ ngữ pháp kiểu BNF tương tự được thêm vào để chỉ định ngữ pháp sinh

Cấu trúc Grammar API

  • API llama nhận cấu trúc dữ liệu ngữ pháp phi ngữ cảnh cho các code point 32-bit
  • Các kiểu phần tử ngữ pháp biểu diễn kết thúc quy tắc, bắt đầu lựa chọn thay thế, tham chiếu quy tắc, ký tự, cận trên của phạm vi ký tự và thêm ký tự thay thế
  • Hàm khởi tạo nhận các thông tin sau
    • mảng quy tắc
    • số lượng quy tắc
    • chỉ số quy tắc bắt đầu
  • llama_grammar_element có type và value, trong đó value được dùng làm code point Unicode hoặc ID quy tắc

Cách lấy mẫu

  • Mã lấy mẫu theo ngữ pháp mô hình hóa một ô tô mát đẩy xuống không tất định
  • Nó duy trì N ngăn xếp để biểu diễn các trạng thái phân tích cú pháp có thể có
  • Quá trình lấy mẫu token hoạt động theo hai bước
    • llama_sample_grammar chỉ giữ lại các ứng viên khớp với ít nhất một ngăn xếp phân tích trong số các token ứng viên
    • llama_grammar_accept_token thêm token đã chọn vào trạng thái ngữ pháp

Tính năng nhập ngữ pháp trong main

  • main được thêm các đối số --grammar và --grammar-file
  • Hai đối số này nhận ngữ pháp BNF mở rộng đơn giản để giới hạn kết quả sinh
  • Bộ phân tích ngữ pháp được cài đặt trong examples/grammar-parser.{h,cpp}
  • Các tính năng ngữ pháp được hỗ trợ gồm phạm vi ký tự, gom nhóm và toán tử lặp
  • Quy tắc root xác định điểm bắt đầu của ngữ pháp
  • Các bản cập nhật sau đó bổ sung hỗ trợ file ngữ pháp, thêm ví dụ, chú thích kiểu shell, dòng trống giữa các quy tắc và cho phép xuống dòng trong nhóm ngoặc

Ví dụ kiểm thử

  • Môi trường kiểm thử được nêu là mô hình M2 Max, 30B
  • Ví dụ Chess
    • Dùng --grammar-file grammars/chess.gbnf sẽ sinh ra định dạng ký pháp cờ vua như 1. e4 e5, 2. Nf3 Nc6
    • Nếu chạy cùng prompt mà không có ngữ pháp thì mô hình sinh ra câu văn thông thường liên quan đến Sir Thomas Gresham
  • Ví dụ biểu thức số học
    • Dùng ngữ pháp nội tuyến để ép theo dạng expr "=" ws num "\n"
    • Kết quả bị giới hạn theo dạng biểu thức số học như 10 *a*1 +b*2 =640
    • Nếu không có ngữ pháp thì đầu ra là một đoạn mã Go
  • Ví dụ JSON
    • Dùng grammars/json.gbnf sẽ sinh ra cấu trúc JSON dạng { "fullName": ..., "address": ... }
    • Nếu không có ngữ pháp thì mô hình sinh văn xuôi kiểu tự giới thiệu
  • Ví dụ tiếng Nhật
    • grammars/japanese.gbnf cho phép hiragana, katakana, dấu câu và phạm vi CJK
    • Khi áp dụng ngữ pháp, đầu ra là danh sách dựa trên ký tự tiếng Nhật
    • Nếu không dùng ngữ pháp thì đầu ra là danh sách các bước bằng tiếng Anh

Thảo luận về review và thiết kế

  • Có đề xuất nhận ngữ pháp từ file, và sau đó hỗ trợ grammar file cùng ví dụ đã được thêm vào
  • Các vấn đề được phát hiện trong quá trình dùng ban đầu gồm xung đột với --prompt-cache và crash do dòng trống trong ngữ pháp
  • Hỗ trợ dòng trống và chú thích, cùng việc cho phép xuống dòng trong nhóm ngoặc, đã được đưa vào các commit tiếp theo
  • Đã có thảo luận về việc có nên đưa parser vào API của llama.cpp hay không
    • Nếu parser ở ngoài API, người dùng downstream sẽ phải sao chép parser để hỗ trợ tính năng này
    • Tác giả muốn giảm thay đổi trong chính llama.cpp, nhưng cũng đồng ý rằng đưa parser vào API sẽ tiện hơn
  • Có đề xuất để llama_grammar giữ một bản sao ngữ pháp nhị phân, nhờ đó người dùng không cần duy trì vòng đời của bản sao đã truyền vào

Thảo luận về hiệu năng và tối ưu hóa

  • Có ý kiến cho rằng ngay cả khi N > 1 token tiếp theo được xác định duy nhất bởi ngữ pháp, cách hiện tại vẫn lấy mẫu từng token một
  • Việc đánh giá theo lô nhiều token cố định có thể tăng mạnh tốc độ suy luận trong những trường hợp như vậy
  • Tác giả trả lời rằng các token vẫn cần được đánh giá và nút thắt có vẻ nằm ở phần đánh giá; họ cho rằng đánh giá theo lô ở mức chuỗi có thể là một điểm tối ưu hóa
  • Cũng có ý tưởng biên dịch ngữ pháp trên GPU thành tensor chuyển trạng thái hoặc che logit trên GPU cho toàn bộ tập token
  • torch-grammar được nhắc đến như một cách tiếp cận tương tự, thực hiện che logit bắt buộc theo ngữ pháp trên GPU cho toàn bộ tập token

Quan sát về hiệu năng

  • Tác giả cho biết mới chỉ thử suy luận trên CPU và trong phạm vi họ thử thì ảnh hưởng hiệu năng không lớn
  • Các con số quan sát trên M2 Max
    • Lấy mẫu không ràng buộc khoảng 0.5ms/token
    • Lấy mẫu có áp dụng ngữ pháp khoảng 6ms/token
    • Đánh giá token của 13B Q4_K khoảng 70ms/token
  • Một người dùng khác báo cáo trường hợp 13B giảm từ khoảng 20T/s xuống 13T/s
  • Tác giả cho biết họ thường thấy overhead ngữ pháp vào khoảng 5ms/token, nhưng với một số ngữ pháp cụ thể tác động lớn hơn và có thể tồn tại các trường hợp xấu

Thảo luận về các mở rộng liên quan

  • Có nhắc đến hướng dùng đầu vào JSON Schema rồi chuyển sang BNF
  • Tác giả cho biết họ có một nhánh cục bộ hoạt động theo ví dụ trong README của jsonformer, và dùng script Python để sinh JSON BNF phù hợp với JSON Schema
  • Sau đó, examples : generate JSON according to schema #1887 được nhắc đến như phần liên kết với PR này
  • Cách tiếp cận này được trả lời là độc lập với biến thể mô hình và cũng có thể dùng cùng các mô hình fine-tune
  • Một PR bổ sung lấy mẫu dựa trên ngữ pháp cho whisper.cpp cũng được nhắc đến riêng

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-23
Các ý kiến trên Hacker News

  • Theo cách tôi hiểu thì cơ chế hoạt động là như thế này. Mô hình ngôn ngữ lấy prompt làm điểm khởi đầu và xuất ra từng token một; cuộc trò chuyện với LLM cũng có thể được xem là người dùng đưa vào một chuỗi token, mô hình sinh ra một phần, rồi người dùng lại nối tiếp vào đó
    Kỹ thuật ngữ pháp này cho phép kiểm soát token ở mức tinh vi hơn nhiều. Ví dụ, nếu đưa đến đoạn Give me the address of the White House as JSON: {"street": ", LLM sẽ trả về 1600 Pennsylvania Ave NW"; ngay khi thấy dấu nháy kép đóng, người dùng chèn ", "City": " để nhận Washington, DC"
    Tuy nhiên, vì đây là dựa trên ngữ pháp, nên nó có thể làm được nhiều thứ hơn rất nhiều chứ không chỉ JSON. Trước đây tôi từng thấy một đề xuất khá hay trên Twitter: OpenAI có thể cho phép truyền một ngữ pháp phi ngữ cảnh xác định làm tham số API, hoặc xa hơn nữa là nhận vài KB dưới dạng một binary WASM nhỏ chính là sampler, rồi chạy nó với vài MB bộ nhớ; như vậy năng lực của LLM có thể được mở rộng đáng kể
    https://twitter.com/grantslatton/status/1637692033115762688

    • Không chỉ vậy, LLM không trực tiếp xuất từng token riêng lẻ, mà đưa ra danh sách gợi ý có trọng số. Token có vẻ hợp lý nhất có trọng số cao nhất, nhưng có thể có nhiều phương án thay thế, bao gồm cả các ký hiệu JSON như dấu nháy
      Thiết lập temperature điều chỉnh khả năng các token không đứng hạng cao nhất được chọn, nhằm giảm đầu ra lặp lại. Việc buộc LLM tuân theo ngữ pháp về cơ bản là lọc danh sách trước khi chọn token, nhưng sự ngẫu nhiên do temperature kiểm soát vẫn có thể còn
      Một tính năng nâng cao hơn là cho phép quay lui khi AI bị kẹt và không thể tạo ra đầu ra hợp lệ
    • Cơ chế thực tế là kiểm tra đầu ra hiện tại cùng các token tiếp theo là ứng viên sampling bằng ngữ pháp, rồi loại bỏ toàn bộ các token ứng viên không khớp. Sau đó áp dụng chiến lược sampling thông thường lên danh sách token hợp lệ còn lại
    • Tôi nghĩ cách giải thích này không đúng. Trước đây cũng đã có thể kiểm soát đầu ra của LLM bằng cách đọc từng token một rồi dừng khi gặp ký tự dừng
      Theo tôi, điểm cốt lõi của PR sampling dựa trên ngữ pháp là llama.cpp dùng ngữ pháp để thu hẹp token đầu ra tiếp theo vào một tập con giới hạn các token có thể có
    • Cũng có phần giải thích chi tiết hơn về cách triển khai cái này: https://github.com/normal-computing/outlines/pull/131
      Nó được viết bởi một trong các nhà phát triển thư viện Outlines; Outlines cũng là một thư viện workflow LLM khá ổn
    • Tôi không hiểu lắm đang nói gì. Bắt đầu từ “passing up”, tôi tự hỏi liệu người này có đang tự đặt thuật ngữ mới không. Đầu vào duy nhất có thể đưa vào LLM là prompt được token hóa
      Ngay cả khi gửi các quy tắc DCFG hoặc phiên bản đã biên dịch như một phần của request, tôi cũng không thấy điều đó thay đổi căn bản cách dự đoán token như thế nào. Nếu mô hình dự đoán thứ không phù hợp với ngữ pháp yêu cầu, ý là lại đưa prompt vào cho đến khi đúng à?

  • Cần chỉ ra rằng thứ này chỉ đặt ràng buộc ngữ pháp lên văn bản do mô hình tạo ra, chứ không thật sự căn chỉnh nội dung. Nó hữu ích khi cần đảm bảo server xuất JSON được định dạng tốt, nhưng có lẽ không giải quyết được nhiều vấn đề alignment hiện nay trong sinh ngôn ngữ
    Ví dụ, hiện Llama hay GPT thường gắn nhãn sai cho các khối mã Markdown. Sampling dựa trên ngữ pháp có thể buộc phải gắn nhãn, nhưng nhãn có đúng hay không thì phụ thuộc ngữ cảnh nên không thể cưỡng ép được. Cũng khó kỳ vọng đầu ra tốt nếu tạo một ngôn ngữ chuyên biệt theo miền mới rồi không căn chỉnh theo ngôn ngữ đó

    • Điều quan trọng nữa là khi xuất hiện chuỗi tự do, đó là một lời mời mở để LLM có thể lao sang hướng hoàn toàn không liên quan. Vì vậy các phương pháp như thế này nên được dùng cùng với những heuristic khác, chẳng hạn phạt lặp lại, để làm lệch sampling khi đi vào vùng văn bản tự do
    • Dù vậy, với Llama thì có thể huấn luyện một vài ví dụ bằng LoRA
      Chẳng hạn có thể tưởng tượng một hệ thống hot-swap LoRA dành cho Markdown và tệp ngữ pháp Markdown tùy theo nhu cầu

  • Tôi thật sự thích cái này. Trước đây tôi từng làm Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Genera...), và cũng đã có một bài liên quan được đăng ở COLING 2022 (https://paperswithcode.com/paper/most-language-models-can-be...)
    Dù vậy, tôi luôn nghĩ rằng hướng đi là các cách tiếp cận như thế này, hoặc những ý tưởng liên quan được liệt kê trong bài này: https://arxiv.org/abs/2306.03081
    Giờ tôi phải nghĩ xem làm sao tạo được ngữ pháp có thể cưỡng ép những thứ như số âm tiết hay quy tắc cú pháp. Hiện LLM làm các tác vụ kiểu đó rất kém vì cách token hóa

    • Hơi bất ngờ, nhưng Nous Hermes viết haiku khá thuyết phục

  • Tôi cũng đã triển khai cái này cho PyTorch: https://github.com/Shopify/torch-grammar. Tôi cũng có một bản hack của text-generation-inference dùng nó; nếu cần tôi có thể chia sẻ

    • Nếu bạn chia sẻ thì tốt quá. Tôi đã định dump vector xác suất token từ một trong các UI LLM, nhưng nếu có điểm xuất phát khác thì sẽ khá hữu ích

  • Với các enum chuỗi dạng nhiều lựa chọn, về cơ bản giống dropdown, tôi tự hỏi liệu khi đưa ra lựa chọn cuối cùng, nếu xét xác suất kết hợp toàn phần của trạng thái có logits thay vì dùng thuật toán tham lam thì có hoạt động tốt hơn không
    Khi token bắt đầu được chia sẻ giữa nhiều mục trong danh sách, điều đó có thể giúp ưu tiên lựa chọn đúng thay vì lựa chọn có token bắt đầu phổ biến nhất. Tất nhiên sau khi một phần logits bị đưa về 0 thì phải điều chỉnh xác suất thì mới thực sự hợp lý

  • “Thư viện” ngữ pháp này đã được trích dẫn như một ví dụ về định dạng: https://github.com/antlr/grammars-v4
    Trong đó có đủ thứ, từ assembly và C++ đến GLSL, ngôn ngữ scripting, số học, trò chơi, shortcut freedesktop, LLVM IR, và cả những định dạng đặc biệt như Verilog

    • Sẽ tiện nếu API suy luận có thể chỉ định shortcut ngữ pháp tiêu chuẩn như HTML, JSON, Python. Nghĩ đến công sức OpenAI đã bỏ ra để tinh chỉnh mô hình Code Interpreter, thật lòng mà nói khá lạ là họ vẫn chưa làm việc này
    • Sẽ rất tuyệt nếu hỗ trợ cú pháp ngữ pháp ANTLR4. Đây là một công cụ xuất sắc

  • Có ai giải thích dễ hiểu được không? Tôi biết LLM ở mức nào đó, nhưng chưa thật sự hiểu Georgi đang làm gì ở đây và vì sao một số người lại phấn khích như vậy

    • LLM không trực tiếp tạo ra “token tiếp theo”. Từ văn bản đầu vào, nó tạo một vector xác suất mà mỗi ô tương ứng với một token, và có thể xem mỗi giá trị gần như là xác suất token đó sẽ xuất hiện tiếp theo
      Các chương trình như ChatGPT “diễn giải” vector xác suất đó rồi chọn, tức lấy mẫu, một trong các token hàng đầu để tạo văn bản. Nhưng cách này đôi khi quá linh hoạt: ngay cả khi muốn đầu ra JSON, nó vẫn có thể chọn token không hợp với cú pháp JSON và tạo ra JSON sai
      Cách “ép” LLM sinh ra thứ như JSON là thay đổi quá trình lấy mẫu. Thay vì chọn bất kỳ token hàng đầu nào, trước hết chỉ giữ lại các token phù hợp với cú pháp JSON, rồi lấy mẫu các token hàng đầu trong tập con đó
    • Khi yêu cầu LLM tạo JSON hoặc một ngôn ngữ khác có ngữ pháp, đôi lúc nó tạo ra cú pháp sai. PR này giới hạn LLM để chỉ xuất ra cú pháp hợp lệ theo ngữ pháp do người dùng cung cấp, bằng cách sửa đổi quy trình lấy mẫu
      LLM tạo văn bản theo đơn vị token. Trước tiên, một mạng nơ-ron khổng lồ gán xác suất cho tất cả token có thể có; sau đó quy trình lấy mẫu dùng các xác suất đó để chọn một token, rồi lặp lại quá trình này
      Quy trình lấy mẫu không phải là mạng nơ-ron nên có thể được thay đổi theo nhiều cách. Cũng có thể dùng lấy mẫu tham lam, luôn chọn token có xác suất cao nhất, nhưng thường thì chọn ngẫu nhiên có trọng số theo xác suất sẽ tốt hơn. Nó tạo ra sự đa dạng và cũng giảm khả năng rơi vào vòng lặp. Tuy nhiên, bất kỳ token nào có xác suất khác 0 đều có thể được chọn, nên JSON sai vẫn có thể xuất hiện. PR này đặt xác suất của mọi token không hợp lệ theo ngữ pháp thành 0 để chúng không thể được chọn
      Cũng có thể có những sửa đổi thú vị khác trong quá trình lấy mẫu. Khi lấy mẫu từng token một, ta có thể đi vào ngõ cụt và không còn lựa chọn nào, nên có thể cho phép quay lui. Xa hơn nữa, ở mỗi bước có thể xét nhiều lựa chọn để tạo một cây các đầu ra khả dĩ, rồi cuối cùng chọn đường đi có xác suất tổng thể cao nhất. Nếu xét mọi lựa chọn thì đó là cây đầy đủ phân nhánh theo số token có thể có, nên sẽ tăng theo cấp số mũ; vì vậy có thể cắt tỉa bằng cách chỉ giữ, chẳng hạn, 5 đường đi tốt nhất ở mỗi bước. Đó là beam search. Vì chi phí chạy mạng nơ-ron tạo xác suất rất lớn, việc tăng chi phí lên 5 lần là khá nặng, nên thường không dùng trong LLM, nhưng vẫn khả thi và kết quả cũng tốt hơn ở mức nào đó. Cũng có thể nghĩ đến việc dùng Monte Carlo Tree Search như các engine cờ vua
    • LLM sẵn sàng tạo ra chuỗi tùy ý. Bạn muốn thứ như “Alice: 42”, nhưng nó có thể trả về kiểu “Xin chào, tôi là một mô hình hữu ích và theo tôi thì Alice chính xác là forty two, nhưng tôi chỉ là một mô hình ngôn ngữ”
      Vì vậy ta đưa ra một ngữ pháp rằng phản hồi phải bắt đầu bằng một chữ cái viết hoa, sau đó là các chữ thường, dấu hai chấm, dấu cách, các chữ số rồi kết thúc. Khi đó, lúc tìm token đầu tiên, chỉ những token tương thích với mẫu đó mới được xét; các bước sau cũng chỉ tiếp tục xét những token tương thích với phần tiếp theo của mẫu
      Loại ngữ pháp này biến việc đó thành một mẫu linh hoạt và hữu ích
    • Xem bình luận của tôi ở đây: https://news.ycombinator.com/item?id=36820884

  • Việc này thú vị nên tôi đang định đưa vào công việc của mình. Tuy nhiên, từ góc nhìn Bitter Lesson, tôi có cảm giác đây có thể không phải là cách tiếp cận tốt nhất ngoài rất ngắn hạn: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • Có thể chỉ là giải pháp tạm thời, nhưng là một giải pháp tạm thời quan trọng. Không rõ trong vài năm tới LLM có “tự nhiên” giải quyết được bài toán sinh văn bản có ràng buộc hay không
    • Tôi hoàn toàn không phải chuyên gia, nhưng theo tôi biết OpenAI dùng cách như vậy trong một số GPT API dành cho lập trình. Tôi cũng từng thấy suy đoán rằng nếu chuyển việc xử lý ngữ pháp đơn giản sang một quy trình đơn giản phù hợp, LLM có thể dùng tài nguyên tính toán hiệu quả hơn cho các việc phức tạp. Tôi không biết điều đó có đúng không

  • Cũng có dự án dùng phương pháp tương tự: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • Tôi muốn được gợi ý các bài báo hoặc bài tổng quan giải thích cách sampling/decoding được thực hiện trong kỷ nguyên mạng nơ-ron đầu-cuối. Tôi biết thời HMM thì decoding trong dịch máy và nhận dạng giọng nói được làm như thế nào, ví dụ như https://en.wikipedia.org/wiki/Viterbi_algorithm hay https://en.wikipedia.org/wiki/Beam_search
    Dạo này tôi có cảm giác mọi người chỉ làm theo kiểu “tham lam”, nhưng không chắc lắm. Nếu có tài liệu gợi ý về chủ đề này thì tốt quá

    • Vừa tham lam vừa ngẫu nhiên :) Thay vì bài báo, tôi khuyên nên xem thuật toán trong hầu hết các triển khai LLM. rwkv.cpp có một bản triển khai Python khá gọn gàng: https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • Đọc tài liệu GPT-4 thì có vẻ không khác nhiều so với những thứ đã nhắc đến
      https://platform.openai.com/docs/api-reference/completions/c...
      Tất nhiên, vì giờ ta biết GPT-4 có kiến trúc mixture of experts, nên bên trong nó đang song song hóa việc tính toán. Ngoài ra còn bao gồm cả cách chỉnh sửa logit bằng các hạng mục presence/frequency penalty