Class BranchStore

High-throughput multi-branch decode operations

The naive approach to N-branch generation is N sequential llama_decode() calls — each paying full GPU kernel launch overhead, memory barrier, and PCIe round-trip. BranchStore eliminates this by packing all branches into a single llama_batch and dispatching once: O(1) GPU round-trips regardless of branch count. The GPU parallelizes across sequences within the batch, so N branches approach the wall-time cost of 1.

Two operations, two packing strategies:

commit() — Generation step. Each branch contributes exactly 1 token. Packs N tokens into a single batch via decode_each (one row per sequence, all at their respective positions). Single llama_decode() call. Logits captured per-branch at batch index i. O(N) total work, O(1) GPU dispatches, O(1) amortized dispatch overhead per branch. Accept-first ordering with rollback: accepts each token into its branch's repeat-penalty window before decode, restores from clones if decode throws.

prefill() — Bulk token injection. Each branch contributes a variable-length token array. Uses a two-pass bin-packing algorithm:

• Pass 1 (planning): Greedy first-fit packs items into chunks ≤ nBatch. Items larger than nBatch get a dedicated chunk and fall through to decode_many's internal auto-chunking (ceil(nTokens / nBatch) calls).
• Pass 2 (dispatch): Normal chunks dispatch via decode_scatter (one llama_decode per chunk). Logits are indexed by flattened cursor position: for item k in a chunk, logits live at cursor + nTokens[k] - 1.

For T total tokens across N branches with batch capacity B:

• Best case (T ≤ B): 1 GPU dispatch, all branches in one batch.
• Worst case: ceil(T / B) dispatches. Each dispatch is fully packed.
• Amortized per-token GPU overhead: O(1/B) — vanishes as batch fills.

Does NOT accept tokens into the sampler penalty window — use for external/replayed tokens where repeat-penalty tracking is unwanted. For model-generated tokens, use commit instead.

Both methods take [branch, token(s)] tuples — the branch-to-token binding is structural, not positional. After either call, each branch's logits snapshot is updated with the output distribution from its decoded token(s), ready for the next produce()/sample() call.