Schema-kısıtlı decoding

Prompt mühendisliği ile yapı istemek, modele bir öneri sunar: "şu formatta cevap ver." Model bunu çoğu zaman dikkate alır, ama bir garanti yoktur. Tek bir kapanmamış parantez, bir fazladan virgül, bir kaçak açıklama cümlesi çıktıyı ayrıştırılamaz (unparseable) hale getirir. OpenAI bunu açıkça ayırır: ham JSON mode sözdizimsel JSON üretebilir, ama yapıyı bir şemaya göre kısıtlamak (Structured Outputs, strict: true) ayrı bir decoding-zamanı güvencesidir.

Constrained decoding öneriyi kurala çevirir. Modelin ürettiği logit vektörüne bir maske uygulanır: dilbilgisine göre o an gelemeyecek her token eksi sonsuz skor alır, yani softmax sonrası olasılığı tam olarak sıfır olur. Model isterse o token'a yüksek logit versin, fark etmez; örnekleme onu asla seçemez.

Aşağıda aynı adım iki kez gösteriliyor. Solda serbest decoding ara sıra geçersiz bir token seçer ve yapı kırılır. Sağda aynı logit'ler bir maskeden geçer: geçersiz seçenekler söner, yalnızca dilbilgisine uyanlar yanar.

Maskeyi üreten şey bir kısıt durumudur: o ana kadar üretilmiş kısmi çıktının dilbilgisinde nerede durduğunu bilen bir bellek. Her token üretildikten sonra bu durum ilerletilir, ve bir sonraki adımda hangi token'ların geçerli olduğu bu duruma bakılarak hesaplanır.

En basit hali bir finite-state machine (FSM, sonlu durum makinesi): sınırlı sayıda durum ve durumlar arası geçişler. Çıktıya bir karakter eklendikçe makine bir durumdan diğerine yürür. Bir durumda yalnızca belirli geçişler tanımlıdır; tanımsız geçişe götüren her token maskelenir. Outlines tam olarak bunu yapar ve regex kısıtlarını FSM'e çevirir.

Aşağıda {"id":...} kabuğu için küçük bir otomata yürüyor. İmleç bir durumdan diğerine geçtikçe, o durumdan çıkan tek geçerli karakter yanar; gerisi sönük kalır. Geçersiz bir karakter hiçbir geçişi ateşleyemez, yani üretilemez.

Geliştirici bir JSON Schema yazar: hangi alanlar zorunlu, tipler ne, hangi değerler kabul edilir. Bu şema doğrudan decoder'a verilemez; önce bir otomataya derlenir. Şemanın her parçası bir kısıt parçasına çevrilir: zorunlu alanlar belli bir sırayı, tipler belli karakter sınıflarını, enum'lar sonlu seçenek kümelerini dayatır.

Burada kritik bir ayrım var. Düz, iç içe geçmeyen yapılar bir FSM ile rahatça ifade edilir. Ama JSON özyinelemeli (recursive) bir dildir: bir nesne başka nesneler, diziler içinde diziler barındırabilir, derinlik önceden bilinemez. Sonlu sayıda durum bunu yakalayamaz. OpenAI da bu yüzden iç içe ve özyinelemeli şemalar için context-free grammar (CFG, bağlamdan bağımsız dilbilgisi) kullanmaya geçtiklerini söyler.

Aşağıda küçük bir şema soldan sağa, kısıt parçalarına ayrışıyor: zorunlu alan, tip kuralı, enum, ve özyinelemeli alt nesne. Her parça tek tek yanıp birleşik kısıt durumunu kuruyor.

Şu ana kadarki resim, model'in karakter karakter ürettiğini varsaydı. Gerçek böyle değil. LLM'ler subword token üretir: {" tek bir token olabilir, name": başka bir token. Dilbilgisi ise karakter ya da dil-token seviyesinde tanımlıdır. Bir LLM token'ı birden çok grammar birimini kesebilir, ve bu hizasızlık (misalignment) naif maskelemeyi yanlış yapar.

Koo ve arkadaşları bu sorunu işin asıl çekirdeği olarak koyar: subword tokenizer'lar belirsizdir ve formal dilbilgileriyle hizalı değildir. Çözümleri detokenizasyonu bir finite-state transducer ile modellemek ve kısıtı otomata-teorik terimlerle yeniden kurmak. Aynı çıktıya götüren farklı token dizilerini doğru saymak, işte bu katmanın işidir.

Aşağıda aynı {"id" metni iki farklı token'laştırmayla üretiliyor. Üstte tek tek karakterler, altta birleşik subword token'lar. İkisi de aynı karakter dizisini verir; doğru bir constrained decoder her iki yolu da geçerli saymak zorundadır.

Her adımda hangi token'ların geçerli olduğunu bulmak, ilkesel olarak tüm vocabulary'yi taramak demektir. Llama 3.1'de bu 128.000 token; her decoding adımında baştan taramak ağır bir yüktür. İşin püf noktası bu taramayı önceden hazırlamak ya da önbelleğe (cache) almaktır.

Outlines bunu bir indeks ile çözer: FSM durumlarından, o durumda geçerli token kümesine bir eşleme önceden kurulur, böylece çalışma anında geçerli token'ları bulmak ortalama O(1) olur, her adımda O(N) tarama değil. XGrammar daha da ileri gider: vocabulary'yi bağlamdan bağımsız (context-independent) token'lara (önceden kontrol edilip cache'lenebilir) ve bağlama bağlı (context-dependent) token'lara (çalışma anında stack ile yorumlanmalı) ayırır.

Aşağıda bir adımın iki yolu yan yana. Üstte naif yol tüm 128K vocabulary'yi tek tek tarar. Altta indeksli yol önceden derlenmiş kümeye tek bakışta ulaşır. İmleç naif tarama boyunca yavaşça ilerlerken, indeks anında çözülür.

Özyineleme FSM'in duvarıdır. Bir FSM'in belleği yoktur: kaç parantez açtığını sayamaz, dolayısıyla "her açılan parantez kapanmalı" kuralını dayatamaz. JSON, SQL, kod gibi iç içe diller tam da bunu gerektirir. Çözüm bir pushdown automaton (PDA): bir FSM'e bir stack eklenmiş hali.

Stack açılan yapıları hatırlar. Her { stack'e bir kayıt iter, her } onu çıkarır (pop). Bir sonraki adımda hangi token'ların geçerli olduğu artık yalnızca o anki duruma değil, stack'in tepesine de bağlıdır. XGrammar CFG-kısıtlı decoding'i tam olarak bir PDA yürütmesi olarak ele alır ve bu stack'i hızlı tutmak için kalıcı (persistent) bir yapı kullanır.

Aşağıda iç içe bir JSON üretilirken stack canlı olarak büyüyüp küçülüyor. Her açılan parantez bir kayıt iter, her kapanış onu çıkarır. Stack boşalmadan çıktı bitemez: işte özyinelemeli yapının garantisi budur.

Constrained decoding güçlü ama sınırlı bir söz verir. Garanti ettiği tek şey, çıktının uygulanan dilbilgisine üyeliğidir. Anlamsal doğruluğu, görev başarısını, hatta tam JSON Schema denkliğini garanti etmez. JSONSchemaBench bunu net ölçer: bir engine aşırı kısıtlıysa geçerli örnekleri reddeder, yetersiz kısıtlıysa geçersizlere izin verir. "Şema destekleniyor" ikili bir özellik değil; coverage (kapsama) artı compliance (uyum) olarak okunmalıdır.

Bu yüzden garanti, dilbilgisi-tokenizer eşlemesinin doğruluğuna bağlıdır, yalnızca bir dilbilgisinin var olmasına değil. Öte yandan kısıt yalnızca sözdizimini de düzeltmez: PICARD, text-to-SQL'de geçersiz devam yollarını eleyerek aramayı geçerli bölgede tutar ve exact match gibi görev metriklerini de iyileştirir. Yani kısıt bazen yalnızca ayrıştırılabilirliği değil, doğruluğu da yükseltir.

Aşağıda iki tuzak yan yana. Aşırı kısıtlı engine geçerli bir örneği yanlışlıkla reddeder; yetersiz kısıtlı engine geçersiz bir örneği yanlışlıkla kabul eder. İdeal olan, tam şema semantiğini izleyen ortadaki bölgedir.

Bu alan iki katmana ayrılır. Üstte arayüz katmanı: LMQL ve Guidance, kısıtı bir programlama dili gibi yazmana izin verir. LMQL prompt'u sorguya çevirir, declaratif kısıtlardan token maskeleri üretir ve raporladığı ölçümlerde %26-85 maliyet tasarrufu gösterir. Guidance ise regex'li gen, liste seçimi için select, CFG kompozisyonu ve şemadan JSON üretimini Python kontrol akışıyla birleştirir.

Altta engine katmanı: Outlines (FSM indeksleme), automata yöntemleri (Koo ve ark., önceki yaklaşımlardan ~7.000x hızlı kısıt derlemesi) ve XGrammar (PDA yürütmesi, token başına <40 µs maske üretimi, CFG'de 100x'e varan hızlanma). Bu iki katman birbirini tamamlar: arayüz kısıtı ifade eder, engine onu hızlı ve doğru çalıştırır. JSONSchemaBench'in ölçtüğü gibi, doğru engine en kötüsünün iki katı kadar şemayı destekleyebilir ve constrained decoding üretimi bazen ~%50 hızlandırır.

Aşağıda yığın katman katman: en üstte geliştirici niyeti, arayüz katmanı, engine katmanı ve en altta token-level maske. Her katman bir alttakine kısıtı aktarır.

Geçerli JSON'u rica etmek bir umuttur; decoder'ı kısıtlamak bir kanıttır.

Prompt yapıyı önerir, model çoğu zaman uyar. Constrained decoding ise geçersiz token'a olasılık sıfır verir: yapı artık bir umut değil, üretim mekanizmasının kendisinden gelen bir garantidir. Bedeli tokenizasyon doğruluğu ve engine mühendisliğidir, ve bu bedel artık büyük ölçüde ödenmiştir.