Skip to content

Invariants

The cross-file contracts. Each is stated once here and nowhere else; every other doc links to it rather than restating it.

Generated by scripts/render_invariants.py. Do not edit. Enforced entries come from the tests that prove them, so a contract and its gate cannot drift apart; asserted entries are hand-written in docs/invariants.src.md.

Enforced by a test

Breaking one of these fails the suite.

binned-walk-bit-identical-to-raw-walk

Predicting through a Dataset carrying the model's own cuts is bit-identical to predicting through the raw matrix, across the whole family: predict, staged, leaf indices and SHAP contributions. This is a documented escape hatch ("pass a Dataset instead of X"), so a divergence would silently change answers for a caller who took the advice.

cuda-training-bit-reproducible

A device fit is bit-reproducible on one device and one build. Histogram cells are int64 fixed point, so every accumulation is an exact integer sum whatever order the atomics land in, and everything downstream of the fill already ran in a fixed order. Three fits of one dataset serialize to identical bytes on every device plane, with the device objective and with the host objective forced. Not claimed: cross-device, cross-toolkit, or host-vs-device equality, which stay tolerance-bound.

cut-order-key

A valid cut carries a strictly positive gain: score_cut_exact admits a candidate only when gain > 0.0, and the level finder only when it beats a best seeded at 0.0. On that domain the bit pattern of a double orders like its value, so split_better, which compares the pattern to keep the warp scan on the integer pipe, ranks every pair exactly as feat_better does. If either finder ever marked a non-positive or NaN gain valid, the two finders would disagree and this test would fail on the -0.0 and NaN rows.

dart-excludes-early-stopping

DART and early stopping are incompatible by construction and the combination throws rather than silently producing wrong validation numbers: DART rescales earlier trees every round, which invalidates the incrementally accumulated validation scores early stopping reads.

device-bin-width-criterion-matches-host

The u8-vs-u16 storage decision uses the same bin-count criterion on both sides, so a device-binned Dataset and a host-binned one hold the same width as well as the same values. Disagreeing would read a plane at the wrong stride, which is a memory-safety fault rather than a wrong number. The u16 section is the load-bearing half: it pushes max_bin past 256 and asserts the widths match, that the width really did switch, and that every cell agrees.

device-cuts-bit-identical

cuda_fit_mappers returns the cuts BinMappers::fit returns, compared as uint32 bit patterns over every branch of create_cuts: all-distinct, greedy, stride, tie runs, signed zeros, and the NaN and infinity tails. The device model hash is only reproducible from the host hash's inputs while this holds; a sign flip on a zero or a one-ulp midpoint difference fails here.

device-finder-screen-is-exact

The device finders screen every cut with fp32 interval bounds and score only the survivors in fp64; the screen may only discard a cut whose gain upper bound is below a gain already certified, so the exact best cut always survives and the chosen split, its bin and its direction are the same bytes the exhaustive fp64 sweep picks. BONSAI_CUDA_FINDER_EXHAUSTIVE disables the screen, and this test requires the two to route every row identically on data built to make the bounds tight: duplicate and near-duplicate columns, plateaus, a constant column, missing values, gradients at 1e-6 and 1e6, unit hessians on the min_child_hess boundary, lambda_l1, and monotone constraints with a positive min_gain_to_split.

device-grower-by-engine-type

Whether a grower runs on a device is answered by its engine type through the registry, never by a caller inspecting the name. The registered spellings still say cuda_ for every device grower, so the predicate agrees with the prefix on every name the table holds; a name outside the table is not a device grower however it is spelled.

device-ingest-chunk-reuse

Device ingest above 8 GiB of raw floats streams chunks through three pinned slots; a slot is reused only after the fence that follows its copy and bin kernel, so a matrix spanning more chunks than slots (here 256 MB row-major, four 64 MB chunks, and sixteen single-chunk columns) bins identically to the host on both paths. A slot reused early would bin a chunk from half-written raw. BONSAI_CUDA_INGEST_RING engages the ring below the threshold so this matrix exercises it; without the flag the same matrix uploads pageable through one slot and must bin the same bytes.

device-objective-formula-matches-host

The device gradient and hessian kernels must stay numerically identical to src/objective.cpp's host formulas. Device-resident training reads them every round with no host cross-check, so a divergence shows up only as a quality difference. This suite is the cross-check: MSE, LogLoss and Poisson, on both the depthwise and levelwise planes, against the same fit with the host objective forced.

device-oversized-tree-refuses-not-falls-back

A tree the device cannot hold is refused, never quietly moved to the host. All three device planes gate on the same histogram budget and throw ConfigError naming the limit; the host plane trains the same dataset without complaint, so the refusal is a device-capacity fact rather than a rejected dataset. Falling back instead would turn a configuration error into a silent performance cliff.

device-root-spends-its-host-rows

A device root carries a host row list only until the engine stages it; from begin_root on it is a count and sums, the shape the identity root has from the start. A tree that ends at the root therefore stamps nothing on the host, which matters in resident mode: the per-row outputs are empty there, and a stamp over the staged rows writes past them.

fit-id-gates-resident-reuse

A row-narrowed view mints a FitId distinct from its parent's, and a copy shares one. Anything caching against a Dataset keys on these tokens, so an equal token means "the same fit" with no allocator caveat: the device resident state is armed for ONE FitId, and a token that compared equal across two different fits would leave the previous fit's labels, scores and rows live under the next one.

infeasible-node-scores-its-parent

A frontier node whose children would fall under min_child_hess contributes its parent score (zero gain) to a level candidate instead of vetoing it. At real depths some frontier node is always near-empty, so a veto rejected every good deep cut. The device level finder holds the same rule, pinned by its own parity case in test_cuda_grower.cpp.

leaf-budget-cannot-bind-is-depthwise

A depth-D tree has at most 2^D leaves, so a budget of 0 or of 2^D and above never stops an expansion: every leaf with positive gain splits, the same set depthwise splits. Sibling histograms are paired by subtraction in both growers, so leaf values agree to float rounding.

  • enforced by: ../tests/unit/test_leafwise_grower.cpp

leaf-budget-route-keeps-the-name

The routed triple is what the table is searched with; cfg.dispatch is what the user wrote and what a saved model carries.

  • enforced by: ../tests/unit/test_make_booster.cpp

leaf-budget-route-round-trips

The saved config carries "leafwise" as written; the load searches the table with the same routed name the save did, so the bytes round-trip and the loaded booster continues on the same plane.

  • enforced by: ../tests/unit/test_model_io.cpp

levelwise-monotone-holds

A levelwise fit under a monotone constraint produces predictions ordered by that feature, on both the CPU and CUDA engines. The mechanism is a projection of the finished leaf table onto the monotone cone (project_monotone), not a veto during growth, so the tree's structure is whatever the unconstrained search would have chosen.

levelwise-rejects-interaction-constraints

The levelwise (oblivious) grower rejects interaction constraints at construction rather than silently ignoring them, on both the CPU and CUDA engines: the throw is in the shared template, so an engine cannot opt out of it. Monotone constraints are honoured rather than rejected, by project_monotone; interaction constraints have no equivalent projection, because they constrain which features may share a path rather than how leaf values are ordered.

perfect-tree-numbering-one-scheme

The flattened node table and ObliviousTree::leaf_for agree on one numbering. The table gives internal node i the children 2i+1 and 2i+2 and appends the leaves after the internals in leaf_table order; leaf_for builds its index by shifting a bit per level, left as 0. Those two must name the same leaf for every root-to-leaf path, or the device epilogue and the host walk read different values out of the same tree. Four sites share the scheme, which is past the count where a normal change reliably updates all of them.

renewal-keeps-monotone

A depthwise or leafwise fit under a monotone constraint stays ordered by that feature after leaf renewal. Renewal replaces each leaf's Newton step with a residual statistic (median, Huber mean, quantile) that can reverse the order the growth-time fence enforced, so the renewed value is clamped back into the fence the grower left for that leaf.

row-list-follows-the-fit

The row list a round trains on belongs to the fit it was materialized for, keyed on the fit's minted token and never on its size: a second fit on a same-sized view of different rows grows the tree those rows grow, not the previous view's.

smaller-child-tie-break-agrees

On equal child row counts the fresh histogram slot goes to the LEFT child. The larger sibling derives by subtracting the smaller from the parent, so host and device must pick the same side or a subtraction reads the wrong sibling's histogram and the tree silently changes. The device makes the same <= comparison twice, in publish_small_child (which child's rows the partition kernel fills) and in leaf_children (which child holds the fresh slot), and those two must agree with each other as well.

train-predict-bin-boundary-parity

A row sitting exactly on a cut routes the same at train time and at predict time. The grower routes on bin <= split_bin while the predict walk routes on the stored raw threshold, and the two agree only because the binner is right-inclusive (bin b holds v in (cuts[b-1], cuts[b]]) and the FLT_MAX top-band closer keeps every finite value above the last cut out of the NaN sentinel. Cut values are the witness: they are the only inputs where a one-ulp disagreement between the two rules changes the leaf.

view-narrows-rows-not-plane

A row view narrows which rows a fit visits and leaves the plane alone: view_n_rows() is the selection, plane_n_rows() stays the storage. Every row id remains a global id into the plane, which is why grad, hess, labels and the row-major mirror stay full length whatever the view selects.

zero-cover-branches-are-real

Oblivious trees densify into a perfect shape, so a trained model really does carry leaves no training row reached. TreeSHAP's zero-cover guard therefore protects against an input that occurs, not a theoretical one. The second half matters as much: held-out rows drawn off the training joint distribution still do not route into a dead leaf, so the guard is about weighting those branches at zero rather than about rows landing there.

Asserted in prose

Two kinds sit here. Some cannot have a unit test: build flags, packaging matrices, claims about nondeterminism, decisions. Others are testable and simply are not marked yet, which makes this section the backlog: promoting one is writing its test and adding the marker. The code: lines name the source carrying each claim, and docs-check fails when one stops resolving.

Device planes

multiclass-device-decline

A multiclass model declines the CUDA predict and TreeSHAP planes and rides the host bin walk; width-1 dense and levelwise models ride the device.

  • code: include/bonsai/booster.hpp : device_plan_input
  • code: src/cuda/shap.cu : pack_shap_paths
  • code: src/python/module.cpp : predict_on_device
  • elaboration: decisions 108 and 111; issue #407 tracks the multiclass half.

device-paths-decline-never-error

Every device predict and SHAP path declines to the host walk, never errors, on capability shortfalls: no CUDA build or device, multiclass, a feature over 255 bins, merged path length over 32, foreign ingest plane, allocation failure. A missing-covers model stays a host-side error, a model defect rather than a capability gap.

  • code: src/cuda/predict.cu : cuda_predict_plan
  • code: src/cuda/shap.cu : cuda_shap_plan
  • elaboration: decision 108.

device-predict-bit-equality

Device predict is bit-equal to the host binned walk, row for row; the epilogue spells its rounding out because the kernel TU compiles with contraction on.

  • code: src/cuda/predict.cu : __fadd_rn
  • code: include/bonsai/detail/bin_walk.hpp : split_bins
  • elaboration: decision 108.

stub-trains-nothing-predicts-anywhere

The cuda growers are registered in every build; without a device, construction and load succeed and training throws with a message naming the fix. Models trained on a device predict on any build.

  • code: src/cuda/histogram_engine_stub.cpp : throw_unavailable
  • code: include/bonsai/registry/typelists.hpp : CudaObliviousGrower
  • elaboration: decision 70.

resident-objective-eligibility

The device-resident objective arms only for MSE, LogLoss, and Poisson, weighted or not, with no DART and a sampler that never reads gradient values; everything else takes the host path. BONSAI_HOST_OBJECTIVE=1 forces the host path.

  • code: include/bonsai/booster.hpp : resident_begin
  • code: src/cuda/detail/device_context.cu : resident_begin
  • elaboration: decision 78.

Training semantics

split-tie-break

Exact gain ties break to the earliest candidate: lowest feature id, then lowest bin, then default-left first. Load-bearing for the bit-identity contract; both scan orders preserve it.

  • code: src/split.cpp : update_best
  • elaboration: decision 16.

subtraction-trick

Level batching populates only each smaller sibling's histograms; the larger sibling derives by cell-wise subtraction, on both planes. Node totals are computed at split time, never accumulated during the fill.

  • code: src/step/primitives.hpp : smaller_child
  • code: src/step/primitives.hpp : finish_split
  • code: include/bonsai/histogram.hpp : Histogram
  • elaboration: decision 19.

gain-and-cover-stamped-at-grow

Split gains and per-node covers are stamped at grow time; neither is reconstructible from a stored tree, so a model saved without them loads with the dependent features (importance, TreeSHAP) declining and saying why.

  • code: include/bonsai/tree.hpp : covers
  • code: src/shap_paths.cpp : pack_shap_paths
  • elaboration: the gain-storage entry in decisions.md.

auto-thread-cap

n_threads=0 resolves to hardware concurrency capped at auto_thread_cap (16) and further capped by any cgroup CPU quota; the quota read is what makes container fits honest.

  • code: include/bonsai/parallel.hpp : auto_thread_cap
  • elaboration: the threading entries in decisions.md.

softmax-true-hessian

Multiclass softmax uses the true diagonal Hessian p(1-p), not the factor-2 convention, floored at 1e-6 before weighting.

  • code: include/bonsai/multiclass_booster.hpp : 1e-6F
  • elaboration: the multiclass entry in decisions.md; guide/12-multiclass.md teaches it.

Data plane

host-determinism

Model bytes are identical across runs, across thread counts (outside one documented relaxation), and across CPU architectures; CI trains on arm64 and x86-64 and compares file hashes per commit. Host builds compile with contraction off, which is what makes the claim hold across compilers. A host fit and a device fit of one dataset agree to 1e-4 in predictions, never byte for byte: the host accumulates histogram cells in float and the device in int64 fixed point, and the device fit's own byte identity is the enforced cuda-training-bit-reproducible.

device-binning-byte-identity

Device ingest produces bins byte-identical to the host mapper's transform: the kernel runs the same binary search over the same cuts, so a device-binned Dataset and a host-binned one are the same object to everything downstream.

  • code: src/cuda/detail/ingest_kernels.cuh : transform_bin
  • code: src/bin_mapper.cpp : BinMapper::transform
  • elaboration: decision 99.

routing-rule-one-source

A row routes left iff its bin is at or below the split bin, with the last bin following default_left. The device kernels mirror the host rule rather than reimplementing it, and the [cuda] parity suite fails when they diverge.

  • code: include/bonsai/dataset.hpp : routes_left
  • code: src/cuda/detail/kernels.cuh : goes_left_dev
  • elaboration: decision 108's bit-equality claim rests on this.

threshold-to-bin-one-inversion

A stored split threshold is turned back into a bin by exactly one function. The grower records threshold = cuts()[bin] and cuts are strictly increasing, so lower_bound recovers the bin exactly; DART, warm start, the device epilogue, and the SHAP packers all go through it rather than re-deriving the mapping.

  • code: include/bonsai/bin_mapper.hpp : bin_of_threshold
  • code: src/cuda/predict.cu : bin_of_threshold
  • elaboration: an edit here is a wire-format change even though no byte layout moves.

max-bin-default

bin_mapper.max_bin defaults to 255, which is what keeps the default bin plane u8; a wider setting switches storage to u16 and costs the device SHAP plane (8-bit intervals).

  • code: include/bonsai/config/bin_mapper_config.hpp : max_bin
  • code: include/bonsai/bin_store.hpp : BinColumns
  • elaboration: api/parameters.md is the generated reference; prose says "255 by default" and links there.

shap-additivity-exact

Host TreeSHAP satisfies the efficiency property exactly: sum(phi) plus the expected value reproduces the raw prediction, by construction of the closed form. The device fp32 path is tolerance-bound instead, and the raw-matrix fp64 host walk is the escape.

  • code: include/bonsai/shap.hpp : tree_shap
  • code: src/shap.cpp : tree_expected_value
  • elaboration: decision 108; its status banner records the fp32 device bound reaching 1e-5 at 200 trees depth 10.

dataset-not-picklable

Dataset objects, host-built or device-resident, do not pickle; rebuild from X and y in the target process. Model objects pickle.

  • code: src/python/module.cpp : __reduce__
  • elaboration: the pickling entry in decisions.md.

Build and packaging

wheel-arch-matrix

The linux x86_64 wheel fatbins the one kernel TU for sm_70 through sm_120 with a compute_90 PTX floor for forward-JIT, links cudart statically, and imports on GPU-less hosts.

  • code: CMakeLists.txt : BONSAI_CUDA_PTX_ARCH
  • elaboration: decision 70; api/install.md carries the support matrix.

static-libomp

BONSAI_OPENMP_STATIC=ON links libomp into the module statically so bonsai and another OpenMP library (XGBoost, LightGBM) in one process cannot deadlock on two runtimes.

  • code: CMakeLists.txt : BONSAI_OPENMP_STATIC
  • elaboration: the libomp entry in decisions.md; api/building.md documents the flag.

python-floor

Supported CPythons are 3.9 through 3.13 on every wheel platform; the 3.9 floor is why nanobind is pinned below 3.

  • code: pyproject.toml : requires-python
  • elaboration: api/install.md carries the matrix.

eight-cli-subcommands

The CLI wires eight subcommands: fit, predict, eval, bench, dump, importance, info, params. info reads the same registry dispatch uses, so it cannot drift from what a build can construct.

multi-gpu-withdrawn

Multi-GPU's supported story is fit-parallelism: N independent single-GPU fits. The data-parallel engine reached measured parity and is withdrawn to a branch; config carries a singular parallel.device_id.

  • code: include/bonsai/config/parallel_config.hpp : device_id
  • elaboration: decisions 76 and 98.

Deleted symbols

Symbols that docs or comments may still name, gone from the tree: Dataset::is_categorical, Dataset::row_major_bins (now Dataset::mirror()), finalize_rows (now finalize_tree), populate_many, NoSampler (now AllRowsSampler), SplitCandidate (now SplitOutput), the 4-axis dispatch (Splitters was never a registry axis). A doc resurrecting one of these is stale, not informative.

  • code: include/bonsai/dataset.hpp : mirror
  • code: include/bonsai/sampler.hpp : AllRowsSampler
  • code: include/bonsai/split.hpp : SplitOutput