](LICENSE) 
A kernel for Vertical Inference — Git-like tree ops for live inference state
A KV cache already holds everything the model has read. Git-like branching is what turns that into structure you can work with: fork a generation at any point, and the child inherits every token before it while diverging under its own sampler, seed, grammar and constraints. The shared prefix is never recomputed — only the divergence costs anything.
So the operations are the ones you already know:
| Git command | liblloyal composition |
|---|---|
git branch | fork() — from the current position |
git branch ‑d / ‑D | prune() / pruneSubtree(), descendants included |
git merge ‑‑ff‑only | fast_forward(parent, child): the parent takes the child's state and keeps its name; every other branch keeps running |
branch ‑D on every branch but one | retainOnly(winner): the winner stays, under its own handle, and every other branch is deleted in one pass, the old trunk with them |
git merge ‑‑squash | decode_scatter() onto the parent — hard: the child's KV is dropped, its output re-decoded |
git rebase | create() + decode_scatter() — replay from content; re-decodes onto a new base rather than moving cells, the only form that survives recurrent state |
| no equivalent | merge_logits(dst, experts, α) — soft: distributions blend, both KVs stay live |
A hard merge costs the tokens twice — the output is re-decoded, not moved — and what returns is an ordinary prefix every later fork inherits.
A soft merge costs nothing:
Several KV histories steer one branch's next token, each keeping its own state — contrastive decoding, DExperts-style, α < 0 for anti-experts. No dispatch, no KV write, identical on recurrent backends.
Two properties make a tree cheap enough to work this way.
It is batched, not walked. Every live branch advances in a single dispatch — N branches at N different positions on N sequences, packed into one llama_batch. Depth costs you time; width mostly doesn't.
A prefix is not only text. An image encoded once becomes a prefix like any other, so N branches can interrogate the same picture with no re-encode. After the KV, nothing downstream knows or cares which rail a cell arrived on.
That combination is what the library is for: search, best-of-N, speculative decoding and multimodal agents stop being N separate generations and become one tree you fork, score and prune.
→ Continuous tree batching for how N branches become one GPU call · the embedding rail for how images join the same lineage.
Continuous Tree Batching
Tree search with N branches normally means N calls to llama_decode(), each paying dispatch and synchronization overhead. BranchStore packs tokens from N branches — each at a different position, on a different seq_id, each needing independent logits — into one llama_batch.
When one row per active branch fits the configured batch, decode_each() advances them all in a single llama_decode(). It submits one batch and does not chunk — sizing the active set against n_batch is the caller's.
Two packing strategies
decode_each is one token per branch. decode_scatter takes variable-length runs and greedy bin-packs them to fill n_batch:
The decode grid
decode.hpp holds the free functions; BranchStore wraps the ones that need branch state.
| Single Sequence | Multi Sequence | |
|---|---|---|
| Single Token | decode::one | decode::each |
| Multi Token | decode::many | decode::scatter |
| Embedding Rows | decode::embd | — |
Embedding rows have no multi-sequence cell: a legacy
llama_batchcarries tokens or rows, not both, so an image placed this way is its own dispatch and never bin-packs with text. A stream of text and rows goes throughdecode::segments, below.
BranchStore
Two tables and three registries, all instance-scoped — no global state.
BranchStore keeps a large generation-checked slot namespace and a smaller KV lease pool. create() and fork() acquire one of each, atomically — the lease first, rolled back if the slot allocation fails — so every live branch is KV-resident and the number of simultaneous branches is bounded by n_seq_max, not by the slot table. The larger namespace is what makes reuse cheap, while the generation counter in the upper 16 bits stops a freed branch's handle from aliasing a newly allocated one.
Lifecycle
Search is surgical (N × prune()); promotion is nuclear (1 × retainOnly(), a single seq_keep pass that vaporizes every loser).
**fork() clones:** KV sequence, sampler chain (penalties, PRNG, filters), grammar state, metrics, logits snapshot, logit bias, cached sampler params. **fork() does not clone:** the steer callback — it captures references, so copying it is unsafe. Call set_steer() on the child if needed.
Logits are cloned by default (
clone_logits = true), not left empty — a child can sample immediately. To skip that copy (~n_vocab × 4bytes; ~600 KB at 150k vocab) when the child will prefill before sampling, use the free function, which takes options; the RAIIBranch::fork()takes none:auto child = branch::fork(parent, store, ForkOpts{.clone_logits = false});
The Embedding Rail (Multimodal)
Images are not described in text before reaching the model. They are decoded, projected into the model's native input embeddings, and admitted through llama_batch.embd beside the token stream. Once admitted they are ordinary live inference state — forkable, shareable, governed by the same branch lifecycle as text.
Three responsibilities, deliberately separated:
| Layer | Owns |
|---|---|
SegmentSource | Producing ordered TEXT / EMBD segments, their position geometry, and which input each belongs to |
decode::segments | Placement: the dispatch shape the context needs, positions, validation, when a segment has landed |
BranchStore::decode_segments | The branch's books as each segment lands: position, KV cells, slack, terminal logits, progress |
decode:: primitives | Packing the right batch and dispatching it |
The portability seam
SegmentSource exposes exactly two kinds of input — TEXT (token ids) and EMBD (embedding rows plus position geometry). The kernel never sees images, codecs, file formats or mtmd_* types; the source never sees a seq_id and never mutates branch position. A binding can therefore use llama.cpp's mtmd, a platform-native encoder, or cached embeddings without reimplementing KV placement.
MtmdSource is the optional llama.cpp adapter, behind <lloyal/mtmd.hpp>. Its constructor validates marker/image counts, decodes the image bytes, tokenizes the interleaved prompt, and rejects unsupported media. The projector runs lazily, per segment, during the walk — which is exactly what lets an encoder reuse one output buffer: each segment is done with before the next is requested, either dispatched or copied into a mixed batch.
A video is one input too: MediaInput::Kind::Video takes the sampled frames of one clip, each an encoded image, with the time each was sampled. The source lays them out as llama.cpp's own video helper does ("Video:", every frame mergeable, a timestamp after each interval), so projectors with temporal merge (the Qwen-VL family) fuse adjacent frames in pairs. Notes on the timeline, such as a transcript, join the timestamp text the layout already has, so they add no text between frames and leave fusion as it was. Decoding the container is the caller's job; the source refuses one.
Consumers that neither include the header nor link mtmd carry no multimodal dependency.
One ordered prefill, one rail
decode::segments() places the sequence strictly in order, and the context decides how. A context that keeps what it was given and attends causally, a reasoning model's, gets each segment as its own dispatch: TEXT through decode::many, EMBD through decode::embd, zero-copy from the encoder's buffer. A context that reads a stream only whole, with no memory, attention that is not causal, or pooling, gets the whole stream as one mixed batch: tokens and rows as entries of one llama_batch_ext, one llama_process. A stream larger than one ubatch is refused before anything runs.
decode_segments() is the branch's side of it: the store supplies the absolute base and the branch's batch, and moves the branch's books as each segment lands. Given on_progress, it says as each segment of an input lands how much of that input is in the KV and of how much. The source describes how a segment is positioned relative to a base, so branch position never crosses into a binding or a codec.
Embedding text, images and video
embedding::encode(ctx, source) embeds an input of text, an image, a video, or text around one, through the same rail. Build the source with add_special, so the model's own BOS and EOS frame the input as it does for text:
Text goes the same way: embedding::encode(ctx, tokens, n_batch) places the text as a one-segment stream. An embedding reads every entry of one dispatch, so the context must read its input whole: pooled, or a model without memory. A model that keeps memory and attends causally, created with embeddings on and pooling NONE, is refused by name.
KV cells and logical position are different quantities
For text, one token is one cell and one position. Multimodal position schemes separate them: an image contributes n_rows embeddings while advancing the branch by only n_pos — under M-RoPE that is max(nx, ny), reported by the codec rather than computed here.
The gap is recorded as embedding-row slack — own and inherited — so fork(), release() and retainOnly() recover exact cell counts. A branch reports the logical position the model expects while tenancy still accounts for every physical cell the image occupies.
The image becomes shared live state
Downstream of the KV, everything is modality-agnostic: a cell does not remember whether it came from .token or .embd. Forking after an image shares its cells via kv::seq_cp — no re-encode, no copy — so N branches attend one image (see Continuous Tree Batching).
Media is not an attachment resent with every call. It becomes part of the live inference lineage that further computation forks from.
Decode invariants
The embedding rail enforces what keeps that lineage valid:
- embedding width must match the resident model's input width —
llama_batchcarries no width, so a wrong one reads past the caller's buffer; - segment geometry is validated before the position buffer is sized and before
positions()runs —at()has necessarily already returned by then; - a non-causal block must fit one batch and micro-batch — splitting it would silently stop it being bidirectional;
- causal attention is restored by RAII on every exit, including a throw;
- empty segments are rejected, so terminal-logit selection stays unambiguous;
- unsupported media is rejected before any dispatch.
Not transactional. Once the first segment is dispatched the branch is mutated. A later error leaves it partially advanced — prune and rebuild rather than continuing from it.
Hot-Swap Sampler & Grammar
Sampler chains, grammars and metrics live in handle-based registries on the store. set_sampler_params() memoizes — unchanged params are a no-op, and a call that names no seed keeps the seed the chain has. set_grammar() swaps mid-generation.
Handles free automatically on prune().
KV Tenancy
kv::tenancy owns the lease pool. A lease is acquired on create() / fork() and released on prune(); retainOnly() keeps the winner's and rebuilds vacancy in one pass. Because a lease is taken with the slot, available() is the real budget for how wide or deep a search can go.
Consumers never see raw seq_ids.
Topology
| Method | FK analogy | Behavior |
|---|---|---|
prune() | RESTRICT | Throws if children exist |
pruneSubtree() | CASCADE | Iterative post-order traversal |
RAII ~Branch() uses CASCADE, so cleanup always succeeds even on deep trees. Multi-tag KV cells mean pruning a parent cannot corrupt a child's cache — a cell is freed only when every tag is gone.
Primitives
- Tokenization — two-pass safe sizing, special-token handling
- Decoding — continuous tree batching, cross-sequence packing, embedding-row injection
- KV Cache — tenancy, sequence ops, state snapshots, long-context compression
- Sampling — grammar-constrained, persistent chains, memoized hot-swap
- Metrics — dual-level entropy/surprisal, rolling perplexity, cloneable
- Embeddings — pooled extraction, L2 normalization, similarity
- Chat Templates — Jinja2 formatting with fallbacks
From Simple to Complex
Single-sequence streaming — the baseline:
Best-of-N — fork once, diverge, keep the best:
Tree search — expand, evaluate, prune, promote:
store.decode_each/decode_scattertakeDecodeEachItem/DecodeScatterItem(branch-aware). The free functions indecode::takedecode::EachItem/decode::ScatterItemand raw seq_ids — a lower layer, not interchangeable.
Architecture
- Header-only — everything inline in
include/lloyal/*.hpp - Managed KV residency —
kv::tenancyowns leases; consumers never see raw seq_ids - Handle-based — generation counters prevent ABA on slot reuse; registries are store-scoped
- Shared model weights — thread-safe registry, multi-context with one model load
- Zero runtime dependencies — C++20 standard library + llama.cpp
- Multi-binding — C++20 concepts decouple from binding types (Node.js, React Native, CLI)
Integration
liblloyal links llama (and common, when present) transitively. Multimodal is opt-in: include <lloyal/mtmd.hpp> and link llama.cpp's mtmd yourself — liblloyal links nothing on your behalf.
Documentation
- Usage guide: `docs/guide.md`
- API reference: lloyal-ai.github.io/liblloyal — or
./scripts/generate-docs.sh - Headers:
include/lloyal/*.hpp, fully Doxygen-annotated
Testing
Unit tests (stubbed — tenancy, topology, tree batching, RESTRICT/CASCADE, registries, embedding-rail accounting) and integration tests against real llama.cpp, plus ASan / UBSan / LeakSan. The runners report their own totals; this page deliberately does not restate them.
Design Principles
- Primitives, not opinions — build your patterns, we provide the tools
- Managed scarcity — leases are automatic; capacity is queryable
- Explicit over implicit — no hidden state, clear contracts
- Testable — no framework coupling, works standalone
- Version-isolated — absorbs llama.cpp API changes
Contributing
See CONTRIBUTING.md.
License
You can build and sell commercial products using liblloyal.
liblloyal 3.0 is source-available under FSL-1.1-Apache-2.0 and converts to Apache 2.0 two years after each release. The restriction is narrow: you cannot offer a competing HDK runtime, managed HDK service, or alternative ability distribution channel.
See `LICENSE-FAQ.md` for permissions and restrictions. See LICENSE for the legal text and NOTICE for attribution including the bundled llama.cpp MIT dependency.
