Llama: Menambahkan Sampling Berbasis Grammar

 (github.com/ggerganov)
1 poin oleh GN⁺ 2023-07-23 | 1 komentar | Bagikan ke WhatsApp
  • PR llama.cpp #1773 mengusulkan fitur yang menambahkan API untuk membatasi kandidat sampling dengan context-free grammar, agar hasil generasi tidak keluar dari format yang ditentukan
  • API menerima struktur data grammar berbasis code point 32-bit, memfilter token kandidat dengan llama_sample_grammar, lalu merefleksikan token terpilih ke status grammar dengan llama_grammar_accept_token
  • Pada main, argumen --grammar dan --grammar-file ditambahkan agar grammar berbentuk extended BNF dapat dimasukkan; contoh yang diberikan mencakup Chess, ekspresi aritmetika, JSON, dan generasi rentang karakter Jepang
  • Pengujian dilakukan pada M2 Max dan model 30B Q4_0; saat grammar diterapkan, output dibatasi agar sesuai dengan notasi catur, ekspresi aritmetika, JSON, dan rentang karakter Jepang, sedangkan tanpa grammar, teks umum atau kode yang berbeda dari prompt dihasilkan
  • Diskusi berfokus pada kendala penggunaan nyata seperti dukungan file grammar, penanganan baris kosong dan komentar, apakah parser harus disertakan dalam API, masking logit berbasis GPU, pemrosesan batch untuk token tetap, dan overhead performa

Perubahan inti PR

  • Ini adalah PR yang menambahkan sampling berbasis grammar ke llama.cpp
  • Sebagai pekerjaan sebelumnya, PR ini merujuk ke #1397 dan pekerjaan CFG dari grantslatton
  • API baru menerima context-free grammar yang diserialisasi untuk memandu dan membatasi sampling
  • Pada main, contoh grammar mirip BNF untuk menentukan grammar generasi ditambahkan

Struktur Grammar API

  • API llama menerima struktur data context-free grammar untuk code point 32-bit
  • Tipe elemen grammar merepresentasikan akhir aturan, awal alternatif, referensi aturan, karakter, batas atas rentang karakter, dan penambahan karakter alternatif
  • Fungsi inisialisasi menerima informasi berikut
    • Array aturan
    • Jumlah aturan
    • Indeks aturan awal
  • llama_grammar_element memiliki type dan value, dengan value digunakan sebagai code point Unicode atau ID aturan

Cara sampling

  • Kode sampling grammar memodelkan nondeterministic pushdown automaton
  • Untuk merepresentasikan status parsing yang memungkinkan, N stack dipertahankan
  • Sampling token bekerja dalam dua tahap
    • llama_sample_grammar hanya menyisakan kandidat token yang cocok dengan salah satu stack parsing
    • llama_grammar_accept_token menambahkan token yang dipilih ke status grammar

Fitur input grammar di main

  • Argumen --grammar dan --grammar-file ditambahkan ke main
  • Kedua argumen menerima grammar extended BNF sederhana untuk membatasi hasil generasi
  • Parser grammar diimplementasikan di examples/grammar-parser.{h,cpp}
  • Fitur grammar yang didukung mencakup rentang karakter, pengelompokan, dan operator pengulangan
  • Aturan root mengidentifikasi titik awal grammar
  • Dalam pembaruan berikutnya, ditambahkan dukungan file grammar, penambahan contoh, komentar bergaya shell, baris kosong di antara aturan, dan izin newline di dalam grup tanda kurung

Contoh pengujian

  • Lingkungan pengujian disajikan sebagai model M2 Max, 30B
  • Contoh Chess
    • Jika menggunakan --grammar-file grammars/chess.gbnf, format notasi catur seperti 1. e4 e5 dan 2. Nf3 Nc6 dihasilkan
    • Jika prompt yang sama dijalankan tanpa grammar, kalimat umum terkait Sir Thomas Gresham dihasilkan
  • Contoh ekspresi aritmetika
    • Grammar inline memaksa bentuk seperti expr "=" ws num "\n"
    • Hasil dibatasi ke bentuk ekspresi aritmetika seperti 10 *a*1 +b*2 =640
    • Tanpa grammar, potongan kode Go dihasilkan
  • Contoh JSON
    • Jika menggunakan grammars/json.gbnf, struktur JSON berbentuk { "fullName": ..., "address": ... } dihasilkan
    • Tanpa grammar, prosa gaya perkenalan diri dihasilkan
  • Contoh bahasa Jepang
    • grammars/japanese.gbnf mengizinkan hiragana, katakana, tanda baca, dan rentang CJK
    • Saat grammar diterapkan, daftar berbasis karakter Jepang dihasilkan
    • Jika dijalankan tanpa grammar, daftar langkah berbahasa Inggris dihasilkan

Review dan diskusi desain

  • Ada usulan agar grammar diterima sebagai file, lalu dukungan grammar file dan contoh ditambahkan setelahnya
  • Masalah yang ditemukan pada penggunaan awal mencakup konflik --prompt-cache dan crash akibat baris kosong di dalam grammar
  • Dukungan baris kosong dan komentar, serta izin newline di dalam grup tanda kurung, dimasukkan dalam commit lanjutan
  • Ada diskusi tentang apakah parser perlu dimasukkan ke API llama.cpp
    • Jika parser berada di luar API, muncul kekhawatiran bahwa pengguna downstream harus menyalin parser untuk mendukung fitur ini
    • Penulis mencoba meminimalkan perubahan pada llama.cpp itu sendiri, tetapi setuju bahwa memasukkan parser ke API akan lebih praktis
  • Ada usulan bahwa jika llama_grammar menyimpan salinan grammar biner, pengguna tidak perlu mempertahankan masa hidup salinan yang mereka berikan

Diskusi performa dan optimisasi

  • Saat N > 1 token berikutnya ditentukan secara unik oleh grammar, pendekatan saat ini dipahami masih melakukan sampling satu per satu
  • Ada diskusi bahwa melakukan evaluasi batch terhadap beberapa token tetap dapat sangat meningkatkan kecepatan inferensi pada kasus seperti ini
  • Penulis menjawab bahwa token harus dievaluasi dan bottleneck tampaknya berada di sisi evaluasi, serta menilai evaluasi batch pada level string bisa menjadi titik optimisasi
  • Ide lain yang diajukan mencakup mengompilasi grammar menjadi tensor transisi status di GPU atau melakukan masking logit GPU untuk seluruh himpunan token
  • torch-grammar disebut sebagai pendekatan serupa yang melakukan masking logit pemaksaan grammar di GPU terhadap seluruh himpunan token

Observasi performa

  • Penulis menyatakan hanya mencoba inferensi CPU, dan dalam cakupan yang ia coba, dampak performanya tidak besar
  • Angka yang diamati pada M2 Max
    • Sampling tanpa batasan sekitar 0,5ms/token
    • Sampling dengan grammar sekitar 6ms/token
    • Evaluasi token 13B Q4_K sekitar 70ms/token
  • Pengguna lain melaporkan kasus pada 13B yang turun dari sekitar 20T/s menjadi 13T/s
  • Penulis umumnya melihat overhead grammar sekitar 5ms/token, tetapi pada grammar tertentu dampaknya lebih besar dan mungkin ada kasus patologis

Diskusi ekstensi terkait

  • Disebutkan arah penggunaan input JSON Schema dengan mengubahnya menjadi BNF
  • Penulis menyatakan memiliki branch lokal yang bekerja sesuai contoh README jsonformer, dan menghasilkan JSON BNF yang sesuai dengan JSON Schema menggunakan skrip Python
  • Setelahnya, examples : generate JSON according to schema #1887 disebutkan terhubung dengan PR ini
  • Pendekatan ini dijawab sebagai independen dari varian model dan dapat digunakan bersama model fine-tune
  • PR terpisah yang menambahkan sampling berbasis grammar ke whisper.cpp juga disebutkan

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-23
Komentar Hacker News

  • Cara kerjanya yang saya pahami seperti ini. Model bahasa mengeluarkan token satu per satu dengan prompt sebagai titik awal, dan percakapan dengan LLM juga bisa dilihat sebagai pengguna memberi urutan token, lalu model menghasilkan sebagian, kemudian pengguna menyambungnya lagi.
    Teknik grammar ini memungkinkan kontrol token yang jauh lebih rinci. Misalnya jika kita memberi Give me the address of the White House as JSON: {"street": ", LLM akan mengembalikan 1600 Pennsylvania Ave NW", dan begitu melihat tanda kutip penutup, pengguna bisa menyuntikkan ", "City": " untuk mendapatkan Washington, DC".
    Namun karena ini berbasis grammar, yang bisa dilakukan bukan hanya JSON, melainkan jauh lebih banyak. Ada usulan bagus yang dulu saya lihat di Twitter, isinya bahwa OpenAI seharusnya menerima deterministic context-free grammar sebagai argumen API, atau lebih jauh lagi menerima biner WASM kecil yang menjadi sampler itu sendiri, ukurannya beberapa KB dan dijalankan dengan memori beberapa MB, sehingga kemampuan LLM bisa diperluas secara signifikan.
    https://twitter.com/grantslatton/status/1637692033115762688

    • Selain itu, LLM tidak langsung mengeluarkan token individual, melainkan menghasilkan daftar rekomendasi berbobot. Token yang paling masuk akal memiliki bobot tertinggi, tetapi bisa ada beberapa alternatif, termasuk simbol JSON seperti tanda kutip.
      Pengaturan temperature menyesuaikan kemungkinan dipilihnya token yang bukan peringkat teratas agar keluaran tidak terlalu berulang. Memaksa LLM mengikuti grammar pada dasarnya adalah memfilter daftar itu sebelum token dipilih, dan tetap bisa menyisakan unsur acak yang dikendalikan oleh temperature.
      Fitur yang lebih canggih adalah mengizinkan backtracking ketika AI buntu dan tidak bisa menghasilkan output yang valid.
    • Implementasi nyatanya adalah memeriksa keluaran saat ini dan token berikutnya yang menjadi kandidat sampling dengan grammar, lalu membuang semua token kandidat yang tidak cocok. Setelah itu, strategi sampling biasa diterapkan pada daftar token valid yang tersisa.
    • Penjelasan ini tampaknya kurang tepat. Sebelumnya pun keluaran LLM bisa dikendalikan dengan membaca token satu per satu lalu berhenti saat menemukan karakter penghenti.
      Menurut saya inti dari PR grammar-based sampling adalah bahwa llama.cpp menggunakan grammar untuk mempersempit token keluaran berikutnya menjadi himpunan terbatas dari token yang memungkinkan.
    • Ada penjelasan yang lebih rinci tentang implementasinya di sini: https://github.com/normal-computing/outlines/pull/131
      Ditulis oleh salah satu pengembang library Outlines, dan Outlines juga merupakan library workflow LLM yang cukup bagus.
    • Saya kurang paham apa yang dibicarakan. Mulai dari “passing up”, rasanya seperti orang ini menciptakan istilah sendiri. Masukan yang bisa diberikan ke LLM hanyalah prompt yang akan ditokenisasi.
      Kalaupun aturan DCFG atau versi terkompilasinya dikirim sebagai bagian dari request, saya tidak mengerti bagaimana itu secara mendasar mengubah cara prediksi token model. Kalau model memprediksi sesuatu yang tidak sesuai grammar yang diminta, apakah maksudnya prompt dikirim ulang sampai cocok?

  • Perlu ditekankan bahwa ini hanya memberi kendala gramatikal pada teks yang dihasilkan model, bukan benar-benar menyelaraskan isinya. Ini berguna ketika server harus dijamin mengeluarkan JSON yang terformat dengan baik, tetapi sepertinya tidak akan menyelesaikan banyak masalah alignment dalam generasi bahasa saat ini.
    Misalnya, Llama atau GPT saat ini sering salah memberi label pada blok kode Markdown. Dengan grammar-based sampling kita bisa memaksa adanya label, tetapi tidak bisa memaksa label itu benar, karena itu bergantung pada konteks. Sulit juga berharap output yang bagus setelah membuat bahasa khusus domain baru tanpa lebih dulu melakukan alignment terhadap bahasa tersebut.

    • Penting juga bahwa ketika string bentuk bebas muncul, itu menjadi undangan terbuka bagi LLM untuk melenceng total ke arah yang aneh. Karena itu, metode seperti ini sebaiknya dipakai bersama heuristik lain seperti repetition penalty untuk membiaskan sampling saat masuk ke area teks bebas.
    • Meski begitu, untuk Llama beberapa contoh bisa dilatih ke dalam LoRA.
      Misalnya bisa dibayangkan sistem yang melakukan hot-swap antara LoRA untuk Markdown dan file grammar Markdown sesuai kebutuhan.

  • Saya sangat suka ini. Dulu saya pernah membuat Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Genera...), dan bahkan sempat terbit di COLING 2022 lewat paper terkait (https://paperswithcode.com/paper/most-language-models-can-be...).
    Saya selalu berpikir pendekatan seperti ini, atau ide-ide terkait yang dicantumkan di paper ini, adalah arah yang tepat: https://arxiv.org/abs/2306.03081
    Sekarang saya jadi ingin memikirkan bagaimana membuat grammar yang bisa memaksakan hal-hal seperti jumlah suku kata atau aturan sintaksis. LLM saat ini sangat buruk dalam tugas seperti itu karena cara tokenisasinya.

    • Cukup mengejutkan, tetapi Nous Hermes menulis haiku dengan lumayan meyakinkan.

  • Saya juga sudah mengimplementasikan ini untuk PyTorch: https://github.com/Shopify/torch-grammar. Saya juga punya versi hack dari text-generation-inference yang memakai ini, dan bisa saya bagikan kalau diperlukan.

    • Akan sangat membantu kalau bisa dibagikan. Saya sempat mencoba membuang vektor probabilitas token dari salah satu UI LLM, jadi kalau ada titik awal lain itu akan sangat berguna.

  • Untuk enumerasi string pilihan ganda, pada dasarnya seperti dropdown, saya penasaran apakah hasilnya akan lebih baik jika pada saat memilih hasil akhir kita mempertimbangkan probabilitas gabungan total di bawah logit yang diberikan, bukan algoritme greedy.
    Jika token awal dibagi bersama oleh beberapa item dalam daftar, pendekatan itu mungkin bisa lebih mengutamakan pilihan yang benar daripada pilihan yang hanya mengandung token awal yang paling umum. Tentu saja setelah sebagian logit menjadi 0, probabilitasnya harus disesuaikan agar benar-benar masuk akal.

  • “Perpustakaan” tata bahasa ini disebut sebagai contoh format: https://github.com/antlr/grammars-v4
    Di sana ada semuanya, mulai dari assembly dan C++ hingga GLSL, bahasa skrip, aritmetika, game, shortcut freedesktop, LLVM IR, Verilog, dan bahkan format-format unik lainnya

    • Akan praktis jika API inferensi bisa menentukan shortcut tata bahasa standar seperti HTML, JSON, atau Python. Mengingat upaya yang OpenAI curahkan untuk melakukan fine-tuning pada model Code Interpreter, jujur agak aneh mereka belum melakukan hal seperti ini
    • Akan sangat bagus jika mendukung sintaks tata bahasa ANTLR4. Itu alat yang hebat

  • Bisa jelaskan dengan sederhana? Saya lumayan paham LLM, tapi masih belum benar-benar menangkap apa yang Georgi lakukan di sini dan kenapa sebagian orang begitu antusias

    • LLM tidak langsung menghasilkan “token berikutnya”. Ia membuat vektor probabilitas yang memetakan setiap slot ke token dari teks masukan, dan tiap nilainya bisa dianggap mendekati probabilitas token itu muncul berikutnya
      Program seperti ChatGPT kemudian “menafsirkan” vektor probabilitas itu dan memilih salah satu token teratas, yaitu melakukan sampling, untuk membuat teks. Namun cara ini kadang terlalu fleksibel, sehingga meski Anda menginginkan keluaran JSON, model bisa memilih token yang tidak sesuai tata bahasa JSON dan menghasilkan JSON yang salah
      Cara “memaksa” LLM menghasilkan sesuatu seperti JSON adalah dengan mengubah proses sampling. Alih-alih memilih sembarang token teratas, kita terlebih dahulu menyisakan hanya token yang sesuai dengan tata bahasa JSON, lalu melakukan sampling token teratas dari subset itu
    • Jika Anda meminta LLM menghasilkan JSON atau bahasa lain yang punya tata bahasa, kadang ia membuat sintaks yang salah. PR ini membatasi LLM agar hanya mengeluarkan sintaks yang valid sesuai tata bahasa yang diberikan pengguna, dengan memodifikasi prosedur sampling
      LLM menghasilkan teks per token. Pertama, jaringan saraf besar menetapkan probabilitas untuk semua token yang mungkin, lalu prosedur sampling menggunakan probabilitas itu untuk memilih satu token dan mengulangi proses ini
      Prosedur sampling bukan jaringan saraf, jadi bisa diubah dengan berbagai cara. Anda bisa melakukan greedy sampling yang selalu memilih token dengan probabilitas tertinggi, tetapi biasanya pilihan acak yang dibobot menurut probabilitas lebih baik. Ini memberi keragaman dan mengurangi kemungkinan terjebak dalam loop. Namun, token apa pun yang punya probabilitas bukan nol tetap bisa terpilih, sehingga JSON yang salah bisa muncul. PR ini membuat probabilitas semua token yang tidak valid secara tata bahasa menjadi 0 agar tidak bisa dipilih
      Ada juga modifikasi menarik lain pada proses sampling. Saat mengambil sampel token satu per satu, Anda bisa masuk ke jalan buntu dan kehabisan pilihan, jadi Anda bisa mengizinkan backtracking. Lebih jauh lagi, Anda bisa mempertimbangkan beberapa pilihan di setiap langkah untuk membentuk pohon keluaran yang mungkin, lalu pada akhirnya memilih jalur dengan probabilitas total tertinggi. Jika semua pilihan dipertimbangkan, hasilnya adalah pohon penuh yang bercabang sebanyak jumlah token yang mungkin dan membesar secara eksponensial, jadi Anda bisa memangkasnya dengan hanya menyisakan misalnya 5 jalur teratas di setiap langkah. Inilah beam search. Ini biasanya tidak dipakai pada LLM karena biaya menjalankan jaringan saraf pembangkit probabilitas sangat mahal, sehingga kenaikan biaya 5 kali lipat terasa memberatkan, tetapi tetap mungkin dilakukan dan hasilnya juga cukup membaik. Bisa juga dibayangkan menggunakan Monte Carlo tree search seperti pada engine catur
    • LLM dengan senang hati akan menghasilkan string sembarang. Anda mungkin menginginkan sesuatu seperti “Alice: 42”, tetapi ia bisa saja mengeluarkan “Halo, saya model yang membantu dan menurut saya Alice tepatnya adalah forty two, tetapi saya hanyalah model bahasa”
      Jadi Anda memberinya tata bahasa bahwa respons harus diawali satu huruf kapital diikuti huruf-huruf kecil, titik dua, spasi, lalu angka-angka, dan berakhir di sana. Lalu ketika mencari token pertama, hanya token yang kompatibel dengan pola itu yang dipertimbangkan, dan setelah itu juga hanya token yang cocok dengan pola berikutnya yang terus dipertimbangkan
      Tata bahasa seperti ini membuat pekerjaan itu menjadi pola yang fleksibel dan berguna
    • Lihat komentar saya di sini: https://news.ycombinator.com/item?id=36820884

  • Ini menarik, jadi saya ingin mencoba memasukkannya ke pekerjaan saya. Hanya saja, dari sudut pandang Bitter Lesson, rasanya ini mungkin bukan pendekatan terbaik kecuali untuk jangka yang sangat pendek: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • Mungkin ini solusi sementara, tetapi solusi sementara yang penting. Belum jelas apakah dalam beberapa tahun ke depan LLM akan “secara alami” menyelesaikan masalah pembuatan teks dengan kendala seperti ini
    • Saya sama sekali bukan ahli, tetapi setahu saya OpenAI menggunakan pendekatan seperti ini pada beberapa GPT API untuk pemrograman. Saya juga pernah melihat dugaan bahwa jika penanganan tata bahasa sederhana diserahkan ke proses sederhana yang memang cocok untuk itu, LLM bisa memakai sumber daya komputasi dengan lebih efektif untuk hal-hal yang kompleks. Saya tidak tahu apakah itu benar

  • Ada juga proyek yang memakai metode serupa: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • Ingin mendapat rekomendasi makalah atau ikhtisar yang menjelaskan bagaimana sampling/decoding dilakukan di era jaringan saraf end-to-end. Saya tahu bagaimana decoding dilakukan pada penerjemahan mesin dan pengenalan suara di era HMM, misalnya hal-hal seperti https://en.wikipedia.org/wiki/Viterbi_algorithm atau https://en.wikipedia.org/wiki/Beam_search
    Belakangan ini saya mendapat kesan bahwa orang-orang melakukannya dengan cara “greedy”, tetapi saya tidak begitu yakin. Akan bagus jika ada rekomendasi materi tentang topik ini