Llama: व्याकरण-आधारित sampling जोड़ा गया

 (github.com/ggerganov)
1 पॉइंट द्वारा GN⁺ 2023-07-23 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • llama.cpp PR #1773 एक ऐसी API जोड़ता है जो context-free grammar के जरिए sampling candidates को सीमित करती है, ताकि generated output तय फ़ॉर्मैट से बाहर न जाए
  • API 32-bit code point आधारित grammar data structure लेती है, llama_sample_grammar से candidate tokens को filter करती है, फिर llama_grammar_accept_token से चुने गए token को grammar state में लागू करती है
  • main में --grammar और --grammar-file arguments जोड़े गए हैं, जिनसे extended BNF फ़ॉर्म की grammar input की जा सकती है; उदाहरण के तौर पर Chess, arithmetic expressions, JSON, और Japanese character range generation दिखाए गए हैं
  • tests M2 Max और 30B Q4_0 मॉडल पर किए गए; grammar लागू होने पर output chess notation, arithmetic expressions, JSON, और Japanese character ranges तक सीमित रहा, जबकि grammar के बिना prompt से असंबंधित सामान्य text या code generate हुआ
  • चर्चा में grammar file support, खाली पंक्तियाँ और comments handling, parser को API में शामिल करने या न करने, GPU-based logit masking, fixed token batch processing, और performance overhead जैसी व्यावहारिक उपयोग की सीमाएँ मुख्य रूप से उठाई गईं

PR के मुख्य बदलाव

  • यह llama.cpp में grammar-based sampling जोड़ने वाला PR है
  • पहले के काम के रूप में #1397 और grantslatton का CFG काम संदर्भ के तौर पर लिया गया है
  • नई API serialized context-free grammar लेकर sampling को guide और constrain करती है
  • main में generation grammar तय करने के लिए BNF-जैसे grammar examples जोड़े गए हैं

Grammar API की संरचना

  • llama API 32-bit code points के लिए context-free grammar data structure लेती है
  • grammar element types rule end, alternative start, rule reference, character, character range upper bound, और alternate character addition को व्यक्त करते हैं
  • initialization function यह जानकारी लेती है
    • rule array
    • rules की संख्या
    • start rule index
  • llama_grammar_element में type और value होते हैं, और value Unicode code point या rule ID के रूप में इस्तेमाल होता है

Sampling का तरीका

  • grammar sampling code एक nondeterministic pushdown automaton को model करता है
  • संभावित parsing states दिखाने के लिए N stacks बनाए रखे जाते हैं
  • token sampling दो चरणों में काम करती है
    • llama_sample_grammar candidate tokens में से सिर्फ़ वे candidates छोड़ता है जो किसी parsing stack से मेल खाते हों
    • llama_grammar_accept_token चुने गए token को grammar state में जोड़ता है

main में grammar input फीचर

  • main में --grammar और --grammar-file arguments जोड़े गए हैं
  • दोनों arguments सरल extended BNF grammar लेकर generation results को सीमित करते हैं
  • grammar parser examples/grammar-parser.{h,cpp} में implement किया गया है
  • supported grammar features में character ranges, grouping, और repetition operators शामिल हैं
  • root rule grammar के starting point की पहचान करता है
  • बाद के updates में grammar file support, examples, shell-style comments, rules के बीच खाली पंक्तियाँ, और parenthesized groups के भीतर line breaks की अनुमति जोड़ी गई

Test उदाहरण

  • test environment M2 Max, 30B मॉडल के रूप में दिया गया है
  • Chess उदाहरण
    • --grammar-file grammars/chess.gbnf इस्तेमाल करने पर 1. e4 e5, 2. Nf3 Nc6 जैसी chess notation generate होती है
    • grammar के बिना वही prompt चलाने पर Sir Thomas Gresham से जुड़ा सामान्य वाक्य generate हुआ
  • Arithmetic expression उदाहरण
    • inline grammar से expr "=" ws num "\n" फ़ॉर्म को अनिवार्य किया गया
    • result 10 *a*1 +b*2 =640 जैसी arithmetic expression shape तक सीमित रहा
    • grammar के बिना Go code snippet generate हुआ
  • JSON उदाहरण
    • grammars/json.gbnf इस्तेमाल करने पर { "fullName": ..., "address": ... } जैसी JSON structure generate हुई
    • grammar के बिना self-introduction जैसी गद्य शैली का output बना
  • Japanese उदाहरण
    • grammars/japanese.gbnf hiragana, katakana, punctuation, और CJK ranges को allow करता है
    • grammar लागू होने पर Japanese characters आधारित सूची generate हुई
    • grammar के बिना English step list generate हुई

Review और design चर्चा

  • grammar को file के रूप में लेने का सुझाव आया था, और बाद में grammar file support तथा examples जोड़े गए
  • शुरुआती उपयोग के दौरान --prompt-cache conflict और grammar में खाली पंक्तियों के कारण crash report हुए
  • खाली पंक्तियाँ और comments support, तथा parenthesized groups के भीतर line breaks की अनुमति बाद के commits में शामिल की गई
  • parser को llama.cpp API में शामिल किया जाए या नहीं, इस पर चर्चा हुई
    • अगर parser API के बाहर हो, तो downstream users को feature support के लिए parser कॉपी करना पड़ेगा, ऐसी चिंता जताई गई
    • लेखक ने llama.cpp में बदलाव कम रखने की कोशिश की, लेकिन parser को API में रखना अधिक सुविधाजनक है, इस बात से सहमति जताई
  • यह सुझाव भी आया कि llama_grammar अगर binary grammar की copy अपने पास रखे, तो user को दी गई copy की lifetime बनाए रखने की ज़रूरत न पड़े

Performance और optimization चर्चा

  • अगर अगले N > 1 tokens grammar से uniquely तय हो रहे हों, तब भी अभी उन्हें एक-एक करके sample किया जाता है, ऐसा समझा गया
  • कई fixed tokens को batch evaluation करने से ऐसे मामलों में inference speed काफ़ी बढ़ सकती है, ऐसी चर्चा हुई
  • लेखक ने जवाब दिया कि tokens का evaluation फिर भी करना पड़ता है, और bottleneck evaluation side पर दिखता है; string-level batch evaluation optimization point हो सकता है
  • GPU पर grammar को state-transition tensor में compile करने या पूरे token set के लिए GPU logit masking करने के विचार भी सामने आए
  • torch-grammar का उल्लेख पूरे token set पर GPU में grammar-enforced logit masking करने वाले समान approach के रूप में किया गया

Performance observations

  • लेखक ने बताया कि उन्होंने सिर्फ़ CPU inference आज़माया और उनकी कोशिशों की सीमा में performance impact बहुत बड़ा नहीं था
  • M2 Max पर देखे गए आँकड़े
    • unconstrained sampling लगभग 0.5ms/token
    • grammar-applied sampling लगभग 6ms/token
    • 13B Q4_K का token evaluation लगभग 70ms/token
  • एक अन्य user ने 13B पर लगभग 20T/s से 13T/s तक गिरावट का मामला बताया
  • लेखक ने कहा कि सामान्यतः grammar overhead लगभग 5ms/token दिखता है, लेकिन कुछ grammars में असर बड़ा था और pathological cases संभव हैं

संबंधित विस्तार चर्चा

  • JSON Schema input को BNF में बदलकर इस्तेमाल करने की दिशा का उल्लेख हुआ
  • लेखक ने बताया कि उनके पास एक local branch है जो jsonformer README example के अनुरूप काम करती है, और एक Python script JSON Schema के अनुरूप JSON BNF generate करती है
  • बाद में examples : generate JSON according to schema #1887 का उल्लेख इस PR से जुड़कर हुआ
  • जवाब में कहा गया कि यह approach model modifications से स्वतंत्र है और fine-tuned models के साथ भी इस्तेमाल की जा सकती है
  • whisper.cpp में भी grammar-based sampling जोड़ने वाला एक अलग PR उल्लेखित हुआ

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-07-23
Hacker News टिप्पणियाँ

  • मेरी समझ में यह ऐसे काम करता है। language model, prompt को शुरुआती बिंदु बनाकर एक-एक token आउटपुट करता है, और LLM के साथ बातचीत को भी ऐसे देखा जा सकता है कि user token sequence देता है, model कुछ generate करता है, फिर user आगे जोड़ देता है
    यह grammar तकनीक tokens पर कहीं ज्यादा बारीक control देती है। उदाहरण के लिए, अगर आप Give me the address of the White House as JSON: {"street": " तक दें, तो LLM 1600 Pennsylvania Ave NW" लौटाएगा, और जैसे ही closing quote दिखे, user ", "City": " inject करके Washington, DC" पा सकता है
    लेकिन क्योंकि यह grammar-based है, यह सिर्फ JSON ही नहीं, उससे कहीं ज्यादा काम कर सकता है। पहले Twitter पर देखा एक सुझाव भी अच्छा था: OpenAI अगर deterministic context-free grammar को API argument के रूप में लेने लगे, या उससे भी आगे जाकर sampler ही बने हुए छोटे WASM binary को कुछ KB में लेकर कुछ MB memory में चलाए, तो LLM की क्षमताएं काफी बढ़ सकती हैं
    https://twitter.com/grantslatton/status/1637692033115762688

    • इतना ही नहीं, LLM सीधे individual tokens output नहीं करता, बल्कि weights वाली recommendation list देता है। सबसे plausible token का weight सबसे ज्यादा होता है, लेकिन quotes जैसे JSON symbols सहित कई alternatives हो सकते हैं
      temperature setting यह adjust करती है कि top-ranked न होने वाले tokens चुने जाने की कितनी संभावना हो, जिससे repetitive output कम होता है। LLM को grammar follow करने के लिए force करना आम तौर पर token selection से पहले list को filter करने जैसा है, और फिर भी temperature जिस randomness को control करता है, वह बच सकती है
      और advanced feature के तौर पर, जब AI अटक जाए और valid output न बना सके, तो backtracking allow करने का तरीका भी है
    • असल में यह मौजूदा output और sampling candidates यानी अगले tokens को grammar से check करता है, और जो candidate tokens match नहीं करते उन्हें पूरी तरह हटा देता है। बचे हुए valid tokens की list पर सामान्य sampling strategy apply होती है
    • मुझे नहीं लगता कि यह explanation सही है। पहले भी LLM में tokens को एक-एक करके पढ़ते हुए stop character मिलने पर रोकने के तरीके से output को control किया जा सकता था
      grammar-based sampling PR का core यह है कि llama.cpp grammar का इस्तेमाल करके अगले output token को possible tokens के सीमित set तक narrow कर देता है
    • इसे implement करने की और detailed explanation भी है: https://github.com/normal-computing/outlines/pull/131
      यह Outlines library के एक developer ने लिखा है, और Outlines भी एक अच्छी LLM workflow library है
    • मुझे ठीक से समझ नहीं आ रहा कि बात क्या है। “passing up” से शुरू करके, ऐसा लगता है कि इस व्यक्ति ने terms नए गढ़े हैं। LLM में जो input दिया जा सकता है, वह सिर्फ tokenized prompt है
      request के हिस्से के रूप में DCFG rules या compiled version भेज भी दें, तो यह token prediction के तरीके को fundamentally कैसे बदलता है, समझ नहीं आता। अगर model ऐसी चीज predict करे जो मांगी गई grammar से match नहीं करती, तो क्या मतलब है कि match होने तक prompt फिर से देते रहें?

  • यह बात ध्यान में रखनी चाहिए कि यह model द्वारा generate किए जाने वाले text पर सिर्फ grammatical constraints लगाता है, content alignment सच में ठीक नहीं करता। जब server से well-formatted JSON निकलना guarantee करना हो, तब यह उपयोगी है, लेकिन मौजूदा language generation की कई alignment समस्याएं शायद इससे solve नहीं होंगी
    उदाहरण के लिए, मौजूदा Llama या GPT अक्सर Markdown code block labels गलत लगा देते हैं। grammar-based sampling से label लगाना force किया जा सकता है, लेकिन label सही है या नहीं, यह context-dependent है इसलिए force नहीं किया जा सकता। कोई नया domain-specific language बनाने के बाद, उस language के हिसाब से align किए बिना अच्छे output की उम्मीद करना भी मुश्किल है

    • यह भी अहम है कि free-form string आते ही LLM के लिए पूरी तरह गलत दिशा में भटकने का खुला न्योता बन जाता है। इसलिए ऐसे methods को free text area में आने पर repetition penalty जैसी दूसरी heuristics से sampling को bias करने के तरीकों के साथ इस्तेमाल करना बेहतर है
    • फिर भी Llama हो तो कुछ examples को LoRA में train किया जा सकता है
      उदाहरण के लिए, जरूरत के हिसाब से Markdown के लिए LoRA और Markdown grammar file को hot-swap करने वाला system कल्पना किया जा सकता है

  • यह मुझे वाकई पसंद आया। पहले मैंने Constrained Text Generation Studio बनाया था(https://github.com/Hellisotherpeople/Constrained-Text-Genera...), और इससे जुड़ा paper COLING 2022 में भी छपा था(https://paperswithcode.com/paper/most-language-models-can-be...)
    फिर भी मुझे हमेशा लगा कि ऐसे तरीके या इस paper में listed related ideas ही आगे का रास्ता हैं: https://arxiv.org/abs/2306.03081
    अब सोचना होगा कि syllable count या syntactic rules जैसी चीजें enforce करने वाली grammar कैसे बनाई जा सकती है। मौजूदा LLM tokenization की वजह से इस तरह के tasks में बहुत खराब हैं

    • हैरानी की बात थी, लेकिन Nous Hermes haiku काफी ठीक-ठाक लिखता है

  • PyTorch के लिए भी इसे implement किया है: https://github.com/Shopify/torch-grammar. इसे इस्तेमाल करने वाला text-generation-inference का hacked version भी है, जरूरत हो तो share कर सकता हूं

    • share करें तो अच्छा होगा। मैं किसी LLM UI में token probability vector dump करने की कोशिश कर रहा था, अगर कोई दूसरा starting point हो तो काफी मदद मिलेगी

  • multiple-choice string enums, यानी असल में dropdown जैसे cases में, final choice करते समय greedy algorithm के बजाय logits दिए हुए state की पूरी joint probability consider करने पर क्या यह बेहतर काम करेगा, यह सोच रहा हूं
    जब starting token list के कई items में shared हो, तो सबसे common starting token वाली choice के बजाय सही choice को prefer किया जा सकता है। बेशक, logits के कुछ हिस्से 0 हो जाने के बाद probabilities adjust करनी होंगी, तभी यह सच में meaningful होगा

  • इस grammar “library” को format example के तौर पर quote किया गया था: https://github.com/antlr/grammars-v4
    इसमें assembly और C++ से लेकर GLSL, scripting languages, arithmetic, games, freedesktop shortcuts, LLVM IR, Verilog जैसे असामान्य formats तक सब कुछ है

    • Inference API में HTML, JSON, Python जैसी standard grammar shortcuts specify कर पाना सुविधाजनक होगा। OpenAI ने Code Interpreter model को fine-tune करने में जितनी मेहनत लगाई है, उसे देखते हुए सच कहें तो अजीब है कि उन्होंने अब तक ऐसा नहीं किया
    • ANTLR4 grammar syntax support हो तो वाकई अच्छा होगा। यह शानदार tool है

  • क्या कोई आसान भाषा में समझा सकता है? LLMs के बारे में कुछ हद तक पता है, लेकिन Georgi यहां क्या कर रहे हैं और कुछ लोग इसे लेकर इतने excited क्यों हैं, यह ठीक से समझ नहीं आ रहा

    • LLM सीधे “next token” generate नहीं करता। Input text से वह एक probability vector बनाता है, जिसमें हर slot एक token से correspond करता है, और हर value को मोटे तौर पर उस token के next आने की probability समझ सकते हैं
      ChatGPT जैसे programs उस probability vector को “interpret” करके top tokens में से एक चुनते हैं, यानी sample करके text बनाते हैं। लेकिन यह तरीका कभी-कभी बहुत flexible होता है, इसलिए JSON output चाहने पर भी JSON grammar से मेल न खाने वाला token चुनकर गलत JSON बना सकता है
      LLM को JSON जैसी चीज़ generate करने के लिए “force” करने का तरीका sampling process को बदलना है। कोई भी top token चुनने के बजाय, पहले केवल वे tokens बचाए जाते हैं जो JSON grammar से मेल खाते हैं, फिर उसी subset से top token sample किया जाता है
    • LLM से JSON या grammar वाली कोई दूसरी language generate करवाएं तो वह कभी-कभी गलत syntax बना देता है। यह PR user-provided grammar के अनुसार LLM को सिर्फ valid syntax output करने तक सीमित करता है, और इसके लिए sampling procedure बदली गई है
      LLM text को token-by-token generate करता है। पहले एक विशाल neural network सभी possible tokens को probabilities assign करता है, फिर sampling procedure उन probabilities का इस्तेमाल करके एक token चुनता है, और यह process repeat होती है
      Sampling procedure neural network नहीं है, इसलिए इसे कई तरीकों से बदला जा सकता है। हमेशा highest probability वाला token चुनने वाली greedy sampling भी possible है, लेकिन आमतौर पर probability-weighted random selection बेहतर होती है। इससे diversity आती है और loop में फंसने की संभावना भी घटती है। लेकिन non-zero probability वाला कोई भी token चुना जा सकता है, इसलिए गलत JSON आ सकता है। यह PR grammar के हिसाब से invalid सभी tokens की probability 0 कर देता है ताकि वे चुने न जा सकें
      Sampling process में और भी दिलचस्प modifications संभव हैं। Token एक-एक करके sample करते हुए dead end में जा सकते हैं जहां कोई विकल्प न बचे, इसलिए backtracking allow की जा सकती है। आगे बढ़कर, हर step पर कई choices consider करके possible outputs का tree बनाया जा सकता है, और अंत में highest overall probability वाला path चुना जा सकता है। सभी choices consider करने पर possible tokens की संख्या जितनी branching वाला full tree बनेगा, इसलिए यह exponentially बढ़ेगा; इसलिए हर step पर top, मान लें, 5 paths ही रखकर pruning की जा सकती है। यही beam search है। Probability generate करने वाले neural network को run करने की cost बहुत ज्यादा होती है, इसलिए cost 5 गुना बढ़ना भारी पड़ता है; इसी वजह से LLMs में आमतौर पर इसका इस्तेमाल नहीं होता, लेकिन यह संभव है और results भी कुछ हद तक बेहतर होते हैं। Chess engines की तरह Monte Carlo tree search इस्तेमाल करने के बारे में भी सोचा जा सकता है
    • LLM खुशी-खुशी कोई भी arbitrary string generate कर देगा। आप “Alice: 42” जैसा कुछ चाहते थे, लेकिन वह “नमस्ते, मैं एक helpful model हूं और मेरे हिसाब से Alice बिल्कुल forty two है, लेकिन मैं सिर्फ एक language model हूं” जैसा output दे सकता है
      इसलिए response के लिए ऐसी grammar दी जाती है कि पहले एक uppercase letter आए, फिर lowercase letters, colon, space, digits और फिर end हो। तब पहला token खोजते समय केवल उसी pattern से compatible tokens consider होंगे, और बाद में भी अगले pattern से compatible tokens ही आगे consider होंगे
      ऐसी grammar इस काम को flexible और useful pattern में बदल देती है
    • मेरा यह comment देख सकते हैं: https://news.ycombinator.com/item?id=36820884

  • यह दिलचस्प है, इसलिए मैं इसे अपने काम में शामिल करने की कोशिश करूंगा। हालांकि Bitter Lesson के नजरिए से लगता है कि बहुत short term को छोड़कर यह शायद best approach न हो: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • यह workaround हो सकता है, लेकिन महत्वपूर्ण workaround है। अगले कुछ वर्षों में LLMs constrained text generation problems को “naturally” solve कर पाएंगे या नहीं, यह साफ नहीं है
    • मैं बिल्कुल expert नहीं हूं, लेकिन मेरी जानकारी में OpenAI programming के लिए कुछ GPT APIs में ऐसा तरीका इस्तेमाल करता है। मैंने यह अनुमान भी देखा है कि simple grammar handling को उसके लिए बने simple process को सौंप देने से LLM complex कामों पर compute resources ज्यादा effectively इस्तेमाल कर सकता है। सच है या नहीं, पता नहीं

  • इसी तरह का तरीका इस्तेमाल करने वाला एक project भी है: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • end-to-end neural network के दौर में sampling/decoding कैसे की जाती है, इसे समझाने वाले paper या overview की सिफारिश चाहिए। HMM के समय machine translation और speech recognition में decoding कैसे होती थी, यह पता है, जैसे https://en.wikipedia.org/wiki/Viterbi_algorithm या https://en.wikipedia.org/wiki/Beam_search जैसी चीजें।
    आजकल ऐसा impression मिलता है कि लोग बस “greedy” तरीके से करते हैं, लेकिन पक्का नहीं है। इस topic पर कोई material recommend कर सके तो अच्छा होगा

    • greedy भी और random भी :) papers के बजाय ज़्यादातर LLM implementations के algorithms देखने की सलाह दूंगा। rwkv.cpp में अपेक्षाकृत साफ़ Python implementation है: https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • GPT-4 docs पढ़कर देखें तो आपने जिन चीज़ों का ज़िक्र किया है उनसे बहुत बड़ा फर्क नहीं लगता
      https://platform.openai.com/docs/api-reference/completions/c...
      बेशक अब हमें पता है कि GPT-4 में mixture of experts architecture है, इसलिए अंदरूनी तौर पर computation को parallelize किया जा रहा है। इसमें presence/frequency penalty terms के जरिए logits को modify करने का तरीका भी शामिल है