Büyük Dil Modelleri için Verimli Kılavuzlu Oluşturma: Yinelemeli FSM İşleme ve Dizin Oluşturma

Bağlantı Tablosu

• Özet ve Giriş
• LLM Örnekleme ve Kılavuzlu Üretim
• Yinelemeli FSM İşleme ve İndeksleme
• Yinelemeli Ayrıştırma Uzantıları
• Tartışma, Referanslar ve Teşekkür

3. Yinelemeli FSM İşleme ve İndeksleme

Daha kesin olmak gerekirse, 5'li sonlu otomat formundaki düzenli ifadeleri ele alıyoruz [Sipser, 1996, Tanım 1.5]:

Tanım 1 (Sonlu Otomat). Sonlu bir otomat veya sonlu durum makinesi (Q, Σ, δ, q0, F) ile verilir; burada Q, sonlu bir durumlar kümesidir, Σ sonlu bir alfabedir, δ : Q × Σ → Q geçiş fonksiyonudur, q0 ∈ Q başlangıç durumu ve F ⊆ Q kabul durumları kümesidir.

V'deki dizileri oluşturan karakterler Σ'dan alınmıştır: yani V ⊂ P(Σ). Baştan sona FSM durumları, Q, basitlik açısından tam sayı değerleri ile temsil edilecektir.

Örnek 1. Kayan nokta sayıları oluşturmak için kullanılabilen ([0-9]*)?\.?[0-9]* normal ifadesi için FSM örnekleme işlemini Şekil 1'de gösteriyoruz. Basit olması açısından, V kelime dağarcığının yalnızca "A", ".", "42", ".2" ve "1" dizelerinden oluşmasına izin verin.

Oluşturma başladığında FSM 0 durumundadır, dolayısıyla algoritmamız FSM tarafından kabul edilmeyeceği için "A" dizesini maskeler. Bu durumda yalnızca ".", "42", ".2" ve "1" örnekleyebiliriz.

".2"yi örneklendirirsek FSM'yi 3. duruma ilerletiriz. Bu durumda yalnızca "42" ve "1" geçerli tamamlamalardır, dolayısıyla örneklemeden önce diğer değerleri maskeleriz. Bunun yerine "1"i örneklendirirsek FSM'yi durum 1'e ilerletiriz; bu durumda ".", ".42", ".2" ve "1" geçerli tamamlamalardır ve maske değişmeden kalır.

Geçerli bir sonraki tokenleri belirlemek için kelime dağarcığını dolaşmak hala en büyük sorundur. Bunun için düzenli ifadenin FSM'sini kullanarak kelimeleri önceden işliyoruz ve bir dizin oluşturuyoruz. Önemli olan, her geçerli FSM durumundan başlamayı düşünmemizdir, çünkü sözlükteki dizeler, düzenli bir ifadenin rastgele bölümleriyle eşleşebilir ve bu bölümler, dolaylı olarak FSM durumlarıdır.

Algoritma 3'te, FSM'deki herhangi bir noktada başlayan eşleşmeler üretmeye yönelik bir prosedür verilmiştir. Sonuç, sağlanan diziyi kabul ederken FSM'nin geçeceği durumları detaylandıran bir alt dizi listesidir.

Bu alt dizilerin başlangıç durumlarını Algoritma 2'deki döngünün tek bir adımında ulaşılan son FSM durumuyla eşleştirerek, FSM durumlarını birbirine bağlayan σ : Q → P(V) haritasıyla kelime dağarcığını verimli bir şekilde indeksleyebiliriz. ve bu eyaletlerde FSM tarafından kabul edilecek kelime dağarcığı unsurları.

Algoritma 4 σ'nun yapısını açıklar.

σ için bir karma haritası kullanmak, Algoritma 2'deki m adımının ortalama olarak yalnızca O(1) maliyetli olmasını sağlayabilir. Ayrıca, σ simge örnekleme prosedürünün dışında oluşturulduğu için, çalışma zamanı maliyeti fiilen önemsizdir, ancak teorik olarak FSM'deki durum sayısına eşit bellek gerektirir (yani |Q|). Neyse ki, düzenli ifadelerin ve sözlüklerin patolojik olmayan kombinasyonları için, sözlükteki her dize FSM tarafından kabul edilmeyecek ve her FSM durumu V'deki bir dizeyle temsil edilmeyecektir.

3.1 Örnekler

Bu bölümde, düzenli ifade yönlendirmeli oluşturmanın pratikte nasıl çalıştığını göstermek için GPT2 ortamını (355M parametreleri) kullanıyoruz. Bunları oluşturmak için Outlines kütüphanesini kullanıyoruz:

Listeleme 3.1 – devamı

Listeleme 3.3 – devamı

3.2 Mevcut yöntemlerle karşılaştırma

Burada açıklanan ve Outlines'ta uygulanan indeksleme yaklaşımının verimliliğini göstermek için Rehberlik kitaplığıyla basit bir karşılaştırma yapıyoruz. Bu yazının yazıldığı an itibarıyla Rehberlik kütüphanesi, her seferinde örneklenen dizinin başlangıcından itibaren uygulanan kısmi düzenli ifade eşleştirmesini kullanıyor ve her adımda LLM'nin kelime dağarcığını (N = 50, 257) tekrarlamak zorunda.

Bu karşılaştırma için kullanılan Rehberlik kodu ve bilgi istemi aşağıdaki gibidir:

Listeleme 3.4 – devamı

İlgili Outlines kodu aşağıdaki gibidir:

Liste 3.5 – devamı

max_tokens'ın değeri değişir ve zamanlamalar, tek bir döngü ve tek tekrar değeri için timeit ile kaydedilir (yani, max_tokens'ın her değeri için yalnızca bir örnek toplanır). Sonuçlar Bölüm 3.2'de gösterilmektedir.

Büyük bir çalışma zamanı farklılığı yaratabilecek herhangi bir yapılandırma gözetimi dışında, örneklenen maksimum token sayısında gözlemlenen ölçeklendirme dikkat çekicidir ve yaklaşımın ima ettiği büyüyen hesaplama sorununun göstergesidir.