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
nis the generated text length andmis 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
nhas 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.
1 maintainer
Metadata
1 maintainer
Release files for kbnf 0.4.2
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| kbnf-0.4.2.tar.gz | 3.2 MB | Details |
Built distributions (wheels)
| File | Reset | |||
|---|---|---|---|---|
| kbnf-0.4.2-cp37-abi3-win_amd64.whl | CPython 3.7 | abi3 | Windows x86-64 | Details |
| kbnf-0.4.2-cp37-abi3-musllinux_1_2_x86_64.whl | CPython 3.7 | abi3 | Linux musl 1.2+ x86-64 | Details |
| kbnf-0.4.2-cp37-abi3-musllinux_1_2_aarch64.whl | CPython 3.7 | abi3 | Linux musl 1.2+ ARM64 | Details |
| kbnf-0.4.2-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl | CPython 3.7 | abi3 | Linux glibc 2.17+ x86-64 | Details |
| kbnf-0.4.2-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl | CPython 3.7 | abi3 | Linux glibc 2.17+ ARM64 | Details |
| kbnf-0.4.2-cp37-abi3-macosx_11_0_arm64.whl | CPython 3.7 | abi3 | macOS 11.0+ ARM64 | Details |
| kbnf-0.4.2-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl | CPython 3.7 | abi3 | macOS 11.0+ ARM64, macOS 10.12+ universal2 (ARM64, x86-64), macOS 10.12+ x86-64 | Details |
Total release size: 12.1 MB
Release files / kbnf-0.4.2.tar.gz
| Download URL | kbnf-0.4.2.tar.gz |
|---|---|
| Size | 3.2 MB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
68d677fd21e64d1d5748933bac74b4c3f3ed7f4adfcd2bf66ebf491c4e9eca6a
|
|
BLAKE2b-256 checksum How to use checksums |
091ec8589f5437769cbb4a240ca88cac905099333f01f8b8569fe6575e2057f2
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-win_amd64.whl
| Download URL | kbnf-0.4.2-cp37-abi3-win_amd64.whl |
|---|---|
| Size | 902.7 kB |
| Tags | CPython 3.7 Windows x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
3a9be9659d0892bdf632c75d6bd964dd8391e869d4a9a528667fb851a5df5415
|
|
BLAKE2b-256 checksum How to use checksums |
f3512848a82589d22531a548417c85a9c584ac4c605236971565887864298556
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-musllinux_1_2_x86_64.whl
| Download URL | kbnf-0.4.2-cp37-abi3-musllinux_1_2_x86_64.whl |
|---|---|
| Size | 1.3 MB |
| Tags | CPython 3.7 Linux musl 1.2+ x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
31def96dc90eaed688278f3f1e317d8d25d96e6a7394ad47bf90cb06901f95a8
|
|
BLAKE2b-256 checksum How to use checksums |
0864050b562e9b4ce99a0ae33ec621585aadc2649d5377c97b18975c18d3eb43
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-musllinux_1_2_aarch64.whl
| Download URL | kbnf-0.4.2-cp37-abi3-musllinux_1_2_aarch64.whl |
|---|---|
| Size | 1.3 MB |
| Tags | CPython 3.7 Linux musl 1.2+ ARM64 abi3 |
|
SHA-256 checksum How to use checksums |
ae0220c692beab721012387240050ffb386203f812bbc2529531df313bc01bbc
|
|
BLAKE2b-256 checksum How to use checksums |
d9a21a642fa98be8018603c5bf4dad5a533617afb27be93cdefddbf530d8de10
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | kbnf-0.4.2-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 1.2 MB |
| Tags | CPython 3.7 Linux glibc 2.17+ x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
a738ad9a27aef66af112a1e720213582cf5123701ec2e24a3c070a97c0729bc1
|
|
BLAKE2b-256 checksum How to use checksums |
0268da3844f700341082dbf9eff226a217d03349073e7d1e80dc86923d3448d4
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
| Download URL | kbnf-0.4.2-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl |
|---|---|
| Size | 1.1 MB |
| Tags | CPython 3.7 Linux glibc 2.17+ ARM64 abi3 |
|
SHA-256 checksum How to use checksums |
f6137e22e209264bf235f7c320661dcc9a0556d892de65a7f5a4cf8ae5ca2596
|
|
BLAKE2b-256 checksum How to use checksums |
03d9705763dc749d3820e7876102d4b6d9674d0c9fbd4ac49dc993482e80b914
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-macosx_11_0_arm64.whl
| Download URL | kbnf-0.4.2-cp37-abi3-macosx_11_0_arm64.whl |
|---|---|
| Size | 1.0 MB |
| Tags | CPython 3.7 abi3 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
da5e42660c2458d87d58fcc0645ec739a31707382a910fc43a0dbcdce9f5a6ad
|
|
BLAKE2b-256 checksum How to use checksums |
0bd07a9d1ae676e6a3aa0488cf3bf355b4ddaa13ce0ebff41ef4afe8a5cdf647
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
Release files / kbnf-0.4.2-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl
| Download URL | kbnf-0.4.2-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl |
|---|---|
| Size | 2.1 MB |
| Tags | CPython 3.7 abi3 macOS 10.12+ universal2 (ARM64, x86-64) macOS 10.12+ x86-64 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
37ad93831ee5e505312708d33b49cba9c454baf0956ed5127c9da998ddfb3434
|
|
BLAKE2b-256 checksum How to use checksums |
cd01307a1077caccdc6e06055913119eed232c1b813739bd27ba84b6b3dee7c9
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.1.0 CPython/3.9.22
|
