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 hashes)

Uploaded Source

Built Distributions

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

Uploaded CPython 3.7+ Windows x86-64

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

Uploaded CPython 3.7+ Windows x86

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

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 hashes)

Uploaded CPython 3.7+ musllinux: musl 1.2+ ARMv7l

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

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 hashes)

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 hashes)

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 hashes)

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 hashes)

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 hashes)

Uploaded CPython 3.7+ manylinux: glibc 2.17+ ARM64

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

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 hashes)

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

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