Skip to main content

A fast constrained decoding engine based on context free grammar.

Project description

kbnf

crates.io docs.rs PyPI CI

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 and m 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

Documentation and examples.

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

kbnf-0.4.0.tar.gz (1.0 MB view details)

Uploaded Source

Built Distributions

kbnf-0.4.0-cp37-abi3-win_amd64.whl (898.0 kB view details)

Uploaded CPython 3.7+ Windows x86-64

kbnf-0.4.0-cp37-abi3-win32.whl (856.3 kB view details)

Uploaded CPython 3.7+ Windows x86

kbnf-0.4.0-cp37-abi3-musllinux_1_2_x86_64.whl (1.3 MB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ x86-64

kbnf-0.4.0-cp37-abi3-musllinux_1_2_armv7l.whl (1.4 MB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ ARMv7l

kbnf-0.4.0-cp37-abi3-musllinux_1_2_aarch64.whl (1.3 MB view details)

Uploaded CPython 3.7+ musllinux: musl 1.2+ ARM64

kbnf-0.4.0-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.2 MB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ x86-64

kbnf-0.4.0-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl (1.3 MB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ s390x

kbnf-0.4.0-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (1.2 MB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ppc64le

kbnf-0.4.0-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (1.1 MB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARMv7l

kbnf-0.4.0-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.1 MB view details)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARM64

kbnf-0.4.0-cp37-abi3-macosx_11_0_arm64.whl (991.9 kB view details)

Uploaded CPython 3.7+ macOS 11.0+ ARM64

kbnf-0.4.0-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl (2.0 MB view details)

Uploaded CPython 3.7+ macOS 10.12+ universal2 (ARM64, x86-64) macOS 10.12+ x86-64 macOS 11.0+ ARM64

File details

Details for the file kbnf-0.4.0.tar.gz.

File metadata

  • Download URL: kbnf-0.4.0.tar.gz
  • Upload date:
  • Size: 1.0 MB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.9.20

File hashes

Hashes for kbnf-0.4.0.tar.gz
Algorithm Hash digest
SHA256 361559a6fa9bcf3c266a8150c8032889693397fbd8735c67841d6c840ec27b39
MD5 449d0c0b58356179a883a22fcc7f0f11
BLAKE2b-256 0250a0d1f7cba74065d799f2253223121d908a8b7da5912d42357331b0897681

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-win_amd64.whl.

File metadata

  • Download URL: kbnf-0.4.0-cp37-abi3-win_amd64.whl
  • Upload date:
  • Size: 898.0 kB
  • Tags: CPython 3.7+, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.9.20

File hashes

Hashes for kbnf-0.4.0-cp37-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 103877625ee4d2e3b2a6030fd2e39172570427eae68e8846feee27663e22129c
MD5 7cb33d50d5cbc8c844d3a1ee55411b95
BLAKE2b-256 641ebde027fb4ecd66ec5dd3709a2211d48a064ec76f7827420db1ebf6ccb219

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-win32.whl.

File metadata

  • Download URL: kbnf-0.4.0-cp37-abi3-win32.whl
  • Upload date:
  • Size: 856.3 kB
  • Tags: CPython 3.7+, Windows x86
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.9.20

File hashes

Hashes for kbnf-0.4.0-cp37-abi3-win32.whl
Algorithm Hash digest
SHA256 fd9756f95ac154ed24d682704640cb401c16ee59fbe0d82d871b2debb01be8e8
MD5 9ed55355f59badd9bbcd0f98e528b139
BLAKE2b-256 a5627d30e54da6d9d189b03df5f7e0e0e86323bf75e429e3c1d0b3ef45085018

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for kbnf-0.4.0-cp37-abi3-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 40123c923d73764f3e592c7bfca6047edce89713e260c38714d86259bedd4202
MD5 0e572aa2c36532249f02f63f9ea87801
BLAKE2b-256 48bfa81b70fc4a91c7e206db1a80f1a1c1efbfa92fe1b80b5678351530c6a2ba

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-musllinux_1_2_armv7l.whl.

File metadata

File hashes

Hashes for kbnf-0.4.0-cp37-abi3-musllinux_1_2_armv7l.whl
Algorithm Hash digest
SHA256 17f68b327c9c2a9a1d356fcf93ce1ad818fb523bf212a814f4bc888f59e7d3ac
MD5 7f025fb551c1bd65369d8cb83e90d1f0
BLAKE2b-256 4fa2fa783a4ebe488ef7451236e7dfe1e74f57cee248fa3b20ba9ebec15cf841

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-musllinux_1_2_aarch64.whl.

File metadata

File hashes

Hashes for kbnf-0.4.0-cp37-abi3-musllinux_1_2_aarch64.whl
Algorithm Hash digest
SHA256 6b4885558948ed8781d9cd73d793668ec745dbf8fbcb0d7c8942d97d8a199e65
MD5 063c55cd450c53bae212d4bc08e0b038
BLAKE2b-256 f11beb8e8d190046a6be5cf42680f24fa7b77fbae63d81924fe311d6584e31b5

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

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

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl.

File metadata

File hashes

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

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl.

File metadata

File hashes

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

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl.

File metadata

File hashes

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

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

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

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for kbnf-0.4.0-cp37-abi3-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 1be1392bdc6c9f4346b9cccbfbd3b29c45b496963f1b8a872150ed7317457ac9
MD5 5348a570e283a79985e7f8c8454a0266
BLAKE2b-256 6a39d0dc383d40beee817989eabacb810a77e936123e6a01d489d6d2027fdf43

See more details on using hashes here.

File details

Details for the file kbnf-0.4.0-cp37-abi3-macosx_10_12_x86_64.macosx_11_0_arm64.macosx_10_12_universal2.whl.

File metadata

File hashes

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

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page