A fast constrained decoding engine based on context free grammar.
Project description
kbnf
This crate provides a constrained decoding engine which ensures that a language model's output adheres strictly to the format defined by KBNF (Koishi's BNF), an enhanced variant of EBNF. KBNF includes features that enhance usability, notably embeddable regular expressions.
If you are interested in the design and implementation behind this crate, you may want to check out my blog.
Features
- Supports full context free grammar with worst case O(m*n^3) time complexity, where
n
is the generated text length andm
is the vocabulary size. - Asymptotically fastest for subclasses of context free grammar.
- Guarantees worst case O(m*n) time complexity for every LR(k) grammar(which includes almost all practical grammars)
- Achieves O(n) time complexity with caching eventually given that
n
has a fixed upper bound, or the grammar is regular.
- Vocabulary-independent.
- BPE, BBPE, you-name-it, all types of vocabulary are supported.
- Supports UTF-8 characters in grammar.
- Embeddable regular expressions.
Documentation
Add to your project
Simply add it to your Cargo.toml
or run cargo add kbnf
in your command line.
Performance
One of the goals of this crate is for the constrained decoding engine to be "fast." This can be interpreted both theoretically and practically.
Theoretically, this crate is designed to provide the asymptotically fastest algorithms for each subclass of context free grammar. By implementing an Earley recognizer with Leo optimization, this crate has successfully achieve linear time complexity for every LR(k) grammar and quadratic time complexity for every unambiguous grammar. For general context free grammar, things are more ambiguous(pun intended): while subcubic algorithms exist(although with a large constant), all other general-purpose parsing algorithms(like Earley, GLR, GLL...) are indeed cubic, like ours.
Practically, this crate tries to make the engine be as efficient as possible for grammars used in practice. While many improvements, such as Earley sets compaction and lazy caching, have been made, this is inherently an ongoing process. If you find the engine is a bottleneck in your application, feel free to open an issue.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for kbnf-0.4.0-cp37-abi3-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 103877625ee4d2e3b2a6030fd2e39172570427eae68e8846feee27663e22129c |
|
MD5 | 7cb33d50d5cbc8c844d3a1ee55411b95 |
|
BLAKE2b-256 | 641ebde027fb4ecd66ec5dd3709a2211d48a064ec76f7827420db1ebf6ccb219 |
Hashes for kbnf-0.4.0-cp37-abi3-musllinux_1_2_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 40123c923d73764f3e592c7bfca6047edce89713e260c38714d86259bedd4202 |
|
MD5 | 0e572aa2c36532249f02f63f9ea87801 |
|
BLAKE2b-256 | 48bfa81b70fc4a91c7e206db1a80f1a1c1efbfa92fe1b80b5678351530c6a2ba |
Hashes for kbnf-0.4.0-cp37-abi3-musllinux_1_2_armv7l.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 17f68b327c9c2a9a1d356fcf93ce1ad818fb523bf212a814f4bc888f59e7d3ac |
|
MD5 | 7f025fb551c1bd65369d8cb83e90d1f0 |
|
BLAKE2b-256 | 4fa2fa783a4ebe488ef7451236e7dfe1e74f57cee248fa3b20ba9ebec15cf841 |
Hashes for kbnf-0.4.0-cp37-abi3-musllinux_1_2_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b4885558948ed8781d9cd73d793668ec745dbf8fbcb0d7c8942d97d8a199e65 |
|
MD5 | 063c55cd450c53bae212d4bc08e0b038 |
|
BLAKE2b-256 | f11beb8e8d190046a6be5cf42680f24fa7b77fbae63d81924fe311d6584e31b5 |
Hashes for kbnf-0.4.0-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0511038b05bc6f9a683e2316b671b4380ec8886fca5ea79ca3286fde1110729c |
|
MD5 | eb31c126ee32d997727cef671bb8f289 |
|
BLAKE2b-256 | abcc78f66b1294213df38c4dcd8d5887eb72c12cf9d98a69db63f2f90fb82f9f |
Hashes for kbnf-0.4.0-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e86ee5876cecf7376bcf2214cb18c1401fdf6630e6866273a8270f1d3b9182bf |
|
MD5 | e3f2bc45905de37c3a4a17e6bd18c75c |
|
BLAKE2b-256 | 5506ac7a89ac2128f8ec69fac3921e5623f99e22ebeae6a8e9f278e86a784f7b |
Hashes for kbnf-0.4.0-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d66704f25ba09a858084118cb4102930ee7792b6e2b10dcb0c5b62e3965bc8ad |
|
MD5 | ef970d530d66c88565309d3caf8cb165 |
|
BLAKE2b-256 | 80455b52d137d5f28f954c39749afb8f3560d3306029db4db45e4555429c9daa |
Hashes for kbnf-0.4.0-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 862bcd9088e79826156bb598da78c1b945ae610eb709e2142edea76237a1202b |
|
MD5 | ef7877c7fe484c4debf41faec8fbee3f |
|
BLAKE2b-256 | 6c0f606c872485dd8460b50cb02490fe75851ad27de43c9fcf80e9f1bd798946 |
Hashes for kbnf-0.4.0-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9147ddb9dea2c1b99ef694ed340405b25742e192d81ec6c5b3b149bda40a9f4b |
|
MD5 | 4c9a439175b5360540fe57b7c3194ba1 |
|
BLAKE2b-256 | 4f46d301adeaf71b8e5058b56b65196241430c6dd37bd748dd0607da3c519663 |
Hashes for kbnf-0.4.0-cp37-abi3-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1be1392bdc6c9f4346b9cccbfbd3b29c45b496963f1b8a872150ed7317457ac9 |
|
MD5 | 5348a570e283a79985e7f8c8454a0266 |
|
BLAKE2b-256 | 6a39d0dc383d40beee817989eabacb810a77e936123e6a01d489d6d2027fdf43 |
Hashes for kbnf-0.4.0-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 953d14bed99b75394e6e26cf69ed43a9902791734f46d7fbd1cc8dae8284ece4 |
|
MD5 | f5df2d4af0246e29c34156ba0854e986 |
|
BLAKE2b-256 | f867e330d762d4eab4ad3ba5ab43c990c88eda9e83d3ddb79fda5f6409513b89 |